关联容器与顺序容器
关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。
关联容器（Associative containers）支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map 和 set。 其中map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引，而值则表示所存储和读取的数据。set 仅包含一个键，并有效地支持关于某个键是否存在的查询。
关联容器类型
一般来说，如果希望有效地存储不同值的集合，那么使用 set 容器比较合适，而 map 容器则更适用于需要存储（乃至修改）每个键所关联的值的情况。在做某种文本处理时，可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用：单词本身是键，而它的解释说明则是值。 set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multi
set，这两种类型允许多个元素拥有相同的键。
注意：关联容器根据键排列元素！所以，在迭代遍历访问容器时，是按照键的顺序访问元素，而与元素在容器中的存放位置无关！
基础pair类型
map类型
map类型的定义
在使用关联容器时，它的键不但有一个类型，而且还有一个相关的比较函数。 所用的比较函数必须在键类型上定义严格弱排序（strict weak ordering）。所谓的严格弱排序可理解为键类型数据上的“小于”关系。当用于一个键与自身的比较时，肯定会导致 false 结果。如果它们相互之间都不存在“小于”关系，则容器将之视为相同的键。用做 map 对象的键时，可使用任意一个键值来访问相应的元素。这与下面的添加元素时行为有一定的对应
map定义的类型
// count number of times each word occurs in the input
map<string, int> word_count; // empty map from string to int
// get an iterator to an element in word_count
map<string, int>::iterator map_it = word_count.begin(); // *map_it is a reference to a pair<const string, int> 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<K, V>::key_type 类型即存放键，而 second成员则为map<K,V>::mapped_type 类型，即存放值。
map元素添加
一、下标添加
map <string, int> word_count; // empty map
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;
将发生：
2.将一个新的键－值对插入到 word_count 中。它的键是 const string 类型的对象，保存 Anna。而它的值则采用值初始化，这就意味着在本例中值为 0。
3.将这个新的键－值对插入到 word_count 中。
4.读取新插入的元素，并将它的值赋为 1。
使用下标访问 map 与使用下标访问数组或 vector 的行为截然不同：用下标访问不存在的元素将导致在 map 容器中添加一个新元素，它的键即为该下标值。
通常来说，下标操作符返回左值。它返回的左值是特定键所关联的值。可如下读或写元素：
// count number of times each word occurs in the input map<string, int> word_count; // empty map from string to int string word; while (cin >> word) ++word_count[word];
二、insert添加
// if Anna not already in word_count,inserts new element with value 1
word_count.insert(map<string, int>::value_type("Anna", 1));
上面语句的实参可以简化如下两种方法：
typedef map<string,int>::value_type valType;
word_count.insert(valType("Anna", 1));
2、insert的返回值
bool 值为 false。在这两种情况下，迭代器都将指向具有给定键的元素。
查找以及读取map中的元素
一、下标读取
map<string,int> word_count; int occurs = word_count["foobar"];
但是：使用下标存在一个很危险的副作用：如果该键不在 map 容器中，那么下标操作会插入一个具有该键的新元素。
二、不修改map对象的查询操作
int occurs = 0;
if (word_count.count("foobar"))
occurs = word_count["foobar"];
int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;
如果希望当具有指定键的元素存在时，就获取该元素的引用，否则就不在容器中创建新元素，那么应该使用
find。
删除map元素
遍历map对象
实际程序演练
// 建立一个map对象，保存所读入的单词及其出现的次数(以单词为键，对应的值为单词出现的次数)
// 利用下标添加元素
#include <iostream>
#include <map>
#include <string>
using namespace std;
// 2013.11.18 Written by C_SuooL_Hu
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
map<string, int> wordCount;
typedef map<string, int> ::iterator valType;
string word;
// 读入单词并统计次数
cout << "Enter some words (Ctrl + Z to end):" << endl;
while (cin >> word)
{
// 如果读入的word存在在容器中，则使键值为word的值++，否则添加以此元素为索引的键，然后键值初始化为0，后++，即为1.
++wordCount[word];
}
// 输出结果，用迭代器
cout << "word\t\t" << "times" << endl;
for (valType iter = wordCount.begin(); iter != wordCount.end(); ++iter)
{
cout << (*iter).first << "\t\t" << (*iter).second << endl;
}
return 0;
}
#include <iostream> #include <map> #include <string> using namespace std;// 2013.11.18 Written by C_SuooL_Hu// mapint main() { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); // count number of times each word occurs in the input map<string, int> word_count;
// empty map from string to int typedef map<string, int> ::iterator valType; string word; while (cin >> word) { // inserts element with key equal to word and value 1; // if word already in word_count, insert does nothing pair<map<string, int>::iterator, bool>
ret =word_count.insert(make_pair(word, 1)); if (!ret.second) // word already in word_count ++ret.first->second; // increment counter }// outputcout << "word\t\t" << "times" << endl;for (valType iter = word_count.begin(); iter != word_count.end(); ++iter){cout
<< (*iter).first << "\t\t" << (*iter).second << endl;}return 0;}
二、单词转换器（转换译码）
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
// 2013.11.18 Written by C_SuooL_Hu
using namespace std;
ifstream& open_file(ifstream&, const string&);
int main()
{
freopen("out.txt", "w", stdout);
// map to hold the word transformation pairs:
// key is the word to look for in the input; value is word to use in the output
map<string, string> trans_map;
string key, value;
// ´´½¨Á÷
ifstream myfile ("trans_map.txt");
ifstream myfilein ("in.txt");
ofstream outfile("out.txt");
// ÅжÏÎļþÊÇ·ñ´ò¿ª
if(!myfile)
{
cout << "Unable to open myfile";
exit(1); // terminate with error
}
if(!outfile)
{
cout << "Unable to open outfile";
exit(1); // terminate with error
}
// read the transformation map and build the map
while (myfile >> key >> value)
{
trans_map.insert(make_pair(key, value));
}
// this block just produces the vector so that we can print it
// for the book
cout << "Here is our transform string input:\n\n";
// read some text to transform
string word;
// ok, now we're ready to do the transformations
// open the input file and check that the open succeeded
string WORD;
bool firstword = true; // controls whether a space is printed
while (myfilein >> WORD)
{
// ok: the actual mapwork, this part is the heart of the program
map<string, string>::const_iterator map_it =
trans_map.find(WORD);
// if this word is in the transformation map
if (map_it != trans_map.end())
{
// replace it by the transformation value in the map
WORD = map_it->second;
}
if (firstword)
firstword = false;
else
cout << " "; // print space between words
cout << WORD;
}
cout << endl; // done with this line of input
return 0;
}
测试结果：
