C++ STL容器详解：从入门到精通

C++ STL容器详解：从入门到精通

一、STL容器概述

STL（Standard Template Library，标准模板库）是C++标准库的核心组件，提供了一套高效、可复用的数据结构和算法。STL容器作为其重要组成部分，用于存储和管理数据集合，遵循泛型编程思想，通过模板实现类型无关性。

STL核心组件

• 容器（Containers）：存放数据的结构，如vector、list、map等

• 算法（Algorithms）：如sort、find、accumulate等（头文件<algorithm>）

• 迭代器（Iterators）：连接算法与容器的"指针风格"对象

• 函数对象/谓词：比较器、定制规则（常用lambda表达式）

• 适配器：容器/迭代器/函数的包装器

二、STL容器分类体系

STL容器按照数据组织方式分为三大类：

1. 序列容器（Sequence Containers）

元素按插入顺序存储，保持线性顺序：

• vector：动态数组，连续内存存储

• deque：双端队列，支持头尾高效操作

• list：双向链表，任意位置插入删除高效

• forward_list：单向链表（C++11）

• array：固定长度数组（C++11）

2. 关联容器（Associative Containers）

元素按键值自动排序，基于红黑树实现：

• set：唯一元素的有序集合

• multiset：允许重复元素的有序集合

• map：键值对映射，键唯一

• multimap：允许重复键的映射

3. 无序关联容器（Unordered Associative Containers）

基于哈希表实现，元素无序，查找效率高（C++11）：

• unordered_set：哈希集合

• unordered_multiset：允许重复的哈希集合

• unordered_map：哈希映射

• unordered_multimap：允许重复键的哈希映射

4. 容器适配器（Container Adapters）

基于其他容器提供特定功能接口：

• stack：栈（后进先出）

• queue：队列（先进先出）

• priority_queue：优先队列

三、序列容器详解

1. vector（动态数组）

核心特性

• 底层实现：连续内存的动态数组

• 随机访问：O(1)时间复杂度

• 尾部操作：push_back/pop_back均摊O(1)

• 中间操作：插入/删除O(n)

• 内存管理：自动扩容（通常按1.5或2倍增长）

常用操作

#include <vector> #include <iostream> int main() { // 多种初始化方式 std::vector<int> v1; // 空vector std::vector<int> v2(5); // 5个0 std::vector<int> v3(5, 10); // 5个10 std::vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表 // 容量管理 v1.reserve(100); // 预留100个元素空间 std::cout << "size: " << v4.size() << std::endl; // 当前元素数量 std::cout << "capacity: " << v4.capacity() << std::endl; // 当前容量 // 访问元素 std::cout << "front: " << v4.front() << std::endl; // 第一个元素 std::cout << "back: " << v4.back() << std::endl; // 最后一个元素 std::cout << "at(2): " << v4.at(2) << std::endl; // 安全访问 // 修改操作 v4.push_back(6); // 尾部添加 v4.insert(v4.begin() + 2, 100); // 中间插入 v4.erase(v4.begin() + 1); // 删除 v4.pop_back(); // 删除尾部 // 高级操作 std::sort(v4.begin(), v4.end()); // 排序 v4.resize(10, 0); // 调整大小 return 0; }

性能优化技巧

// 预分配避免频繁扩容 void vector_reserve_demo() { // ❌ 错误做法：不预分配 std::vector<int> bad_vec; for (int i = 0; i < 10000; ++i) { bad_vec.push_back(i); // 可能触发多次内存重新分配 } // ✅ 正确做法：预分配容量 std::vector<int> good_vec; good_vec.reserve(10000); // 一次性分配足够内存 for (int i = 0; i < 10000; ++i) { good_vec.push_back(i); // 不会触发重新分配 } } // 高效删除元素 void vector_erase_demo() { std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // ❌ 低效：从前往后删除 for (auto it = vec.begin(); it != vec.end();) { if (*it % 2 == 0) { it = vec.erase(it); // O(n)操作，总体O(n²) } else { ++it; } } // ✅ 高效：使用remove_if + erase vec.erase( std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }), vec.end() ); // O(n)操作 } // 使用emplace避免不必要的拷贝 void modern_vector_usage() { std::vector<std::pair<int, std::string>> vec; //