2.8 Map

The Map class is a templated container to store key-value pairs. The container is dynamically allocated, and key-indexed. Duplicate keys are not allowed. When a key-value pair storage is attempted with an already existing key an Exception::Key::Duplicate is thrown. The Map stores the key-value pairs in sorted order. The key is used to sort the pairs. Thus key must implemented the basic comparision operators ==, !=, <, and >. The sorting allows for a dicotomic search, which is faster than an exhaustive scan search, especially for big maps.

A Map::Pair structure is defined to store the key-value pairs. This structure can be used to add key-value pairs directly to the container, without having to split them up into key and value. The Map::Pair can be used outside the Map class. This structure mainly defines constructors and key and value storage members. No other additional member function or special operator.


Synopsis


  #include <lyric/Map.hpp>
  
  template <class KEY, class VAL>
  class Map
  {
  public:
    struct Pair
    {
      Pair ();
      Pair (const KEY& k, const VAL& val);
      KEY key;
      VAL value;
    };
    ~Map ()
      throw ();
    Map (Size initsize=0, Size resize=1)
      throw (Exception::Memory::Alloc);
    Map (const Map& map)
      throw (Exception::Memory::Alloc);
    Map& operator = (const Map& map)
      throw (Exception::Memory::Alloc);
    const VAL& operator [] (const KEY& key) const
      throw (Exception::Key::NotFound);
    VAL& operator [] (const KEY& key)
      throw (Exception::Key::NotFound);
    Size size () const
      throw ();
    void clean ()
      throw ();
    Array1D<KEY> keys () const
      throw (Exception::Memory::Alloc);
    bool has (const KEY& key) const
      throw ();
    void add (const KEY& key, const VAL& val)
      throw (Exception::Memory::Alloc,
             Exception::Key::Duplicate);
    void add (const Map<KEY,VAL>::Pair& pair)
      throw (Exception::Memory::Alloc,
             Exception::Key::Duplicate);
    void remove (const KEY& key)
      throw (Exception::Key::NotFound);
  };


Description


˜Map ()
Destroys this map, releasing eventually reserved memory. All stored key-value pairs are destroyed.

Map (Size initsize = 0, Size resize = 1)
Constructs this map with a starting memory size initsize and a given resize factor. See class List constructor documentation for a detailed description of initsize and resize (Section 2.4).
|\ Exception::Memory::Alloc
is thrown if not enough memory is found for the initial size.

Map (const Map& map)
Constructs this map from map. All properties, content, and status of map are cloned into this map.
|\ Exception::Memory::Alloc
is thrown if not enough memory is found for this to clone map.

Map& operator = (const Map& map)
Clones map into this map. All properties, content, and status of map are given to this.
|\ Exception::Memory::Alloc
is thrown if not enough memory is found for this to clone map.

const VAL& operator [...] (const KEY& key) const
Returns a const reference to a value identified by a given key.
|\ Exception::Key::NotFound
is thrown if the given key is not found in this map.

VAL& operator [...] (const KEY& key)
Returns a reference to a value identified by a given key.
|\ Exception::Key::NotFound
is thrown if the given key is not found in this map.

Size size () const
Returns the size of this map.

void clean ()
Cleans this map. Removes all stored key-value pairs and returns used memory to the system. See class List clean function documentation for a detailed description of clean’s action (Section 2.4).

Array1D<KEY> keys () const
Returns all keys stored in this map in a 1D key-array. The resulting key-array is sorted in the same order as the stored keys in this map.
|\ Exception::Memory::Alloc
is thrown if not enough memory is found to store this->size() keys.

bool has (const KEY& key) const
Returns true if this map contains the key given as argument, false if not. This function can be used to check for the existance of a given key in this when unsure before using the [key] operator, which in case of inexstance of the key throws an Exception::Key::NotFound.

void add (const KEY& key, const VAL& value)
Adds the key-value pair to this map. As well key and value are cloned into this.
|\ Exception::Key::Duplicate
is thrown if the given key already exists in this map.
|\ Exception::Memory::Alloc
is thrown if not enough memory is found for this to store the given key-value pair.

void add (const Map<KEY,VAL>::Pair& pair)
Adds the key-value pair to this map. As well they key-part and value-part of pair are cloned into this.
|\ Exception::Key::Duplicate
is thrown if the given key-part of pair already exists in this map.
|\ Exception::Memory::Alloc
is thrown if not enough memory is found for this to store the given key-value pair.

void remove (const KEY& key)
Removes the key-value pair identified by key from this map.
|\ Exception::Key::NotFound
is thrown if the given key doesn’t exists in this map.