Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509, Advanced Programming II

2 March 2004 - STL Maps

Outline

What are Maps?
- The Pair Datatype
- Map Types
- Map Sorting Behavior
The Map Template Class
- Map Constructors
- Growing and Shrinking Maps
- Map Relation Operators
- Iterators
- Other Map Member Functions
Map Timings

What are Maps?

A map is a sorted associative container.
- Map elements are sorted within the map.
- Each map element associates one value with another.
  - For example, 1 is associated with "eins".
A map mathematically behaves like a function.
- A function associates one value (its argument) with another (the return value).
- translate(1) = "eins".
A special kind of vector (approximate).
A programming data structure.
- Usually known as tables or associative arrays.
- Often restricted to strings as keys.

The Pair Datatype

Represents a pair of values.

A template class of two parameters.

template < 
  typename FirstT, typename SecondT >
struct pair {
  FirstT first;
  SecondT second;
  pair(FirstT f, SecondT s) 
    : first(f), second(s) { }
  };

The handy make_pair() template function.
- std::pair<string, int> count("hello", 1); vs.
- make_pair("hello", 1);
- Watch out for the template parameter-type matching.
Defined in <utility>, but usually included as part of other includes (e.g., <map>).

Map Types

A map is a set of values; each value is a pair.
- The first value in a pair is the key value
- The second value is the associated value (or a-value).
A map has (at least) four associated types:
1. The type of the map itself.
```
std::map<keyT, avalueT>
```
2. The type of the values in the map.
```
std::pair<const keyT, avalueT>
```
  - Also known as std::map<keyT,avalueT>::value_type.
  - More on that const later.
3. The type of the key in a map value (which is a pair).
  - keyT, also known as std::map<keyT,avalueT>::key_type.
4. The type of the a-value in a map value.

Map Sorting Behavior

A map is a sorted associative container.
Map values (that is, pairs) are sorted order on keys only.
- [ (1, 10) (2, 9) (3, 8) ] is a map.
- [ (10, 1) (11, 2) (8, 3) ] is a not a map (probably).
Maps remove pairs with duplicate keys only.
- Add (1, "one") to [ (1, "eins") ] and get
  [ (1, "eins") ].
- Add (1, "one") to [ (i, "one") ] and get
  [ (1, "one") (i, "one") ].
Maps grow and shrink automatically with no explicit sizing.
Key values can be read but can't be written.
- Keys determine order, changing keys changes the order.
- This is expensive and hard to detect.
- Hence the const KeyT type in the map-element type.
A-values may be read and written.

The Map Template Class

With template parameters
```
<typename keyT, 
 typename avalueT, 
 typename Compare = less<keyT> >
```
- Compare is part of the map type.
  map<int,int,less<int> > is not the same type as map<int,int,greater<int> >
keyT is the type of the first value stored in the map.
avalueT is the type of the values associated with keys.
Compare determines sorting order and equality over keys.
- Compare is a trichotomy.
  - Exactly one of a < b or b < a or a == b is always true.
- < is a trichotomy, <= is not .

Map Constructors

The default constructor.

std::map<keyT, avalueT> 
  m(const Compare & c = Compare());

The copy constructor.
```
std::map<keyT, avalueT> m1(m2);
```
The segment-copy constructor.
```
std::map<keyT, avalueT> m(start, end);
```
- What kind of values are given in the iterator range?

Growing and Shrinking Maps

No reserve(), capacity(), push_back(v), pop_back(), push_front(v), or pop_front() member functions.
Insertion and deletion through insert() and erase().
- m.insert(v) uses no iterator.
  - What is the type of v? pair<keyT,avalueT>.
  - Returns (iterator, bool).
    bool is true if the map size increased.
    iterator points to the new value if bool is true.
    iterator is undefined if bool is false.
- m.insert(i, v) provided for compatibility.
  - The iterator i is a hint.
  - Returns an iterator to v; insertion not indicated.
- m.insert(start, end) returns nothing.

Erasing Map Elements

m.erase(i) erases only the referenced pair *i.
m.erase(k) erases all pairs containing key k; returns the number of erased pairs.
- That's either 0 or 1 for maps.
m.erase(s, e) erases the pairs specified in the iterator range.
Iterator Invalidation.
- Erasing a value invalidates only the associated iterator.
```
for (std::map<int, int>::iterator i = iim.begin();
     i != iim.end();
     i++)
  iim.erase(i);
```
  Use iim.clear() instead.
- Only erasing a value invalidates iterators.

Map Relation Operators

Equality (==) and lexicographic (<) relations.
- These are STL global relations, not map member functions.
Equality is the same number of the same kind of pairs.
- Both the key and a-values are compared.
- [ (1, "red") (2, "blue") ] != [ (1, 2) (2, 4) ]
- Remember, this is equality between maps, no equality between map pairs.
The lexicographic relation is dictionary ordering.
- Both pair values are used during the comparisons.
  p1 < p2
  if p1.first < p2.first
  or p1.first == p2.first && p1.second < p2.second

Iterators

Pairs in a map have type pair<const keyT,avalueT>.
- The type <keyT, avalueT> is not the same as the type <const keyT, avalueT>.
- The iterators reference pairs of type pair<const keyT,avalueT>.
- A pair's key can't be changed, but its value can be.
Map iterators are bidirectional iterators.
- No jumping, no distance measurement, no inequality relations.

Map iterators are mutable, but the key value is constant.

std::map<int, int>::iterator i = iim.begin();

*i = std::make_pair(1, 2)

i->first = 1

i->second = 2

The member functions m.begin(), m.end() and so on.

Reading and Writing Map Values

Iterator read and write.
- But writing is restricted to a-values.
Map value access via the [] operator.
- m[k] always returns a map element, even if k isn't in m as a key.
- If k isn't a key in m, m[k] returns the default value avalueT().
  - This adds the pair (k, avalueT()) to m.
- Be careful with [] because it can change the map.
  Careless use of [] can result in gigantic maps.

Map Range Member Functions

m.lower_bound(k) returns an iterator to the first (or leftmost) pair with a key of at least k or end().
m.upper_bound(k) returns an iterator to the first (or leftmost) pair with a key more than k or end().
m.equal_range(k) returns the pair (m.lower_bound(k), m.upper_bound(k)).
These replace the like named generic functions. (Why?)

Other Map Member Functions

m.find(k) returns an iterator to pair with key k or m.end().

m.count(k) returns the number of pairs having key value k.

Use m.count(k) or m.find() to check for k in m.

if (m[k] == "hi") . . .

if (m.find(k) != m.end()) and (m[k] == "hi")

if (m.count(k) == 1) and (m[k] == "hi")

m.size(), m.max_size(), and m.empty().
- Prefer m.empty() to m.size() == 0.

Map Timings

A map is implemented as a (mostly) balanced tree.
- Most operations require a tree traversal, and so have O(log n) behavior.
Given an n-element map m,
- m.insert(p) takes 0(log n).
  - But m.insert(i, p) might take (approximately) constant time if i is a good guess.
- m.erase(i) takes 0(log n).
- m[k] takes 0(log n).
- m.count(k) and m.find(k) take 0(log n).
- m.lower_bound(k), m.upper_bound(k), and m.equal_range(k), all take 0(log n).
- Map iterator ++ and -- are constant time.

Container Performance Comparison

	vector	list	map⁴
insert and erase	O(n)	O(1)	O(log n)
`push_front()`	O(n)¹	O(1)	O(log n)¹
`find()`³	O(n)	O(n)	O(log n)
C[i]	O(1)	O(n)²	O(log n)
iterator	random	bidirectional	bidirectional

Notes
1. Vectors and maps don't implement push_front(X); c.insert(c.begin(), X) is the equivalent .
2. Lists don't implement operator []; std::advance(l.begin(), i) is the equivalent.
3. std::find() is a generic algorithm re-reimplemented by maps but not by either vectors or lists but
4. These classifications apply to all sorted associative containers.

Container Invalidation Comparison

	vector	list	maps⁴
`c.insert(i, v)`	`j >= i`, possibly all	none	none
`c.erase(i)`	`j >= i`	`i`	`i`
`c.push_back(v)`	`c.end()`, possibly all	none	none³
`c.pop_back()`	`--c.end()`, `c.end()`	`--c.end()`	`--c.end()`³
`c.push_front(v)`	all¹	`c.begin()`	`c.begin()`¹
`c.pop_front()`	all²	`c.begin()`	`c.begin()`²

Notes
1. Vectors and maps don't implement push_front(X); c.insert(c.begin(), X) is the equivalent.
2. Vectors and maps don't implement pop_front(); c.erase(c.begin()) is the equivalent.
3. Maps don't implement m.push_back(X) or pop_back(); m.insert(X) and m.erase(--m.end()) are the equivalents.
4. These classifications apply to all sorted associated containers.

Maps vs. Vectors

Maps are better than vectors because:
- The index (key) type can be arbitrary.
  - Index maps by strings, or by nodes, or by ...
- The index (key) space can be sparse.
  - Storing m[1] and m[1000000] takes two elements.
- Maps have better iterator-invalidation behavior than do vectors.
- Insertions and deletions are faster in maps then in vectors.
Vectors are better than maps because:
- Element access is faster in vectors than in maps.
- Vectors have more powerful iterators than do maps.
- Vectors have a smaller storage footprint than do maps.
Consider using sorted vectors instead of maps.
- Staged inserts followed by lookups favor vectors over maps.
- Interleaved inserts and lookups favor maps over vectors.

Map vs. Vector Example

Two cases:
1. A sequence of n inserts followed by a sequene of n lookups.
2. A sequence of n insert-lookup pairs.
Conditions:
- Each insertion is of a random number, each lookup is for a random number.
- The lookup performs a binary search.

Points to Remember

Maps are cool, and cool programmers use maps.
- But don't forget sorted vectors.
Map elements are stored in sorted order.
- Map operations aren't cheap.
Map elements are pairs of values.
- Asymmetric values: key and associated value.
Be careful when accessing maps with [].
- Unintended map bloat.

This page last modified on 12 March 2004.