目录

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

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

---

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

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