前言：

在算法竞赛中，如果要用到例如 队列，栈 等数据结构类型时，不用自己构造，在C++中已将封装好了多种容器，只需引用头文件就可以进行使用，极大的提高了编写效率。

1. vector：

#include <iostream>
#include <vector>     //对应头文件
using namespace std;
//语法 ：  vector<类型> arr(长度,[初值])
void print_str(char a[]){
    cout << a[0] << endl;
}

int main(){
    vector<int> arr; //创建整型数组 arr，如果没有定义长度，则默认长度为0；
    vector<int> arr1(10, 0);//创建长度为10的整形数组，初值为0
    //类比，我们可以定义不同的类型数组
    vector<double> arr3(10, 2);
    vector<char> arr4(10, '*');
    //二维数组
    vector<vector<int>> arr_2(5, vector<int>(5, 0));
    //构造初始5行，初始5列的二维数组，初值为0；


    //尾插：
    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);//此时arr的长度已经变成了3
    
    //尾删

    arr.pop_back();
    arr.pop_back();//此时arr的长度为1；

    //获取数组长度 
    cout << arr.size() << endl; // size = 1；

    //清空数组
    arr.clear();

    //判断数组是否为空， 返回的是布尔值
    cout << arr.empty() << endl; //空值返回1

    
    //改变数组的长度
    arr.resize(5, 10);//将arr数组长度改为5，且对新加入的数值初始化为10；

    //迭代器遍历
    for(auto x : arr){
        cout << x << endl;
    }
}

2. priority_queue<>优先队列：

using namespace std;

//对于有大量元素且需要排序时可以使用， 边插入边排序
int main(){
    //优先队列，默认为大顶堆
    priority_queue<int> pque;
    pque.push(1);
    pque.push(3);
    pque.push(4);
    pque.push(2);
    cout << pque.top() << endl;//堆区的最大值

    pque.pop();
    pque.pop();//移除队列的第一项 
    cout << pque.top() << endl;

    //小顶堆
    priority_queue<int, vector<int>, greater<int>> pque_small;
    pque_small.push(6);
    pque_small.push(4);
    pque_small.push(5);
    cout << pque_small.top() << endl;//小顶堆，为4
}
/*
注意：
    1.仅堆顶可读：只可访问堆顶，其他元素都不可读到
    错误用法：
    cout << pque[1] << endl;  

    2.所有元素都是不可写：堆中的所有元素都是不可修改的
    错误用法：
    pque[1] = 2;
    pque.top() = 1;   
    
*/

3.set集合

#include <iostream>
#include <set>
using namespace std;
int main(){
    //set 有确定性 互异性 从小到大排序 
    //
    set<int> st;                //储存int类型（从大到小）
    set<int, greater<int>> st2; //储存int的集合（从小到大）
    st.insert(2);
    st.insert(4);
    st.insert(2);
    st.insert(3);

    //查找find 返回的是迭代器，如果找不到返回尾迭代器
    if(st.find(2) != st.end()){
        cout << "Yes" << endl;
    }
    //查找count 返回该元素在集合set中的个数，如果找不到则返回0
    //对于普通函数，该函数仅有0和1两个返回值，但对于multiset(无互异性)的来说，count返回该元素在集合中的个数
    if(st.count(2) == 1){
        cout << "Yes" << endl;
    }


    //可使用迭代器进行遍历
    for(auto &ele : st){
        cout << ele << endl;
    }
    //删除元素
    st.erase(2);
    cout << " " << endl;
    //大小：
    cout << st.size() << endl;

    //清空 clear
    st.clear();

    //判空
    cout << st.empty() << endl;

    //使用迭代器进行遍历
    for(auto &ele : st){
        cout << ele << endl;
    }

    for(set<int>::iterator it = st.begin(); it != st.end(); ++it){
        cout << *it << endl;
    }
    /*适用情形：
        元素去重
        维护顺序
        元素是否出现过，当所存储的数据较多时（-10^18 -- 10^18）,vis数组无法完成，就可以使用set数组完成
    */

    
    //注意：
    //set的迭代器取到的元素是只读的，不可修改，要想修改，需要先erase，再insert
    //set元素虽然可以遍历，但是仅可使用迭代器进行遍历，不存在下标这一概念，无法使用下标进行访问
    

}

4.pair二元组

#include <utility>

#include <iostream>

using namespace std;

//二元组pair ：就是用来存储二元组的

/*

pair<第一个值的类型， 第二个值的类型> = {第一个值， 第二个值}；

*/

int main(){

pair<int, int> p1 = {1, 2};

pair<char, int> p2 = {'a', 2};

cout << p1.first << " " << p1.second << endl; //输出 1 2

cout << p2.first << " " << p2.second << endl; //输出 a 2

//pair可以判断是否相等

if(p1 == p2){

cout << "Yes" << endl;

}else{

cout << "No" << endl;

}

//二元组可以嵌套,但是套的太多就抽搐了🤔

pair<int, pair<int, int>> p3;

}

5. map图

#include <iostream>
#include <map>
using namespace std;

//提供对数时间的有序键值对结构，底层原理是红黑树
//映射
/*
    结构：
    map<键类型,值类型,比较器(默认可以不写)>
    键类型：要储存键的数据类型
    值类型：要储存值的数据类型
    比较器：键比较大小使用的比较器， 默认为less<类型>，可自定义
*/
int main(){
    map<int, int> mp1;                  // int -> int 的映射（从小到大）
    map<int, int, greater<int>> mp2;    // int -> int 的映射（从大到小）

    map<string, int> st1;               // string -> int 的映射
    map<int, vector<int>> ve;           // int -> vector 的映射

    //增
    mp1[2] = 2;                         // 2 -> 1
    mp1[1] = 1;                         // 1 -> 2

    //find()查找 返回找到元素的迭代器， 注意是对 键 的查找
    if(mp1.find(2) != mp1.end()){
        cout << "yes" << endl;          // yes
    }

    //count() 统计map中键值出现的个数
    cout << mp1.count(1) << endl;       // 输出 1
    cout << mp1.count(3) << endl;       // 输出 0
    /*注意：对于map来说，即使没有给赋map值，但是该键已经存在，如下行代码：
        mp1[3];       
        虽然没有给她赋值，但是map中还是存在该键 3 ，且初始值为 0 
        即：
        cout << mp1.count << endl;      // 输出 1 


        if(mp1.find(3) != mp1.end()){
            cout << "yes" << endl;      // yes
        }
    */
    
    //大小
    cout << mp1.size() << endl;         //输出 2
    
    //清除
    mp1.clear();

    //判空
    cout << mp1.empty() << endl;        // 输出 1   


    mp1[2] = 2;                        
    mp1[1] = 1;
    mp1[999] = 7894;

    //迭代器, 迭代到map的值为结构题， frist对应键， second对应值
    for(map<int, int>::iterator it = mp1.begin(); it != mp1.end(); ++it){
        cout << it->first << " " << it->second << endl;
    }
    /*  输出：
        1 2
        1 1
        999 7894
    */

    for(auto &pr : mp1){
        cout << pr.first << " " << pr.second << endl;
    }
    //输出结果同上；

    /*
        适用情况：
        -例如统计每个字符串或字符出现的次数（map<string, int>）
    */
    


}

6.string字符串

这是我认为最有用库，没学这个之前面对字符串时我都在干什么？

#include <iostream>
#include <cstring> //等效于下面写法
//#include <string.h>

using namespace std;
//c++的结构体中允许存在函数
struct MM{
    int age;
    void print(){
        cout << age << endl;
    }
};

int main(){
    //如何访问函数
    MM mm;
    mm.age = 11;
    //mm.print();
//1， string的创建方式
    string str1  = "str1"; //构造函数
    string str2;
    str2 = "str2";// 与上方不一样，调用拷贝构造函数

    string str3("str3");

    //了解
    string str4(4, 'x'); //用4个x初始化字符串；
    //下标从0开始 
    string str5("ILoveYou", 1, 4); //用字符串的从下标1开始的4位初始化str5；
    cout << str5 << endl;

//2， C++string与c语言char* 的区别
    
    //c++中没有'/0';
    str2 = "HelloWorld";
    char array[] = "HelloWorld";
    cout << str2.size() << endl;
    cout << str2.length() << endl;
    //不可以使用printf()
    //printf("%s", str2);
    
    //c++ string为我们提供了一个访问字符串的接口：.data(), .str()
    //使用这两个函数才能实现对字符串的访问
    printf("%s\t%s\n", str2.data(), str2.c_str());

//3 .string的基本操作
    //赋值删改查
    //3.1 c++的赋值方式 通过函数赋值 assign
    string s1("IMissYou");
    string s2;        //string s2(s1);
    s2.assign(s1);    //s2=s1;
    cout << s2 << endl;

    s2.assign(s1, 1, 4);//用字符串的从下标1开始的4位初始化s2;
    cout << s2 <<endl;

    s2.assign(4, 'K');
    cout << s2 <<endl;
    //3.2 比较 c++ string和c语言string比较规则是一样的
    //”123“ ”13“， 后者大
    string frist = "123";
    string second = "12";
    cout << (frist > second) << endl;
    cout << (frist != second) << endl;
    cout << (frist < second) << endl;
    
    cout << frist.compare(second) << endl;
    //3.3字符串的链接操作
    frist = frist + second;
    cout << frist << endl;
    //使用函数进行链接
    frist.append(second, 0 ,1);
    cout << frist << endl;

    //3.4查找函数
    /*
        返回的是string::npos        等于-1;
        find ：从左往右找字符串或字符出现的位置；
        rfind：从后往前找
    */
    string str6 = "abcdefghijklmn";
    if(str6.find("efg") != string::npos){
        cout << str6.find("efg") << endl;
    }//返回查找到的下标

    //3.5 替换 replace
    string str7 ("Helloworld");
    str7.replace(1, 4, 4, 'o');
    cout << str7 << endl;   
    //3.6 删除字符串 erase;
    string str8 = "Helloworld";
    str8.erase(1, 4);
    str8.erase(1); //删掉下标1以后的所有内容
    
    cout << str8 << endl;

}

7.迭代器

这东西还是不用为好

// 为什么要选择迭代器？
/*
    很多数据结构并不是线性的（例如红黑树）， 对于非线形的数据结构，下表是没有意义的，无法使用下标来遍历整个数据结构
    迭代器的作用就是定义某个数据结构的遍历方式， 通过迭代器的增减，代表遍历到的位置，通过迭代器就能成功遍历非线性结构了
    例如set的实现是红黑树， 我们没有办法用下标来访问元素的，但是通过迭代器就可以实现
*/
    set<int> b;
    for(set<int>::iterator it = b.begin(); it != b.end(); ++it){
        cout << *it << endl;
    }

//迭代器用法
/*
    对于vector容器,它的迭代器功能比较完整，以它为例
        .begin()        头迭代器
        .end()          尾迭代器 
        .rbegin()       反向头迭代器
        .rend()         反向尾迭代器
        迭代器 + 整型     将迭代器向后移动
        迭代器 - 整型     将迭代器向前移动
        迭代器++         将迭代器向后移动1位
        迭代器--         将迭代器向前移动1位
        迭代器-迭代器     两个迭代器的距离
        pre(it)         返回it的前一个迭代器
        next(it)        返回it的后一个迭代器
    对于其他容器，由于其结构特性，上面的功能不一定都有（例如set的迭代器是不能相减求距离的）
*/

//常见问题
/*
    .end()和.rend指向的位置是无意义的值
    对于一个长度为10的数组，for(int i = 0; i < 10; i++) 其中10就是不可以访问到的
    对于一个长度为10的容器，for(auto it = a.begin(); it != a.end(); ++it), .end是不可以访问的
*/

//ps： 如果你跟我一样是菜鸡，那还是老老实实用for循环遍历吧（> _ <）

8.队列

#include <iostream>
#include <queue>
using namespace std;
/*
queue的常见操作，这里的队列就和数据结构一样的队列

empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
front(): 返回队首元素的引用。
back(): 返回队尾元素的引用。
push(): 在队尾添加一个元素。
pop(): 移除队首元素。
*/
int main(){
    queue<int> q;
    q.push(1);                      //入队
    q.push(2);                      //入队
    q.push(3);                      //入队 

    cout << q.front() << endl;      //返回对首元素 输出 1
    cout << q.back() << endl;       //返回对尾元素 输出 2

    q.pop();                        // 出队

    cout << q.empty() << endl;      // 判空 空返回1 ， 非空返回2
    cout << q.size() << endl;       // 输出队列大小

}

9.stack 栈

#include <iostream>
#include <stack>
using namespace std;
/*
push(): 在栈顶添加一个元素。
pop(): 移除栈顶元素。
top(): 返回栈顶元素的引用，但不移除它。
empty(): 检查栈是否为空。
size(): 返回栈中元素的数量

*/
int main(){
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);                      // 入栈

    cout << s.top() << endl;        // 返回栈顶元素 3

    cout << s.empty() << endl;      // 判空。空输出1， 非空返回0

    cout << s.size() << endl;       // 输出 栈的大小

    s.pop();                        // 出栈
}

总结：

建议先学点数据结构的相关知识再进行该容器的学习。