1. vector 变长数组

倍增的思想

size() - 返回元素个数

empty() - 返回是否为空

size, empty所有容器都有，时间复杂度为O(1)

clear() - 清空

front() - 返回第一个数

back() - 返回最后一个数

push_back() - 向vector插入一个数

pop_back() - 把vector最后一个数删去

begin()迭代器 - vector第一个数, a[0] = a.begin()

end()迭代器 - vector最后一个数的后面一个数, a[size] = a.end()

支持随机寻址

支持比较运算，按字典序

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

using namespace std;

int main()
{
    vector<int> a;
    vector<int> a(10);
    vector<int> a(10, 3);
    vector<int> a[10];

    for(int i = 0; i < 10; i ++ ) a.push_back(i);

    for(int i = 0; i < a.size(); i ++ ) cout << a[i] << ' ';
    cout << endl;

    // 迭代器遍历 
    for(vector<int>::iterator i = a.begin(); i != a.end(); i ++ ) cout << i << endl;
    cout << endl;

    // 范围遍历 - C++11
    for(auto x : a) cout << x << ' ';
    cout << endl;

    // 按字典序比较大小 
    vector<int> a(4, 3), b(3, 4);
    if(a < b) puts("a < b");

    // 去重
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    // 累加求和、连接字符串
    vector<int> a{1,2,3,4,5}
    int sum = accumulate(a.begin(),a.end(),0);

    vector<string> a{"hello","world","!"};
    string str = accumulate(a.begin() , a.end() , string(""))

    // 删除单个元素/指定元素
    auto it = p.begin() + l;
    p.erase(it);

    p.erase(remove(p.begin(), p.end(), w), p.end());

    return 0;
}

2. string 字符串

substr() - 返回某一个子串

c_str() - 返回string对应的字符数组的头指针

size()

empty()

clear()

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

using namespace std;

int main()
{
    string a = "abc";

    a += "def";
    a += 'c';

    cout << a << endl;
    cout << a.substr(1, 2) << endl; // 第一个参数为下标起始位置(从0开始), 第二个下标为输出长度，长度超出则输出到最后一个字符为止 
    cout << a.substr(1); // 直接返回从1开始的所有字符串
    printf("%s\n", a.c_str()); // 返回string a存储的字符数组的起始地址 

    return 0;
}

3. queue 队列

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

front() - 返回队头元素

back() - 返回队尾元素

pop() - 把队头弹出

size()

empty()

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

using namespace std;

int main()
{
    queue<int> q;

    q = queue<int>(); // 清空队列 

    return 0;
}

4. priority_queue 优先队列

push() - 往堆中插入元素

top() - 返回堆顶元素

pop() - 把堆顶元素弹出

默认为大根堆（从大到小）

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

using namespace std;

int main()
{
    priority_queue<int> heap;

    // 定义小根堆（从小到大）方法
    // 1.
    heap.push(-x);

    // 2.
    priority_queue<int, vector<int>, greater<int>> heap;

    return 0;
}

5. stack 栈

push() - 往栈顶添加元素

top() - 返回栈顶元素

pop() - 弹出栈顶元素

size()

empty()

6. deque 双端队列

队头队尾都可插入删除元素，可随机访问，为一个加强版的vector

size()

empty()

clear()

front()

back()

push_back()、pop_back()

push_front()、pop_front()

begin()、end()

[]

缺点：速度较慢

7. set, map, multiset, multimap

基于平衡二叉树（红黑树）实现, 本质上是动态维护有序序列

size()

empty()

clear()

begin()/end() - ++、–返回前驱和后继 O(logn)

set中忽略重复元素, multiset中不忽略

set/multiset:

insert() - 插入一个数

find() - 查找一个数，不存在则返回end迭代器

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

erase()

1、输入是一个数x，删除所有x O(k + logn), k为x个数

2、输入一个迭代器，删除这个迭代器

lower_bound() - 返回大于等于x的最小的数的迭代器

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

multiset<int> p;
int x;

p.erase(x); // 删除多个数
p.erase(p.find(x)); // 删除单个数

auto mid = next(mid, x);
auto mid = prev(p.begin(), x);
// 表示将指针前移/后移x位后的位置

-- mid;
++ mid;
// 将指针前/后移1位

map/multimap

insert() 插入的数是一个pair

erase() 输入的参数是pair或者迭代器

find()

[] - 时间复杂度O(logn)

lower_bound()、upper_bound()

坏处是增删改查的时间复杂度为O(logn)

8. unordered_set, unordered_map, unordered_multiset, unordered_multimap

基于hash表实现

和上面类似，好处是增删改查的时间复杂度为O(1)

不支持 lower_bound()、 upper_bound()、迭代器的++,–操作

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

using namespace std;

int main()
{
    unordered_multimap<string, int> a;

    return 0;
}

9. bitset, 压位

#include<bitset>

int a;
string b = "0101";

bitset<4> a;
bitset<4> b;
bitset<4> c(19);
bitset<4> d("0101"); // 位数不够高位省去，位数过多高位补0

bitset<10000> S - <>中定义个数

~, &, |, ^

>>, <<

==, !=

[]

count() - 返回有多少个1

any() - 判断是否至少有一个1

none() - 判断是否全为0

set() - 把所有位置变成1

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

reset() - 把所有位变成0

flip() - 等价于~

flip(k) - 把第k位取反

10. pair<,> - 存储一个二元组

first - 第一个元素

second - 第二个元素

支持比较运算，以first为第一关键字，second为第二关键字(字典序)

可看成两个变量的结构体，且实现了比较函数

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

using namespace std;

int main()
{
    pair<int, string> p;
    p = make_pair(10, "abc"); // 构造一个pair 
    p = {20, "abc"}; // C++11初始化pair
    pair<int, pair<int, int>>; // pair存储三个属性 

    return 0;
}