C++ STL常用容器总结（vector, deque, list, map, set）

1. vector（动态数组）

特点

• 动态大小的数组，内存连续存储
• 支持随机访问，时间复杂度O(1)
• 尾部插入删除效率高O(1)，中间插入删除效率低O(n)

定义和初始化

#include <vector>

vector<int> vec1;                          // 默认初始化，vec1为空
vector<int> vec2(vec1);                    // 使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end()); // 使用vec1初始化vec3
vector<int> vec4(10);                      // 10个值为0的元素
vector<int> vec5(10,4);                    // 10个值为4的元素
vector<int> vec6{1,2,3,4,5};              // 列表初始化

常用操作

// 添加元素
vec1.push_back(100);                       // 尾部添加元素
vec1.insert(vec1.begin(), 50);            // 在开头插入50
vec1.insert(vec1.end(), 5, 3);            // 从末尾插入5个值为3的元素

// 访问元素
cout << vec1[0] << endl;                   // 下标访问
cout << vec1.at(0) << endl;               // at()访问，有边界检查
cout << vec1.front() << endl;             // 首元素
cout << vec1.back() << endl;              // 尾元素

// 删除元素
vec1.pop_back();                          // 删除末尾元素
vec1.erase(vec1.begin());                 // 删除首元素
vec1.erase(vec1.begin(), vec1.begin()+2); // 删除[0,2)区间元素

// 容器信息
int size = vec1.size();                   // 元素个数
bool isEmpty = vec1.empty();              // 判断是否为空
vec1.clear();                            // 清空所有元素

遍历方法

// 1. 下标法
for(int i = 0; i < vec1.size(); i++) {
    cout << vec1[i] << " ";
}

// 2. 迭代器法
for(vector<int>::iterator it = vec1.begin(); it != vec1.end(); it++) {
    cout << *it << " ";
}

// 3. 范围for循环（C++11）
for(auto x : vec1) {
    cout << x << " ";
}

2. deque（双端队列）

特点

• 双端队列，支持两端快速插入删除O(1)
• 支持随机访问O(1)
• 内存不连续，由多个块组成

定义和初始化

#include <deque>

deque<int> dq1;                           // 默认初始化
deque<int> dq2(10);                       // 10个值为0的元素
deque<int> dq3(10, 5);                    // 10个值为5的元素
deque<int> dq4{1,2,3,4,5};               // 列表初始化

常用操作

// 添加元素
dq1.push_back(100);                       // 尾部添加
dq1.push_front(50);                       // 头部添加
dq1.insert(dq1.begin()+1, 75);          // 指定位置插入

// 访问元素
cout << dq1[0] << endl;                   // 下标访问
cout << dq1.at(0) << endl;               // at()访问
cout << dq1.front() << endl;             // 首元素
cout << dq1.back() << endl;              // 尾元素

// 删除元素
dq1.pop_back();                          // 删除尾部元素
dq1.pop_front();                         // 删除头部元素
dq1.erase(dq1.begin());                  // 删除指定位置元素

// 容器信息
cout << dq1.size() << endl;              // 元素个数
cout << dq1.empty() << endl;             // 是否为空
dq1.clear();                             // 清空

3. list（双向链表）

特点

• 双向链表，内存不连续
• 不支持随机访问，只能顺序访问
• 任意位置插入删除效率高O(1)

定义和初始化

#include <list>

list<int> lst1;                          // 默认初始化
list<int> lst2(10);                      // 10个值为0的元素
list<int> lst3(10, 5);                   // 10个值为5的元素
list<int> lst4{1,2,3,4,5};              // 列表初始化

常用操作

// 添加元素
lst1.push_back(100);                     // 尾部添加
lst1.push_front(50);                     // 头部添加
auto it = lst1.begin();
advance(it, 2);                          // 迭代器前进2位
lst1.insert(it, 75);                     // 指定位置插入

// 访问元素（只能通过迭代器）
cout << lst1.front() << endl;           // 首元素
cout << lst1.back() << endl;            // 尾元素

// 删除元素
lst1.pop_back();                         // 删除尾部
lst1.pop_front();                        // 删除头部
lst1.remove(75);                         // 删除所有值为75的元素
lst1.erase(lst1.begin());               // 删除指定位置

// 链表特有操作
lst1.sort();                            // 排序
lst1.reverse();                         // 反转
lst1.unique();                          // 去除连续重复元素

// 容器信息
cout << lst1.size() << endl;
cout << lst1.empty() << endl;
lst1.clear();

遍历方法

// 迭代器法
for(list<int>::iterator it = lst1.begin(); it != lst1.end(); it++) {
    cout << *it << " ";
}

// 范围for循环
for(auto x : lst1) {
    cout << x << " ";
}

4. map（关联容器-映射）

特点

• 存储键值对(key-value)
• 按key自动排序（基于红黑树）
• key唯一，查找效率O(log n)

定义和初始化

#include <map>

map<string, int> mp1;                    // 默认初始化
map<string, int> mp2{{"apple", 5}, {"banana", 3}, {"orange", 8}};  // 列表初始化

常用操作

// 插入元素
mp1["apple"] = 5;                        // 下标法插入/修改
mp1.insert(pair<string, int>("banana", 3)); // insert插入
mp1.insert(make_pair("orange", 8));      // make_pair插入
mp1.emplace("grape", 6);                 // emplace插入（C++11）

// 访问元素
cout << mp1["apple"] << endl;            // 下标访问
cout << mp1.at("apple") << endl;         // at()访问

// 查找元素
auto it = mp1.find("apple");             // 查找，返回迭代器
if(it != mp1.end()) {
    cout << "Found: " << it->second << endl;
}

// 判断元素是否存在
if(mp1.count("apple") > 0) {             // count返回0或1
    cout << "apple exists" << endl;
}

// 删除元素
mp1.erase("apple");                      // 根据key删除
mp1.erase(mp1.find("banana"));          // 根据迭代器删除

// 容器信息
cout << mp1.size() << endl;
cout << mp1.empty() << endl;
mp1.clear();

遍历方法

// 迭代器法
for(map<string, int>::iterator it = mp1.begin(); it != mp1.end(); it++) {
    cout << it->first << ": " << it->second << endl;
}

// 范围for循环
for(auto& pair : mp1) {
    cout << pair.first << ": " << pair.second << endl;
}

// C++17结构化绑定
for(auto& [key, value] : mp1) {
    cout << key << ": " << value << endl;
}

5. set（关联容器-集合）

特点

• 存储唯一元素，自动排序
• 基于红黑树实现
• 查找、插入、删除效率O(log n)

定义和初始化

#include <set>

set<int> st1;                           // 默认初始化
set<int> st2{1, 3, 5, 7, 9};           // 列表初始化
set<int> st3(st2.begin(), st2.end());  // 迭代器初始化

常用操作

// 插入元素
st1.insert(10);                         // 插入单个元素
st1.insert({20, 30, 40});              // 插入多个元素
auto result = st1.insert(10);           // insert返回pair<iterator, bool>
if(result.second) {
    cout << "插入成功" << endl;
}

// 查找元素
auto it = st1.find(10);                 // 查找，返回迭代器
if(it != st1.end()) {
    cout << "Found: " << *it << endl;
}

// 判断元素是否存在
if(st1.count(10) > 0) {                 // count返回0或1
    cout << "10 exists" << endl;
}

// 删除元素
st1.erase(10);                          // 根据值删除
st1.erase(st1.find(20));               // 根据迭代器删除
st1.erase(st1.begin(), st1.end());     // 删除范围

// 集合运算
set<int> st4{1, 2, 3};
set<int> st5{2, 3, 4};
set<int> result_union, result_intersection;

// 并集
set_union(st4.begin(), st4.end(), st5.begin(), st5.end(), 
          inserter(result_union, result_union.begin()));

// 交集
set_intersection(st4.begin(), st4.end(), st5.begin(), st5.end(),
                inserter(result_intersection, result_intersection.begin()));

// 容器信息
cout << st1.size() << endl;
cout << st1.empty() << endl;
st1.clear();

遍历方法

// 迭代器法
for(set<int>::iterator it = st1.begin(); it != st1.end(); it++) {
    cout << *it << " ";
}

// 范围for循环
for(auto x : st1) {
    cout << x << " ";
}

容器选择指南

通用操作

所有STL容器都支持的操作：

• size() - 返回元素个数
• empty() - 判断是否为空
• clear() - 清空所有元素
• begin(), end() - 返回迭代器
• ==, != - 比较操作符