Detailed use of the associated containers of C++Primer notes

Associated container

  The association container supports the ability to efficiently find and read elements by keys. The two basic associated container types are map and set. The elements of a map are organized as key-value pairs: the key serves as the index of the element in the map, and the value represents the data stored and read. Set contains only one key and effectively supports queries about whether a key exists. Objects of set and map types are not allowed to add a second element to the same key. If a key must correspond to multiple instances, use the multimap or mutiset types, which allow multiple elements to have the same key.

Pair type: Defined in the header utility.

Creation and use of pair:

#include<utility>
pair<string,int> author("Peter",30);
cout<<author.first<<"t"<<author.second<<endl;//Data members can be accessed directly
//Use typedef to simplify
typedef pair<string,string> Student;
Student s1,s2("aaa","bbb");
s1.first="ccc";
s1.second="ddd";
//Use the make_pair function to generate a new pair object
string first="eee",second="fff";
Student s3=make_pair(first,second);

The map type: A map is a collection of key-value pairs.

The map < K, V > ::key_type is the type of the key used as the index in the map

The map < K, V > ::mapped_type is used in the map as the type of the associated value

The map < K, V > ::value_type is a pair type

The map iterator is dereferenced to produce an object of type pair:

map<string,int>::iterator map_it = word_count.begin();
cout<<map_it->first<<""<<map_it->second<<endl;

Using subscripts to access map objects:

There are two ways to add key-value pairs. You can do this with an insert member, or you can get the element first with the subscript operator and then assign a value to it.

Accessing a map with subscripts is very different from accessing an array or a vector with subscripts. Accessing nonexistent elements with subscripts results in the addition of a new element in the map container whose key is the value of that subscript.

Method one:

map<string,int> word_count;
word_count["Peter"]=10;//That's like adding a key-value pair
//Create a map object that keeps track of the number of times each word appears.
map<string,int> word_count;
string word;
while(cin>>word)
{
++word_count[word];
}

Method 2: using insert:

map<string,int> word_count;
word_count.insert(map<string,int>::value_type("aaa",1));
//Rewrite the word statistics program with the insert method
map<string,int> word_count;
string word;
while(cin>>word)
{
pair<map<string,int>::iterator,bool> ret=word_count.insert(make_pair<string,int>(word,1));
if(!ret.second)//If the insert is not successful, prove that the original key value already exists, the statistic value will be +1
{
++ret.first->second;//First is an iterator that points to the inserted key
}
}

Find and read elements in the map:

  Using the subscript operator is a simpler approach, but it has the side effect of inserting a new element with the key when the key is not in the map container.

The map container provides two operations: count and find

M.count (k) returns the number of occurrences of k in m, which can only be 1 or 0 for map objects, and more values may appear for mutimap containers.

M.ind (k) returns the iterator returned by index k

The count method is used to find the presence or absence of the specified key in the map, while the find method is suitable for finding the element corresponding to the specified key in the map container.

//Reads an element without inserting a new one
int occurs;
map<string,int>::iterator it= word_count.find("foobar");//Returns the end iterator if it does not exist
if(it!=word_count.end())//Probably not
{
occurs=it.second;
}

Remove elements from the map object:

M. ase(k) deletes the element whose key is k in m. The return value is the number of deleted elements, which must be 0 or 1 for the map container.

M. ase(p) removes the element pointed to by iterator p from m. The return value is of type void.

M. ase(b,e) removes a segment from m that is scoped by a pair of iterators. The return value is of type void.

Iteration traversal of map object:

map<string,int> word_count;
word_count["aaa"]=1;
word_count["bbb"]=2;
word_count["ccc"]=3;
map<string,int>::const_iterator iter = word_count.begin();
while(iter!=word_count.end())
{
cout<<iter->second<<endl;
iter++;
}

The set type:

The map container is a collection of key-value pairs, while the set container is simply a collection of keys. The set container is best used when you only want to know if a value exists.

Add elements to set:

set<int> set1;
pair<set<int>::iterator,bool> p=set1.insert(1);//Returns an object of type pair with an iterator and a Boolean value
set1.insert(2);
int arr[]={1,2,3};
set<int> set2;
set2.insert(arr,arr+3);//Return void

Get elements from set: similar to the map method, use the find and count functions.

Multimap and multiset types:

In the map and set containers, a key can correspond to only one instance. The multimap and multiset types allow a key to correspond to multiple instances. It supports the same operations as map and set, with one exception: multiply does not support subscript operations.