Dictionaries

Also known as map or table, is an abstract data type (ADT)

Relies on key, value pair

Inserting a duplicate key into dictionary:

deny the insert attempt, and keep the original entry
replace the existing entry

Member functions:

isEmpty()
getNumberOfEntries()
add(searchKey, )
remove(searchKey)
clear()
getItem(searchKey)
contains(searchKey)
traverse(visit)

Template

template<class KeyType, class ValueType>

Interface

virtual bool isEmpty() const = 0;

In an interface, there is no body of code, but just a signature of functions with virtual keyword. Any class that uses those function, is responsible for implementing the bsy of those functions.

template<class KeyType, class ValueType>
class DictionaryInterface {
    public:
        virtual bool isEmpty() const = 0;
        virtual int getNumberOfEntries() const = 0;
        virtual add(const KeyType & searchKey, ) ;
}

Entry class

An entry object has two parts: search key, and object value

template<class KeyType, class ValueType>
class Entry {
    private:

    protected:
        void setKey(
    public:
        Entry();
        Entry(KeyType 

        bool isEmpty(
        ValueType getItem(

        void setKey(
        void add(
        void remove(


}

Design og the Entry Class

Implementation

Linear implementation

Array based
Linked-list

class ArrayDictionary : public DictionaryInterface<KeyType, ValueType>
{
    private:
        static const int DEFAULT_CAPACITY = 21;

        Entry<
        int itemCount (
           findEntryIndex(
        void destroyDictionary(

    public:
        bool isEmpty(
        int getNumberOfEntries(
        bool add(
        bool remove(
        void clear(

}

Non-linear implementation

Using Binary Search Tree

#include "DictionaryInterface.h"
#include ""