Lecture Notes for SE 598, Data Structures and Algorithms

2 August 2000 - STL Maps and Multimaps

  1. what are maps and multimaps

    1. mathematical behavior - functions and relations (approximate)

    2. a special kind of vector (approximate)

    3. a programming data structure

      1. usually known as tables or associative arrays

      2. usually restricted to strings as keys

    4. a sorted associative container

      1. sorted - as with the sets and multisets, but only on the first value

      2. associative - the second value

  2. maps and multimaps - stl behavior

    1. a special kind of set or multiset - of value pairs

      1. the first value is the key, the second is the value associated with the key

      2. two types - of the key value map and of the associated value

        1. the third type is the pair itself

      3. having a pair of values makes things interesting

    2. value pairs stored in sorted order on keys only

    3. maps remove pairs with duplicate keys only; multimaps keep them

    4. grows and shrinks; don't need to be sized

    5. writing keys is more restricted than reading keys

    6. values may be read and written with equal facility

  3. a map-multimap is a template class

    1. with template <class Key class T, class Compare = less<T>, class Allocator = allocator>

    2. Key is the type of the first value stored in the map

    3. T is the type of the values associated with keys

    4. Compare determines sorting order and equality over keys

      1. tricotomy, equality

      2. < is acceptable, <= is not

  4. map-multimap constructors

    1. the default constructor - map<Key,T> m(const Compare & c = Compare())

    2. the copy constructor - map<Key,T> map1(map2);

    3. the segment-copy constructor map<Key,T> t(start, end); - also the optional compare parameter

      1. what kind of values are given in the iterator range

    4. multimap constructors are the same as the map constructors, except with multimap instead of map

  5. growing and shrinking maps and multimaps

    1. no reserve(), capacity(), d.push_back(v), d.pop_back(), d.push_front(v), or d.pop_front() member functions

    2. insert() and erase()

      1. map m.insert(v) - no iterator

        1. what is the type of v - pair<Key,T>

        2. returns pair<iterator,bool>

      2. multimap mm.insert(v) always inserts v, returns an iterator to v

      3. map and multimap insert(i, v)

        1. inserter compatibility

        2. the iterator i is a hint

        3. return an iterator to v - insertion not indicated for maps

      4. map and multimap insert(start, end) - no iterator, returns nothing

      5. map and multimap erase(i) - deletes only the referenced pair

      6. map and multimap m.erase(k) - deletes all pairs containing key k; returns the number of deleted pairs

      7. map and multimap erase(s, e)

    3. size(), max_size(), and empty() member functions

    4. map and multimap count(k) member function - return the number of pairs having key value k

  6. map and multimap relation operators - equality and lexicographic less-than

    1. equality - the same number of the same kind of pairs

  7. iterators

    1. pairs in a map or multimap have type pair<const Key,T>

      1. the type pair<Key,T> is not the same as the type pair<const Key,T>

      2. the iterators reference pairs of type pair<const Key,T>

      3. a pair's key can't be changed, but its value can be

    2. map and multimap iterators are bidirectional iterators - no jumping, no distance measurement, no inequality relations

    3. map and multimap iterators are mutable - unlike sets and multimaps; but the key value is constant

    4. the usual member functions - begin(), end(), and so on

  8. reading and writing values

    1. iterator read and write, but write restricted to values, not keys

    2. map value access via the [] operator

      1. m[k] always returns a value, even if k isn't in m as a key

      2. if k isn't a key in m, m[k] returns the default value T()

      3. the [] operator doesn't apply to multimaps - which value is returned

    3. range member functions - map and multimap

      1. lower_bound(k) - the iterator to the first (or leftmost) pair with a key of at least k or end()

      2. upper_bound(k) - the iterator to the last (or rightmost) pair with a key of at most k or end()

      3. equal_range(k) - the pair (lower_bound(k), upper_bound(k))

  9. other member functions

    1. map and multimap find(k) - return an iterator to pair with key k or end()

    2. map and multimap count(k) - return the number of pairs having key k

This page last modified on 3 August 2000.