常用STL的操作以及特点

C++ 标准模板库（STL）提供了很多常用的数据结构和算法，极大简化了开发工作。STL 包括容器（如 vector、list、map 等）、算法（如排序、查找等）以及迭代器。以下是一些常用 STL 容器的操作以及它们的特点：

1. vector（动态数组）

vector 是一个动态数组，大小可以动态增长或缩小。

常用操作：

std::vector<int> vec = {1, 2, 3};
vec.push_back(4);   // 在末尾添加元素
vec.pop_back();     // 删除末尾元素
vec.size();         // 返回元素个数
vec.empty();        // 判断是否为空
vec[1];             // 访问第二个元素
vec.clear();        // 清空所有元素

特点：

• 动态大小：可以根据需要自动扩展。
• 随机访问：支持常数时间复杂度的随机访问操作（operator[] 和 at()）。
• 内存管理：当需要扩展时，可能会导致重新分配内存，效率略低。
• 时间复杂度：插入/删除操作的时间复杂度为 O(1)（末尾），其他位置为 O(n)。

2. list（双向链表）

list 是双向链表，适合频繁进行插入和删除操作的场景。

常用操作：

std::list<int> lst = {1, 2, 3};
lst.push_back(4);    // 在末尾添加元素
lst.push_front(0);   // 在头部添加元素
lst.pop_back();      // 删除末尾元素
lst.pop_front();     // 删除头部元素
lst.size();          // 返回元素个数
lst.clear();         // 清空所有元素
lst.remove(2);       // 删除所有等于 2 的元素

特点：

• 双向链表：支持常数时间复杂度的插入和删除操作。
• 顺序访问：不支持随机访问，需要顺序遍历。
• 空间占用较大：由于每个节点都需要存储前后指针，空间利用率相对较低。
• 时间复杂度：插入、删除为 O(1)，访问为 O(n)。

3. deque（双端队列）

deque 是双端队列，支持两端的高效插入和删除操作。

常用操作：

std::deque<int> deq = {1, 2, 3};
deq.push_back(4);    // 在末尾添加元素
deq.push_front(0);   // 在头部添加元素
deq.pop_back();      // 删除末尾元素
deq.pop_front();     // 删除头部元素
deq.size();          // 返回元素个数
deq[1];              // 访问第二个元素
deq.clear();         // 清空所有元素

特点：

• 双端操作：支持 O(1) 时间复杂度的双端插入和删除。
• 随机访问：支持常数时间复杂度的随机访问。
• 适用于双端处理：比 list 更灵活，可以高效操作两端。

4. stack（栈）

stack 是基于 deque 或 vector 实现的后进先出（LIFO）数据结构。

常用操作：

std::stack<int> stk;
stk.push(1);        // 压栈
stk.pop();          // 弹栈
stk.top();          // 返回栈顶元素
stk.empty();        // 判断是否为空
stk.size();         // 返回栈中的元素个数

特点：

• 后进先出：只能访问栈顶元素，无法随机访问。
• 基于容器实现：默认使用 deque，但也可以使用 vector 或 list。
• 时间复杂度：常数时间的插入、删除和访问操作。

5. queue（队列）

queue 是基于 deque 实现的先进先出（FIFO）数据结构。

常用操作：

std::queue<int> que;
que.push(1);        // 入队
que.pop();          // 出队
que.front();        // 返回队首元素
que.back();         // 返回队尾元素
que.empty();        // 判断是否为空
que.size();         // 返回队列中元素个数

特点：

• 先进先出：只能操作队首和队尾。
• 时间复杂度：常数时间的插入、删除和访问操作。

6. priority_queue（优先队列）

priority_queue 是基于堆实现的队列，元素按优先级顺序出队。

常用操作：

std::priority_queue<int> pq;
pq.push(10);        // 入队
pq.pop();           // 出队，移除优先级最高的元素
pq.top();           // 返回优先级最高的元素
pq.empty();         // 判断是否为空
pq.size();          // 返回队列中元素个数

特点：

• 优先级排序：默认最大堆，优先级高的元素优先出队。
• 时间复杂度：插入和删除的时间复杂度为 O(log n)。

7. set 和 unordered_set（集合）

set 是有序集合，unordered_set 是无序集合（基于哈希表实现）。

常用操作：

std::set<int> s;
s.insert(1);        // 插入元素
s.erase(1);         // 删除元素
s.count(1);         // 判断元素是否存在
s.find(1);          // 查找元素
s.size();           // 返回元素个数
s.clear();          // 清空集合

特点：

• set：基于红黑树实现，支持自动排序。插入、删除、查找的时间复杂度为 O(log n)。
• unordered_set：基于哈希表实现，不保证元素顺序，插入、删除和查找的时间复杂度为 O(1)。

8. map 和 unordered_map（映射）

map 是有序键值对映射，unordered_map 是无序键值对映射。

常用操作：

std::map<int, std::string> mp;
mp[1] = "one";      // 插入或更新元素
mp.erase(1);        // 删除键为 1 的元素
mp.find(1);         // 查找键为 1 的元素
mp.size();          // 返回元素个数
mp.clear();         // 清空映射

特点：

• map：基于红黑树实现，按键值排序。插入、删除、查找的时间复杂度为 O(log n)。
• unordered_map：基于哈希表实现，不保证元素顺序，插入、删除和查找的时间复杂度为 O(1)。

9. algorithm（算法）

STL 提供了很多常用算法，如排序、查找、遍历等。

常用操作：

std::vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end());            // 排序
std::reverse(vec.begin(), vec.end());         // 逆序
std::find(vec.begin(), vec.end(), 4);         // 查找元素 4
std::count(vec.begin(), vec.end(), 1);        // 统计元素 1 的个数
std::accumulate(vec.begin(), vec.end(), 0);   // 求和

特点：

• 泛型算法：与任何 STL 容器配合使用。
• 高效实现：大多数算法的时间复杂度为 O(n log n) 或 O(n)。

10. 迭代器（Iterator）

STL 容器的元素可以通过迭代器进行遍历和操作。

常用操作：

std::vector<int> vec = {1, 2, 3};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";
}

特点：

• 抽象访问：可以无缝遍历任何 STL 容器，而无需关心其内部结构。
• 灵活操作：支持常见的迭代模式，如前向、双向、随机访问等。

总结

STL 提供了强大的数据结构和算法库，使得开发者可以快速、高效地解决许多常见的问题。每种容器和算法