In the previous post, we explored two of the STL's sequence containers:
These containers are ideally suited for situations where we need to keep track of an ordered list of elements. However, representing data in ordered lists is not optimal in many applications.
In this installment of Play interactively with C++, we will explore STL Associative Containers.
Associative and Sequential containers differ from one another in a fundamental way:
The Associative container types are:
Elements Ordered by Key | |
---|---|
map |
Associative array--holds key-value pairs |
set |
Container in which the key is the value |
multimap |
map in which a key can appear multiple times |
multiset |
set in which a key can appear multiple times |
Unordered Collections | |
---|---|
unordered_map |
map organized by a hash function |
unordered_set |
set organized by a hash function |
unordered_multimap |
Hashed map --keys can appear multiple times |
unordered_multiset |
Hashed set --keys can appear multiple times |
A map
is a collection of key-value pairs. For example, each pair might contain a book's author as a key and a book's name as its value. We speak of such a data structure as mapping authors to books.
The map
type is often referred to as an associative array. An associative array is like a normal array except that its subscripts don't have integers. Values in a map
are found by a key rather than by their position.
In contrast, a set
is simply a collection of keys. A set
is most useful when we simply want to know whether a value is present.
map
¶To illustrate how to use a map, we are going to write a word-counting program.
#include <string>
#include <sstream>
#include <iostream>
#include <map>
std::string text = "The k-medoids algorithm is a clustering algorithm related to the k-means algorithm and the \
medoidshift algorithm Both the k-means and k-medoids algorithms are partitional breaking the dataset up \
into groups and both attempt to minimize the distance between points labeled to be in a cluster and a \
point designated as the center of that cluster";
// Create a string stream from the string
std::stringstream s(text);
std::string word;
// empty map from string to size_t
// This map stores elements in which the keys are strings and the values are size_ts
std::map<std::string, size_t> word_count;
// Use a string-stream to fetch and increment the counter for word
for (int i = 0; s >> word; i++){
++word_count[word];
}
When we fetch an element from a map, we get an object of type pair. Briefly, a pair is a template type that holds two (public) data elements named first and second. The pairs used by map have a first member that is the key and a second member that is the corresponding value.
// for each element in the map print the results
for (const auto &w : word_count){
std::cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << std::endl;
}
Both occurs 1 time The occurs 1 time a occurs 3 times algorithm occurs 4 times algorithms occurs 1 time and occurs 4 times are occurs 1 time as occurs 1 time attempt occurs 1 time be occurs 1 time between occurs 1 time both occurs 1 time breaking occurs 1 time center occurs 1 time cluster occurs 2 times clustering occurs 1 time dataset occurs 1 time designated occurs 1 time distance occurs 1 time groups occurs 1 time in occurs 1 time into occurs 1 time is occurs 1 time k-means occurs 2 times k-medoids occurs 2 times labeled occurs 1 time medoidshift occurs 1 time minimize occurs 1 time of occurs 1 time partitional occurs 1 time point occurs 1 time points occurs 1 time related occurs 1 time that occurs 1 time the occurs 6 times to occurs 3 times up occurs 1 time