遍历vector

1. 基于范围的 for 循环（C++11 起推荐使用）

#include <vector>
#include <iostream>

std::vector<int> vec = {1, 2, 3, 4, 5};

for (const auto& element : vec) {
    std::cout << element << " ";
}

• 使用 const auto& 避免不必要的拷贝（尤其对大型对象有用）。
• 如果你需要修改元素，可以去掉 const 或使用 auto&。

2. 使用迭代器

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

或者使用 const_iterator（只读）：

for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
    std::cout << *it << " ";
}

3. 传统下标循环

for (size_t i = 0; i < vec.size(); ++i) {
    std::cout << vec[i] << " ";
}

• 注意：size() 返回的是 size_t（无符号类型），避免与有符号整数比较产生警告。

4. 使用 std::for_each（函数式风格）

#include <algorithm>

std::for_each(vec.begin(), vec.end(), [](int n) {
    std::cout << n << " ";
});

输出两层循环的vector

方法 1：基于范围的 for 循环（推荐）

for (const auto& row : matrix) {
    for (const auto& elem : row) {
        std::cout << elem << " ";
    }
    std::cout << "\n";  // 每行结束后换行
}

方法 2：传统下标循环

for (size_t i = 0; i < matrix.size(); ++i) {
    for (size_t j = 0; j < matrix[i].size(); ++j) {
        std::cout << matrix[i][j] << " ";
    }
    std::cout << "\n";
}

⚠️ 注意：使用 size_t 避免有符号/无符号比较警告。

方法 3：迭代器方式

for (auto row_it = matrix.begin(); row_it != matrix.end(); ++row_it) {
    for (auto elem_it = row_it->begin(); elem_it != row_it->end(); ++elem_it) {
        std::cout << *elem_it << " ";
    }
    std::cout << "\n";
}

遍历deque

在 C++ 中，std::deque（双端队列）是一个支持在两端高效插入/删除、同时支持随机访问的顺序容器。遍历 deque 的方式非常灵活，几乎和 vector 一样丰富。

方法 1：基于范围的 for 循环（C++11 起，推荐）

#include <iostream>
#include <deque>

std::deque<int> dq = {10, 20, 30, 40};
for (const auto& elem : dq) {
    std::cout << elem << " ";
}
// 输出: 10 20 30 40

如果需要修改元素：

for (auto& elem : dq) {
    elem *= 2; // 所有元素翻倍
}

方法 2：使用下标（随机访问）

for (size_t i = 0; i < dq.size(); ++i) {
    std::cout << dq[i] << " ";       // 或 dq.at(i)
}

方法 3：使用迭代器（正向）

// 普通迭代器
for (auto it = dq.begin(); it != dq.end(); ++it) {
    std::cout << *it << " ";
}

// 只读迭代器（推荐用于只读场景）
for (auto it = dq.cbegin(); it != dq.cend(); ++it) {
    std::cout << *it << " ";
}

方法 4：反向遍历（从尾到头）

// 基于范围（C++17 不支持直接反向范围 for，需用迭代器）
for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
    std::cout << *rit << " ";
}
// 输出: 40 30 20 10

方法 5：使用 std::for_each + lambda

#include <algorithm>

std::for_each(dq.begin(), dq.end(), [](int n) {
    std::cout << n << " ";
});

⚠️ deque 遍历注意事项

特性	说明
✅ 支持随机访问	可用 dq[i]、dq.at(i)，时间复杂度 O(1)
✅ 支持双向迭代	++it / --it 都高效
✅ 迭代器可能失效	仅当在头部或尾部扩容时，所有迭代器可能失效（与 vector 类似，但比 list 更敏感）
🔄 内存非连续	虽然支持随机访问，但底层是分段连续存储，缓存性能略低于 vector

遍历set

在 C++ 中，std::set 是一个有序、唯一的关联容器（通常基于红黑树实现），遍历方式与 vector 类似，但由于其元素是 const 的（不可修改），有一些细节需要注意。

1. 基于范围的 for 循环（推荐，C++11 起）

#include <iostream>
#include <set>

std::set<int> mySet = {3, 1, 4, 1, 5};

for (const auto& elem : mySet) {
    std::cout << elem << " ";  // 输出: 1 3 4 5
}

• 元素自动按升序排列（默认使用 std::less）。
• 不能通过遍历修改元素（因为 set 中的 key 是 const 的），所以用 const auto& 是安全且高效的。

2. 使用迭代器

for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " ";
}

或只读迭代器（更明确）：

for (auto it = mySet.cbegin(); it != mySet.cend(); ++it) {
    std::cout << *it << " ";
}

3. 使用 std::for_each + lambda

#include <algorithm>

std::for_each(mySet.begin(), mySet.end(), [](const int& n) {
    std::cout << n << " ";
});

• std::set 不支持下标访问（如 mySet[i] 是非法的）。
• 遍历时元素自动排序（除非你自定义了比较函数）。
• 所有遍历方式都是只读的——这是由 set 的设计决定的（修改 key 会破坏内部结构）。

遍历list

在 C++ 中，std::list 是一个双向链表容器，支持高效的插入和删除操作（但不支持随机访问）。遍历 std::list 的方式与其他 STL 容器类似，但由于其底层是链表结构，不能使用下标（如 list[i]）。

注意事项

特性	说明
❌ 不支持下标访问	mylist[0] 是非法的，编译会报错
✅ 支持修改元素	通过非 const 引用或迭代器可修改值
✅ 迭代器稳定	插入/删除（除被删元素外）不会使其他迭代器失效
🔄 双向遍历	支持 ++it 和 --it，以及 rbegin()/rend()

方法 1：基于范围的 for 循环（C++11 起，推荐）

#include <iostream>
#include <list>

std::list<int> mylist = {10, 20, 30, 40};
for (const auto& elem : mylist) {
    std::cout << elem << " ";
}
// 输出: 10 20 30 40

如果需要修改元素，可用 auto&：

for (auto& elem : mylist) {
    elem *= 2; // 所有元素翻倍
}

方法 2：使用迭代器

// 正向遍历
for (auto it = mylist.begin(); it != mylist.end(); ++it) {
    std::cout << *it << " ";
}

// 只读遍历（更安全）
for (auto it = mylist.cbegin(); it != mylist.cend(); ++it) {
    std::cout << *it << " ";
}

方法 3：反向遍历（从尾到头）

for (auto rit = mylist.rbegin(); rit != mylist.rend(); ++rit) {
    std::cout << *rit << " ";
}
// 输出: 40 30 20 10

方法 4：使用 std::for_each + lambda

#include <algorithm>

std::for_each(mylist.begin(), mylist.end(), [](int n) {
    std::cout << n << " ";
});

性能提示

• std::list 遍历速度通常比 std::vector 慢（因为内存不连续，缓存不友好）。
• 如果只是顺序读取且不需要频繁中间插入/删除，优先考虑 vector 或 deque。

遍历map

特性	说明
自动排序	std::map 内部基于红黑树，遍历时按键升序输出
key 不可修改	遍历时 pair.first 是 const，不能修改 key
value 可修改	可通过 pair.second = newValue 修改值（若用非 const 引用）
无重复 key	插入相同 key 会覆盖旧值

在 C++ 中，std::map 是一个有序的键值对（key-value）关联容器，每个元素是一个 std::pair<const Key, Value>。遍历 map 的结果会按键的升序自动排序（默认使用 std::less<Key>）。

方法 1：基于范围的 for 循环（C++11 起，推荐）

#include <iostream>
#include <map>
#include <string>

std::map<std::string, int> scores = {
    {"Alice", 95},
    {"Bob", 87},
    {"Charlie", 92}
};

for (const auto& pair : scores) {
    std::cout << pair.first << " => " << pair.second << "\n";
}

或者使用结构化绑定（C++17 起更清晰）：

for (const auto& [key, value] : scores) {
    std::cout << key << " => " << value << "\n";
}

方法 2：使用迭代器

for (auto it = scores.begin(); it != scores.end(); ++it) {
    std::cout << it->first << " => " << it->second << "\n";
}

方法 3：使用 std::for_each + lambda

#include <algorithm>

std::for_each(scores.begin(), scores.end(), [](const auto& p) {
    std::cout << p.first << " => " << p.second << "\n";
});

一、基本特性总览

容器	底层结构	是否有序	元素是否唯一	支持随机访问	插入/删除效率（典型位置）	是否支持下标 []
vector	动态数组	否	否	✅ O(1)	尾部：O(1) 中间/头部：O(n)	✅
deque	分段连续数组	否	否	✅ O(1)	两端：O(1) 中间：O(n)	✅
list	双向链表	否	否	❌	任意位置：O(1)（需迭代到位置）	❌
set	红黑树（平衡 BST）	✅（按键）	✅	❌	任意位置：O(log n)	❌
map	红黑树	✅（按键）	✅（key 唯一）	❌	任意位置：O(log n)	✅（map[key]，但会插入默认值）

遍历方式对比

容器	范围 for	下标 []	迭代器	反向遍历	遍历时修改元素
vector	✅	✅	✅	✅	✅（非 const）
deque	✅	✅	✅	✅	✅
list	✅	❌	✅	✅	✅
set	✅	❌	✅	✅	❌（key 是 const）
map	✅	❌（不能用于遍历）	✅	✅	✅（可改 value，不能改 key）

性能对比（时间复杂度）

操作	vector	deque	list	set / map
尾部插入	O(1) amortized	O(1)	O(1)	O(log n)
头部插入	O(n)	O(1)	O(1)	O(log n)
中间插入	O(n)	O(n)	O(1)*	O(log n)
随机访问	O(1)	O(1)	O(n)	❌
查找（按值）	O(n)	O(n)	O(n)	O(log n)
删除（已知位置）	O(n)	O(n)	O(1)	O(log n)
内存局部性	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐	⭐⭐

使用场景建议

容器	推荐使用场景
vector	- 需要频繁随机访问 - 数据量固定或主要在尾部增删 - 对缓存友好（高性能循环）
deque	- 需要在两端高效插入/删除（如队列、滑动窗口） - 不需要中间插入
list	- 需要在任意位置频繁插入/删除（且已有迭代器） - 不关心随机访问和内存连续性 - 实现 LRU 缓存等
set	- 需要自动去重 + 自动排序 - 快速判断元素是否存在
map	- 需要键值映射 + 自动按键排序 - 快速通过 key 查找 value

完整容器列表

容器类型	是否有序	允许重复	底层实现	头文件
std::set	✅ 是	❌ 否	红黑树（平衡二叉搜索树）	<set>
std::multiset	✅ 是	✅ 是	红黑树	<set>
std::unordered_set	❌ 否	❌ 否	哈希表 + 链地址法（或开放寻址）	<unordered_set>
std::unordered_multiset	❌ 否	✅ 是	哈希表	<unordered_set>
std::map	✅ 是	❌ 否（key 唯一）	红黑树	<map>
std::multimap	✅ 是	✅ 是（相同 key 可多次出现）	红黑树	<map>
std::unordered_map	❌ 否	❌ 否（key 唯一）	哈希表	<unordered_map>
std::unordered_multimap	❌ 否	✅ 是	哈希表	<unordered_map>

 所有 unordered_* 容器要求 key 类型支持哈希（即提供 std::hash<Key> 特化），否则需自定义哈希函数。

时间复杂度对比（平均 / 最坏）

操作	set / map （红黑树）	multiset / multimap	unordered_* （哈希表）
插入	O(log n)	O(log n)	平均 O(1) 最坏 O(n)（哈希冲突严重或 rehash）
删除	O(log n)	O(log n)	平均 O(1) 最坏 O(n)
查找（by key）	O(log n)	O(log n)	平均 O(1) 最坏 O(n)
范围查询 （如 lower_bound）	✅ O(log n)	✅	❌（不支持有序范围）
遍历全部元素	O(n)，有序	O(n)，有序	O(n)，无序