# string



## 输入输出

- `>>`  从输入流读取一个 `string`  , 读入的时候跳过前导空格，读到第一个空格为止
- `<<`  把一个 `string`  写入输出流
- `getline(cin, s)` : 读入整行内容，直到遇到回车或文件尾
- `getline(cin, s , ';')`   : 后面加入字符参数，表示每次读到指定的字符为止



## 大小和容量

- `size()`  和 `length()` 等效，计算长度
- `empty()`  用来检查字符串是否为空 或者  `s==`



## 元素存取

- 下标操作符号 `[]`  对字符串包含的字符进行访问
- `at()`  ： 对字符串包含的字符进行访问，会检查越界错误



## 比较函数

- 字符串有大小之分，按英文字典的序区分大小
  - 支持的比较操作符号 `> , >= , < , <= , == , !=`

## 更改内容

- 赋值直接使用 `=` ， 字符串刚定义的时候是空的，不能直接用 `[]` 赋值

- 增加字符： `+ , append() , push_back()`

  - `s.append(5, 'x')`  : 添加 $5$ 个字母 $x$

- 插入字符串： `insert()` 函数

  - `s.insert(0, str)`  :  $str$ 内容从 $0$ 下标开始
  - `s.insert(1, str)` :  $str$ 内容从 $1$  下标开始

- 删除函数 ： `erase()`  , 替换函数  `replace()`

  - $s.replace(1,2,str)$ : 从索引 $1$ 开始的 $2$ 个替换成后面的字符串 $str$
  - $s.erase(13)$ : 从索引 $13$  开始往后全删除
  - $s.erase(7,5)$  : 从索引 $7$ 开始往后删 $5$ 个

- 提取子串 `substr()`

  - $s.substr()$ :  返回 $s$  的全部内容

  - $s.substr(5)$  : 返回从索引 $5$  开始的所有内容

  - $s.substr(7,6)$ : 返回从 $7$ 开始连续的 $6$ 个字符

    

- 搜索与查找
  - `s.find(s1)`  : 在字符串 $s$   中查找 $s1$ , 返回第一次找到的位置
  - `s.find(s1, x)` : 在字符串 $s1$  中从 $x$ 位置开始查找 $s1$ , 返回第一次找到的位置







# vector

## 常用命令

- `vector<int> a`

  - 定义一个数据元素类型为 $int$  的 $vector$ , 类型可以为任何的基本类型，如 ： `int, double ,char ,结构体, vector`
  - 二维： `vector<vector<int>> a`

- `a.clear()`

  - 初始化，清空数据，但是不会释放内存

- `a.push_back(2)`

  - 向尾部插入 $2$

- `a.size()`

  - 返回 `vector()` 的元素个数

- `vector<int>::iterator it`

  - `it`  是 `vector` 的迭代器，

  - ```c++
    for(auto it = a.begin; it !=a.end() ; it++)
        cout<<*it<<endl;
    ```

- `a[x]`

  - 引用 `vector` 内下标为 `x`  的元素，跟数组一样

- `sort(a.begin() , a.end() , cmp)`

  - 对 `vector` 内的数据元素进行排序

- `a.insert(a.begin()+i , x)`

  - 在第 `i+1` 个元素前面插入 `x`

- `a.erase(a.begin()+2)`

  - 删除第 $3$ 个元素

- `a.rease(a.begin()+1, a.begin()+j)`

  - 删除 $i$ 到 $j-1$ 这个区间的元素







# set

- 数据集合，不允许有相同元素，单次操作复杂度 $O(logn)$ , 常数大



## 常用命令

- `set<int> s`
  - 定义一个元素数据类型为 $int$  的 $set$
  - `set<node> s`
    - 这个时候的 $node$ 类型需要重载运算符或者写比较函数
- `set<int>::iterator it`
  - 迭代器，可以用来遍历 $set$ 中的数据
- `s.clear()`
  - 初始化，清空数据
- `s.empty()`
  - 判断是否为空，为空返回 $true$ , 否则返回 $false$
- `s.size()`
  - 返回元素的个数
- `s.insert(5)`
  - 插入元素 $5$ , 如果之前已经有则不进行插入操作
- `it = s.find(5)`
  - 查找值为 $5$ 的位置，找到返回迭代器，找不到返回 `s.end()`
- `s.count(5)`
  - 查找出现的次数，只会是 $0$ 或者 $1$
- `it = s.lower_bound(x)`
  - 返回第一个值大于等于 $x$  的迭代器，找不到返回 `s.end()`
- `it = s.upper_bound(x)`
  - 返回第一个值大于 $x$  的迭代器，找不到返回 `s.end()`
- `s.erase(5)`
  - 删除值为 $5$  的数据
- `s.erase(it)`
  - 删除迭代器指向位置的数据





# multiset

- 数据集合，允许有相同元素，单词操作复杂度 $O(logn)$ , 常数大



## 常用命令

- 大部分与 `set` 相同

- `s.erase(5)`

  - 删除值为 $5$ 的全部数据

- `equal_range()`

  - ```c++
    ret = s.equal_range(5);
    s.erase(ret.first , ret.second)
    ```

  - `equal_range ` 作用是返回一个 $pair$ , 存储的是两个迭代器，数据起始和结束位置

  - `ret->first`  就是  `s.lower_bound(5)`

  - `ret->second`  就是 `s.upper_bound(5)`

  



# map

- 键$(key)$值$(value)$对 , 不允许有多个 $key$ ,单次操作时间复杂度为 $o(logn)$



## 常用命令

- `map<int,int >mp`
  - 定义一个 `key` 类型为 $int$ , `value` 类型为 $int$  的 $map$
- `map<int,int> :: iterator it`
  - 迭代器，$*it$  得到的是一个 $pair$  对
- `mp.clear()`
  - 初始化，清空数据
- `mp.size()`
  - 返回 `map` 里面元素个数
- `mp.empty()`
  - 判断 `map` 是否为空
- `mp[5] = 4`
  - 插入数据，如果之前有，就会修改值
- `mp.insert(pair<int,int>(5,4))`
  - 插入数据，如果之前存在 `key` 为 $5$ 的数据，插入失败
- `it = mp.find(5)`
  - 查找 `key` 为 $5$ 对应的数据，找到返回对应的迭代器，找不到返回 `mp.end()`

- `mp.count(5)`

  - 统计 `key` 为 $5$  的数据个数，要么返回 $0$  要么返回 $1$

- `it = mp.lower_bound(x)`

  - 返回第一个 `key` 大于等于 $x$ 的迭代器，找不到返回 `mp.end()`

- `it = upper_bound(x)`

  - 返回第一个 `key` 大于 $x$ 的迭代器，找不到返回 `mp.end()`

- `s.erase(5)`

  - 删除 `key` 为 $5$ 的数据

- `s.erase(it)`

  - 删除迭代器指向位置的数据

- 输出

  - ```c++
    cout<<mp[key]<<endl;
    for(auto it = mp.begin() ; it!=mp.end() ; it++)
        cout<<it->first<<" "<<(*it).second<<endl;
    ```



## 扩展

- `multimap` : 支持相同的 `key`
- `unordered_map` :  `key` 唯一，无序，底层是哈希表





# queue

- 队列，元素先进先出，只能从头部取，尾部进入，不能通过下标或迭代器访问队列中的元素



## 常用命令

- `queue<node> q`
  - 定义元素数据类型为 $node$  的 $queue$ , 压入和弹出的元素都是 $node$ 类型
- `q.push(x)`
  - 将 $x$  插入到队尾
- `q.pop()`
  - 删除队首元素
- `x = q.front()`
  - 取出队首元素
- `x = q.back()`
  - 取出队尾元素
- `q.size()`
  - 返回队列元素个数
- `q.empty()`
  - 判断队列是否为空，如果为空返回 `true` , 否则返回 `false`





# stack

- 栈，元素后进先出，只能访问栈顶元素，不能通过下标或迭代器访问栈中的元素



## 常用命令

- `stack<node> stk`
  - 定义元素数据类型为 `node` 的 `stack`
- `stk.push(x)`
  - 将 `x` 压入栈顶
- `stk.top()`
  - 访问栈顶元素
- `stk.pop()`
  - 删除栈顶元素
- `stk.size()`
  - 返回栈中元素个数
- `stk.empty()`
  - 判断栈是否为空，如果为空返回 `true`  否则返回 `false`





# deque

- 双端队列，可以在对头和队尾插入和删除，并且可以通过下标或迭代器访问元素



## 常用命令

- `deque<node> q;`

  - 定义一个元素数据类型为 `node` 的 `deque`

- `q.push_front(x)  q.push_back(x)`

  - 将 $x$  插入到对头或队尾

- `x = q.front()  x = q.back()  x = q[i]`

  - 取队首、队尾或第 $i$ 个元素（下标从  $0$  开始）

- `q.size()`

  - 返回双端队列中元素的个数

- `q.empty()`

  - 判断是否为空，为空返回 `true`  否则返回 `false`

- `q.insert(q.begin()+i , 100)`

  - 在双端队列中第 $i$ 个元素的后面插入 $100$

- `q.erase( q.begin()+i )`

  - 删除队列中第 $i+1$ 个的元素

- `q.clear()`

  - 清空双端队列

- 迭代器遍历

  - ```c++
    for(auto it = q.begin() ; it!=q.end() ; it++)
        cout<<*it<<endl;
    // 反向遍历
    for(auto it = q.rbegin() ; it!=q.rend() ; it++)
        cout<<*it<<endl;
    ```





# priority_queue



- 优先队列，支持插入数据，取出队首元素，队首元素为优先级最高



## 常用命令

- `priority_queue<int> q`
  - 定义一个元素数据类型为 $int$ 的优先队列，元素大的优先级高
- `priority_queue<int , vector<int> , greater<int> > q`
  - 元素小的优先级高
- `q.empty()`
  - 判断队列是否为空，如果为空返回 `true`  否则返回 `false`
- `q = q.top()`
  - 取队首元素
- `q.pop()`
  - 删除队首元素
- `q.push(x)`
  - 插入数据 $x$
- `q.size()`
  - 返回队列的元素个数





# list

- `list` 将元素按顺序存储在链表中，允许快速的插入和删除，不支持随机存取



## 常用命令

- `list<int> lst`

  - 定义一个数据元素类型为 `int` 的 `list`

- `lst.clear()`

  - 初始化，清空数据

- `lst.size()`

  - 返回 `list` 当前元素个数

- `list<int>::iterator it`

  - 迭代器

- `lst.push_back(2)`

  - 向尾部插入 $2$

- `lst.push_front(3)`

  - 向头部插入 $3$

- `lst.insert(it, 10)`

  - 向迭代器位置插入一个 $10$

- `lst.insert(it , 3 , 20)`

  - 向迭代器位置插入 $3$  个 $20$

- `lst.pop_back()`

  - 删除尾部元素

- `lst.pop_front()`

  - 删除头部元素

- `it = lst.erase(it)`

  - 删除迭代器位置所在元素并返回下一个元素位置的地址

- `lst.erase(it1, it2)`

  - 删除 $it1$  到 $it2$  （不包括 $it2$  位置） 的所有元素

- `lst.remove(20)`

  - 删除 $lst$ 里面所有元素值是  $20$ 的数据

- `lst.sort()`

  - 对 `lst` 内的数据元素进行排序

- `lst.sort(cmp)`

  - 也可以使用自定义比较函数排序

- `lst.remove()`

  - 数据翻转

- `lst.unique()`

  - 对排好后的数据进行去重，也可以自定义比较函数

- `merge()`

  - 将两个有序的链表合并成另一个有序的链表

  - ```c++
    a.sort()
    b.sort()
    a.merge(b, cmp)  // 合并后，b 变成空
    ```