stl的正确食用方式（不定时更新）

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>
using namespace std;

sort函数的使用

假设一个数组 a 的 [x,y) 部分需要排序，则：

sort(a+x,a+y); //对数组a的 [x,y) 进行升序排序，直接改变这一区间的元素顺序

如果要降序，就需要传入比较函数了，方法和下面类似，这里不再打出

当然也可以对结构体等使用，这时就得传入比较函数来确定需要比较的函数，例如

//关键字排序
struct scores{
    int Chinese,Math;
}class1;

bool cmp(class1 a,class1 b){ //关键字排序规则，降序
    if(a.Chinese!=b.Chinese)return a.Chinese>b.Chinese;
    return a.Math>=b.Math;
}

int main(){
    sort(a+x,a+y,cmp);
}

实际上对于任意的对象，有了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);
int pos1=upper_bound(a+x,a+y,value);

---

不定长数组：vector

这玩意我是基本没用到过啦，不过紫书后面的大整数类用的就是不定长数组（也可以称之为向量）。恰如它的翻译“不定长数组”，其实就是类似于 a- [] -

定义

#include <vector>  //导入不定长数组的模板库
using namespace std;

建立各种数据类型的不定长数组

vector<int> vectorint;
vector<double> vectordouble;
vector<char> vectorchar;

balabala……当然他可以是二维/三维的，such as:

vector<int*> a;  //二维vector
vector<int**> a;  //三维vector

方法

vector对象的存放/删除

v.push_back(num);  //在数组的最后添加一个数据
v.pop_back();  //删除最后一个数据
v.erase(pos);  //删除pos位置的数据
v.erase(begin,end);  //删除 [begin,end) 区间的数据
v.insert(pos,elem);  //在pos位置插入数据elem

vector对象的数据读取/查找

num=v[i];  //正常就可以像数组这么用
v.front();  //传回第一个数据
v.back();  //传回最后一个数据
v.at(idx);  //传回索引idx所指的数据，如果idx越界，抛出out_of_range

v.begin();  //返回数组头的指针/迭代器
v.end();  //返回数组尾+1的指针/迭代器
v.rbegin();  //传回一个逆向队列的第一个数据
v.rend();  //传回一个逆向队列的最后一个数据的下一个位置

vector对象的大小

v.size();  //返回容器中实际数据的个数
v.max_size();  //得到vector最大可以是多大
v.resize(num);  //改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
v.capacity();  //返回当前vector分配的大小
v.reserve(num);  //改变当前vector所分配空间的大小
v.clear();  //移除容器中所有数据
v.empty();  //判断容器是否为空

vector对象的其他函数

v1.swap(v2);  //交换两个vector（好像是这么用的，有待考证）
c.assign(beg,end);  //将[beg; end)区间中的数据赋值给c
c.assign(n,elem);  //将n个elem的拷贝赋值给c
get_allocator;  //使用构造函数返回一个拷贝
v.~ vector <Elem>();  //销毁所有数据，释放内存    

内存管理与效率（补充）

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。没有使用reserve，你可以像这样来做：

vector<int> v;
for (int i = 1; i <= 1000; ++i) v.push_back(i);

在大多数STL实现中，这段代码在循环过程中将会导致2到10次重新分配。（10这个数没什么奇怪的。记住vector在重新分配发生时一般把容量翻倍，而1000约等于210。）

把代码改为使用reserve，我们得到这个：

vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);

这在循环中不会发生重新分配。

2》使用“交换技巧”来修整vector过剩空间/内存
有一种方法来把它从曾经最大的容量减少到它现在需要的容量。这样减少容量的方法常常被称为“收缩到合适（shrink to fit）”。该方法只需一条语句：

vector<int>(ivec).swap(ivec);

表达式vector(ivec)建立一个临时vector，它是ivec的一份拷贝：vector的拷贝构造函数做了这个工作。但是，vector的拷贝构造函数只分配拷贝的元素需要的内存，所以这个临时vector没有多余的容量。然后我们让临时vector和ivec交换数据，这时我们完成了，ivec只有临时变量的修整过的容量，而这个临时变量则持有了曾经在ivec中的没用到的过剩容量。在这里（这个语句结尾），临时vector被销毁，因此释放了以前ivec使用的内存，收缩到合适。

---

集合：set

在计算与人工智能概论课划水

set 就是数学上的集合——每个元素只出现一次，且从小到大排序。

和 sort 一样，自定义类型也可以构造 set ，但同样必须定义 < 运算符

原理上 set 使用了二叉树，同时，对于关联容器来说，不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

另外，在set中查找是使用二分查找

定义

#include <set>
using namespace std;

常见的可以直接使用的类型 set 有

set<int> intset;  //定义一个int类型的set容器
set<float> floatset;  //定义一个float类型的set容器
set<char> charset;  //定义一个char类型的set容器
set<string> strset;  //定义一个string类型的set容器

跟其他的容器看起来也差不多吧

方法

set对象的存放

s.insert(key_value);  //将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置
s.inset(first,second);  //将定位器first到second之间的元素插入到set中，返回值是void

s.erase(iterator);  //删除定位器iterator指向的值
s.erase(first,second);  //删除定位器first和second之间的值
s.erase(key_value);  //删除键值key_value的值

Ps set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。

set对象的数据读取

显然set容器是没办法向数组那样直接用下标查询的，查询只能靠迭代器来实现

s.find(value);  //返回给定值value的指针，如果没找到则返回end()
s.lower_bound(key_value);  //返回第一个大于等于key_value的定位器
s.upper_bound(key_value);  //返回最后一个大于等于key_value的定位器
s.count();  //用来查找set中某个某个键值出现的次数
s.begin();  //返回set容器的第一个迭代器
s.end();  //返回set容器的最后一个迭代器
s.rbegin();  //传回一个逆向set的第一个数据
s.rend();  //传回一个逆向set的最后一个数据的下一个位置

Ps count()这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了

Ps 注意begin()和end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.

set对象的大小

s.empty();  //判断set容器是否为空
s.size();  //返回当前set容器中的元素个数
s.max_size();  //返回set容器可能包含的元素最大个数
s.clean();  //删除set容器中所有的元素

---

映射：map

这个东西真的跟 python 的 dict 是差不多的（我觉得就一样！！！）

就是 key 到 value 的一个映射

简单的理解一下，其实就是数组的下标变成了非数字的各种数据类型，比如字符，字符串。

定义

#include <map>
using namespace std: 

然后就跟其他的数据结构不太一样了

map <char,int> char2int_map;
map <string,int> str2int_map;

当然也可以

map <char,char> char2char_map;
map <char,string> char2str_map;
map <string,char> str2char_map;

方法

map对象添加元素

map<int, string> map1;  
map1.insert(pair<int, string>(1,"one"));
map1.insert(map<int, string>::value_ type(2,"two"));
map1[3]="three";  //map中最简单最常用的插入添加！

map对象的查找

find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。

map<int, string >::iterator it;
it=map1.find(3);
if(it==maplive.end())
    cout<<"No find"<<endl;
else 
    cout<<"Find"<<endl;

map对象的删除

map<int ,string >::iterator it;
it=maplive.find(3);
if(it==maplive.end())
    cout<<"no find"<<endl;
else  maplive.erase(it);  //delete 112;

map对象的交换

map中的swap不是一个容器中的元素交换，而是两个容器交换

map1.swap(map2);

其他

map中的元素是自动按key升序排序,所以不能对map用sort函数

以下列出map的其他各种方法 （大同小异）

m.begin();  //返回指向map头部的迭代器
m.clear();  //删除所有元素
m.count();  //返回指定元素出现的次数
m.empty();  //如果map为空则返回true
m.end();    //返回指向map末尾的迭代器
m.equal_range();  //返回特殊条目的迭代器对
m.erase();  //删除一个元素
m.find();   //查找一个元素
m.get_allocator();//返回map的配置器
m.insert(); //插入元素
m.key_comp();  //返回比较元素key的函数
m.lower_bound();  //返回键值>=给定元素的第一个位置
m.max_size();  //返回可以容纳的最大元素个数
m.rbegin(); //返回一个指向map尾部的逆向迭代器
m.rend();   //返回一个指向map头部的逆向迭代器
m.size();   //返回map中元素的个数
m.swap();   //交换两个map
m.upper_bound();  //返回键值>给定元素的第一个位置
m.value_comp();   //返回比较元素value的函数

Ps：注意用map的时候大部分要标准化，比如大小写统一之类的

---

栈、队列和优先队列

栈(stack)

栈，用一个很神奇的东西描述一下——腔肠动物（有口无肝门）有点恶心

不过也道出了栈的本质——只有一个出入口（吃什么吐什么）

像一个桶，最底下的东西是最先放进去的，也只有在最后才能拿出来，进去的顺序是12345，出来的顺序就是54321。

我们基本的写法是自己用数组模拟并定义相关的各种函数，但既然有了这样一个模板库，我们就方便很多了（如果你大致知道一点类就知道，其实C++已经把这些数据结构封装成了类,所以我们才可以直接调用）

以下开始正题：

定义

#include <stack>  //导入栈的模板库
using namespace std;

栈里可以存放的数据类型挺多的，例如：

stack <int> stkInt;  //一个存放int的stack容器。
stack <float> stkFloat;  //一个存放float的stack容器。
stack <string> stkString;  //一个存放string的stack容器。 

甚至可以定义个指针类型啥的（反正指针我忘记怎么打了）

方法

stack对象的存放

stack.push(elem);  //往栈头添加元素
stack.pop();  //从栈头移除第一个元素 

stack对象的拷贝构造与赋值

stack(const stack &stk); / /拷贝构造函数
stack& operator=(const stack &stk);  //重载等号操作符

such as

stack<int> stkIntA, stkIntC;
stack<int> stkIntB(stkIntA);
stack<int> stkIntD;
stkIntD = stkIntC;

stack对象的数据读取

stack.top();  //返回最后一个压入栈元素

stack对象的大小

stack.empty();  //判断堆栈是否为空
stack.size();  //返回堆栈的大小

经典例题

表达式括号匹配

栈

双栈排序

队列(queue)

这个我就不用什么奇怪的东西来形容了，这个就是有入口有出口，按顺序排队进去排队出来

（干正事吧，芭芭脱丝）

定义

#include<queue>
using namespace std;

同样也有存各种数据类型的队列

queue <int> queueInt;  //一个存放int的queue容器。
queue <float> queueFloat;  //一个存放float的queue容器。
queue <string> queueString;  //一个存放string的queue容器。 

方法

queue对象的存取

queue.push(X);  //在队尾压入新元素 ，X为要压入的元素
queue.pop();  //删除队列首元素但不返回其值

queue对象的数据读取

queue.front();  // 返回队首元素的值，但不删除该元素
queue.back();  //返回队列尾元素的值，但不删除该元素  

queue对象的大小

queue.empty();  //判断堆栈是否为空
queue.size();  //返回堆栈的大小

经典例题

广度优先算法(bfs)就是一个使用队列的例子

其他的例题嘛。。。说实在我好像没写过多少，看到再列出来吧

---

这里又开始咕了

· 优先队列

---