Lecture Notes for CS 509, Advanced Programming II

19 March 2002 - STL Maps

1. what are maps

   1. mathematical behavior - functions

   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. the pair datatype

   1. represents a pair of values

   2. a template class of two parameters

   3. the public member fields are first and second

   4. the handy make_pair() template function

      1. std::pair<string, int> count("hello", 1); vs.

      2. make_pair("hello", 1);

      3. watch out for the template parameter-type matching

   5. defined in <utility>

3. maps behavior

   1. a special kind of set 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

   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

4. a map is a template class

   1. with template <class Key>

   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

5. map 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

6. growing and shrinking maps

   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. map insert(i, v)

         1. inserter compatibility

         2. the iterator i is a hint

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

      3. map insert(start, end) - no iterator, returns nothing

      4. map erase(i) - deletes only the referenced pair

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

      6. map erase(s, e)

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

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

7. map relation operators - equality and lexicographic less-than

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

8. iterators

   1. pairs in a map 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 iterators are bidirectional iterators - no jumping, no distance measurement, no inequality relations

   3. map iterators are mutable - but the key value is constant

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

9. 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. range member functions - map

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

10. other member functions

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

This page last modified on 2 April 2002.