!!!Chapter 10 Associative Containers
Associative containers support efficient lookup and retrieval by a key.
The two primary associative-container types are map and set.
The elements in a map are key-value pairs: The key serves as an index into the map, and the value represents the data that are stored and retrieved.
A set contains only a key and supports efficient queries to whether a given key is present.
An object of map or set type may contain only a single element with a given key. To have multiple instance with a single key, we can usemultimap or multiset.
| map | Associative array; elements stored and retrieved by key |
| set | Variable-sized collection with fast retrieval by key |
| multimap | map in which a key can appear multiple times |
| multiset | set in which a key can appear multiple times |
To use associative types, we should include the header:
#include<map>
#include<set>10.1 Preliminaries: the pair Type
pair is a library type defined in the utility header.
Creating and Initializing pairs
A pair holds two data values, Like the containers, pair is a template type.
A pair holds two data members, each of which has the corresponding named type. The two data members can be different:
pair<string, string> anon;
pair<string, vector<int> > line;We can also provide initializers for each member:
pair<string, string> author("Jay", "joe");Operations on pairs
the pair class gives us direct access to its data members: its members are public. These members are named first and second.
| pair<T1, T2> p1; | Create empty pair with two elements. Elements are value initialized |
| pair<T1, T2> p1(v1. v2) | Create pair and initialize the elements |
| make_pair(v1, v2) | Create a new pair from the values v1 and v2. The type of the pair is inferred from types of v1 and v2 |
| p1 < p2 | Return true if p1.first < p2.first or if !(p2.first < p1.first) && p1.second < p2.second. |
| p1 == p2 | first and second members are respectively equal |
| p.first | Returns the data member of p named first |
| p.second | Returns the data member of p named second |
if(author.first=="Jay" && author.second=="joe")
//do somethingGenerating a New pair
The library defines the make_pair function, we can use this function to make a new pair to assign to an existing pair:
pair<string, string> next_auth;
string first, last;
while(cin >> first >> last)
{
next_author = make_pair(first, last);
//do something...
}//method 2
next_author=pair <string, string> (first, last);
//method 3
while(cin >> next_author.first >> next_author.second)10.2 Associative Containers
Associative containers do not have front, push_front, pop_front, back, push_back, pop_back operations.
Operations common to sequential and associative containers:
1. Three constructors:
C<T> c; //empty container
C<T> c1(c2); //copy of c2
C<T> c(b,e); //copy of elements from b to e<, <=, >, >=, ==, !=c.begin();
c.end();
c.rbegin();
c.rend();For map, value_type is a pair representing the types of the keys and associated values.
5. The swap and assignment operator:
c1 = c2;
c1.swap(c2);6. The clear and erase operations:
c.erase(p);
c.erase(b,e);
c.clear();7. The size operations
c.size();
c.max_size();
c.empty();Elements Are Ordered by Key
When we iterate across an associative container, we are guaranteed that the elements are accessed in key order, irrespective of the order in which the elements were placed in the container.
| Container | Useful for |
|---|---|
| list | lists use up memory wherever it is available and do not reallocate memory for the entire container each time an element is added. They are most useful when elements need to be added in a random order, or sorted. Random access, however, is not possible without iterators. |
| vector | vectors are overall the best container type available and should be used anytime a programmer is unsure of which container to use. They support random access, but elements can only be pushed onto the end. Thevectors support the subscript operators, and elements can be added anywhere in the container but at a larger expense. |
| deque | A deque is particularly useful if elements need to be added to either the front or back at any given time.deques are basically double-ended stacks, and elements can be added or removed at either the front or back, but when re-allocating memory, a deque allocates more memory than a vector. Random access is also supported. Note: Erwin.schaefer 12:15, 25 July 2011 (UTC) On most implementations, deques use an array of pages. They should allocate what they need (at least, by page) and have not the full-reallocation penalty that vectors run into when growing out of capacity. To the least least, re-allocation should not be worse than vectors... |
| map | maps are associative containers where random access is supported via using the key, which is paired up with a mapped element. This is most useful for something like a dictionary. |
| set | A set is simply a collection of keys, and can be used for making a word-list or something similar. The difference between a set and a sequential container is that aset is automatically sorted. |
10.3 The map Type
The map type is often referred to as an associative array.
10.3.1 Defining a map
| map<k, v> m; | empty map with key and value types k and v |
| map<k, v> m(m2); | m as a copy of m2 |
| map<k, v> m(b, e); | m as a copy of the elements denoted by b,e Elements must be able to convert to pair<const k, v> |
Constraints on Key Type
The key for associative container have not only a type, but also an associated comparison function. By default, library use < to compare the keys.
We must define a strict weak ordering comparison function over the key types(eg. "less than"). The comparison function must always yield false when we compare a key with itself. (还需要传导性，且相互一致）
If we have two keys, neither is "less than" the other, the container will treat them as equal. When used as a key to a map, either value could be used to access the corresponding element.
The key type needs to support only the < operator. There is no requirement that is support other relational operators.
10.3.2 Types Defined by map
| map<K, V>::key_type | The type of the keys |
| map<K, V>::mapped_type | The type of the values |
| map<K, V>::value_type | A pair whose first element has type const map<K, V>::key_type and the second element is map<K, V>::mapped_type |
Dereferencing a map Iterator Yields a pair
map<string, int>::iterator map_it=word_count.begin();
cout << map_it->first;
cout << map_it->second;
map_it->first = "new key"; //error: key is const
++map_it->second; //ok: we can change the value10.3.3 Adding Elements to a map
We can add elements to a map by using the insert member or by fetching an element using the subscript operator and then assigning a value to the element returned.
10.3.4 Subscripting a map
When we write:
map<string, int> word_count; //empty map
word_count["Anna"] = 1;- word_count is searched for the element whose key is Anna.
- The element is not found, so a new key-value pair is inserted into word_count. The key is aconst string holding Anna. The value is value initialized, meaning in this case, the value is 0.
- The newly inserted element is fetched and is given the value 1.
For map, using an index that is not already present adds an element with that index to the map. And the associated value is value-initialized: An element of class type is initialized with default constructor; a built-in type is initialized to 0.
Using the Value Returned from a Subscript Operation
We can read/write the returned value:
cout << word_count["Anna"]; //prints 1
++word_count["Anna"]; //add one to the value
cout << word_count["Anna"]; //prints 2Unlike vector or string, the type returned by map subscript operator differs from the type obtained by dereferencing a map iterator.
Programming Implications of the Subscript Behavior
We can write succinct programs with the subscript feature:
map<string, int> word_count;
string word;
while(cin >> word)
++word_count[word];10.3.5 Using map::insert
| m.insert(e) | e is a value_type of m. If key (e.first) is not in m, inserts a new element; if key is in m, then m is unchanged. Returns a pair containing a map iterator referring to the inserted element and a bool indicating whether the element was inserted or not |
| m.insert(beg,end) | beg/end should refer to the same value_type as m. For each element, if the given key is not in m, it inserts the key and its associated value into m. Return void. |
| m.insert(iter,e) | If key (e.first) is not in m, inserts the new element using the iterator iter as a hint for where to begin the search for where the new element should be stored. Returns an iterator that refers to the element in m with given key. |
Using insert Instead of Subscripting
// if Anna not already in word_count, inserts new element with value 1
word_count.insert (map<string, int>::value_type("Anna", 1));By using insert, we don't need to initialization the value, and we can insert the arguments more efficiently.
//use make_pair
word_count.insert(make_pair("Anna", 1));
//use typedef
typedef map<string, int>::value_type valType;
word_count.insert(valType("Anna", 1)); Testing the Return from insert
If we want to insert an element with a key that is already in the map, then insert does nothing.
The insert that takes iterator does not return a value, but the insert takes a pair will return a value to indicate the insert succeed/failed.
//rewrite word count program with insert
map<string, int> word_count;
string word;
while(cin >> word)
{
//insert will return a pair, which is used to initialize ret
pair<map<string, int>::iterator, bool> ret=word_count.insert(make_pair(word,1));
if(!ret.second) //the word already exist
++ret.firss->second;
}10.3.6 Finding and Retrieving a map Element
The simplest way to retrieving a value is by subscript:
map<string, int> word_count;
int occurs = word_count["foobar"];We can use count and find to determine if a key is present without causing it to be inserted:
| m.count(k) | Returns the number of occurrences of k within m. |
| m.find(k) | Returns an iterator to the element indexed by k, if there is one Or return an off-the-end iterator if the key is not present |
Using count to Determine Whether a Key is in the map
The count member for a map always returns either 0 or 1. Because a map may have only one instance of any given key.
If the return value is nonzero, we can use the subscript operator to fetch the value associated with the key without insert the element:
int occurs = 0;
if (word_count.count("foobar"))
occurs = word_count["foobar"];Retrieving an Element Without Adding it
int occurs = 0;
map<string, int>::iterator it = word_count.find("foobar");
if(it!=map.end())
occurs = it->second;10.3.7 Erasing Elements from a map
| m.erase(k) | Removes the element with key k from m. Returns size_type indicating the number of elements removed |
| m.erase(p) | Removes element referred to by the iterator p from m. p must refer to an actual element in m; p != m.end(). Returns void |
| m.erase(b,e) | b<=e. If b==e, then delete nothing. e could equal to m.end(). Returns void |
if (word_count.erase(word))
cout << word << "removed\n";
else cout << word << "is not found\n";10.3.8 Iterating across a map
When we use an iterator to traverse a map, the iterators yield elements in ascending key order.
10.3.9 A Word Transformation Map P 369
My own version(you need to create f1.txt/f2.txt/f3.txt in the correct folder):
#include<fstream>
#include<vector>
#include<utility>
#include<String>
#include<map>
using namespace std;
int main()
{
ifstream f1, f2;
ofstream f3;
f1.open("f1.txt");
map<string, string> tran;
string oriWord,newWord;
while(f1 >> oriWord >> newWord)
{
tran[oriWord]=newWord;
}
f2.open("f2.txt");
f3.open("f3.txt");
map<string, string>::iterator nWord;
while(f2 >> oriWord)
{
nWord=tran.find(oriWord);
if(nWord != tran.end())
f3 << nWord->second << " ";
else
f3 << oriWord << " ";
}
}10.4 The set Type
A set is most useful when we want to know whether a value is present.
Set support most of the map operations, except two:
1. set does not provide a subscript operator
2. set does not define mapped_type. (value_type and key_type are the same type)
As with set, the keys of a set must be unique and may not be changed.
10.4.1 Defining and Using sets
When we initialize a set from a range of elements or insert a range of elements, only one element with a given key is actually added.eg. P 373
Adding Elements to a set
1. insert a key, which will return a pair containing an iterator to the element with this key and a bool indicating whether the element was added.
2. inset an iterator or iterator range, will return void.
Fetching an Element from a set
To fetch an element from a set, we use find operation. Or we can use count to check if the key exists or not.
As with map. the keys in a set are also const. If we have an iterator of the set, we can only read it; we cannot write through it.
10.5 The multimap and multiset Types
The types multiset and multimap allow multiple instance of a key.
The operations supported by multimap and multiset are the same as those on map and set, with one exception:multimap does not support subscripting.
10.5.1 Adding and Removing Elements
Because keys need not be unique, insert always adds an element.
The version of erase that takes a key removes all elements with that key. It returns a count o how many elements were removed. The versions that take an iterator or an iterator range remove only the indicated elements and return void.
10.5.2 Finding Elements in a multimap or multiset
When a multimap or multiset has multiple instance of a given key, those instance will be adjacent elements within the container.
| m.lower_bound(k) | Returns an iterator to the first element with key not less than k |
| m.upper_bound(k) | Returns an iterator to the first element with key greater than k |
| m.equal_range(k) | Returns a pair of iterator. The first is m.lower_bound(k) The second is m.upper_bound(k) |
The find operation returns an iterator that refers to the first instance of the key we're looking for.
The count function tells us how many times a given key occurs.
Using Iterator-Oriented Solution
If the key is in the container:
lower_bound will refer to the first instance of thekey; upper_bound will refer an iterator just after the last instance.
If the key is not in the multimap:
Both lower_bound and upper_bound will refer to the point at which the key could be inserted without disrupting the order.
The equal_range Function
It works similar to lower/upper bound, just return a pair of both values.