map Library

<map>


A map<K,V> m is a set of key-value pairs with unique, sorted keys of type K and values of type V. m[k] efficiently (O(log n) time) returns the value associated with k (as an lvalue), or creates a default value (0 if V is numeric) if k is used for the first time. A map iterator points to a pair<const K, V>, which has members first of type const K and second of type V. pair<K,V> x(k,v); // Create a pair x containing copies of k and v
x.first // k
x.second // v
x=make_pair(k,v) // x.first=k; x.second=v;

map<K,V> m; // map sorted by < on K
map<K,V,f>() // map sorted by f(x,y) instead of x<y on K
m[k]=v; // Associate v (type V) with unique key k of type K
m[k] // Retrieve v, or associate V() with k if new
m.size() // Number of unique keys
m.empty() // true if m.size() == 0
map<K,V>::iterator // bidirectional, points to a pair<const K, V>
map<K,V>::const_iterator // points to a pair<const K, const V>
m.begin() // Points to first pair (lowest k)
m.end() // Points 1 past last pair
m.find(k) // Points to pair containing k or m.end() if not found
m.erase(k) // Remove key K and its associated value
m.erase(b) // Remove pair pointed to by iterator b
m.erase(b, e) // Remove sequence [b, e)
m.clear() // Make empty: m.erase(m.begin(), m.end())
m==m2 // Compare maps, also !=, <, <=, >, >=
We use m.find(k) rather than m[k] when we wish to look up k without increasing the size of m if k is not found. // Read words, print an alphabetical index of words with their counts
string s;
map<string, int> m;
while (cin >> s)
++m[s];
for (map<string, int>::const_iterator p=m.begin(); p!=m.end(); ++p)
cout << p->first << " " << p->second << endl;
A multimap is a map that allows duplicate keys. It support all map operations except []. Elements are added by inserting a pair<K,V> and retrieved by m.equal_range(k) which returns a pair of iterators defining the sequence of pairs matching k. multimap<K,V,f> m; // f defaults to < on K
m.insert(make_pair(k,v)) // Insert a pair
pair<multimap<K,V,f>::iterator, multimap<K,V,f>::iterator> p
= m.equal_range(k) // Sequence with key k is [p->first, p->second)

f (when used as a template argument) is a functoid (or function object), a class that looks like a function by overloading (). For example:
template <class T> class GreaterThan {
public:
bool operator()(const T& a, const T& b) const {return b < a;}
};

map<string, int, GreaterThan<T> > m; // keys sorted in reverse order