当前位置：首页 > news >正文

（C++）STL标准库（vector动态数组）（list列表）（set集合）（map键值对）相关对比，基础教程

news 2025/7/13 6:04:35

C++四大容器深度解析：vector、list、set、map (8000字详解)

一、容器概述与基础概念

1.1 STL容器分类

1.2 容器共性特征

1.3 复杂度表示法

二、vector（动态数组）

2.1 基本特性

2.2 核心操作

增加元素

删除元素

修改元素

查找元素

2.3 性能分析

2.4 最佳实践

三、list（双向链表）

3.1 基本特性

3.2 核心操作

增加元素

删除元素

修改元素

查找元素

3.3 特殊操作

3.4 性能分析

3.5 最佳实践

四、set（有序集合）

4.1 基本特性

4.2 核心操作

增加元素

删除元素

查找元素

修改元素

4.3 性能分析

4.4 最佳实践

五、map（有序映射）

5.1 基本特性

5.2 核心操作

增加元素

删除元素

修改元素

查找元素

5.3 特殊操作

5.4 性能分析

5.5 最佳实践

六、容器对比与选择指南

6.1 功能对比矩阵

6.2 性能对比总结

6.3 选择决策树

6.4 典型应用场景

七、高级技巧与最佳实践

7.1 自定义比较函数

7.2 高效遍历与删除

7.3 容器适配器

7.4 性能优化技巧

7.5 C++17新特性

八、总结与综合示例

8.1 容器选择黄金法则

8.2 综合应用示例：学生成绩系统

8.3 最终建议

C++四大容器深度解析：vector、list、set、map (8000字详解)

一、容器概述与基础概念

1.1 STL容器分类

C++标准模板库(STL)提供了多种容器类型，主要分为两大类：

序列容器：保持元素插入顺序
- vector：动态数组
- list：双向链表
- deque：双端队列
- array：固定大小数组(C++11)
- forward_list：单向链表(C++11)
关联容器：元素按键排序
- set：唯一键集合
- map：键值对集合
- multiset：允许重复键的集合
- multimap：允许重复键的键值对集合

1.2 容器共性特征

所有容器都支持以下操作：

size_type size() const;      // 返回元素数量
bool empty() const;          // 检查容器是否为空
void clear();                // 清空容器
iterator begin();            // 返回起始迭代器
iterator end();              // 返回结束迭代器
void swap(container& other); // 交换两个容器内容

1.3 复杂度表示法

O(1)：常数时间复杂度
O(n)：线性时间复杂度
O(log n)：对数时间复杂度
O(n log n)：线性对数时间复杂度

二、vector（动态数组）

2.1 基本特性

底层实现：动态分配的连续内存空间
内存管理：当容量不足时，自动分配更大内存（通常是2倍扩容）
访问方式：支持随机访问（下标操作）
适用场景：需要快速随机访问，尾部操作频繁

2.2 核心操作

增加元素

void push_back(const T& value);     // 尾部添加元素（拷贝）
void push_back(T&& value);          // 尾部添加元素（移动）
void emplace_back(Args&&... args);  // 尾部直接构造元素（C++11）
iterator insert(const_iterator pos, const T& value); // 指定位置插入

示例：

vector<int> vec;
vec.push_back(10);              // 拷贝添加
vec.emplace_back(20);           // 直接构造
vec.insert(vec.begin() + 1, 15); // 在第二个位置插入15
// vec: [10, 15, 20]

删除元素

void pop_back();                         // 删除尾部元素
iterator erase(const_iterator pos);      // 删除指定位置元素
iterator erase(const_iterator first, const_iterator last); // 删除范围

示例：

vec.pop_back();         // 删除20
vec.erase(vec.begin()); // 删除10
// vec: [15]

修改元素

T& operator[](size_type pos);       // 下标访问（无边界检查）
T& at(size_type pos);               // 下标访问（有边界检查）
void resize(size_type count);       // 改变容器大小
void reserve(size_type new_cap);    // 预留空间

示例：

vec[0] = 100;         // 修改第一个元素
vec.at(0) = 200;      // 安全修改
vec.resize(5);        // 扩大容器，新增元素默认初始化
vec.reserve(100);     // 预留空间，避免多次扩容

查找元素

// 使用标准算法查找
auto it = find(vec.begin(), vec.end(), value);
if (it != vec.end()) {// 找到元素
}

2.3 性能分析

操作	时间复杂度	说明
尾部插入	O(1) 均摊	偶尔需要扩容
头部插入	O(n)	需要移动所有元素
随机访问	O(1)	直接计算地址
中间插入	O(n)	需要移动后续元素
尾部删除	O(1)
头部删除	O(n)	需要移动所有元素
查找	O(n)	需要遍历

2.4 最佳实践

使用reserve()预分配空间减少扩容开销
优先使用emplace_back()而非push_back()
避免在中间位置频繁插入/删除
使用shrink_to_fit()释放多余内存

三、list（双向链表）

3.1 基本特性

底层实现：双向链表节点
内存管理：每个元素独立分配
访问方式：顺序访问
适用场景：频繁在任意位置插入/删除

3.2 核心操作

增加元素

void push_front(const T& value);    // 头部添加
void push_back(const T& value);     // 尾部添加
void emplace_front(Args&&... args); // 头部直接构造
void emplace_back(Args&&... args);  // 尾部直接构造
iterator insert(const_iterator pos, const T& value); // 指定位置插入

示例：

list<string> tasks;
tasks.push_back("Task1");
tasks.emplace_front("Urgent");
tasks.insert(++tasks.begin(), "Important");
// tasks: ["Urgent", "Important", "Task1"]

删除元素

void pop_front();                   // 删除头部元素
void pop_back();                    // 删除尾部元素
iterator erase(const_iterator pos); // 删除指定位置
void remove(const T& value);        // 删除所有匹配值
void unique();                      // 删除连续重复值

示例：

tasks.pop_front();          // 删除"Urgent"
tasks.remove("Task1");      // 删除所有"Task1"
tasks.unique();             // 删除连续重复值

修改元素

// 通过迭代器修改
auto it = tasks.begin();
*it = "New Task";

查找元素

// 使用标准算法查找
auto it = find(tasks.begin(), tasks.end(), value);

3.3 特殊操作

void sort();                     // 排序
void merge(list& other);         // 合并有序列表
void splice(const_iterator pos, list& other); // 移动元素
void reverse();                  // 反转链表

示例：

list<int> list1 = {1, 3, 5};
list<int> list2 = {2, 4, 6};
list1.merge(list2);      // list1: [1,2,3,4,5,6], list2为空
list1.reverse();         // [6,5,4,3,2,1]

3.4 性能分析

操作	时间复杂度	说明
任意位置插入	O(1)	只需修改指针
任意位置删除	O(1)	只需修改指针
随机访问	O(n)	需要遍历
查找	O(n)	需要遍历
排序	O(n log n)	归并排序实现

3.5 最佳实践

使用emplace系列函数提高效率
优先使用remove()进行值删除
使用splice()高效移动元素
避免频繁遍历大型链表

四、set（有序集合）

4.1 基本特性

底层实现：红黑树（自平衡二叉搜索树）
元素特性：唯一键、自动排序
适用场景：需要有序唯一元素、快速查找

4.2 核心操作

增加元素

pair<iterator, bool> insert(const T& value);
iterator insert(iterator hint, const T& value);
pair<iterator, bool> emplace(Args&&... args);

示例：

set<int> numbers;
auto [it1, success1] = numbers.insert(10); // 成功插入
auto [it2, success2] = numbers.insert(10); // 失败，元素已存在
numbers.emplace(20); // 直接构造插入

删除元素

size_type erase(const T& value);  // 按键删除
iterator erase(const_iterator pos); // 按位置删除
iterator erase(const_iterator first, const_iterator last); // 范围删除

示例：

numbers.erase(10); // 删除键为10的元素
auto it = numbers.find(20);
if (it != numbers.end()) {numbers.erase(it);
}

查找元素

iterator find(const T& value);       // 查找元素
size_type count(const T& value);     // 统计元素数量（0或1）
iterator lower_bound(const T& value); // 返回第一个不小于value的元素
iterator upper_bound(const T& value); // 返回第一个大于value的元素
pair<iterator, iterator> equal_range(const T& value); // 返回匹配范围

示例：

set<int> scores = {60, 70, 80, 90, 100};
auto it = scores.find(80); // 查找80分
auto lb = scores.lower_bound(75); // 第一个>=75的元素（80）
auto ub = scores.upper_bound(85); // 第一个>85的元素（90）

修改元素

元素不可修改（会破坏排序）
需要先删除后插入：

auto it = scores.find(70);
if (it != scores.end()) {int newScore = 75;scores.erase(it);scores.insert(newScore);
}

4.3 性能分析

操作	时间复杂度	说明
插入	O(log n)	平衡树插入
删除	O(log n)	平衡树删除
查找	O(log n)	平衡树查找
遍历	O(n)	中序遍历
范围查询	O(log n + k)	k为结果集大小

4.4 最佳实践

使用emplace()直接构造元素
使用lower_bound()/upper_bound()进行范围查询
自定义比较器实现特殊排序规则
避免存储大对象（考虑指针或智能指针）

五、map（有序映射）

5.1 基本特性

底层实现：红黑树（存储键值对）
元素特性：键唯一、按键自动排序
适用场景：键值对关联、按键快速查找

5.2 核心操作

增加元素

pair<iterator, bool> insert(const value_type& value);
iterator insert(iterator hint, const value_type& value);
pair<iterator, bool> emplace(Args&&... args);
T& operator[](const Key& key); // 访问或插入
T& operator[](Key&& key);
T& at(const Key& key); // 带边界检查的访问

示例：

map<int, string> students;
students.insert({101, "Alice"}); // 插入键值对
students.emplace(102, "Bob");    // 直接构造
students[103] = "Charlie";       // 使用下标操作符插入

删除元素

size_type erase(const Key& key);  // 按键删除
iterator erase(const_iterator pos); // 按位置删除
iterator erase(const_iterator first, const_iterator last); // 范围删除

示例：

students.erase(102); // 删除键为102的学生
auto it = students.find(103);
if (it != students.end()) {students.erase(it);
}

修改元素

// 通过迭代器修改值
auto it = students.find(101);
if (it != students.end()) {it->second = "Alice Smith"; // 修改值
}// 通过下标操作符修改
students[101] = "A. Smith";

查找元素

iterator find(const Key& key);       // 查找键
size_type count(const Key& key);     // 统计键出现次数（0或1）
iterator lower_bound(const Key& key); 
iterator upper_bound(const Key& key);
pair<iterator, iterator> equal_range(const Key& key);

示例：

auto it = students.find(101); // 查找学号101
if (students.count(102) > 0) {// 学号102存在
}

5.3 特殊操作

// C++17 try_emplace 和 insert_or_assign
auto [it, inserted] = students.try_emplace(104, "David"); // 只在键不存在时插入
auto [it, inserted] = students.insert_or_assign(101, "Alice Brown"); // 插入或更新

5.4 性能分析

操作	时间复杂度	说明
插入	O(log n)	平衡树插入
删除	O(log n)	平衡树删除
查找	O(log n)	平衡树查找
下标访问	O(log n)	可能触发插入
遍历	O(n)	中序遍历

5.5 最佳实践

使用try_emplace()避免不必要的拷贝
使用insert_or_assign()实现更新或插入
使用自定义类型作为键时提供比较函数
使用at()进行安全访问（避免意外插入）

六、容器对比与选择指南

6.1 功能对比矩阵

特性	vector	list	set	map
随机访问	✓ (O(1))	✗	✗	✗
快速插入/删除	尾部O(1)	任意O(1)	O(log n)	O(log n)
自动排序	✗	✗	✓	✓ (按键)
唯一元素	✗	✗	✓	✓ (按键)
键值对存储	✗	✗	✗	✓
内存连续性	✓	✗	✗	✗
缓存友好	✓	✗	✗	✗

6.2 性能对比总结

操作	vector	list	set	map
头部插入	O(n)	O(1)	O(log n)	O(log n)
尾部插入	O(1)	O(1)	O(log n)	O(log n)
中间插入	O(n)	O(1)	O(log n)	O(log n)
随机访问	O(1)	O(n)	O(n)	O(n)
按键查找	O(n)	O(n)	O(log n)	O(log n)
值删除	O(n)	O(1)	O(log n)	O(log n)
范围查询	O(n)	O(n)	O(log n + k)	O(log n + k)

6.3 选择决策树

需要键值对存储吗？
- 是 → 选择map
- 否 → 进入2
需要元素唯一且有序吗？
- 是 → 选择set
- 否 → 进入3
需要频繁在任意位置插入/删除吗？
- 是 → 选择list
- 否 → 进入4
需要随机访问或内存连续性吗？
- 是 → 选择vector
- 否 → 根据其他需求选择

6.4 典型应用场景

vector 适用场景：

需要随机访问元素（如数学向量）
尾部操作频繁（如栈实现）
数据缓存（缓存友好）
需要最小内存占用

// 向量运算示例
vector<double> vec1 = {1.0, 2.0, 3.0};
vector<double> vec2 = {4.0, 5.0, 6.0};
vector<double> result;
transform(vec1.begin(), vec1.end(), vec2.begin(), back_inserter(result), plus<double>());
// result: [5.0, 7.0, 9.0]

list 适用场景：

高频中间位置插入/删除（如任务队列）
需要高效合并/拆分（如大文件处理）
实现LRU缓存

// LRU缓存实现
list<pair<int, string>> cache;
unordered_map<int, list<pair<int, string>>::iterator> index;void access(int key) {if (index.find(key) != index.end()) {// 移动到前端cache.splice(cache.begin(), cache, index[key]);}
}

set 适用场景：

需要唯一元素集合（如用户ID）
需要自动排序（如排行榜）
需要快速存在性检查

// 单词统计
set<string> dictionary;
string word;
while (cin >> word) {dictionary.insert(word);
}
cout << "Unique words: " << dictionary.size();

map 适用场景：

键值对关联数据（如学生信息）
需要按键快速查找
需要按键排序

// 学生管理系统
map<int, Student> students;
students.emplace(101, Student("Alice", 90.5));
students.emplace(102, Student("Bob", 85.0));// 查找学生
auto it = students.find(101);
if (it != students.end()) {cout << it->second.name << ": " << it->second.score;
}

七、高级技巧与最佳实践

7.1 自定义比较函数

// set自定义排序
struct CaseInsensitiveCompare {bool operator()(const string& a, const string& b) const {return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](char c1, char c2) {return tolower(c1) < tolower(c2);});}
};set<string, CaseInsensitiveCompare> words;
words.insert("Apple");
words.insert("apple"); // 不会插入，因为视为相同

7.2 高效遍历与删除

// 安全删除满足条件的元素（所有容器通用）
for (auto it = container.begin(); it != container.end(); ) {if (condition(*it)) {it = container.erase(it); // erase返回下一个迭代器} else {++it;}
}// C++20 简化写法
erase_if(container, [](const auto& item) {return condition(item);
});

7.3 容器适配器

// 基于vector实现栈
stack<int, vector<int>> myStack;// 基于deque实现队列
queue<int> myQueue;// 基于vector实现优先队列
priority_queue<int, vector<int>, greater<int>> minHeap;

7.4 性能优化技巧

vector预分配：使用reserve()减少扩容开销
元素移动：使用移动语义减少拷贝

vector<string> words;
string largeStr = "very long string...";
words.push_back(move(largeStr)); // 移动而非拷贝

自定义分配器：针对特定场景优化内存分配
结构体优化：小对象更高效

// 优化前
map<string, Data> bigMap;// 优化后：使用指针或智能指针
map<string, unique_ptr<Data>> optimizedMap;

7.5 C++17新特性

// 结构化绑定遍历map
for (const auto& [key, value] : myMap) {cout << key << ": " << value << endl;
}// map插入优化
myMap.try_emplace(key, arg1, arg2); // 只在键不存在时构造
myMap.insert_or_assign(key, value); // 插入或更新// 节点操作（C++17）
map<int, string> src = {{1, "one"}, {2, "two"}};
map<int, string> dst;
auto node = src.extract(1); // 提取节点
dst.insert(move(node));     // 插入到另一个map

八、总结与综合示例

8.1 容器选择黄金法则

默认选择vector：除非有特殊需求
需要键值对选map：关联数据存储
需要唯一有序选set：集合操作
高频任意位置操作选list：链表特性
考虑性能与内存：vector连续内存优势

8.2 综合应用示例：学生成绩系统

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;struct Student {int id;string name;double score;// 用于set排序bool operator<(const Student& other) const {return score > other.score; // 按成绩降序}
};class GradeSystem {
private:vector<Student> students;          // 所有学生set<Student> rankedStudents;       // 按成绩排序map<int, Student*> idIndex;        // ID快速查找public:void addStudent(int id, string name, double score) {students.push_back({id, name, score});auto& newStudent = students.back();rankedStudents.insert(newStudent);idIndex[id] = &newStudent;}void updateScore(int id, double newScore) {auto it = idIndex.find(id);if (it != idIndex.end()) {// 更新排名rankedStudents.erase(*(it->second));it->second->score = newScore;rankedStudents.insert(*(it->second));}}void printTopStudents(int n) {cout << "Top " << n << " students:\n";int count = 0;for (const auto& student : rankedStudents) {if (count++ >= n) break;cout << student.name << ": " << student.score << endl;}}Student* findStudent(int id) {auto it = idIndex.find(id);return (it != idIndex.end()) ? it->second : nullptr;}
};int main() {GradeSystem system;system.addStudent(101, "Alice", 95.5);system.addStudent(102, "Bob", 88.0);system.addStudent(103, "Charlie", 92.5);system.updateScore(102, 90.5); // Bob成绩更新system.printTopStudents(2);/*输出：Top 2 students:Alice: 95.5Charlie: 92.5*/if (auto student = system.findStudent(103)) {cout << "Found: " << student->name << endl;}return 0;
}

8.3 最终建议

理解底层实现：选择容器前了解其数据结构
考虑操作频率：分析最常用操作
使用现代C++特性：emplace、移动语义等
性能测试：关键路径进行性能分析
组合使用容器：解决复杂问题

// 高效查找与顺序保持
vector<Employee*> employees; // 保持插入顺序
map<int, Employee*> idIndex; // ID快速查找

通过深入理解这四大容器的特性和适用场景，您将能够为不同需求选择最合适的数据结构，编写出高效、可维护的C++代码。

查看全文

http://www.lryc.cn/news/585850.html

【Lucene/Elasticsearch】**Query Rewrite** 机制

U盘直接拔出不在电脑上弹出有何影响

张量拼接操作

文件上传漏洞2-常规厂商检测限制绕过原理讲解

【学习笔记】Nginx常用安全配置

新型深度神经网络架构：ENet模型

零基础搭建监控系统：Grafana+InfluxDB 保姆级教程，5分钟可视化服务器性能！

《通信原理》学习笔记——第一章

PID控制算法理论学习基础——单级PID控制

houdini vat 学习笔记

LangChain 代理（Agents）学习

《Java Web程序设计》实验报告五 Java Script学习汇报

dubbo源码学习3-dubbo反射调用服务源码分析

Leetcode百题斩-二分搜索

【Linux仓库】虚拟地址空间【进程·陆】

飞算 JavaAI 智能编程助手：颠覆编程旧模式，重构新生态

ubuntu18.04 升级Ubuntu 20.04

vue3 el-table动态表头

Vue 项目打包部署还存在问题？你知道怎么做吧？

React - css 模块化(modules)

解决‘vue‘ 不是内部或外部命令，也不是可运行的程序

智慧公安总体建设方案PPT(78页)

江协科技STM32入门教程——通信接口

《Java Web程序设计》实验报告四 Java Script前端应用和表单验证

Vue.js：从 Web 到桌面的跨端实践与技术选型指南

C++四大容器深度解析：vector、list、set、map (8000字详解)

一、容器概述与基础概念

1.1 STL容器分类

1.2 容器共性特征

1.3 复杂度表示法

二、vector（动态数组）

2.1 基本特性

2.2 核心操作

增加元素

删除元素

修改元素

查找元素

2.3 性能分析

2.4 最佳实践

三、list（双向链表）

3.1 基本特性

3.2 核心操作

增加元素

删除元素

修改元素

查找元素

3.3 特殊操作

3.4 性能分析

3.5 最佳实践

四、set（有序集合）

4.1 基本特性

4.2 核心操作

增加元素

删除元素

查找元素

修改元素

4.3 性能分析

4.4 最佳实践

五、map（有序映射）

5.1 基本特性

5.2 核心操作

增加元素

删除元素

修改元素

查找元素

5.3 特殊操作

5.4 性能分析

5.5 最佳实践

六、容器对比与选择指南

6.1 功能对比矩阵

6.2 性能对比总结

6.3 选择决策树

6.4 典型应用场景

七、高级技巧与最佳实践

7.1 自定义比较函数

7.2 高效遍历与删除

7.3 容器适配器

7.4 性能优化技巧

7.5 C++17新特性

八、总结与综合示例

8.1 容器选择黄金法则

8.2 综合应用示例：学生成绩系统

8.3 最终建议

相关文章：