STL

STL

创新互联建站是专业的信州网站建设公司,信州接单;提供成都做网站、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行信州网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。

#include

#include(推荐)

sort()

sort函数用于给一个数组进行排序,在algorithm库里。

使用方法为sort(v.begin(),v.end(),cmp)),这里的v.begin()是开始的指针位置,v.end()是结束的指针位置(这里的表示是左闭右开,也就是说v.end()并不在排序内容里),cmp可要可不要,如果使用的是自定义类型且没有重载运算符就一定需要。

这个数组的类型可以是自定义类型或者STL中的vector,需要注意的是如果采用的是自定义类型则需要重载运算符(也可以如上面说的一样用cmp)。

stack

模拟栈,在里。

stack A;

常用函数

A.push(a);

入栈

A.pop();

出栈

A.top();

返回栈顶元素(但不出栈)

queue

模拟队列,在里。

queue A;

常用函数

A.push(a);

入队

A.pop();

出队

A.front();

返回队首元素(但不出队)

deque

双端队列

priority queue

优先队列,一个类似于堆的数据结构,在里。

默认是大根堆,如果想让他是小根堆的话有两种办法,其中一种是重载小于号。

能以O(logN)复杂度完成插入元素,删除最值,寻找最值。

Priority_queue A;

常用函数

A.push(a);

插入

A.pop();

删除最值(默认为最大值)

A.top();

返回最值(但不删除)

pair

一个包含两个可以不同的数据值的类型。

pair A;

往往Type1,Type2都是标准类型,但如果是自定义类型,需要重定义运算符;

常用函数

赋值:make_pair(t1,t2);

返回对应的值:A.first,A.second;

vector

向量(Vector)是一个封装了动态大小数组的顺序容器。跟任意其它类型容器一样,它能够存放各种类型的对象。可以简单的认为,向量是一个能够存放任意类型的不定长的动态数组,在vector库里。

定义方式:vector A;

容器特性

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

动态数组

支持对序列中的任意元素进行快速直接访问,甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。

能够感知内存分配器的(Allocator-aware)

容器使用一个内存分配器对象来动态地处理它的存储需求。

相当于是个动态数组,每次可以往末端插入一个元素,下标从0开始。

实现方式是每次不够大的时候暴力倍长,可以发现均摊是线性的。

常用操作

A.clear();

清空

A.push_back(a);

尾部添加元素

A.pop_back();

尾部删除元素

A.empty();

检查是否为空,空返回true

v.size()

这个一个unsigned int类型。也就是说对空的vector的size()-1会得到2^32-1。因此写代码的时候应带尽量避免这种写法。(或者强制类型转化成int)

v.resize()

其复杂度是O(max(1, resize()中的参数-原来的size()))的。

如果是大小变大的resize(),且可以指定新扩展的位置的值。若未指定则调用其默认构造函数,例如int之类的会默认是0。

v.clear()和vector().swap(v)的区别。

前者是假装清空了,实际内存没有被回收。

后者是真的回收了,不过需要和v.size()的大小成正比的时间。

后者的意思是使用vector<>()这句话调用无参的构造函数生成一个vector<>类型的对象,然后和v交换,之后其生存期结束被销毁会自动调用其~vector<>()析构函数。注意<>里面要写v一样的类型(例如int)

set

一个存储集合的容器,在set库里。

map相当于是一个下标可以是任何数值的数组,如果访问时没有赋值就会返回零。

内部使用红黑树(一种平衡树)实现。

当set<>中的第一个参数是自定义类型的时候需要重新定义小于号。

复杂度基本上是O(log(当前大小))。

定义方式:set A;

常用函数

A.insert(a);

插入a

A.erase(a);

删除a:

A.find(a);

查找a,如果查找成功,返回对应指针,查找失败返回尾指针

A.begin(),A.end();

返回头指针与尾指针,尾指针不存储具体内容

map

存储一个从key到value的映射。某种意义上就是“广义”数组,在map库里。

map相当于是一个下标可以是任何数值的数组,如果访问时没有赋值就会返回零。

内部使用红黑树(一种平衡树)实现。

当map<,>中的第一个参数是自定义类型的时候需要重新定义小于号。

复杂度基本上是O(log(当前大小))

map A;Type1是key类型,Type2是value类型。

可以通过A[B]=C这种形式赋值,B为Type1,C为Type2。

常用函数

A.clear();

清空

A.empty();

判断是否为空

A.insert(pair (C,D));

插入(不建议这么写)

A.erase(B);

删除,B可以是key值也可以是指针

A.begin(),A.end();

头指针,尾指针

m[x]

哪怕你什么也不干只写一个m[x];也会新建一个点。

因此当你想知道map中是否存在这个映射的时候最好使用m.count(x)。

很多时候可以有效卡常。

multiset和multimap

是可重集合和可重映射。

有两个注意的:第一个是count函数复杂度变成了O(lg(集合大小)+答案)的,也就是如果有很多相同元素,那么count函数代价很大。

第二个是删除x的话,使用s.erase(x)会把所有权值为x的删除。

如果只想删掉一个需要s.erase(s.find(x))。

unordered_set和unordered_map

基于哈希实现的集合和映射。

基本上里面的类型只能是int,long long,double这种非自定义类型。 因为其基于哈希)

在c++11及以后存在,之前没有,乱用可能会CE。

空间常数比较大,时间常数不小,比数组访问慢很多,慎用。

不能顺序遍历,不支持lower_bound。

迭代器

只介绍set/map的迭代器。

bitset

高精度压位二进制。

一个用于处理二进制串的“数组”,在里。

所有时间复杂度是线性的操作,常数都是1/32大概。

下标从0开始。

bitset A;//n为长度;

支持所有位运算: << , >> , & , | , ^ ;

常用函数

A.count();

统计1的个数

A.reset();

清0

A.set();

全赋为1

A.size();

返回位数

lower bound()/upper bound()

lower_bound(v.begin(),v.end(),c)可以在一个有序数组当中找出刚好大于或等于c的数,在algorithm库里,可以使用自定义类型,用法与sort相类似。

upper_bound函数类似,这个函数则是在有序数组中找出刚好大于c的数。

next permutation/prev permutation(全排列算法)

algorithm头文件中包含了next_permutation(v.begin(),v.end())和prev_permutation(v.begin(),v.end())两个全排列函数,分别给出一个序列在全排列中的下一个和上一个序列(按字典序),如果存在这样的序列则返回true,不存在则返回false,但仍会得到一个序列。

对于一个任意元素不相同的序列来说,正序排列是最小的排列方式,相应的逆序排列是最大的排列方式,以整数序列{1,2,3}为例,{1,2,3}是第一个排列,{3,2,1}则是最后一个排列,因此序列{1,2,3}没有上一个序列,{3,2,1}没有下一个序列。

pq.swap(pq2)

并非原创,仅是整理,请见谅


文章题目:STL
网页链接:http://scyanting.com/article/dsoihsj.html