首页 > 编程语言 > 详细

[知识点]C++中STL容器之map

时间:2019-02-13 00:58:11      阅读:102      评论:0      收藏:0      [点我收藏+]

标签:sort函数   gin   操作   ont   ack   字符   使用方法   bound   队列   

---恢复内容开始---

一、前言

鉴于最近不少次都要用到map我却总是出各种bug,于是决定写一篇总结来巩固一下。

 

二、什么是STL

全称Standard Template Library,中文名标准模板库,目的是标准化组件,属于C++语言的一部分,说白了就是算法的整合包,最常用的例子便是快速排序,在C中你只能老老实实地码出来,而C++中调用<algorithm>中的sort函数即可。

 

三、STL容器

STL分为六个部分,这里重点介绍其中的容器(containers)部分。STL容器本质是一些常用的数据结构的模板,简化操作。容器分为如下几种,并列出几种最常用的:

1、序列式容器(常用:vector/向量)

2、适配器容器(常用:stack/栈,queue/队列,priority_queue/优先队列)

3、关联式容器(常用:set/集合,map/映射)

今天,我们重点介绍map,即映射。

 

四、map的用途

I miss the taste of the sweeter life...哦对不起串了。

从名字就很好理解作用了——映射,令一物与另一物之间建立起一一映射的关系,以便获得将不方便查找的信息。

举个例子,一个很简单的问题,读入n个长度为m的字符串,再询问q次某某字符串是否在其中。初学者选择字符一一比对,O(nmq);这是有人说,聪明人看到字符串早就去Hash了,可以,but,为保证正确性,哈希值同样会很大,开一个数组去存怕是无内存上限。

那好,我们将得到的哈希值编一个号,比如某巨大的数我们将它视作1,另一个巨大的数编成2,再把编号与值一一对应的关系给记录下来,用什么记录?

map:正是在下。

 

五、map的声明与功能

上面提了,map用途在于自动建立编号与值的对应。那么STL提供了哪些函数供我们来捣鼓里面的东西呢?

 

1、构造

map <int, string> a;

简单明了,前者为编号,后者为值,此处值为字符串。

 

2、插入数据

方法一(以pair形式):

a.insert(pair <int, string>(1, "Zhangsan")); 
a.insert(pair <int, string>(2, "Lisi")); 
a.insert(pair <int, string>(3, "Wangwu")); 

方法二(以value_type形式):

a.insert(map <int, string> :: value_type(1, "Zhangsan"));  

方法三(以数组形式):

a[1] = "Zhangsan";

需要注意的是,方法一二无法覆盖数据,而方法三可以,即如果编号为1的map已经被映射到“Zhangsan”,可以通过数组形式直接修改。

 

3、数据遍历

这里引入新概念——迭代器。先声明:

map <int, string>::iterator it; 

使用方法也很简易:

for (it = a.begin(); it != a.end(); it++)  
   cout << it -> first << ‘ ‘ << it -> second << endl;

这个是前向迭代器,同样还有反向迭代器,如下:

map <int, string> :: reverse_iterator rit;

for
(rit = a.rbegin(); rit != a.rend(); rit++) cout << rit -> first << ‘ ‘ << rit -> second << endl;

同样地,还有用数组的方式遍历:

int s = a.size();
for (int i = 1; i <= s; i++) 
    cout << i <<   << a[i] << endl;

其中,size函数是用来获取map中有多少项数据。

注意点:在遍历时我们用了begin()和end(),两者类型均为迭代器。我们发现遍历起始点为begin(),当迭代器不等于end()时继续,这意味着begin()为开头标识,它包括了数据内容,即第一项数据;end()为结尾标识,但它是最后一项数据后面的一个独立的标识,本身并不表示任何数据。

 

4、查找数据

①判断是否出现用count函数

②判断出现在哪里用find函数

map <int, string> :: iterator itx;
itx = map.find(1);
int x = map.count(1);

map <int, string> :: iterator ity;
ity = map.find(4);
int y = map.count(4);

count函数只返回0或1,如上述代码中,x = 1, y = 0;

find函数返回的是一个迭代器,如上述代码中,itx -> first = 1, ity -> second = "Zhangsan";

而如果没有该数据的话,则返回的是it = a.end()(末尾标识)。

 

5、上界下界(待修改)

lower_bound()返回要查找关键字的下界,即值 >= 给定元素的第一个位置,upper_bound()返回上界,即值 > 给定元素的第一个位置。

 1 map <int, int> a;
 2 
 3 int main() {
 4     a[1] = 1, a[2] = 2, a[3] = 3, a[4] = 4;
 5     map <int, int> :: iterator it;
 6     for (int i = 1; i <= 4; i++) {
 7         it = a.lower_bound(i);
 8         printf("%d ", it -> first);
 9     }
10     for (int i = 1; i <= 4; i++) {
11         it = a.upper_bound(i);
12         printf("%d ", it -> first);
13     }
14     return 0;
15 }

输出结果为“1 2 3 4 2 3 4 4”

 

6、删除元素

这里介绍两种删除方法:单删除,区间删除。

 

 

7、排序问题

 

 

 

六、小结

STL普遍有一个前闭后开的特性,这里有两处均能体现:一处是关于begin()和end()的定义,一处是erase()的区间删除方式,以后应该还会接触到更多。

平时STL容器用的不是太多,也就queue, priority_queue, map较为常用。算法倒是经常用(algorithm库),以后有机会再慢慢总结STL的其他部分。

[知识点]C++中STL容器之map

标签:sort函数   gin   操作   ont   ack   字符   使用方法   bound   队列   

原文:https://www.cnblogs.com/jinkun113/p/10367638.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号