题目描述

C++ STL总结

样例

字符串哈希的本质：用一个K进制的角度，来把一个字符串，看成是一个数字(: 乱入

1. 先来看看vector的基础用法

定义一个长度为10，每个元素的值为-1的vector数组

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

    for(auto x : a) cout << x << endl;
    return 0;
}

如何定义10个vector

vector<int> a[10];

size()和empty()是所有容器中都有的API，时间复杂度是O(1)的。但是clear()就不是，队列中就没有clear()
vector倍增的思想——C++中，系统为某一程序分配空间的时候，所需的时间与空间大小无关，与申请次数有关。所以使用vector的时候，尽可能地减少申请次数。32->64->128，先开一个32的，不够了倍增，变成64的，然后go on。
假如数组长度为n, 申请空间(开辟空间)次数是O(log n)，额外的copy的次数均摊是O(1)，比如push()操作。
从而可见倍增的好处——申请空间的次数不多，并且额外操作的次数也不多。

vector
- size()
- empty()
- clear()
- front()/back()
- push_back()/pop_back()
- begin()/end() a.begin() = a[0]，a.end() = a[a.size()]end()表示最后一个数的后面一个数
-
- 支持比较运算，按字典序——黑科技
- erase() vector的删除操作的时间复杂度是O(n)的

pair<int, int> 可以存储一个二元组

pair<int, string> p 定义一个pair
p.first取得pair的第一个元素
p.second取得pair的第二个元素

支持比较运算，以first为第一关键字，以second为第二关键字（也是字典序），可以看作是“长度为2的字符串”

pair初始化的一个方式

p = make_pair(10, "yxc");
p = {20, "abc"};

pair的应用场景——如果一个对象有2种不同的属性，我们就可以用pair来存储它。如果还要按照属性排序，就把要排序的属性存储到first里面，另一个存储到second里面。最后对整个pair排个序就可以。

pair也可以存储拥有3个不同属性的对象

pair<int, pair<int, int> > p

pair就可以看作是实现了一个结构体，结构体中有2个元素，还多实现了一个比较函数

vector的3种遍历方式

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

using namespace std;

int main()
{
    vector<int> a;

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

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

    // second
    // for(vector::iterator i = a.begin(); i != a.end(); i ++) cout << *i << ' ';
    for(vector<int>::iterator i = a.begin(); i != a.end(); i ++) cout << *i << ' ';
    cout << endl;

    for(auto i = a.begin(); i != a.end(); i ++) cout << *i << ' ';
    cout << endl;

    // a.begin() = a[0], a.end() = a[a.size()]

    // third
    for(auto x : a) cout << x << ' ';
    cout << endl;

    return 0;
}

vector支持比较2个vector的大小，按照字典序

int main()
{
    // 按字典序来比较2个vector的大小
    vector<int> a(4, 3), b(3, 4);

    if(a < b) puts("Steven and Mika");

    return 0;
}

----------

#### string, 字符串，substr(), c_str()
`size()` 
`empty()` 
`clear()`

##### string常用用法1——可以在字符串后面加上一个新的字符串

string a = “stevenlovemika”;

a += “forever”;
a += “ever”

cout << a << endl;
cout << a.substr(1) << endl; // 默认输出到字符串结尾
cout << a.substr(1, 10) << endl; // 10大于了字符串的长度，输出到字符串结尾的地方就行

##### string常用用法2——使用printf输出一个字符串
`printf("%s\n", a.c_str())` c_str()可以返回一个字符数组的起始地址

----------

#### queue, 队列
`size()`
`empty()`
`push()`  向队尾插入一个元素
`front()` 返回队头元素
`back()`  返回队尾元素
`pop()`   弹出队头元素

#### 注意queue，priority_queue，stack都是没有clear()这个API的
#### 那么如何清空一个队列queue呢？——重新构造一个queue就行
`queue<int> q;`
`q = queue<int> ()` 重新构造一个q

----------

#### priority_queue，优先队列，默认是大根堆
`push()` 插入一个元素
`top()` 返回堆顶元素
`pop()` 弹出堆顶元素

priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > min_heap;

----------

#### stack 栈
`size()`
`empty()`
`push()` 向栈顶插入一个元素
`top()`  返回栈顶元素
`pop()`  弹出栈顶元素

----------

#### deque 双端队列，一个加强版的vector，非常牛的一个DS，就是速度有些慢
`size()`
`empty()`
`clear()`
`front()/back()`
`push_back()/pop_back()`
`push_front()/pop_front()`
`begin()/end()`
`[] 支持随机寻址`

#### set
##### set中主要包含了2个，一个是set，一个是multiset
`set<int> S`
`multiset<int> MS`
二者的区别是：set中不能有重复元素，multiset是可以有重复元素的
set的所有操作的时间复杂度都是`O(logn)`

`set/multiset`
    `insert()` 插入一个数
    `find()`   查找一个数，不存在的话，返回end()迭代器
    `count()`  返回某一个数的个数
    `erase()`
        (1) 输入是一个数x，删除所有x（时间复杂度为`O(k + log n)`, k是x的个数）
        (2) 输入一个迭代器，删除这个迭代器 (主要是针对multiset而言)
    `lower_bound()/upper_bound()`
        `lower_bound(x)` 返回大于等于x的最小的数的迭代器
        `upper_bound(x)` 返回大于x的最小的数的迭代器 （如果不存在，返回`end()`）
    `begin()/end()` 支持 ++ -- 操作，返回前驱和后继。有序序列的前驱指的是前面一个数，后继指的是后面一个数。时间复杂度是`O(log n)`

----------


`map/multimap` 存储的是一个pair<>，map中存储的是2个数之间的一个映射
    `insert()` 插入的数是一个pair
    `erase()`  输入的参数是pair或者迭代器
    `find()`
    `[]` map可以跟数组一样来使用，比如“随机寻址”。但是时间复杂度是`O(logn)`，而数组是`O(1)`
    `lower_bound()/upper_bound()`

// #include [HTML_REMOVED]

map[HTML_REMOVED] a;

a[“steven”] = 1;
cout << a[“steven”] << endl;

stdout —— 1
```

unordered_set, unordered_map, unordered_multiset, unordered_map 哈希表
API和上面的相似，不过增删改查的时度是O(1)的，上面的都是O(logn)的
不支持lower_bound/upper_bound，因为内部是没有序的，unorder嘛
也不支持 迭代器的 ++ --，凡是跟排序有关的操作，都是不支持的

bitset 压位

为什么要压位？——bool型变量，是1个字节的，1024个就是1024B，也就是1KB。一个字节是8位，压入8位的话，就只需要128B了。空间是原先的1/8。

压位bitset就是每一个字节上去存8位。比正常的bool数组要省8位内存，空间是1/8

应用——

假如有一个1000 x 10000的矩阵，存bool型变量，如果正常，就是10的8次方，空间就是100MB.如果用bitset的话，就是12MB。(假如限制是64MB)

用法——

bitset 压位
bitset<10000> s; 长度为10000的bitset
支持各种位运算，比如 ~s, &, |, ^
支持移位操作，将bitset看成是一个整数，>>, <<, ==, !=
支持[]，取出的某一位是0或1
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0(为空)
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 把所有位取反，等价于~
flip(k) 把第k位取反