标签: 关联容器

顺序容器按照位置来存储它们的元素，关联容器使用key。 两种基本的关联容器类型是map和set，map包含有key-value pair，set仅仅包含了key。 set可以用来保存那些我们希望忽略的文本，而map非常适合用来存储字典。 关联容器的类型： map set multimap multiset unordered_map unordered_set unordered_multimap unordered_multiset 关联容器的头文件： #include map #include set #include unordered_map #include unordered_set 11.1 Using an Associative Container ---------------------------------------------------------------- map通常被称为关联矩阵（associative array），因为它的特性类似array， map和array的区别是，map的下标不一定是整型数。 如果用map存储号码簿，人名就是key，电话号码就是value，我们可以通过人名索引到号码。 再比如下面这段用于计算字符串出现次数的代码： mapstring, size_t word_count; string word; while (cin word)     ++word_count ; for (const auto w : word_count)     cout w.first " occurs " w.second endl; 执行结果是： $ ./hello hello hello world world world hello occurs 2 world occurs 3 和顺序容器一样，关联容器也是模板，这意味着它需要参数才能完成初始化。 比如在上面的代码里，string就是key的类型，size_t是value的类型，使用key来索引value。 下面是一段有关set的代码： mapstring, size_t word_count; setstring exclude = {"hello", "world"}; string word; while (cin word) {     if (exclude.find(word) == exclude.end())         ++word_count ; } for (const auto w : word_count)     cout w.first " occurs " w.second endl; 执行结果是： $ ./hello hello world world maria maria here here occurs 1 maria occurs 2 11.2 Overview of the Associative Container ---------------------------------------------------------------- 关联容器支持大部分的和顺序容器一样的操作，比如size()、clear()等。 关联容器不支持push_front或者push_back，这两个操作对关联容器没有意义。 关联容器不支持使用element和count构成的构造函数或者insert函数。 另外，关联容器具备自己独特的方法，比如对hach值的tuning。 另外，关联容器的迭代器是双向的。 关联容器的初始化： mapstring, string authors = {         {"Joyce", "James"},         {"Austen", "Jane"},         {"Dickens", "Charles"} }; map和set的key必须是独一无二的，但是multimap和multiset的key可以有很多个元素。 比如下面的代码： vectorint ivec; for (vectorint::size_type i = 0; i != 10; ++i) {     ivec.push_back(i);     ivec.push_back(i); } setint iset(ivec.begin(), ivec.end()); multisetint miset(ivec.begin(), ivec.end()); cout ivec.size() endl; cout iset.size() endl; cout miset.size() endl; 执行结果是： $ ./hello 20 10 20 key的类型，必须使得元素之间可以比较。 我们也可以自定义key的比较方式，称为strict weak ordering：  * 两只key不能同时小于对方。  * 如果k1小于k2，k2小于k3，那么k1一定会小于k3.  * 如果两只key都没有小于对方，则它们相等，如果k1=k2，k2=k3，则k1=k3。 如果多只key相等，那么它们都会索引到同一个value。 为了自定义一个可比较的multiset，我们必须指定了两个类型，一是key，一是comparion类型。 比如下面的代码： bool compare(const Sales_data lhs, const Sales_data rhs) {     return lhs.isbn() rhs.isbn(); } int main(int argc, char *argv ，如果没有此元素则添加； c.at ，如果没有此元素则throw一个out_of_range异常。 关联容器如何搜索元素？ 如果我们关心这个特定的元素是否存在，则使用find； 如果我们关心这个特定的multimap元素是否存在，则使用count。 另外，使用lower_bound配合upper_bound也是一个好办法。 另外，equal_range更直接，它的返回值pair刚好对应lower_bound和upper_bound。 11.4 The Unordered Containers ---------------------------------------------------------------- 无序容器的key，通过hash值来存储。。 如果我们无法对key进行排序的话，就可以考虑使用无序容器。 无序容器实际上是把它的各个元素放置在了n个木桶里，再通过hash索引过去。 hash表，也称散列表，是根据关键码值(key value)而直接进行访问的数据结构。也就是说， 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。做法是，通过把Key使用固定 的算法函数即所谓的哈希函数转成一个整型数字，然后将该数字对数组长度取余，取余结果就当作数组 的下标，将value值存储再以该数字为下标的数组空间里。  * 有关无序容器的内容有些复杂，后面还需要深入学习！