关联容器与顺序容器

关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

关联容器（Associative containers）支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map 和 set。 其中map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引，而值则表示所存储和读取的数据。set 仅包含一个键，并有效地支持关于某个键是否存在的查询。

关联容器类型

一般来说，如果希望有效地存储不同值的集合，那么使用 set 容器比较合适，而 map 容器则更适用于需要存储（乃至修改）每个键所关联的值的情况。在做某种文本处理时，可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用：单词本身是键，而它的解释说明则是值。 set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multi set，这两种类型允许多个元素拥有相同的键。

将C语言梳理一下，分布在以下10个章节中：

注意：关联容器根据键排列元素！所以，在迭代遍历访问容器时，是按照键的顺序访问元素，而与元素在容器中的存放位置无关！

// count number of times each word occurs in the input
map word_count; // empty map from string to int
// get an iterator to an element in word_count
map::iterator map_it = word_count.begin(); // *map_it is a reference to a pair objectcout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element

map_it->first = "new key"; // error: key is const

++map_it->second; // ok: we can change value through an iterator

对迭代器进行解引用将获得一个pair对象，其first成员具有const map::key_type 类型即存放键，而 second成员则为map::mapped_type 类型，即存放值。

map word_count; // empty map
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

将发生：

// count number of times each word occurs in the input
map word_count; // empty map from string to int
string word;
while (cin >> word)
++word_count[word];

// if Anna not already in word_count,inserts new element with value 1
word_count.insert(map::value_type("Anna", 1));

上面语句的实参可以简化如下两种方法：

typedef map::value_type valType;
word_count.insert(valType("Anna", 1));

2、insert的返回值

map word_count;
int occurs = word_count["foobar"];

但是：使用下标存在一个很危险的副作用：如果该键不在 map 容器中，那么下标操作会插入一个具有该键的新元素。