《C++Primer》关联容器

● 关联容器类型

map                           关联数组,元素通过键来存储和读取

set                             大小可变的集合,支持通过键实现的快速读取

multimap                 支持同一个键多个出现的map类型

multiset                    支持同一个键多个出现的set类型

 

● pair类型

00d0b0f6200b5ee8679f4759c94f1d071. pair包含两个数值,与容器一样,pair也是一种模板类型。但是又与之前介绍的容器不同,在创建pair对象时,必须提供两个类型名,两个对应的类型名的类型不必相同

pair<string,string>anon;

pair<string,int>word_count;

pair<string, vector<int> >line;

当然也可以在定义时为每个成员提供初始化式:

pair<string,string>author(“James”,”Joy”);

pair类型的使用相当的繁琐,如果定义多个相同的pair类型对象,可以使用typedef简化声明:

typedef pair<string,string> Author;

Author proust(“March”,”Proust”);

Author Joy(“James”,”Joy”);

2、pair对象的操作

对于pair类,可以直接访问其数据成员:其成员都是公有的,分别命名为first和second,只需要使用普通的点操作符

string firstBook;if(author.first==”James” && author.second==”Joy”)

firstBook=”Stephen Hero”;

3、生成新的pair对象

除了构造函数,标准库还定义了一个make_pair函数,由传递给它的两个实参生成一个新的pair对象
pair<string, string> next_auth;

string first,last;

while(cin>>first>>last) {   

      next_auth=make_pair(first,last);    //…

}
还可以用下列等价的更复杂的操作:
next_auth=pair<string,string>(first,last);
由于pair的数据成员是公有的,因而可如下直接地读取输入:
pair<string, string> next_auth;

while(cin>>next_auth.first>>next_auth.last) {    //…}

 

● map类型

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>

在使用类型容器时,它的键不但有一个类型,而且还有一个相关的比较函数。默认情况下,标准库使用键类型定义的 < 操作符来实现键的比较。

 

map定义的类型:

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的接口时,需谨记value_type是pair类型,它的值成员可以修改,但键成员不能修改。

 

map迭代器进行解引用将产生pair类型的对象。

map<string, int>::iuterator mapIt = wordCount.begin();

cout<<mapIt->first;

cout<<mapIt->second;

mapIt ++;

 

给map添加元素:

使用下标:

map<string, int> wordCount;

wordCount[“Anna”] = 1;

1.在wordCount中查找键为Anna的元素,没有找到。

2.将一个新的键值对插入到wordCount中。它的键是const string类型的对象,保存Anna。而它的值则采用值初始化,这就意味着在本例中值为0。

3.将这个新的键值对插入到wordCount中。

4.读取新插入的元素,并将它的值赋为1。

使用下标访问map与使用下标访问数组或vector的行为截然不同:用下标访问不存在的元素将导致在map容器中添加一个新的元素,他的键即为该下标值,所关联的值采用值初始化。

 

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的元素。

 

用insert代替下标运算:wordCount.insert(make_pair(“Anna”, 1));

 

判断是否插入成功:

pair<map<string, int>::iterator, bool> ret = wordCount.insert(make_pair(“Anna”,1));

if(!ret.second)    插入不成功!

 

查找并读取map中的元素:

m.count(k)    返回m中k的出现次数(0或1)
m.find(k)    如果容器中存在键为k的元素,则返回指向该元素的迭代器。如果不存在,则返回end()值。

 

从map对象中删除元素:

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类型

 

map对象的迭代遍历:

map<string, int>::const_iterator mapIt = wordCount.begin();

while(mapIt!=wordCount)

{

      cout<<mapIt->first<<mapIt->second<<endl;

      mapIt++;

}

 

● set类型

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

   set中的键也为count,在获取指向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返回在保持容器元素顺序的前提下该键应被插入的第一个位置。

          若键不存在,返回的迭代器相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
typedef multimap<string, string>::iterator authors_it;

authors_it beg = authors.lower_bound(search_item),

                    end =authors.upper_bound(search_item) ;

while(begin!=end)

{

        cout<<beg->second<<endl;

        ++beg;

}

 

使用equal_range函数:

pair<authors_it, authors_it> pos = authors.equal_bound(search_item);

while(pos.first != pos.second)

{

       cout<<pos.first->second<<endl;

       ++pos.first;

}

         

  

 

BY:AloneMonkey

本文链接:http://www.blogfshare.com/cplus-review-five.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>