C++ - STL (一个标准模版库)
(不定时更新)
STL 里包含了许多我们特别常用的标准数据结构和算法的模版,比如栈(stack),队列(queue),映射(map),优先队列(priority_queue),还有向量(priority_queue)等等。
有了这样一个模板库,像我这种懒人终于不需要手打一些数据结构啦(会是会,但我就是不想打)
再着,因为下个月月底得打ACM的新生赛了,因为各种各样的事咕了好久没有复习C++了,总归得开始点知识储备
所以得充实充实自己的脑袋瓜啦(啊,脑壳好疼)
2020/11/29 突然想起来我有带《算法设计入门经典》,里面也有一大块是讲 STL 的,我决定就按着它的顺序复习(和学习)了
复习时间表
以此时间表来观察鸽子有多鸽
2020/11/28 栈和队列
2020/11/29 排序检索
2020/11/30 不定长数组
2020/12/03 集合
2020/12/20 映射
(你看,咕咕咕了好久)
排序与检索
排序(sort)
sort 函数默认使用数组元素默认的大小进行升序排序,只有在需要按照特殊依据进行排序时才需要传入额外的比较函数。
我习惯上会定义成cmp
原理嘛~~~其实就是快速排序(quicksort)
导入
sort 所在的库文件是
#include <algorithm> |
sort函数的使用
假设一个数组 a 的 [x,y) 部分需要排序,则:
sort(a+x,a+y); //对数组a的 [x,y) 进行升序排序,直接改变这一区间的元素顺序 |
如果要降序,就需要传入比较函数了,方法和下面类似,这里不再打出
当然也可以对结构体等使用,这时就得传入比较函数来确定需要比较的函数,例如
//关键字排序 |
实际上对于任意的对象,有了cmp和重载<号,sort()都是可以进行相关的排序的(比如后面的victor,调用的方式改成了sort(v.begin(),v.end())
)
检索
lower_bound() 和 upper_bound() 所在的库文件也是
lower_bound (应用于有序区间)
这是二分查找(binary search)的一种版本,试图在已排序的[first,last)中寻找元素value:
如果[first,last)具有与value相等的元素(s),便返回一个迭代器,指向其中第一个元素;
如果没有这样的元素存在,便返回“假设这样的元素存在时应该出现的位置”,
也就是说,它返回一个迭代器,指向第一个“不小于value”的元素;
如果value大于 [first,last) 内的任何一个元素,则返回last。
upper_bound (应用于有序区间)
算法upper_bound是二分查找(binary search)法的一个版本。它试图在已排序的[first,last)中寻找value。更明确地说,它会返回“在不破坏顺序的情况下,可插入value的最后一个合适的位置”。
由于STL规范“区间圈定”时的起头和结尾并不对称(是的,[first,last)包含first但不包含last),所以upper_bound与lower_bound的返回值意义大有不同。如果你查找某值,而它的确出现在区间之内,则lower_bound返回的是一个指向该元素的迭代器。然而upper_bound不这么做,因为upper_bound所返回的是在不破坏排序状态的情况下,value可被插入“最后一个”合适位置。
所以,如果value存在,那么它返回的迭代器将指向value的下一位置,而非指向value本身。
lower_bound() 和 upper_bound() 的使用
int pos1=lower_bound(a+x,a+y,value); |
不定长数组:vector
这玩意我是基本没用到过啦,不过紫书后面的大整数类用的就是不定长数组(也可以称之为向量)。恰如它的翻译“不定长数组”,其实就是类似于 a- [] -
定义
#include <vector> //导入不定长数组的模板库 |
建立各种数据类型的不定长数组
vector<int> vectorint; |
balabala……当然他可以是二维/三维的,such as:
vector<int*> a; //二维vector |
方法
vector对象的存放/删除
v.push_back(num); //在数组的最后添加一个数据 |
vector对象的数据读取/查找
num=v[i]; //正常就可以像数组这么用 |
vector对象的大小
v.size(); //返回容器中实际数据的个数 |
vector对象的其他函数
v1.swap(v2); //交换两个vector(好像是这么用的,有待考证) |
内存管理与效率(补充)
1》使用reserve()函数提前设定容量大小,避免多次容量扩充操作导致效率低下。
(1) size()告诉你容器中有多少元素。它没有告诉你容器为它容纳的元素分配了多少内存。
(2) capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。那是容器在那块内存中总共可以容纳多少元素,而不是还可以容纳多少元素。如果你想知道一个vector或string中有多少没有被占用的内存,你必须从capacity()中减去size()。如果size和capacity返回同样的值,容器中就没有剩余空间了,而下一次插入(通过insert或push_back等)会引发上面的重新分配步骤。
(3) resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后,size将会返回n。如果n小于当前大小,容器尾部的元素会被销毁。如果n大于当前大小,新默认构造的元素会添加到容器尾部。如果n大于当前容量,在元素加入之前会发生重新分配。
(4) reserve(Container::size_type n)强制容器把它的容量改为至少n,提供的n不小于当前大小。这一般强迫进行一次重新分配,因为容量需要增加。
例如:
假定你想建立一个容纳1-1000值的vector
vector<int> v; |
在大多数STL实现中,这段代码在循环过程中将会导致2到10次重新分配。(10这个数没什么奇怪的。记住vector在重新分配发生时一般把容量翻倍,而1000约等于210。)
把代码改为使用reserve,我们得到这个:
vector<int> v; |
这在循环中不会发生重新分配。
2》使用“交换技巧”来修整vector过剩空间/内存
有一种方法来把它从曾经最大的容量减少到它现在需要的容量。这样减少容量的方法常常被称为“收缩到合适(shrink to fit)”。该方法只需一条语句:
vector<int>(ivec).swap(ivec); |
表达式vector
集合:set
在计算与人工智能概论课划水
set
就是数学上的集合——每个元素只出现一次,且从小到大排序。
和 sort
一样,自定义类型也可以构造 set
,但同样必须定义 <
运算符
原理上 set
使用了二叉树,同时,对于关联容器来说,不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。插入的时候只需要稍做变换,把节点的指针指向新的节点就可以了。删除的时候类似,稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去,和内存移动没有关系。
另外,在set中查找是使用二分查找
定义
#include <set> |
常见的可以直接使用的类型 set 有
set<int> intset; //定义一个int类型的set容器 |
跟其他的容器看起来也差不多吧
方法
set对象的存放
s.insert(key_value); //将key_value插入到set中 ,返回值是pair<set<int>::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置 |
Ps set中的删除操作是不进行任何的错误检查的,比如定位器的是否合法等等,所以用的时候自己一定要注意。
set对象的数据读取
显然set容器是没办法向数组那样直接用下标查询的,查询只能靠迭代器来实现
s.find(value); //返回给定值value的指针,如果没找到则返回end() |
Ps count()这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了
Ps 注意begin()和end()函数是不检查set是否为空的,使用前最好使用empty()检验一下set是否为空.
set对象的大小
s.empty(); //判断set容器是否为空 |
映射:map
这个东西真的跟 python 的 dict
是差不多的(我觉得就一样!!!)
就是 key 到 value 的一个映射
简单的理解一下,其实就是数组的下标变成了非数字的各种数据类型,比如字符,字符串。
定义
#include <map> |
然后就跟其他的数据结构不太一样了
map <char,int> char2int_map; |
当然也可以
map <char,char> char2char_map; |
方法
map对象添加元素
map<int, string> map1; |
map对象的查找
find()函数返回一个迭代器指向键值为key的元素,如果没找到就返回指向map尾部的迭代器。
map<int, string >::iterator it; |
map对象的删除
map<int ,string >::iterator it; |
map对象的交换
map中的swap不是一个容器中的元素交换,而是两个容器交换
map1.swap(map2); |
其他
map中的元素是自动按key升序排序,所以不能对map用sort函数
以下列出map的其他各种方法 (大同小异)
m.begin(); //返回指向map头部的迭代器 |
Ps:注意用map的时候大部分要标准化,比如大小写统一之类的
栈、队列和优先队列
栈(stack)
栈,用一个很神奇的东西描述一下——腔肠动物(有口无肝门)有点恶心
不过也道出了栈的本质——只有一个出入口(吃什么吐什么)
像一个桶,最底下的东西是最先放进去的,也只有在最后才能拿出来,进去的顺序是12345,出来的顺序就是54321。
我们基本的写法是自己用数组模拟并定义相关的各种函数,但既然有了这样一个模板库,我们就方便很多了(如果你大致知道一点类就知道,其实C++已经把这些数据结构封装成了类,所以我们才可以直接调用)
以下开始正题:
定义
#include <stack> //导入栈的模板库 |
栈里可以存放的数据类型挺多的,例如:
stack <int> stkInt; //一个存放int的stack容器。 |
甚至可以定义个指针类型啥的(反正指针我忘记怎么打了)
方法
stack对象的存放
stack.push(elem); //往栈头添加元素 |
stack对象的拷贝构造与赋值
stack(const stack &stk); / /拷贝构造函数 |
such as
stack<int> stkIntA, stkIntC; |
stack对象的数据读取
stack.top(); //返回最后一个压入栈元素 |
stack对象的大小
stack.empty(); //判断堆栈是否为空 |
经典例题
队列(queue)
这个我就不用什么奇怪的东西来形容了,这个就是有入口有出口,按顺序排队进去排队出来
(干正事吧,芭芭脱丝)
定义
#include<queue> |
同样也有存各种数据类型的队列
queue <int> queueInt; //一个存放int的queue容器。 |
方法
queue对象的存取
queue.push(X); //在队尾压入新元素 ,X为要压入的元素 |
queue对象的数据读取
queue.front(); // 返回队首元素的值,但不删除该元素 |
queue对象的大小
queue.empty(); //判断堆栈是否为空 |
经典例题
广度优先算法(bfs)就是一个使用队列的例子
其他的例题嘛。。。说实在我好像没写过多少,看到再列出来吧
这里又开始咕了
· 优先队列