Associative Containers in C++

Associative containers support efficient lookup and access by key. The two primary associative containers are set and map. The elements of a map are key-value pairs, where the key acts as an index and the value represents the data associated with that index; the elements of a set contain only a key. A set supports efficient key lookup, and is presumably implemented with a hash table under the hood.

The C++ standard library provides 8 associative containers, and these 8 containers differ along three dimensions:

1. set or map
2. ordered or unordered---whether there is an unordered prefix
3. duplicate keys allowed or forbidden---whether there is a multi prefix

This article focuses on set and map; for content related to the other containers, refer to the C++ API.

Using set and map

Using a map:

//count how many times each word appears in the input
map<string,size_t> word_count;	//create a new map
string word;
while(cin>>word)
	++word_count[word];    //increment the count for this word by 1
for(const auto &w:word_count)
	cout<<w.first<<" occurs "<<w.second<<((w.second>1)?" times":" time")<<endl;

Note that for the subscript operation on a map, if you use word_count[word], then when the key word is not found, an element with key word is added and its value is value-initialized. If you use word_count.at(word), then when the key word is not found, an out_of_range exception is thrown.

Using a set:

//count how many times each word appears in the input
map<string,size_t> word_count;
set<string> exclude={"The","But","And","Or","An"};
string word;
while(cin>>word)
	if(exclude.find(word)==exclude.end())   //when the word is not found in the set, find returns the end iterator
	++word_count[word];

The pair class and the extra type aliases in associative containers

The pair class is defined in the header utility, and a pair holds two data members. Like the containers, pair is a template used to generate specific types. When creating a pair, we must supply two type names.

pair<string,size_t> word_count;	//holds a string and a size_t

Unlike the other standard library types, the data members of a pair are public; the two members are named first and second respectively, and the elements stored in a map are exactly of pair type.

Associative containers also define other types that represent the types of the container’s keys and values:

• key_type the container’s key type
• mapped_type the type associated with each key, applicable only to map
• value_type for set, the same as key_type; for map, it is pair<const key_type,mapped_type>

set<string>::value_type v1;	//string
set<string>::key_type v2;  //string
map<string,int>::value_type v3;	//pair<const string,int>
map<string,int>::key_type v4;	//string
map<string,int>::mapped_type v5;//int

Iterators of associative containers

When you dereference an iterator of an associative container, you get a reference to a value of the container’s value_type. For a map, value_type is a pair type whose first member holds the const key and whose second member holds the value:

//obtain an iterator to an element in word_count
auto map_it=word_count.begin();
//*map_it is a reference to a pair<const string,size_t> object
cout<<map_it->first;
cout<<" "<<map_it->second;
map_it->first="new key";  //error, the key is const
++map_it->second;   //the value element can be changed

The keys in a set are also const. You can use a set to read element values, but you cannot modify them:

set<int> iset={0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it=iset.begin();
if(set_it!=iset.end()){
	*set_it=42;   //error, a const key cannot be modified
	cout<<*set_it<<endl;
}