目录

pair

string

queue

priority_queue：优先队列

stack 

deque--双端队列

set -- multiset

map -- multimap  

无序关联容器

bitset：压位

---

上篇vector指路👇

stl : vector

pair

我们之前用到过一次，当时对他有了基本的了解，这里再回顾一下就好。内容不是很多。

pair用来存储两个相关联的数据，且这两个数据的数据类型可以不同。常说pair用来存储键值对。其使用时需要引头文件  #include <utility> 

pair的实现是一个结构体，第一个元素由 .first 进行索引，第二个元素使用  .second 索引。(注意这里使用时后面不用加括号()哦 )

pair的创建

    pair<int,string> p;p={2,"ax"};pair<int,int>q={1,2};pair<int,int>r(1,1);auto s=make_pair('c',"sdv");//make_pair函数的主要优点是它可以自动推断出pair的类型，不需要显式地指定pair的类型pair<int,pair<int,string>> t;//嵌套的 pair 可以用来组织和表示具有层次结构的数据，其中不同层次的信息被封装在不同的元素中

注意写的格式，哪里是() 哪里是{ } 区分清楚 

p.first;//获取第一个元素
p.second;//获取第二个元素

当两个pair要进行比较的时候，一般是按照字典序，以第一个元素优先比较，当两个pair的第一个元素相同时，才会比较第二个元素。

string

string也算比较常用了。其头文件是 #include<string>  

    string c;c.size();c.empty();c.length();//和size一样c+='c';c+="vf";//如果我们是以string创建字符串(也就相当于一个字符数组)，用+=运算符来读入下一个字符，实际上是字符/字符串的连接//这可以类比为逐个字符读取并将其连接到字符串的过程，因为每次读取一个字符，都将其追加到字符串的末尾//c++中的substr()函数，第一个参数是起始位置，第二个参数是子串长度。 但大部分其它语言中第二个参数表示截至位置c.substr(1,2);//返回第1-2个字符c.substr(1);//直接返回从第一个字符开始的整个子串c.substr(1,5);//如果我们第二个参数的位置写出的数字要大于整个字符串的长度，那么会输出从第一个参数所对数字的位置开始，到字符串的末尾cout<<c.substr(1,5)<<endl;cout<<c.substr(1,2)<<endl;//用cout可以直接输出cout<<c<<endl;//如果要使用printf进行输出，就要用c_str()函数printf("%s",c.c_str());

常用的就都写在代码里了。

当然它也包含 size()计算字符串大小(不包含末尾结束符 '\0' )   /  clear()清空字符串  / empty() 判断字符串是否为空

但是c语言中的sizeof会包含   '\0'  ，因为C风格的字符串是一个字符数组，数组的最后一个元素是结束标志\0。sizeof运算符返回的是整个数组（包括\0）所占用的字节数。

注意区分：strcmp 也是我们比较字符串常用的函数。这里要分清楚，在c++中使用该函数，要引头文件  #include<cstring>

queue

队列遵循先进先出

    queue<int> q;//创建了一个元素都为int类型的队列q.size();q.empty();q.back();//返回队列末尾元素q.pop();//弹出队头元素q.push(1);//向队尾插入元素    q.front();//返回队头元素//queue没有自带的clear() 清空队列元素的函数//如果想要清空q=queue<int>();

注意它没有自带的clear()函数 

其头文件是#include<queue> 

priority_queue：优先队列

其是靠堆来实现的。需要回顾的可以看一下

数据结构：堆 

要注意的是，优先队列的堆：默认是大根堆。

没有自带的clear()函数 

优先队列的创建 

    priority_queue<int> q;//创建了一个元素是int类型的优先队列，即大根堆//如果想要创建小根堆，可以在插入元素的时候，插入原数的负数形式q.push(-x);//也可以priority_queue<int,vector<int>,greater<int>> q;//注意引vector的头文件//这样所创建的就是一个小根堆

注意其头文件也是 #include<queue> 

常用函数

    q.empty();q.size();q.pop();//弹出堆顶q.push(1);//插入一个元素，会自动插入到符合堆的性质的位置q.top();//返回堆顶元素

stack 

栈遵循先进后出

    stack<int> s;s.pop();//弹出栈顶元素s.push(1);//向栈顶插入一个元素s.top();//返回栈顶元素s.size();s.empty();

头文件是  #include<stack>

没有内置clear() 函数 

deque--双端队列

其实是一个加强版的vector。很多函数都包含，但是由于速度实在太慢，不太常用。

    deque<int> d;d.size();d.empty();d.clear();//清空队列d.back();//返回最后一个元素d.front();//返回队首元素d.pop_back();//弹出最后一个元素d.push_back(1);//在队尾插入一个元素d.pop_front();//弹出队首元素d.push_front(2);//在队头插入元素d[1];//支持数组形式的随机寻址//支持迭代器d.begin();d.end();

头文件 #include<deque> 

这里强调一下随即寻址d[1]   ，vector也是支持随机寻址的。

set -- multiset

使用时头文件 #include<set> 

    set<int> s;//如果我们向set中插入一个重复的元素，那程序会忽略掉这个操作multiset<int> q;//multiset中可以有重复元素s.size();s.empty();s.clear();s.insert(1);//插入元素s.insert(2);s.erase(1);//这里我们写的是删除值为1的元素，那么会删除所有值为1的元素//如果我们传入的参数写的是该元素的迭代器，那么会删除之后并回下一个元素的迭代器//注意如果要删除一个范围内的元素的erase函数，那么应该使用参数是两个迭代器，而不是数字s.erase(s.begin(),s.begin()++);//删除该区间内的元素，并返回下一个元素的迭代器s.upper_bound(1);//返回第一个>1的元素的迭代器s.lower_bound(1);//返回第一个>=1的元素的迭代器s.count(1);//返回某个元素的个数s.find(1);//查找一个数，如果这个数存在，就返回其迭代器，若不存在返回set.end()s.begin();s.end();

关于迭代器：我们上篇里说过：

这里补充迭代器可以进行的操作，这里 set 和 multiset 以及下面要说的 map 和 multimap 的迭代器都是可以进行 ++ -- 操作的

map -- multimap  

这和上面的set组合基本函数都差不多。这里不在重复写了。

头文件是 #include<map>

map和multimap是两种常用的关联式容器，它们都是基于键值对的数据结构，这两种容器的主要区别在于，map不允许两个元素有相同的键值，而multimap允许键值重复  

 set组合和map组合的区别

也就是他们的区别是一个是存储两个值(要使用pair)，一个只存储一个值。

map的创建以及键值的映射关系

    //类似于数组，但是map这样的寻址时间复杂度是O(logn) 而数组是O(1)//map的第一个参数是“键” 第二个参数是“值”map<int,int> a;a[1]=2;map<string,int> b;b["cd"]=1;map<int ,string> c;c[2]="fe";

函数

    a.size();a.empty();a.clear();a.find(10);//查找以该元素为“键”的键值对的迭代器a.insert(pair<int,int>(10,10));//函数参数是pair类型的键值对a.count(10);//参数是以该值为“键”的元素个数a.erase(a.begin());//参数是一个迭代器//同样也有两个迭代器参数删除一整个区间元素的写法，返回的是下一个元素的迭代器a.upper_bound(10);a.lower_bound(10);//对于这两个函数参数是“键”，返回迭代器

无序关联容器

unordered_set

unordered_map

unordered_multiset

unordered_multimap 

这四个名字很直接，就是表示是无序的。

无序容器的底层实现是哈希表，因此它们的插入、删除和查找操作的平均时间复杂度都是O(1)。然而，由于它们是无序的，所以不支持lower_bound()、upper_bound()函数，也不支持迭代器的++和--操作。

bitset：压位

bitset 是一个位集合的模板类，用于表示固定大小的位序列。bitset 以非常高效的方式存储位信息，每个位都只占用一个比特（0或1），并且支持各种位运算操作。“压位”通常指的是使用 bitset 进行位操作

我们上面所提到的容器，<>尖括号内部写的都是元素类型，但是bitset<>尖括号里写的是元素个数。

    bitset<1000> b;b.any();//判断是否至少有一个1b.none();//判断是否全为0b.count();//返回1的个数b.set();//把所有位置置1b.set(1);//将第一个位置置1b.set(k,v);//将第k位置为vb.reset();//把所有位置置0b.reset(1);//将第一个位置置0b.flip();//将所有位取反~b.flip(k);//把第k位取反

这个暂时写的原理作用不是很清楚，下午看有需要补充的会来改一下。 

---

好了，第二部分数据结构结束了。

有问题欢迎指出！一起加油！！！