关联容器

作用

关联容器支持通过键来高效的查找和读取元素

  • map 的元素以键-值对的形式组织:键用作元素在map中的索引 , 而值表示所存储和读取的元素
  • set 仅包含一个键 , 并有效的支持关于某个键是否存在的查询
    1
    2
    3
    4
    5
    6
    ================关联容器类型=================
    map 关联数组:元素通过键来进行存储或读取
    set 大小可变的集合,支持通过键实现的快速读取
    multimap 支持同一个键多次出现的map类型
    multiset 支持同一个键多次出现的set类型
    ================================================

pair类型

包含在utility 头文件中

pair类型提供的操作

1
2
3
4
5
6
7
8
pair<T1 , T2> p1;
pair<T1 , T2> p1(v1 , v2);
make_pair(v1 , v2) ; 以v1 和 V2 值创建一个新的pair对象
p1 < p2 两个pair对象之间的小于运算 , 其定义遵循字典序 , 如果p1.first < p2.first 或者 !(p2.first <p1.first) && p2.second < p1.second
则返回true
p1 == p2
p.first
p.second

生成pair对象的三种方法

method1

1
2
3
4
5
6
pair<string , string> next;
string first , last;
while(cin>>first>>last)
{
next = make_pair(first , last);
}

methid2

1
next = pair<string , string>(first , last);

method3

1
2
3
4
pair<string , string> next;
while(cin>>next.first>>next.second)
{//
}

关联容器不提供 front , push_front , pop_front , back , push_back , pop_back 操作

map类型

1
#include <map>

map的构造函数

1
2
3
4
map<k , v> m; 创建一个名为m的空map对象
map<k , v> m(m2)
map<k , v> m(b , e) 创建map类型的对象m 。 存储迭代器b和e标记的范围内的所有副本。
注:元素的类型必须能转换为pair<const k , v>

map定义的类型

value_type 是存储元素的键以及值的pair类型 , 而键为const类型

1
2
3
4
map<k , v>::key_type 在map容器中做索引的键的类型
map<k , v>::mapped_type 在map容器中为键所关联的类型
map<k , v>::value_type 一个pair类型 , 他的first元素具有const map<k ,v>::key_type类型
而second元素为map<k , v>::mapped_type类型

要点: #### map迭代器进行解引用将产生pair类型的对象 #### 程序实例:

1
2
3
4
map<string , int>::iterator map_it = word_count.begin();
cout<<map_it->first;
cout<<" "<<map_it->second;
++map_it->second;

map容器额外定义的类型别名(typedef)

可以用作用域操作符来获取类型成员

1
map<string , int >::key_type

map添加元素

使用下标访问map对象:

1
2
map<string , int> word_count;
word_count["Anna"] = 1;//如果没有这一元素的话就地添加啦 , 当然系统会自动为该键所对应的值初始化为0

经典例题:

1
2
3
4
5
6
7
//统计单词出现的次数
map<string , int> word_count;
string word;
while(cin>>word)
{
word_count[word]++;
}

map::insert

1
2
3
4
5
6
7
8
========================操作=========================
m.insert(e) e是一个用在m上的value_type类型的值
如果e.first不在m中,则插入一个值为e.second的新元素
如果存在的话, 保持m不变
该函数返回一个pair类型的对象,pair<map<k , v>::iterator , bool>
m.insert(beg , end) beg和end是迭代器哦,标记范围
m.insert(iter , e) 返回值为指向m中具有给定键的值
=============================================================

实例:

1
2
3
4
5
6
--word_count.insert(map<string , int>::value_type("Anna" , 1));
--word_count.insert(mak_pair("Anna" , 1));
--typedef map<string , int >::value_type valType;
word_count.insert(valType("Anna" , 1));
--------以上是三种初始化方法,我建议第二中-----

检测insert的返回值

map对象中的一个给定键只对应一个元素。如果试图插入一个已经存在的值, 则insert不做任何操作 但是,带有一个键-值形参的insert函数将返回一个值, 包含一个迭代器和一个bool值的pair对象 。其中迭代器指向map容器中具有相应键的元素,而bool值则表示是否插入了该元素

1
2
3
4
5
6
7
8
9
10
11
12
//重写统计单词数目
map<string , int> word_count;
string word;
while(cin>>word)
{
pair<map<string , int>::iterator , bool> ret=
word_count.insert(make_pair(word , 1));
if(!ret.second)
{
++ret.first->second;
}
}

查找并读取map中的元素

1
2
3
4
=====================不修改map对象的查询操作=============
m.count(k) 返回k出现的次数
m.find(k) 如果容器中存在按k索引的元素,则返回指向该元素的迭代器。如果不存在,则返回m.end()
=================================================================================================

建议:

如果只是单纯的查找,就用count
如果查找完后要使用这个元素,那就用find

map中删除元素

1
2
3
4
5
=====================从map对象中删除元素================================
m.erase(k) 删除m 中值为k的元素,返回值为 size_type 类型,表示删除元素的个数
m.erase(p) 从m中删除迭代器p所指向的元素 , p必须指向m中存在的元素
m.erase(b , e)
=============================================================================

map对象的迭代遍历

1
2
3
4
5
6
map<string , int>::iterator map_it = word_count.begin();
while(map_it != word_count.end())
{
cout<<map_it->first<<map_it->second;
++map_it;
}//这个单词统计可以按字典序输出单词

set类型

set容器只是简单的键的机=集合

注意:

  • set容器中,value_type 不是 pair类型 , 而是与key_type相同的类型
  • set容器中储存的键必须唯一的,且不可以修改
  • set中的元素必须互不相同,一旦相同,自动呢屏蔽

在set中添加元素

method1

1
2
set<string> set1;
set1.insert("haha");//此版本的返回值为 pair<set<string>::iterator , bool>

method2

1
2
set<int> set2;
set2.insert(ivec.begin() , ivec.end());

获取set中的元素

1
2
s.find();
s.count();

multimapmultiset类型

二者均不支持下标运算

元素的添加或删除

实例:

1
2
3
multimap<string , string> authors;
authors.insert(make_pair(string("bbs") , string("fish")));
authors.insert(make_pair(string("bbs") , string ("fishc")));

带有一个参数的erase将删除拥有该键的所有元素,并返回删除元素的个数 size_type

在这两种容器中查找元素

面向迭代器的解决方案:

1
2
3
4
5
6
======================返回迭代器的关联容器操作============================
m.lower_bound(k) 返回一个迭代器 , 指向键不小于k的第一个元素
m.upper_bound(k) 返回一个迭代器, 指向键大于k的第一个元素
a。equal_range(k) 返回一个迭代器的pair对象
它的first成员等价于m.lower_bound(k) , 而second成员则等价于m.upper_bound(k)
===================================================================================================

如果该键存在,则返回两个不同的迭代器
如果不存在,则返回同一个迭代器,指向依据元素的排列顺序该键应该插入的位置

则有:

1
2
3
4
5
6
7
8
9
10
11
for(multimap<string , string>::iterator it = authors.lower_bound();
it != authors.upper_bound() ; ++it)
{}
------------------
//使用equal_range()
multimap<string , string>::iterator range = authors.equal_range();
while(range.first != range.second)
{
++range.firet;
}

热评文章