c_map

Table Of Contents

Introduction, c_map

A map is a collection that associates arbritrary key value pairs. This differs significantly from the most of other collection classes, which use positioning, or just existence to store elements. Maps store values assicated with a key value, which can then be retreived using the key. Thus maps are an ordered (sorted), associative collection. As key-value pairs are inserted into the map, they are kept in a sorted order. Key collisions (a key collision occurs when an attempt is made to insert a key-value pair into a map when the key already exists in the map) are resolved by re-setting the value for the existing pair (thus invoking T::operator==()).

The use of c_map_pair is enforced so c_map can conform to the c_collection interface for add(), and other member functions that take a singular value. It also provides a convinient methodology for traversal and value extraction.

Maps can be traversed in order, or in reverse order. Because the sorting is performed during the insertion process, ordered traversal is very fast. Value retreival by key is much more efficient than with the non-associative collection object, as the map is implemented as a binary tree, so a significantly smaller portion of the key set must be searched on average.

A few things should be kept in mind when using maps, if your data is already sorted, the map will be extrememly inefficient in both insertion, and key traversal. You will obtain much better performance if your data set is at least marginaly randomized.

API Refrence
  • c_map( void )

    This is the default constructor. It creates an empty map.

  • c_map( const c_map& that )

    This is the copy constructor. The constructed map becomes a copy of the supplied map.

  • ~c_map( void )

    The destructor, frees all internal storage.

  • virtual int add( const KEY& elm )

    This member function adds a new element into the map. Please note that this version will add an element with a blank value.

  • virtual int add( const c_map_pair<KEY,VALUE>& elm )

    This member function adds a new element to the map. It sets both the key, and value for the element.

  • virtual int remove_all( void )

    This blanks to the map. It removes all the elements from the map, and frees all associated memory. It is called by defualt during destruction.

  • virtual int clear_values( void )

    Unlike remove_all, clear_values does not deallocate the map, instead it iterates through all the elements in the map, and sets the value equal to a default VALUE object (which is just constructed via VALUE::VALUE()).

  • virtual c_collection_iter<c_map_pair<KEY,VALUE>> * prepare_iter( const collection_sorting_order ord = raw_order ) const

    virtual int first( c_collection_iter<c_map_pair<KEY,VALUE>>* iter, c_map_pair<KEY,VALUE>& elm ) const

    virtual int next( c_collection_iter<c_map_pair<KEY,VALUE>>* iter, c_map_pair<KEY,VALUE>& elm ) const

    virtual int prev( c_collection_iter<c_map_pair<KEY,VALUE>>* iter, c_map_pair<KEY,VALUE>& elm ) const

    virtual int last( c_collection_iter<c_map_pair<KEY,VALUE>>* iter, c_map_pair<KEY,VALUE>& elm ) const

    virtual void complete_iter( c_collection_iter<c_map_pair<KEY,VALUE>>* iter ) const

    These are the implementation of the c_collection interface.

  • virtual int least( c_map_pair<KEY,VALUE>& elm ) const

    Least will set elm.m_key, and elm.m_value equal to the least most element (according to operator<) in the collection. Since c_map stores elements in a sorted state, it is able to look up this node in an efficient manner.

  • virtual int greatest( c_map_pair<KEY,VALUE>& elm ) const

    greatest() performs the opposite action of least, setting elm.m_key and elm.m_value to the value of the greatest node in the tree.

  • virtual int find( KEY& key ) const

    This version of find returns either TRUE (if key exists in the map) or FALSE (if key does not exist in the map).

  • virtual int find( c_map_pair<KEY,VALUE>& elm ) const

    This version of find returns TRUE if elm.m_key is present in the map, and also sets elm.m_value in elm to the value for the node that matches elm.m_key.

  • virtual int is_key( const KEY& key ) const

    This member function returns true if elm is a key in the map, and false if it is not.

  • virtual const c_map_pair<KEY,VALUE>> key_find( const KEY& key ) const

    For a given key, key_find will return a constant map pair that contains the key and value for the given key. If the key is not found, the returned pair will have a blank key, and value (set to whatever the default constructors for KEY, and VALUE produce).

  • virtual const c_map_pair<KEY,VALUE>> val_find( const VALUE& val ) const

    For a given value, val_find will return a constant map pair that contains the key and value for the first node that contains the given value. If the value is not found, the returned pair will have a blank key, and value (set to whatever the default constructors for KEY, and VALUE produce). Please note that the map is traversed node by node to find a matching value, so this process is extremely inefficient.

  • virtual int remove( const c_map_pair<KEY,VALUE>& pair )

    This function will remove the node who's key matches pair.m_key. TRUE is returned if remove finds a matching node and removes it, otherwise FALSE is returned.

  • virtual int remove( const KEY& key )

    This version of remove is just overloaded to take a single KEY object instead of a pair object.

  • virtual int operator==( const c_map<KEY,VALUE>& map )

    Equality operator. This member function will return TRUE if the following conditions are met:

    • both maps contain the same number of elements
    • for each of the elements in the first map, a matching key can be found in the second map. KEY::operator== is used to determien weather or not keys are equal.
    If these conditions are not met, opeator== returns FALSE.

  • virtual int get_count( void ) const

    This returns a count of the number of nodes in the tree.

  • virtual insert_status insert( const KEY& key, const VALUE& value )

    This function inserts the node into the tree. If key is already present in the map, the value for the node at key will be updated.

  • virtual int depth( void ) const

    This function returns the maximum depth of the tree. This function traverses the entire tree.

  • virutal const c_map<KEY,VALUE>& operator=( const c_map<KEY,VALUE>& right )

    The assignment operator. This function will destroy the lvalue, and then proceed to make itself a copy of the rvalue.

  • Example Code:
    void make_me_a_match( void ) 
    {
      c_map<c_string,c_string> mr_matchmaker;
    
      mr_matchmaker.add( c_string("Bob"), c_string("Jane") );
      mr_matchmaker.add( c_string("Joe"), c_string("Joan") );
      mr_matchmaker.add( c_string("Don"), c_string("Bess") );
      mr_matchmaker.add( c_string("Dan"), c_string("Niki") );
      mr_matchmaker.add( c_string("Sue"), c_string("Bill") );
    
      c_map_pair<c_string,c_string> match;
      match.m_key = "Joe";
    
      if( mr_matchmaker.find(match) ) {
        cout << match.m_key "'s match is: " << pair.m_value << endl;
      }
      else {
        cout << match.m_key << " has no match, bummer!" << endl;
      }
    }
    

    Up