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 ""