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, ) ;
}

Implementation

Linear implementation

Array based
Linked-list

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(


}

Non-linear implementation



In [ ]: