关联容器 Associative Containers
关联容器包括：
l map
l set
l multimap
l multiset
10.1 初步知识：pair类型
创建和初始化pairs
Examples:
|
pair<string, string> anon; // holds two strings
pair<string, int> word_count; // holds a string and an int
pair<string, vector<int> > line; // holds string and vector<int>
|
使用typedef简化定义：
|
typedef pair<string, string> Author;
Author proust("Marcel", "Proust");
Author joyce("James", "Joyce");
|
pair操作
可以直接访问pair的数据成员。这些数据成员都是public。（the pair class gives us direct access to its data members: Its members are public.）
|
string firstBook;
// access and test the data members of the pair
if (author.first == "James" && author.second == "Joyce")
firstBook = "Stephen Hero";
|
10.2 关联容器
关联容器共享了很多顺序容器的操作。但是关联容器还定义了自己特有的操作。
关联容器的元素是按key进行排序的。当我们迭代访问一个关联容器时，保证是按照key的顺序来访问，而不是按照元素在容器中的顺序来访问的。When we iterate across an associative container, we are guaranteed that the elements are accessed in key order, irrespective of the order in which the elements were placed in the container.
10.3 map
定义map
|
map<k, v> m;
|
创建一个名字是m的空的map。
|
|
map<k, v> m(m2);
|
创建一个名字是m的map，m是m2的拷贝。m和m2必须具有相同的key和value类型。
|
|
map<k, v> m(b, e);
|
创建一个名字是m的map，它是迭代器b和e指定的元素的拷贝。元素的类型必须可以转换成<const k, v>
|
key类型的约束条件
key不仅仅有类型，而且还包括对比方法。缺省条件下，使用>操作符比较key。这就是说，作为key的类型必须定义<操作。
map定义的类型
map定义的类型包括：
|
map<K, V>::key_type
|
用于索引map的key的类型
|
|
map<K, V>::mapped_type
|
map中与key关联的 值的类型
|
|
map<K, V>::value_type
|
pair
它的第一个元素的类型必须是const的map<K, V>::key_type；第二个元素的类型必须是map<K, V>::mapped_type。
|
value_type是一个pair，只能修改pair的值，而不能修改key。
map迭代器解引用生成pair
当我们解引用一个map迭代器，得到的是一个容器值的引用, 这个值的类型是value_type类型。
Example:
|
// 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> object
cout << 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
|
向map添加元素
有2种方法：
l 使用insert
l 先用下标操作符索引元素，然后对此元素进行赋值。
通过下标索引map
在map中下标就是key。如果使用的下标值不存在，就会在map里追加一个元素，它的key就是这个下标值。
|
map <string, int> word_count; // empty map
…
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;
|
map下标操作的返回值类型是mapped_value。
使用map::insert
一个简单的例子可以看出insert和下标操作的区别：
|
int main() {
map <string, int> word_count ;
word_count["first"] =1;
word_count["first"] =9;
cout << word_count["first"] << endl;
word_count.clear();
word_count.insert( map<string, int>::value_type("first", 1) );
word_count.insert( map<string, int>::value_type("first", 9) );
cout << word_count["first"] << endl;
return 0;
}
|
输出：
insert返回的是一个pair。first是指向元素的map迭代器，second是bool值，表示元素是否插入成功。如果key存在时，直接返回map中的元素迭代器；如果key不存在，创建一个新的pair，然后插入map，返回这个新元素对应的迭代器。
map查找
下标操作提供了最简单的访问获得键值的方法：
|
map<string,int> word_count;
int occurs = word_count["foobar"];
|
int occurs = word_count["foobar"];但是这样的取值方法其实还有可能隐含着一个插入操作。如果word_count不包含"foobar"，则先插入以"foobar"作为key的元素。值则是按默认值处理，等于0，这样occurs就被赋值为0.
另一类方法：
|
m.count(k)
|
返回k在m中出现的次数
|
|
m.find(k)
|
如果k存在，返回指向该元素的迭代器。如果不存在，返回off-the-end迭代器。
|
先用这类方法进行判断，然后再用下班取值，就可以避免如果key不存在，直接取值导致向map插入元素带来的副作用。
Example（使用count检查某个key是否存在）:
|
int occurs = 0;
if (word_count.count("foobar"))
occurs = word_count["foobar"];
|
Example（读取元素而不插入元素）:
|
int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;
|
删除map元素
有三类删除元素的操作：
|
m.erase(k)
|
删除key值是k的元素。返回值的类型是size_type，表示删除元素的个数。
|
|
m.erase(p)
|
删除由迭代器p指向的元素。p!=m.end()。返回值是void。
|
|
m.erase(b,e)
|
删除由迭代器b,e指定访问内的所有元素。返回值是void。
|
10.4 set
其实就是只有key的map。
10.5 multimap 和 multiset 类型
multimap追加元素，还是按照pair来追加的。
|
// adds first element with key Barth
authors.insert(make_pair(
string("Barth, John"),
string("Sot-Weed Factor")));
// ok: adds second element with key Barth
authors.insert(make_pair(
string("Barth, John"),
string("Lost in the Funhouse")));
|
multimap的find操作
find的返回值是迭代器：
|
// author we'll look for
string search_item("Alain de Botton");
// how many entries are there for this author
typedef multimap<string, string>::size_type sz_type;
sz_type entries = authors.count(search_item);
// get iterator to the first entry for this author
multimap<string,string>::iterator iter =
authors.find(search_item);
// loop through the number of entries there are for this author
for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) cout <<
iter->second << endl; // print each title
|
对比map的find操作：
|
//int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;
|
另一种面向迭代器的解决方案
这种方案包含了3种操作，这3种操作返回值都是指针。它们提供了另一种访问集合元素的方法，虽然这些方法对于map和set也适用，但是更多情况还是用在multimap和multiset。
|
m.lower_bound(k)
|
返回指向key值不小于k的第一个元素的迭代器。
|
|
m.upper_bound(k)
|
返回指向key值大于k的第一个元素的迭代器
|
|
m.equal_range(k)
|
返回一个迭代器的pair。
first相当于m.lower_bound(k)；
second相当于m. upper_bound(k)。
|
例如，key数据如下：
If key=3, lower_bound=第一个3; upper_bound=5
if key=4; lower_bound=第一个5; upper_bound=5。这表明此key不存在（判断条件lower_bound= upper_bound），同时也表示出这个key在容器中的插入位置。
使用容器：文本查询程序
这部分其实最好先自己写写看。
需求：
读入指定文件，然后统计指定单词出现的次数，按规定的格式来显示。
规定格式包括：
l 出现的总的次数
l 行号 内容
按照这个要求我先写了一个，然后再回去读大师的说法，比对不足。