STL

Standard Template Library：

容器（Containers）：容器是一种数据结构（如vector）
迭代器（Iterators）：用于访问数据结构
算法（Algorithms）：通过迭代器对数据结构操作的函数

数据结构	描述	库
`vector`	向量（动态数组）：末尾添加、删除	`<vector>`
`list`	链表：每个元素与下一个元素连接	`<list>`
`stack`	栈：后进先出	`<stack>`
`queue`	队列：先进先出	`<queue>`
`deque`	双端队列：两端都可	`<deque>`
`set`	集合：元素不重复，无序	`<set>`
`map`	映射：键值对	`<map>`

vector

库：<vector>

创建：

1 2	vector<string> cars; vector<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

访问、更改：

索引
.at()
.front()：第一个
.back()：最后一个

添加：.push_back() 在末尾添加

删除：.pop_back() 删除末尾元素

大小：.size()

检查是否为空：.empty()

遍历：

for + .size()
for - each循环

list

可在开头、结尾添加和删除
不支持索引访问

库：<list>

创建：

1 2	list<string> cars; list<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

访问、更改：

.front()
.back()

添加：

.push_front()
.push_back()

删除：

.pop_front()
.pop_back()

大小：.size()

检查是否为空：.empty()

遍历：

for + .size()
for - each

stack

LIFO： Last in, First Out，后进先出
只能访问堆栈顶部的元素

库：<stack>

创建：stack<string> cars;（只能这样）

添加：.push()

访问：.top()

更改：.top

删除：.pop()

大小：.size()

检查是否为空：.empty()

queue

FIFO： First in, First Out，先进先出
只能访问前面或后面的元素

库：<queue>

创建：queue<string> cars; 只能这样

添加：.push() 在队列末尾添加一个元素

访问、更改：

.front()
.back()

删除：.pop()

大小：.size()

检查是否为空：.empty()

deque

可以从两端（在前面和后面）添加和删除元素
可以通过索引号访问元素

库：<deque>

创建：

1 2	deque<string> cars; deque<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

访问、更改：

索引
.at()
.front()
.back()

添加：

.push_front()
.push_back()

删除：

.pop_front()
.pop_back()

大小：.size()

检查是否为空：.empty()

遍历：

for + .size()
for - each

set

存储唯一元素，按升序自动排序
可以添加、删除，不能更改
不能按索引号访问（因为顺序基于排序而不是索引）

库：<set>

创建：

1 2	set<string> cars; set<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

降序排序：

1	set<int, greater<int>> numbers = {1, 7, 3, 2, 5, 9};

添加：.insert()

删除：.erase()

删除所有元素：.clear()

大小：.size()

检查是否为空：.empty()

遍历： for - each

map

键值对：只能通过键访问，每个键唯一
键按升序排序

库：<map>

创建：

1 2	map<string, int> people map<string, int> people = { {"John", 32}, {"Adele", 45}, {"Bo", 29} };

访问、更改：

键：[]
.at()

添加：

.[] =
.insert()

删除：.erase()

删除所有元素：.clear()

大小：.size()

检查是否为空：.empty()

检查是否存在键：.count()

遍历：

for - each + auto
.first + .second

map<string, int> people = { {"John", 32}, {"Adele", 45}, {"Bo", 29} };

for (auto person : people) {
  cout << person.first << " is: " << person.second << "\n";
}

降序排序：（只能针对键）

1	map<string, int, greater<string>> people = { {"John", 32}, {"Adele", 45}, {"Bo", 29} };

iterator

类似指针：指向数据结构来访问、更改，而不是赋值取值
迭代器的类型必须与数据结构的类型匹配

遍历：

vector<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};

vector<string>::iterator it;

for (it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

**.begin()：**返回一个迭代器：指向第一个元素

**.end()：**返回一个迭代器：指向最后一个元素的后一个位置

注意：begin() ， end() 是属于数据结构的函数（vector），他们不属于 Iterator本身。但它们与迭代器一起使用，来访问和迭代元素。

**auto：**让编译器自动确定正确的数据类型

// vector<string>::iterator it = cars.begin();

auto it = cars.begin();

for (auto it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

for-each vs iterator：

for-each：只读取，不修改
iterator：在迭代过程中添加或删除、反向迭代、跳过元素

反向迭代：rbegin()，rend

1
2
3

for (auto it = cars.rbegin(); it != cars.rend(); ++it) {
  cout << *it << "\n";
}

遍历其他数据结构：

支持：vector，list，deque，map，set
不支持：stack，queue

map<string, int> people = { {"John", 32}, {"Adele", 45}, {"Bo", 29} };

for (auto it = people.begin(); it != people.end(); ++it) {
  cout << it->first << " is: " << it->second << "\n";
}

排序：sort(numbers.begin(), numbers.end()); （升序）

降序排序：sort(numbers.rbegin(), numbers.rend());

搜索：find(start_iterator, end_iterator, value)

查找

1 2	vector<int> numbers = {1, 7, 3, 5, 9, 2}; auto it = find(numbers.begin(), numbers.end(), 3);

大于特定值的第一个元素：upper_bound()（需要先进行排序）

1
2
3

vector<int> numbers = {1, 7, 3, 5, 9, 2};
sort(numbers.begin(), numbers.end());
auto it = upper_bound(numbers.begin(), numbers.end(), 5);

最小元素：min_element()

1 2	vector<int> numbers = {1, 7, 3, 5, 9, 2}; auto it = min_element(numbers.begin(), numbers.end());

最大元素：max_element()

1 2	vector<int> numbers = {1, 7, 3, 5, 9, 2}; auto it = max_element(numbers.begin(), numbers.end());

修改：

复制：copy()

1
2
3

vector<int> numbers = {1, 7, 3, 5, 9, 2};
vector<int> copiedNumbers(6);
copy(numbers.begin(), numbers.end(), copiedNumbers.begin());

填充：fill()

1 2	vector<int> numbers(6); fill(numbers.begin(), numbers.end(), 35);