参考链接：

[C++ STL] vector使用详解 - fengMisaka - 博客园 (cnblogs.com)

[C++ STL] deque使用详解 - fengMisaka - 博客园 (cnblogs.com)

[C++ STL] list使用详解 - fengMisaka - 博客园 (cnblogs.com)

[C++ STL] set使用详解 - fengMisaka - 博客园 (cnblogs.com)

[C++ STL] map使用详解 - fengMisaka - 博客园 (cnblogs.com)

[C++ STL] 常用算法总结 - fengMisaka - 博客园 (cnblogs.com)

Acwing算法基础课

std::string

cplusplus.com/reference/string/string/substr/

string substr (size_t pos = 0, size_t len = npos) const;

cplusplus.com/reference/string/string/find/

size_t find (const string& str, size_t pos = 0) const noexcept;

cplusplus.com/reference/string/string/erase/

string& erase (size_t pos = 0, size_t len = npos);

cplusplus.com/reference/string/to_string/

string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

cplusplus.com/reference/string/stoi/

// stoi example
#include <iostream>   // std::cout
#include <string>     // std::string, std::stoi

int main () {
  std::string str_dec = "2001, A Space Odyssey";
  std::string str_hex = "40c3";
  std::string str_bin = "-10010110001";
  std::string str_auto = "0x7f";

  std::string::size_type sz;   // alias of size_t

  int i_dec = std::stoi (str_dec,&sz);
  int i_hex = std::stoi (str_hex,nullptr,16);
  int i_bin = std::stoi (str_bin,nullptr,2);
  int i_auto = std::stoi (str_auto,nullptr,0);

  std::cout << str_dec << ": " << i_dec << " and [" << str_dec.substr(sz) << "]\n";
  std::cout << str_hex << ": " << i_hex << '\n';
  std::cout << str_bin << ": " << i_bin << '\n';
  std::cout << str_auto << ": " << i_auto << '\n';

  return 0;
}

cplusplus.com/reference/string/stod/

// stod example
#include <iostream>   // std::cout
#include <string>     // std::string, std::stod

int main () {
  std::string orbits ("365.24 29.53");
  std::string::size_type sz;     // alias of size_t

  double earth = std::stod (orbits,&sz);
  double moon = std::stod (orbits.substr(sz));
  std::cout << "The moon completes " << (earth/moon) << " orbits per Earth year.\n";
  return 0;
}

vector

变长数组，倍增的思想

• size() 返回元素个数（所有容器都有，时间复杂度为O(1)）
• empty() 返回是否为空（所有容器都有，时间复杂度为O(1)）
• clear() 清空
• front()/back() 返回第一个数a[0]/最后一个数a[a.size()-1]
• push_back()/pop_back() 插入/弹出最后一个数
• begin()/end() 迭代器第一个数a[0]/最后一个数的后面一个数a[a.size()]
• [] 支持随机访问（下标）
• 支持比较运算，按字典序比较

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    // vector 初始化
    vector<int> a;
    vector<int> a(10); // 定义一个长度为10的vector
    vector<int> a(10, 3); // 定义一个长度为10的vector，每个元素都初始化为3

    // vector 添加元素
    for (int i = 0; i < 10; i++) {
        a.push_back(i);
    }
    // vector遍历
    // 下标访问vector
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << ' ';
    }

    // 迭代器访问vector
    for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
        cout << *i << ' ';
    }

    // 范围遍历
    for (auto x: a) {
        cout << x << ' ';
    }
    
    // vector 支持比较运算，按字典序比较
    vector<int> a(4, 3), b(3, 4);
    if (a < b) {
        puts("a < b");
    }
    
    return 0;
}

pair

存储一个二元组，前后两个变量的类型可以是任意的。

某个东西有两种不同的属性，有一个属性需要排序，可以将需要排序的属性放到first中，将不需排序的关键字放到second中。

嵌套的pair可以用于存储一个三元组。

• first 第一个元素
• second 第二个元素
• 支持比较运算，按字典序，以first为第一关键字，以second为第二关键字

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int main() {
    // pair 初始化
    pair<int, int> p1;
    
    pair<int, string> p2;
    p2 = make_pair(10, "yxc");
    p2 = {20, "abc"};
    
    // 嵌套的pair可以用于存储三元组
    pair<int, pair<int, int>> p3;

    return 0;
}

string

字符串，substr()，c_str()

• size()

• length()

• empty()

• clear()

• 支持加法运算

• substr() 第一个参数是位置，第二个参数是长度

  如果长度大于string则一直输出到最后一个字母

  第二个参数可省略，省略时也是从pos开始一直输出到最后一个字母

• c_str() 返回字符数组的起始地址

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int main() {
    // 初始化
    string a = "yxc";

    // 支持加法运算
    a += "def";
    a += "c";

    cout << a.substr(1, 2) << endl; // 输入字符串从1开始的两个字符
    cout << a.substr(1, 10) << endl; // 输入字符串从1开始到最后一个字符
    cout << a.substr(1) << endl; // 输入字符串从1开始到最后一个字符

    printf("%s\n", a.c_str());

    return 0;
}

queue

队列

• size()

• empty()

• push() 向队尾插入一个元素

• front() 返回队头元素

• back() 返回队尾元素

• pop() 弹出队头元素

• 没有clear() 函数，如果想清空队列，可以重新构造一个队列

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

int main() {
    // 初始化
    queue<int> q;
    // 没有clear()函数，如果想清空，可以重新构造一个队列
    q = queue<int>();

    return 0;
}

priority_queue

优先队列，默认是大根堆

• size()

• empty()

• 没有clear()函数

• push() 插入一个元素

• top() 返回堆顶元素

• pop() 返回堆顶元素

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

int main() {
    // 初始化，默认为大根堆
    priority_queue<int> heap;
    int x;
    cin >> x;

    // 定义小根堆的两种方式
    // 方式1：直接插入一个负数
    heap.push(-x);

    // 方式2：多加两个参数
    priority_queue<int, vector<int>, greater<int>> heap;

    return 0;
}

stack

栈

• size()

• empty()

• 没有clear()函数

• push() 向栈顶插入一个元素

• top() 返回栈顶元素

• pop() 弹出栈顶元素

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>

using namespace std;

int main() {
    // 初始化
    stack<int> s;

    // 没有clear()函数
    while (!s.empty()) {
        s.pop();
    }
    

    return 0;
}

deque

双端队列，两端都能插入删除，支持随机访问，缺点是速度慢

• size()
• empty()
• clear()
• front()/back()
• push_back()/pop_back()
• push_front()/pop_front()
• begin()/end()
• [] 支持随机访问

set, map, multiset, multimap

set, map, multiset, multimap, 基于平衡二叉树（红黑树）, 动态维护有序序列

• size()
• empty()
• clear()
• begin()/end() ++, -- 返回前驱和后继，时间复杂度O(logn)

set 无重复元素，插入重复元素会被忽略

multiset 有重复元素

• insert() 插入一个数

• find() 查找一个数

• count() 返回某一个数的个数

• erase()

  对multiset，如果输入一个数x，则删除所有x，时间复杂度O(k + logn)，k是x的个数

  如果输入一个迭代器，则删除这个迭代器

• lower_bound() 返回大于等于x的最小的数的迭代器，如果不存在返回end()

• upper_bound() 返回大于x的最小的数的迭代器

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

int main() {
    set<int> s;
    multiset<int> ms;
    
    return 0;
}

map

multimap

• insert() 插入的数是一个pair
• erase() 输入的参数是pair或者迭代器
• find()
• [] 时间复杂度O(logn)
• lower_bound()/upper_bound() 返回大于x的最小的数的迭代器

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>

using namespace std;

int main() {
    map<string, int> a;
    
    a["yxc"] = 1;
    cout << a["yxc"] << endl;
    
    return 0;
}

unordered_set, unordered_map, unordered_multiset, unordered_multimap

哈希表，和上面类似，增删改查的时间复杂度是O(1)

不支持lower_bound()/upper_bound()，迭代器的++，--

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> a;
    
    a["yxc"] = 1;
    cout << a["yxc"] << endl;

    unordered_multimap<string, int> b;

    return 0;
}

bitset

压位，省8倍空间

• bitset<10000>s;

• ~, &, |, ^

• >>, <<

• ==, !=

• []

• count() 返回有多少个1

• any() 返回是否至少有一个1

• none() 判断是否全为0

• set() 把所有位置成1

• set(k, v) 将第k位变成v

• reset() 把所有位变成0

• flip() 等价于~

• flip(k) 把第k位取反