[C++][基础]8_容器
[C++][基础]8_容器
8.1 顺序容器
8.2 关联容器
注：在迭代关联容器时，我们可以确保按键的顺序访问，而与元素在容器中的存放位置完全无关。
关联的本质在于元素的值与某个特定的键相关联。
map和set的键必须是唯一的，且不能修改。
8.2.1 pair类型
Pair是一种模板类型，但不是容器。
Eg:
typedef pair<string, int> Student;
Student jack("Jack", 18);
if(jack.first == "Jack" && jack.second == 18)
cout << "Right" << endl;
Eg:
string name = "Tom";
int age = 19;
Student tom = make_pair(name, age);
if(tom.first == "Tom" && tom.second == 19)
cout << "Right" << endl;
8.2.2 map类型
8.2.2.1 map对象的定义
对于map类型的键类型，只有一个约束：就是必须支持 < 操作符。
8.2.2.2 map定义的类型
map<K, V>::key_type 键的类型
map<K, V>::mapped_type 键所关联的值的类型
map<K, V>::value_type 一个pair类型，它的first元素是key_type，它的第二个元素是mapped_type
8.2.2.3 给map添加元素
(1)使用下标
使用下标可以返回键所关联的值，如果该键不在map中，则自动添加这个键。
Eg:
map<string, int> word_count;
word_count["David"] = 18;
假如word_count中没有David这个键，则添加这个键，并把它的关联值设为18。
如果有这个键，则仅仅是把这个键的值设为18。
Eg:
map<string, int> word_count;
string word;
while(cin >> word)
{
cout << ++word_count[word];
}
在上例中，每当第一次输入一个词，自动生成该键，以后每次输入同一个词，就会加1。
(2)map::insert
Eg:
word_count.insert(make_pair("Jack", 18);
word_count.insert(make_pair("Jack", 123));
如果map中已经存在相同元素，则插入无效。Jack对应的值仍为18。
8.2.2.4 给map删除元素
m.erase(k) 删除m中键为k的元素，返回size_type类型的值，表示删除的元素个数
m.erase(p) 从m中删除迭代器p所指向的元素。p必须指向m中确实存在的元素，且不能等于m.end()
m.erase(b, e) 删除一段范围的元素，b，e是迭代器。b必须小于等于e。
8.2.2.5 查找map元素
m.count(k) 返回m中k出现的次数
m.find(k) 返回m中指向k的迭代器， 若该迭代器不存在，则返回超出末端迭代器，即m.end()。
8.2.3 set类型
set支持大部分的map操作。
但有两种例外：set不支持下标操作符，而且没有定义mapped_type。在set中，value_type不是pair类型，而是与key_type相同的类型。它们指的是set中存储的元素类型。
8.2.4 multimap和multiset类型
在map和set中，一个键只能对应一个实例。而multimap和multiset则允许一个键对应多个实例。
multimap和multiset所支持的操作分别与map和set的操作相同，只有一个例外：multimap不支持下标操作。
8.2.4.1 元素的添加和删除
8.2.4.2 查找元素
8.3 泛型算法