6.stl常用函数

一、通用基础函数（几乎所有容器都支持）

这些函数是所有容器的共性，是使用 STL 容器的基础：

函数	功能说明
empty()	判断容器是否为空，返回bool值（空返回true），时间复杂度 O (1)
size()	返回容器中元素的个数，时间复杂度 O (1)（list/forward_list 除外，O (n)）
clear()	清空容器中所有元素，释放内存（不同容器释放策略略有差异）
begin()	返回指向容器第一个元素的迭代器（可读可写，非 const 容器）
end()	返回指向容器末尾之后的迭代器（尾后迭代器，不可解引用）
cbegin()/cend()	返回只读的 const 迭代器（不能通过迭代器修改元素）
swap()	交换两个同类型容器的内容，时间复杂度 O (1)（底层交换内部指针，效率极高）

示例（通用函数）：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3};
    
    // 通用函数使用
    cout << "是否为空：" << boolalpha << vec.empty() << endl; // 输出false
    cout << "元素个数：" << vec.size() << endl; // 输出3
    
    vec.clear();
    cout << "清空后元素个数：" << vec.size() << endl; // 输出0
    
    vector<int> vec2 = {4, 5};
    vec.swap(vec2); // 交换两个vector
    cout << "交换后vec的第一个元素：" << vec[0] << endl; // 输出4
    
    return 0;
}

---

二、序列式容器常用函数（vector/list/deque）

1. vector（最常用的动态数组）

vector 是新手最常接触的容器，除通用函数外，核心函数：

函数	功能说明
push_back(val)	在容器尾部添加元素，平均 O (1)（扩容时 O (n)）
pop_back()	删除尾部元素，O (1)
resize(n)	调整容器大小为 n，不足补默认值，超出则删除后面元素
reserve(n)	预分配 n 个元素的内存（仅扩容，不改变 size），避免频繁扩容
at(index)	访问索引 index 的元素，带越界检查（越界抛out_of_range异常）
[]	访问索引 index 的元素，无越界检查（效率更高，新手慎用）
front()	返回第一个元素的引用，O (1)
back()	返回最后一个元素的引用，O (1)
insert(iter, val)	在迭代器 iter 位置插入元素，O (n)（后续元素需移动）
erase(iter)	删除迭代器 iter 位置的元素，O (n)（后续元素需移动）

vector 示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec;
    vec.push_back(10); // 尾部添加10
    vec.push_back(20);
    cout << "尾部元素：" << vec.back() << endl; // 输出20
    
    vec.reserve(100); // 预分配100个空间，避免频繁扩容
    vec.resize(5); // 调整为5个元素，后3个补0
    cout << "第3个元素：" << vec.at(2) << endl; // 输出0
    
    vec.insert(vec.begin() + 1, 15); // 在第2个位置插入15
    for (int num : vec) cout << num << " "; // 输出10 15 20 0 0
    
    vec.erase(vec.end() - 2); // 删除倒数第2个元素
    cout << endl << "最后一个元素：" << vec.back() << endl; // 输出0
    
    return 0;
}

2. list（双向链表）

list 的优势是任意位置插入 / 删除效率高（O (1)），但不支持随机访问，核心函数：

函数	功能说明
push_front(val)	在头部添加元素，O (1)
pop_front()	删除头部元素，O (1)
insert(iter, val)	在迭代器 iter 位置插入元素，O (1)（链表特性，无需移动元素）
erase(iter)	删除迭代器 iter 位置的元素，O (1)
sort()	自带排序函数（vector 需用全局 sort），O (n log n)
splice(iter, list2)	把 list2 的元素拼接至 iter 位置，O (1)（链表指针调整）

3. deque（双端队列）

兼顾 vector 和 list 的特性，支持双端操作，常用函数：push_front()/pop_front()/push_back()/pop_back()（均为 O (1)），其余和 vector 类似。

---

三、关联式容器常用函数（map/set/unordered_map）

关联式容器以键值对（map）或唯一值（set）组织，核心是快速查找（O (log n) 或 O (1)）。

1. map（键值对，键唯一，有序）

map 的元素是pair<const Key, T>，常用函数：

函数	功能说明
insert(pair)	插入键值对，如map.insert({1, "a"})，键已存在则插入失败
emplace(key, val)	直接构造键值对插入（比 insert 更高效），O (log n)
operator[key]	访问 / 插入键为 key 的元素（键不存在则插入默认值），O (log n)
find(key)	查找键为 key 的元素，返回迭代器（找不到返回 end ()），O (log n)
count(key)	统计键为 key 的元素个数（map 中只能是 0 或 1），O (log n)
erase(key)	删除键为 key 的元素，O (log n)

map 示例：

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> mp;
    mp[1] = "apple"; // 插入键1，值apple
    mp.emplace(2, "banana"); // 高效插入
    
    // 查找键2
    auto it = mp.find(2);
    if (it != mp.end()) {
        cout << "键2的值：" << it->second << endl; // 输出banana
    }
    
    cout << "键3的个数：" << mp.count(3) << endl; // 输出0
    mp.erase(1); // 删除键1
    cout << "map大小：" << mp.size() << endl; // 输出1
    
    return 0;
}

2. set（值唯一，有序）

set 的元素是唯一的，常用函数：insert(val)/find(val)/count(val)/erase(val)，用法和 map 类似（无[]操作）。

3. unordered_map/unordered_set（哈希表实现）

无序，查找 / 插入 / 删除平均 O (1)，函数和 map/set 基本一致，区别是不支持排序相关操作（无 begin () 到 end () 的有序遍历）。

---

四、容器适配器常用函数（stack/queue/priority_queue）

容器适配器是对基础容器的封装，接口更简单：

1. stack（栈，后进先出）

函数	功能说明
push(val)	入栈（添加到栈顶），O (1)
pop()	出栈（删除栈顶元素，无返回值），O (1)
top()	返回栈顶元素的引用，O (1)

2. queue（队列，先进先出）

函数	功能说明
push(val)	入队（添加到队尾），O (1)
pop()	出队（删除队首元素，无返回值），O (1)
front()	返回队首元素的引用，O (1)
back()	返回队尾元素的引用，O (1)

3. priority_queue（优先队列，堆实现）

函数	功能说明
push(val)	插入元素并调整堆，O (log n)
pop()	删除优先级最高的元素（堆顶），O (log n)
top()	返回优先级最高的元素（堆顶），O (1)

---

总结

1. 通用函数：empty()、size()、clear()、begin()/end()是所有容器的基础，必须掌握；
2. 序列式容器：vector 重点用push_back()/pop_back()/[]/at()，list 重点用push_front()/insert()/erase()；
3. 关联式容器：map/set 核心是find()/insert()/erase()，unordered 系列更高效但无序；
4. 容器适配器：stack 用push()/pop()/top()，queue 用push()/pop()/front()，优先队列用top()而非front()。