Notes from C++ Primer

Associative containers differ in fundamental respect from the sequential containers: elements in associative containers are stored and retrieved by a key, in contrast to elements in a sequential container, which are stored and accessed sequentially by their position within the container.

Associative container supports using key to find and access element with high efficiency. There‘re two base associative container type: map and set. The element of map is organized with the key-value form: the key is used as the index of map, and the value is the data of storing and accessing. The set contains only one key and supports efficient queries to whether a given key is present.

pair Type

pair is also a kind of template type, but with two type parameters passing when pair is initialized.

pair<string, string> anon;			// holds two stringspair<string, int> word_count;		// holds a string and an intpair<string, vector<int> > line;	// holds string and vector<int>

We also can provides initial value in definition:

pair<string, string> author("James", "Joyce");

If we need to define many same pair type, we can use typedef to simplify the declaration:

typedef pair<string, string> Author;Author proust("Marcel", "Proust");Author joyce("James", "Joyce");

pair object has two member variable: first, and second. The dot operation can be used to access them:

string firstBook;// access and test the data members of the pairif(author.first == "James" && author.second == "Joyce")	firstBook = "Stephen Hero";

The library provides make_pair function to generate new pair object:

pair<string, string> next_auth;string first, last;while(cin >> first >> last){	// generate a pair from first and last	next_auth = make_pair(first, last);		// process next_auth ...}

These operations are equivalent to the below operations:

// use pair constructor to make first and last into a pairnext_auth = pair<string, string>(first, last);

or read directly from input stream:

pair<string, string> next_auth;// read directly into the members of next_authwhile(cin >> next_auth.first >> next_auth.second){	// process next_auth ...}

map Type

A map is a collection of key-value pairs. It is often referred as an associative array: use the key to get value instead of using position to get value. There‘s a constraint for the key type. The type of key must support the comparasion function "<". And the "<" relationship must be validate.

Dereference the map iterator will generate pair type object:

// count number of times each word occurs in the inputmap<string, int> word_count;	// empty map from string to int// get an iterator to an element in word_countmap<string, int>::iterator map_it = word_count.begin();// *map_it is a reference to a pair<const string, int> objectcout << map_it->first;			// prints the key for this elementcout << map_it->second;			// prints the value of the elementmap_it->first = "new key";		// error: key is const++map_it->second;				// ok: we can change value through an iterator

Associative Containers