首页 > 笔记 > stl库的简单应用

stl库的简单应用

记性不好,贴着怕忘了。。。

有stack、queue、priority_queue、map…(未完待续)

images

随便p了张图


00:00/00:00

 

先普及一下基础知识。。。

容器是储存元素的东西,C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。若需要存储的元素数在编译器间就可以确定,可以使用数组来存储,否则,就需要用到容器类了。
1、vector
连续存储结构,每个元素在内存上是连续的;
支持高效的随机访问和在尾端插入/删除操作,但其他位置的插入/删除操作效率低下;
2、deque
连续存储结构,即其每个元素在内存上也是连续的,类似于vector,不同之处在于,deque提供了两级数组结构,第一级完全类似于vector,代表实际容器;另一级维护容器的首位地址。
这样,deque除了具有vector的所有功能外,还支持高效的首端插入/删除操作。
3、list
非连续存储结构,具有双链表结构,每个元素维护一对前向和后向指针,因此支持前向/后向遍历。
支持高效的随机插入/删除操作,但随机访问效率低下,且由于需要额外维护指针,开销也比较大。
顺序性容器
vector
从后面快速的插入与删除,直接访问任何元素
deque
从前面或后面快速的插入与删除,直接访问任何元素
list
双链表,从任何地方快速插入与删除
关联容器
set
快速查找,不允许重复值
multiset
快速查找,允许重复值
map
一对多映射,基于关键字快速查找,不允许重复值
multimap
一对多映射,基于关键字快速查找,允许重复值

1.stack

头文件:<stack>

stack模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元素类型是必要的,在不指定容器类型时,默认的容器类型为deque。

例子

stack<int> s1;

stack<string> s2;

操作

入栈,如例:s.push(x);

出栈,如例:s.pop();//注意,出栈操作只是删除栈顶元素,并不返回该元素。

访问栈顶,如例:s.top()

判断栈空,如例:s.empty(),当栈空时,返回true。

访问栈中的元素个数,如例:s.size()

2.queue

头文件:<queue>

与stack模板类很相似,queue模板类也需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque类型。

例子

queue<int> q1;

queue<string> q2;

操作

入队,如例:q.push(x); 将x接到队列的末端。

出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。

访问队首元素,如例:q.front(),即最早被压入队列的元素。

访问队尾元素,如例:q.back(),即最后被压入队列的元素。

判断队列空,如例:q.empty(),当队列空时,返回true。

访问队列中的元素个数,如例:q.size()

3.priority_queue

在<queue>头文件中,还定义了另一个非常有用的模板类priority_queue(优先队列)。优先队列与队列的差别在于优先队列不是按照入队的顺序出队,而是按照队列中元素的优先权顺序出队(默认为大者优先,也可以通过指定算子来指定自己的优先顺序)。

priority_queue模板类有三个模板参数,第一个是元素类型,第二个容器类型,第三个是比较算子。其中后两个都可以省略,默认容器为vector,默认算子为less,即小的往前排,大的往后排(出队时序列尾的元素出队)。

操作

入队,如例:q.push(x); 将x接到队列的末端。

出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。

访问队首元素,如例:q.top(),即最早被压入队列的元素。

访问队尾元素,如例:q.back(),即最后被压入队列的元素。

判断队列空,如例:q.empty(),当队列空时,返回true。

访问队列中的元素个数,如例:q.size()

例子

最基本的:priority_queue<int> Q;

优先队列最基本的功能就是出队时不是按照先进先出的规则,而是按照队列中优先级顺序出队。
知识点:1、一般存放实型类型,可比较大小
2、默认情况下底层以Vector实现
3、默认情况下是大顶堆,也就是大者优先级高,后面可以自定义优先级比较规则

次基本的功能:int a[5]={3,4,5,2,1};    priority_queue<int> Q(a,a+5);

可以将一个存放实型类型的数据结构转化为优先队列,这里跟优先队列的构造函数相关。
上面那个默认构造一个空的优先队列,什么都使用默认的。
而这里使用的是
priority_queue(InputIterator first,InputIterator last)
就是给出了一个容器的开口和结尾,然后把这个容器内容拷贝到底层实现(默认vector)中去构造出优先队列。这里也使用了一个默认的比较函数,也是默认大顶堆

第三基本的功能:typedef pair<long,int> Pair;priority_queue< Pair,vector< Pair >,greater< Piar > > Q;

这个里面定义了一个制定存放元素(Node),底层实现以vector实现(第二个参数),优先级为小顶堆(第三个参数)。
前两个参数没什么说的,很好理解,其中第三个参数,默认有三写法:
小顶堆:greater<TYPE>
大顶堆:less<TYPE>

最常用的功能:

1.重载小于号

运算符重载是通过创建运算符函数实现的,运算符函数定义了重载的运算符将要进行的操作。运算符函数的定义与其他函数的定义类似,惟一的区别是运算符函数的函数名是由关键字operator和其后要重载的运算符符号构成的。

通俗的讲,就是当小于号执行时,前后都是这个结构体,就调用这里的内容。。。

重载运算符的格式

<返回类型说明符> operator <运算符符号>(<参数表>)
{
<函数体>
}

重载小于号还有两种方法,一种是在结构体内重载,一种是在外重载。

在结构体外(推荐使用这种,以为这样可以与sort,set通用)

在结构体内

2.用comp代替算子(greater,less),在comp里重载括号

4.map

1、map简介

map是一类关联式容器,它是模板类。关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置类获取。它的特点是增加和删除节点对迭代器的影响很小,除了操作节点,对其他的节点都没有什么影响。对于迭代器来说,不可以修改键值,只能修改其对应的实值。

2、map的功能

1、自动建立Key - value的对应。key 和 value可以是任意你需要的类型,但是需要注意的是对于key的类型,唯一的约束就是必须支持<操作符。

2、根据key值快速查找记录,查找的复杂度基本是Log(N),如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次。

3、快速插入Key – Value 记录。

4、快速删除记录

5、根据Key 修改value记录。

6、遍历所有记录。

3、map的定义

使用map得包含map类所在的头文件:#include <map>

map对象是模板类,需要关键字和存储对象两个模板参数,基本的定义模式如下:

map<int, string> ma;

这样就定义了一个以int为键,值为string的map对象ma。

4、在map中添加元素

使用下标操作符获取元素,然后给元素赋值

map<string, int> word_count; // 定义了一个空的map对象word_count;

word_count[“hello world”] = 1;

程序说明:

1.在word_count中查找键为hello world的元素,没有找到.

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

3.将这个新的键-值对插入到word_count中

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

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

5、查找并获取map中的元素

使用下标获取元素存在一个很危险的副作用:如果该键不在map容器中,那么下标操作会插入一个具有该键的新元素。(重要)

因此引入map对象的查询操作:

map.count(k) : 返回map中键k的出现次数(对于map而言,由于一个key对应一个value,因此返回只有0和1,因此可以用此函数判断k是否在map中)

map.find(k) :  返回map中指向键k的迭代器,如果不存在键k,则返回超出末端迭代器。

所以获取方法就是先查询一下,如果存在再获取值,要不就会创建新的元素

 

6、从map中删除元素

移除某个map中某个条目用erase()

该成员方法的定义如下

iterator erase(iterator it); //通过一个条目对象删除

iterator erase(iterator first, iterator last); //删除一个范围

size_type erase(const Key& key); //通过关键字删除

clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());

7、 map对象的迭代遍历

与其他容器一样,map同样提供begin和end运算,以生成用于遍历整个容器的迭代器。

一个样例程序

转自http://www.cnblogs.com/JCSU/articles/1996876.html(懒得写了)

输出结果:

Insert method: value_type
Insert failed!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“seen” -> total: 2
“swim” -> total: 4
“walk” -> total: 6

Insert method: array
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“seen” -> total: 2
“swim” -> total: 4
“walk” -> total: 7

Find!

Delete word “seen” done!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“swim” -> total: 4
“walk” -> total: 7
Delete word “swim” done!
“find” -> total: 1
“jump” -> total: 3
“look” -> total: 5
“walk” -> total: 7
Delete all word done!

mapWordRecVerb is empty!

“so” -> total: 50
“the” -> total: 100
mapWordRecPrep is empty!

未完待续


1 COMMENT

  1. cyf2016-08-24 下午4:04

    沙发

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×