三种容器 std::vector、std::map、std::unordered_set 的对比分析

目录

1.添加元素

1.1 std::vector

1.2 std::map

1.3 std::unordered_set

2. 查找元素

2.1 std::vector

2.2 std::map

2.3 std::unordered_set

3. 遍历容器

3.1 std::vector

使用范围基for循环（range-based for loop）

使用迭代器：

3.2 std::map

3.3 std::unordered_set

4.删除元素

4.1 std::vector

4.2 std::map

4.3 std::unordered_set

5. 综合分析

6.优缺点对比

示例代码片段

7. 总结

---

在C++编程中，选择合适的容器对于代码的性能和功能至关重要。本文将对比分析 std::vector、std::map 和 std::unordered_set 这三种常用容器的使用方式、特点，特别是在添加元素、查找元素和遍历容器等方面的表现。

1.添加元素

1.1 std::vector

std::vector 是一个动态数组，支持快速随机访问，但在插入或删除元素时，可能需要移动大量数据。

std::vector<std::pair<int, int>> problems;  
problems.emplace_back(std::pair<int, int>(randomValue1, randomValue2));

1.2 std::map

std::map 是一种平衡二叉搜索树（红黑树）实现的有序关联容器，插入操作的时间复杂度为 O(log n)，且自动按键排序。

std::map<std::string, int> incorrectProblems;  
incorrectProblems.insert(std::pair<std::string, int>(exp, result.second));

1.3 std::unordered_set

std::unordered_set 是基于哈希表的无序关联容器，插入操作的平均时间复杂度为 O(1)，但在最坏情况下可能退化为 O(n)。

std::unordered_set<std::string> uniqueProblems;  
uniqueProblems.insert(exp);

2. 查找元素

2.1 std::vector

在 std::vector 中查找元素通常需要线性搜索，时间复杂度为 O(n)，但如果数据有序，可以使用二分查找优化。

auto it = std::find_if(problems.begin(), problems.end(),   [=](const auto& problem) {   return problem.first == value1 && problem.second == value2;   });

2.2 std::map

std::map 使用平衡二叉树结构，查找操作的时间复杂度为 O(log n)，且支持按键直接访问。

auto it = incorrectProblems.find(exp);  
if (it != incorrectProblems.end()) {  // 元素存在  
}

2.3 std::unordered_set

std::unordered_set 基于哈希表实现，查找操作的平均时间复杂度为 O(1)。

if (uniqueProblems.find(exp) != uniqueProblems.end()) {  // 元素存在  
}