现在的位置: 首页 > 综合 > 正文

C++ Primer学习笔记——$10 关联容器

2018年03月30日 ⁄ 综合 ⁄ 共 4752字 ⁄ 字号 评论关闭
题记:本系列学习笔记(C++ Primer学习笔记)主要目的是讨论一些容易被大家忽略或者容易形成错误认识的内容。只适合于有了一定的C++基础的读者(至少学完一本C++教程)。
 
作者: tyc611, 2007-01-25


   本文主要讨论C++标准库中的关联容器(associative container),内容主要涉及map, set, multimap和multiset四类容器。
   如果文中有错误或遗漏之处,敬请指出,谢谢!


概述
   关联容器(Associative Container)与顺序容器(Sequential Container)的本质区别在于:关联容器是通过键(key)存储和读取元素的,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。
 
   关联容器支持通过键来高效地查找和读取元素,两个基本的关联容器是map和set。map的元素是“键-值”对的二元组形式:键用作元素在map中的索引,而值则表示所存储和读取的数据。set仅包含一个键,并有效地支持关于某个键是否存在的查询。set和map类型的对象所包含的元素都具有不同的键。如果需要一个键对应多个实例,则需要使用multimap或multiset类型。这两种类型允许多个元素拥有相同的键。
 
 map  关联数组:元素通过键来存储和读取
 set  大小可变的集合,支持通过键实现的快速读取
 multimap  支持同一个键多次出现的map类型
 multiset  支持同一个键多次出现的set类型
 
pair类型
 
   pair模板类用来绑定两个对象为一个新的对象,该类型在<utility>头文件中定义。pair类型提供的操作如下表:
 
 pair<T1, T2> p1;  创建一个空的pair对象,它的两个元素分别是T1和T2类型,采用值初始化
 pair<T1, T2> p1(v1, v2);

 创建一个pair对象,它的两个元素分别是T1和T2类型,其中first成员初始化为v1,second成员初始化为v2

 make_pair(v1, v2)  以v1和v2值创建一个新的pair对象,其元素类型分别是v1和v2的类型
 p1 < p2  字典次序:如果p1.first<p2.first或者!(p2.first < p1.first)&& p1.second<p2.second,则返回true
 p1 == p2  如果两个pair对象的first和second成员依次相等,则这两个对象相等。
 p.first  返回p中名为first的(公有)数据成员
 p.second  返回p中名为second的(公有)数据成员
 
关联容器
 
   关联容器共享大部分顺序容器的操作,但不提供front, push_front, back, push_back以及pop_back操作。
   具体而言,有顺序容器中的:前三种构造函数;关系运算;begin, end, rbegin和rend操作;类型别名;swap和赋值操作,但关联容器不提供assign函数;clear和erase函数,但erase函数返回void类型;关于容器大小的操作,但resize函数不能用于关联容器。
 

map类型
   map类型定义在头文件<map>中。map是键-值对的集合,通常看作关联数组:可使用键作为下标来获取一个值。map类定义内部定义的类型有key_type, mapped_type, value_type,如下表所示:
 
 map<K, V>::key_type  在map容器内,用做索引的键的类型
 map<K, V>::mapped_type  在map容器中,键所关联的值的类型
 map<K, V>::value_type  map的值类型:一个pair类型,它的first元素具有
const map<K, V>::key_type类型,而second元素
则为map<K, V>::mapped_type类型
 
注意:map的元素类型为pair类型,且键成员不可修改。其它类型别名与顺序容器一样。
 
map对象的定义
 
 map<K, V> m;  创建一个名为m的空map对象,其键和值的类型分别为K和V
 map<K, V> m(m2);  创建m2的副本m,m与m2必须有相同的键类型和值类型
 map<k, V> m(b, e);  创建map类型的对象m,存储迭代器b和e标记的范围内所有元素的副本。元素的类型必须能转换为pair<const k, v>
 
键类型的约束
 
   在使用关联容器时,它的键不但有一个类型,而且还有一个相关的比较函数。默认情况下,标准库使用键类型定义的 < 操作符来实现键的比较。这个比较函数必须满足:当一个键和自身比较时,结果必定是false;当两个键之间都不存在“小于”关系时,则容器将之视为相同的键。也就是说,map内的元素按键值升序排列。
 
operator[]
 
 A::reference operator[](const Key& key);
 []操作符返回键key所关联的值的引用;如果该键key不存在,则向map对象添加一个新的元素,元素的键为key,所关联的值采用值初始化。(要特别留意这个副作用)
 
注:map下标操作符返回的类型(mapped_type&)与对map迭代器进行解引用获得的类型(value_type)不相同。
   例如:
      map <string, int> wordCount;   // empty map
      word_count["Hello"] = 1;
   上面的代码首先创建一个空的map对象,然后执行下列步骤:
   1)在wordCount中查找键为“Hello”的元素,没有找到;
   2)将一个新的键-值对插入到wordCount中,其中,键为“Hello”,值为0
   3)读取新插入的键-值对的值,并将它的值赋为1。
应用实例,下面的程序用来统计一篇英文文章中单词出现的频率:

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<string, int> wordCount;
    string word;
    while (cin >> word)
        ++wordCount[word];
    
    for (map<string, int>::iterator it = wordCount.begin(); it != wordCount.end(); ++it)
        cout<<"Word: "<<(*it).first<<" /tCount: "<<(*it).second<<endl;
    
    return 0;
}

 
map::insert
 
 m.insert(e)    e是一个用在m上的value_type类型的值,如果键(e.first)不在m中,则插入e到m中;如果键已经在m中存在,则保持m不变。
   该函数返回一个pair类型对象,如果发生了插入动作,则返回pair(it, true);否则返回pair(it, false)。其中,it是指向键为e.first那个元素的迭代器。
 m.insert(beg, end)

 beg和end是标记元素范围的迭代器,其中的元素必须为value_type类型的键-值对。对于该范围内的所有元素,如果它的键在m中不存在,则将该键及其关联的值插入到m。返回void类型。

 m.insert(iter, e)  insert(e),并以iter为起点搜索新元素的位置。返回一个迭代器,指向m中键为e.first的元素。
 
注:当需要插入一个map元素时,一是可以用map::value_type来构造一个pair对象,另外,也可以用make_pair来构造这个对象。
 
查找元素
 
 m.count(k)  返回m中k的出现次数(0或1)
 m.find(k)  如果容器中存在键为k的元素,则返回指向该元素的迭代器。
 如果不存在,则返回end()值。
 
删除元素
 
 m.erase(k)  删除m中键为k的元素,返回size_type类型的值,表示删除的元素个数(0或1)
 m.erase(p)  从m中删除迭代器p所指向的元素。p必须指向m中确实存在的元素,而且不能等于e.end()。返回void类型
 m.erase(b, e)  从m中删除[b, e)范围内的元素,返回void类型
 

set类型
   set类型定义于<set>头文件中。set容器支持大部分map容器的操作,如:构造函数;insert操作;count和find操作;erase操作。两个例外情况是:set不支持下标操作符,而且没有定义mapped_type类型。与map一样,set容器存储的键也必须是唯一的,而且不能修改。
 

multimap和multiset类型
   map和set容器中,一个键只能对应一个实例。而multiset和multimap类型则允许一个键对应多个实例。
 
   multimap和multiset所支持的操作分别与map和set的操作相同,只有一个例外:multimap不支持下标运算。为了顺序一个键可以对应多个值这一特性,map和mulitmap,或set和multiset中相同的操作都以不同的方式做出了一定的修改。
 
元素的添加和删除
 
   map和set容器中的insert和erase操作同样适用于multimap和multiset容器,实现元素的添加和删除。
 
   由于键不要求是唯一的,因此每次调用insert总会添加一个元素。
 
   而带有一个键参数的erase将删除拥有该键的所有元素,并返回删除元素的个数;而带有一个或一对迭代器参数的erase版本只删除指定的元素,并返回void类型。
 
查找元素
 
   在map和set容器中,元素是有序存储的(升序),同样multimap和multiset也一样。因此,在multimap和multiset容器中,如果某个键对应多个实例,则这些实例在容器中将相邻存放,即迭代遍历时,可保证依次返回特定键所关联的所有元素。
 
   要查找特定键所有相关联的值,可以有下面三种方法:
   1)配合使用find和count来查找:count函数求出某键出现的次数,而find操作返回指向第一个键的实例的迭代器。
 
   2)使用lower_bound和upper_bound函数:这两个函数常用于multimap和multiset,但也可以用于map和set容器。所有这些操作都需要传递一个键,并返回一个迭代器。
 m.lower_bound(k)  返回一个迭代器,指向键不小于k的第一个元素
 m.upper_bound(k)  返回一个迭代器,指向键大于k的第一个元素
 m.equal_range(k)  返回一个迭代器的pair对象;它的first成员等价于
 m.lower_bound(k),而second成员则等价于
 m.upper_bound(k)
 
注意:形成的有效区间是[lower_bound(k), upper_bound(i)),是个半开半闭区间。
     lower_bound返回的迭代器不一定指向拥有特定键的元素。如果该键不在容器中,则lower_bound返回在保持容器元素顺序的前提下该键应被插入的第一个位置。
     若键不存在,返回的迭代器相同。
   3)使用equal_range,其实质跟法2)相同。
 

   如果文中有错误或遗漏之处,敬请指出,谢谢!


 

参考文献:
[1] C++ Primer(Edition 4)
[2] Thinking in C++(Volume Two, Edition 2)
[3] International Standard:ISO/IEC 14882:1998

抱歉!评论已关闭.