STL

Array 数组

固定大小、连续内存分配、快速随机访问。
实现方式

int arr[10]; // 传统C风格数组
std::array<int, 10> arr; // C++11引入的std::array

操作总结

操作	语法	时间复杂度
访问元素	`arr[index]` 或 `arr.at(index)`	O(1)
修改元素	`arr[index] = value`	O(1)
获取大小	`arr.size()`	O(1)
填充值	`arr.fill(value)`	O(n)
迭代	使用迭代器或范围for循环	O(n)

Vector 向量、动态数组

动态大小，连续内存分配。快速随机访问。尾部插入/删除高效
实现方式

#include <vector>
std::vector<int> vec;

操作总结

操作	语法	时间复杂度
添加元素(尾)	`vec.push_back(value)`	均摊O(1)
删除元素(尾)	`vec.pop_back()`	O(1)
插入元素	`vec.insert(position, value)`	O(n)
删除元素	`vec.erase(position)`	O(n)
访问元素	`vec[index]` 或 `vec.at(index)`	O(1)
获取大小	`vec.size()`	O(1)
容量操作	`vec.capacity()`, `vec.reserve(n)`	O(1)/O(n)
清空	`vec.clear()`	O(n)

迭代

vector<int> v(10, 3);

// 传统循环
for (int i = 0; i < 10; i++) {
    cout << v[i] << " ";
}
cout << endl;

// 基于范围循环
for (auto item : v) {
    cout << item << " ";
}
cout << endl;

// 迭代器循环
for (auto item = v.begin(); item != v.end(); item++) {
    cout << *item << " ";
}
cout << endl;

单层vector

vector<int> v;                  // 创建空vector
vector<int> v(5);               // 创建大小为5的vector，初始值为0
vector<int> v(5, 1);            // 创建大小为5的vector，初始值为1

v.push_back(10);                // 尾部插入元素
v.pop_back();                   // 删除尾部元素
v.insert(v.begin()+2, 20);      // 在指定位置插入元素
v.erase(v.begin()+1);           // 删除指定位置元素
v.clear();                      // 清空vector

int x = v[0];                   // 访问元素（不检查边界）
int y = v.at(0);                // 访问元素（检查边界）
bool empty = v.empty();         // 判断是否为空
int size = v.size();            // 获取元素数量
v.resize(10);                   // 调整大小

双重vector

vector<vector<int>> v2d;        // 创建空二维vector
vector<vector<int>> v2d(5, vector<int>(3)); // 5x3的二维vector，初始值为0
vector<vector<int>> v2d(5, vector<int>(3, 1)); // 5x3的二维vector，初始值为1

v2d.push_back(vector<int>(4));  // 添加一行（4列）
v2d[0].push_back(10);           // 在第一行末尾添加元素

int val = v2d[1][2];            // 访问元素
v2d[2].erase(v2d[2].begin()+1); // 删除第二行的第二个元素

双端队列 (Deque)

动态大小。高效的头尾操作。
实现方式

#include <deque>
std::deque<int> dq;

操作总结

操作	语法	时间复杂度
头部添加	`dq.push_front(value)`	O(1)
尾部添加	`dq.push_back(value)`	O(1)
头部删除	`dq.pop_front()`	O(1)
尾部删除	`dq.pop_back()`	O(1)
访问元素	`dq[index]` 或 `dq.at(index)`	O(1)
获取大小	`dq.size()`	O(1)
清空	`dq.clear()`	O(n)

栈 (Stack) - 适配器

LIFO (后进先出)结构。基于其他容器实现(默认deque)
实现方式

#include <stack>
std::stack<int> st;

操作总结

操作	语法	时间复杂度
压栈	`st.push(value)`	O(1)
出栈	`st.pop()`	O(1)
访问栈顶	`st.top()`	O(1)
检查空	`st.empty()`	O(1)
获取大小	`st.size()`	O(1)

队列 (Queue) - 适配器

FIFO (先进先出)结构。基于其他容器实现(默认deque)
实现方式

#include <queue>
std::queue<int> q;

操作总结

操作	语法	时间复杂度
入队	`q.push(value)`	O(1)
出队	`q.pop()`	O(1)
访问队首	`q.front()`	O(1)
访问队尾	`q.back()`	O(1)
检查空	`q.empty()`	O(1)
获取大小	`q.size()`	O(1)

容器的基本操作

操作	方法名	适用容器
插入元素	`push_back()`	vector, deque, list
	`push_front()`	deque, list, forward_list
	`push()`	stack, queue, priority_queue
	`insert()`	序列容器(vector,deque,list) + 关联容器
删除元素	`pop_back()`	vector, deque, list
	`pop_front()`	deque, list, forward_list
	`pop()`	stack, queue, priority_queue
	`erase()`	序列容器 + 关联容器
访问首元素	`front()`	vector, deque, list, queue
访问尾元素	`back()`	vector, deque, list
访问顶部元素	`top()`	stack, priority_queue
容器大小	`size()`	所有容器(除forward_list)
检查空容器	`empty()`	所有容器
清空容器	`clear()`	所有容器

map

由 {键，值} 对组成的集合，以某种比较键大小关系的谓词进行排列。

基于红黑树，有序
示例

#include <map>
using namespace std;

map<string, int> m;

m["apple"] = 5;                 // 插入/修改元素
m.insert({"banana", 3});        // 插入元素
m.erase("apple");               // 删除元素

if (m.count("apple")) {         // 检查键是否存在
    int val = m["apple"];       // 访问元素
}

bool empty = m.empty();         // 判断是否为空
int size = m.size();            // 获取元素数量
m.clear();                      // 清空map

// 遍历map
for (const auto& pair : m) {
    cout << pair.first << " " << pair.second << endl;
}

// 遍历map c++17
for (auto& [key, value] : m) {
    cout << key << ": " << value << endl;
}

unordered_map

哈希表实现，无序但更快

#include <unordered_map>
using namespace std;

unordered_map<string, int> um;

um["apple"] = 5;                // 插入/修改元素
um.insert({"banana", 3});       // 插入元素
um.erase("apple");              // 删除元素

if (um.find("apple") != um.end()) { // 检查键是否存在
    int val = um["apple"];      // 访问元素
}

bool empty = um.empty();        // 判断是否为空
int size = um.size();           // 获取元素数量
um.clear();                     // 清空unordered_map

总结

vector：动态数组，支持快速随机访问
stack：后进先出(LIFO)结构
queue：先进先出(FIFO)结构
deque：双端队列，两端都可高效插入删除
map/unordered_map：键值对集合，map有序，unordered_map更快但无序