我的STL笔记

c++的standard template library主要有序列容器。。。

边刷题边整理，顺便做一些跟Java、Python里数据结构的对比

c++的标准模板库的核心包含三个组件：

vector

实现了线性表，
初始化：

vector<int> nums; 
vector<int> nums{1,2,3}; // initial items
vector<int> nums(100); // size 100 of full zeros
vector<int> nums(100, 1); // size 100 of full ones
vector<bool> bs(100, true);
vector<string> ss{"a", "bc"};
vector<int> nums(another_nums.begin(), another_nums.end()); // copy
vector<int> nums2{1,2,3}
bool eq = (nums == nums2);  // 可以之间用 == 判断是否相等哦 !

vec.begin(), vec.end() 返回起始或末尾元素的迭代器
vec.front(), vec.back() 返回起始或末尾元素的引用
注意vec.end()返回的是末尾元素的下一个位置，因此访问末尾元素要*(vec.end()-1)

在末尾插入：nums.push_back(1);
显示容器大小：vec.size(), 容器预分配大小：vec.capacity()
注：C++ STL 之 vector 的 capacity 和 size 属性区别
size 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个元素。
capacity 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。

给容器预留空间：vec.reserve()， 改变大小：vec.resize()
注：在 STL 中，拥有 capacity 属性的容器只有 vector 和 string。

访问vector的元素可以用[]访问，不进行越界检查 (运行时越界不报错)，推荐使用vec.at()会进行越界检查，越界时报错

// vector 容器的遍历方式
for (int i = 0; i < vec.size(); i++) vec[i];

for (auto k : vec) k;

for (auto it = vec.begin(); it != vec.end(); it++) *it
// type it : vector<T>::iterator
// auto 令编译器自动推断类型

Attention !!!
学过Java的童鞋可能有这样的疑问了

在Java中，如果要用一个邻接表去定义一个图，那么通常是用 ArrayList[] edges = new ArrayList<Integer>[10] 然后再对数组的每个位置 new 一个 ArrayList类

在c++中，你可以直接这么写：

vector<unordered_set<int>> edges(10);
// 内部的 unordered_set<int> 已经初始化好了
edges[1].insert(2);
for (auto v : edges[1]) {
    cout << v;
}
// 同时 vector<unordered_set<int>> copy(edges)  是深复制
// 此时对 copy 中的 元素进行修改不会影响 edges !!!

对Python而言，线性表最直接的实现就是内置的List了，python标准库array还提供了限制类型的列表。

在Java语言中，线性表的实现是一个泛型接口类List，有两个类ArrayList和LinkedList实现了这个接口，它们分别是顺序表和双链表。

deque

双端队列 deque<int> dq;

插入：
dq.push_back(1);　 dq.push_front(1);

Java的Deque是一个接口类，其实现有ArrayDeque, LinkedList, 常用方法是:
offerFirst, offerLast, peekFirst, peekLast, pollFirst, pollLast, LinkedList在空指针情况下这些方法均不报错。

Python的deque是封装在标准库collections下

class collections.deque([iterable[, maxlen]])
# 初始化, 表示创建一个内含数字1，2，3 最大长度为5的dequq
dq = deque([1,2,3], 5)

常用方法是append, appendleft, pop, popleft, extend, extendleft, reverse
从3.5版本开始，python的deque实现了非常多的dunder methods，支持许多像列表一样的语法糖。

stack

栈的实现，默认的容器是deque

stack<int> st;
st.push(0);  // 入栈
st.top();  // 访问栈顶元素
st.pop();  // 删除栈顶元素，注意 并不会返回栈顶元素
st.empty();  // bool值，是否为空
st.size();  // 返回栈的元素个数

在python中，直接使用列表list即可，不需要栈

Java中有一个Stack<T>的泛型类，支持方法：st.size() -> int, st.isEmpty() -> boolean, st.push(T t), st.peek() -> T, st.pop() -> T

注：Java中的Stack的pop方***返回栈顶元素，而C++的pop不会

queue

队列，容器类型默认也是deque

queue<double> q;
q.push(3.14);  // 入队
q.pop();  // 出队，不返回队顶元素
q.front();  // 访问队首元素
q.back();  // 访问队尾元素
q.empty();
q.size();

python的队列其实是封装在标准库queue中，是一个线程安全的队列（之前的deque也是线程安全的，都用到了threading.Lock()），本意是用来线程间的通信的，所以实现的方法很少，比如不能传入comparator进行比较（除非你写一个wrapper class去修饰原来的那个类，重写比较的那几个dunder methods，比如__eq__, __le__，或者是用标准库functools下的cmp_to_key函数，你看过源码就知道了）

队列和优先队列都是继承的一个队列的基类

from queue import Queue, PriorityQueue
q = Queue(10)    # max size
pq = PriorityQueue(2)
q.get()    # 不会报错但是会线程阻塞
pq.put(2)
pq.qsize()    # 1
pq.empty()    # False
'''主要的方法就是get, put, qsize和empty'''

在Java语言中，Queue<T>只是一个接口类，从而实际使用Queue必须用到LinkedList这个实现了Queue接口的类。Queue定义的接口方法有：poll, peek, offer, size, isEmpty等

set / unordered_set

set是基于平衡二叉树的树结构,unordered_set是哈希表.

unordered_set<int> hs{1};
hs.insert(2); // insert an item
hs.erase(2);  // delete an item, 不存在也不报错
hs.find(2) != hs.end(); // an item exists or not

// 遍历
for (auto k : s) {
    cout << k << endl;
}
for (unordered_set<T>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it << endl;    // 注意这里返回的是地址
}
for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << endl;    // 可以使用 auto 令编译器自动推断变量的类型
}

python与之对应的集合操作是add, discard(remove), remove只能删除在集合里的元素不然会报错, 成员测试符in.

Java对应的方法是add, remove, contains,用法跟c++类似,值得注意的是如果add, remove方法成功改变了集合, 会返回boolean值true.

map / unordered_map

c++中的 map 跟 Java 中的非常类似，单纯的map是树结构的 binary search tree，类似于 Java 的 TreeMap，需要键类型是可以排序的；unordered_map是哈希表，类似于 Java 的 HashMap，需要键类型实现了 hashCode 和 equalsTo方法。

初始化：

// 在 < > 内填入 key - value 的类型
unordered_map<int, string> hash;  // 键类型要是可哈希的，且必须要能用 == 来比较
map<string, int> tree;  // 键类型需要是可以比较的
// 在初始化时赋值
unordered_map<int, string> up{{1, "No1"}, {2, "No2"}, {3, "No3"}};

常用方法

cout << up[1] << endl;  // 通过键访问值
cout << up[4] << endl;  // 键不存在，返回空串，不报错
// 判断键是否存在，注意此处返回 true （因为上一行，这里像python defaultdict）
bool isin = (up.find(4) != up.end()) 
cout << up.size() << endl;  // 返回键 key 的个数
up.erase(100);    // 删去某个 key，键可以不存在

如果要遍历map的值：

for (auto it = m.begin(); it != m.end(); it++)
    it->second;  // do sth.
}

我们知道map容器是根据键值进行排序的

lower_bound(k)返回一个迭代器，指向键不小于k的第一个元素

upper_bound(k)返回一个迭代器，指向键大于k的第一个元素

string

字符串类
可以使用 "=" 进行赋值，使用 "==" 进行等值比较，使用 "+" 做串联。

// 读入字符串
string stuff;
cin >> stuff;
getline(cin, stuff);

string str = "123";
str += "4"; // +=, append(), push_back()都可以用来添加字符添加字符
bool equal = (str == "1234");

str.size(); str.length(); 
// 字符串长度, 注意java中String类只能用.length()访问长度
bool empty = str.empty();
str.substr(str.length()-6, 6);  // 截取后6位子串
str.substr(1, 5);  // 从第 1 位开始，截选长度为 5 的子串。（第一个参数不能越界，第二个参数可以越界） 
// str.substr(str.size(), 10) 是空串, str.substr(str.size() + 1, 10) 会报错
int t = stoi(str);  // 将字符串转换为整数

tips:

1. s[0] 是一个 char类型, 即 for (char c : s)
2. 可以对字符串里的char进行排序：sort(s.begin(), s.end());
3. 删除字符串的一个子串：s.erase(s.begin(), s.begin() + 3);

在Java中，String类不能直接用括号访问，必须用s.charAt(0)
Java的String类可以用new String(new char[]{'a', 'b'})去创建，也可以new String(new byte[]{97, 110});.
如果要对字符串进行频繁的操作，可以使用StringBuilder类

StringBuilder sb = new StringBuilder();
sb.append('a');
sb.reverse().toString();    // 字符串逆序

algorithm

max_element / min_element

返回一个序列的最大元素的指针

vector<int> nums{1,3,5};
int p[] = {2,3,4};
int m1 = *max_element(nums.begin(), nums.end());
int m2 = *max_element(&p[0], &p[sizeof(p)/4]);  // sizeof(p) / 4 = 3

__gcd

返回两个数的最大公约数

int a = __gcd(10, 4);

sort

对容器进行排序

sort(&nums[0], &nums[100]);  // 对一个长度为100的数组排序 注意不是&nums[99]
sort(vec.begin(), vec.end());  // 对vector进行排序
sort(str.begin(), str.end());  // 对string的char字符进行排序

int nums[] = {1, 2, 3, 4};
sort(&nums[0], &nums[4], greater<int>());    // 逆序排列 nums

注意：
不能对unordered_set这类无序的容器进行排序

accumulate

int sum = accumulate(vec.begin(), vec.end(), 0);  // 求vector<int>容器内所有数的和
int sum = accumulate(&nums[0], &nums[100], 0);  // 对数组求和

lower_bound, upper_bound
提供二分查找的函数，注意要提供一个有序的数组
upper_bound返回第一个大于的元素的下标； (类似于python的bisect.bisect_right)
lower_bound返回第一个大于等于元素的下标； (类似于python的bisect.bisect_left)
使用方法

vector<int> nums{1, 2, 3, 4, 5};
int k = upper_bound(nums.begin(), nums.end(), 4) - nums.begin();
// k = 4
int k = upper_bound(nums.begin(), nums.end(), 100) - nums.begin()；
// k = 5，即如果 值大于容器中的所有元素，返回容器的长度

int p[5] = {1, 4, 9, 10, 14};
k = lower_bound(p, p + 5, 11) - p; // 数组的用法类似

注：数组也可以使用auto语法进行遍历

#include <bits/stdc++.h>

using namespace std;

int main() {
    int nums[10];
    memset(nums, 0, sizeof(nums));
    nums[1] = 20;
    for (auto k : nums) {
        cout << k << endl;
    return 0;
}

其它常用方法：

1. C++ 整数与字符串互相转换

char c = '2';
int a = c - '0';  // 如何将整数的 char 变成 int 类型

string s = to_string(7);  // int -> string