深入理解C++ 容器类

承接Qt/C++软件开发项目，高质量交付，灵活沟通，长期维护支持。需求所寻，技术正适，共创完美，欢迎私信联系！

引言

        C++ 标准库提供了丰富的容器（container）类型，用于存储和管理数据。这些容器不仅简化了编程工作，还提供了高效的数据管理和操作方法。本文将详细介绍 C++ 中常见的标准容器类，包括顺序容器、关联容器以及无序关联容器，并探讨它们的特点、使用场景及性能表现。

1. 顺序容器（Sequence Containers）

        顺序容器是按照插入顺序存储元素的容器。它们支持随机访问、前向迭代和后向迭代。主要的顺序容器有 std::vector、std::deque、std::list 和 std::forward_list。

1.1 std::vector

• 特点：动态数组，支持快速随机访问。
• 优点：
  • 连续内存分配，访问速度快。
  • 支持高效的尾部插入和删除操作。
• 缺点：插入或删除中间元素效率较低，因为需要移动其他元素。
• 适用场景：当你需要快速访问和频繁在尾部插入/删除元素时。
• 示例代码：

#include <iostream>
#include <vector>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};vec.push_back(6); // 尾部插入for (const auto& elem : vec) {std::cout << elem << " ";}return 0;
}

1.2 std::deque（双端队列）

• 特点：两端都可以高效地插入和删除元素。
• 优点：
  • 支持快速的前端和尾端插入/删除操作。
  • 内存块不连续，但对用户透明。
• 缺点：随机访问比 std::vector 慢。
• 适用场景：需要频繁在两端进行插入和删除操作。
• 示例代码： 

#include <iostream>
#include <deque>int main() {std::deque<int> dq = {1, 2, 3};dq.push_front(0); // 前端插入dq.push_back(4);  // 尾部插入for (const auto& elem : dq) {std::cout << elem << " ";}return 0;
}

1.3 std::list（双向链表）

• 特点：双向链表，支持快速的任意位置插入和删除。
• 优点：插入和删除操作的时间复杂度为 O(1)，前提是已有迭代器指向插入点。
• 缺点：随机访问效率低。
• 适用场景：需要频繁在任意位置插入和删除元素。
• 示例代码：

#include <iostream>
#include <list>int main() {std::list<int> lst = {1, 2, 3};lst.insert(lst.begin(), 0); // 在开头插入lst.push_back(4);           // 在结尾插入for (const auto& elem : lst) {std::cout << elem << " ";}return 0;
}

1.4 std::forward_list（单向链表）

• 特点：单向链表，节省内存，只支持前向遍历。
• 优点：更少的内存开销，适用于只需要前向遍历的情况。
• 缺点：不支持双向遍历。
• 适用场景：当只需要前向遍历且希望节省内存时。
• 示例代码：

#include <iostream>
#include <forward_list>int main() {std::forward_list<int> flst = {1, 2, 3};flst.push_front(0); // 在开头插入for (auto it = flst.begin(); it != flst.end(); ++it) {std::cout << *it << " ";}return 0;
}

2. 关联容器（Associative Containers）

        关联容器以键值对的形式存储数据，并根据键自动排序。主要的关联容器有 std::set、std::map、std::multiset 和 std::multimap。

2.1 std::set

• 特点：键唯一，自动排序。
• 优点：查找、插入和删除操作的时间复杂度为 O(log n)。
• 适用场景：需要保证元素唯一性和有序性。
• 示例代码：

#include <iostream>
#include <set>int main() {std::set<int> s = {5, 1, 3, 2, 4};for (const auto& elem : s) {std::cout << elem << " ";}return 0;
}

2.2 std::map

• 特点：键值对，键唯一，自动排序。
• 优点：快速查找、插入和删除操作。
• 适用场景：需要键值映射关系，并且键必须唯一。
• 示例代码：

#include <iostream>
#include <map>int main() {std::map<std::string, int> m = {{"apple", 1}, {"banana", 2}};m["orange"] = 3;for (const auto& [key, value] : m) {std::cout << key << ": " << value << "\n";}return 0;
}

2.3 std::multiset

• 特点：允许重复键，自动排序。
• 适用场景：允许相同元素存在，并保持有序性。
• 示例代码： 

#include <iostream>
#include <set>int main() {std::multiset<int> ms = {1, 2, 2, 3};for (const auto& elem : ms) {std::cout << elem << " ";}return 0;
}

2.4 std::multimap

• 特点：键值对，允许重复键，自动排序。
• 适用场景：允许多个键映射到同一个值，并保持有序性。
• 示例代码： 

#include <iostream>
#include <map>int main() {std::multimap<int, std::string> mm = {{1, "apple"}, {1, "orange"}, {2, "banana"}};for (const auto& [key, value] : mm) {std::cout << key << ": " << value << "\n";}return 0;
}

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

        无序关联容器也以键值对形式存储数据，但不保证任何特定顺序。主要的无序关联容器有 std::unordered_set、std::unordered_map、std::unordered_multiset 和 std::unordered_multimap。

3.1 std::unordered_set

• 特点：键唯一，不保证顺序。
• 优点：平均查找、插入和删除操作的时间复杂度为 O(1)。
• 适用场景：需要快速查找、插入和删除操作，但不需要有序性。
• 示例代码： 

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> us = {1, 2, 3, 4, 5};for (const auto& elem : us) {std::cout << elem << " ";}return 0;
}

3.2 std::unordered_map

• 特点：键值对，键唯一，不保证顺序。
• 优点：平均查找、插入和删除操作的时间复杂度为 O(1)。
• 适用场景：需要快速查找、插入和删除操作，但不需要有序性。
• 示例代码：

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<std::string, int> um = {{"apple", 1}, {"banana", 2}};um["orange"] = 3;for (const auto& [key, value] : um) {std::cout << key << ": " << value << "\n";}return 0;
}

3.3 std::unordered_multiset

• 特点：允许重复键，不保证顺序。
• 适用场景：允许相同元素存在，但不需要有序性。
• 示例代码： 

#include <iostream>
#include <unordered_set>int main() {std::unordered_multiset<int> ums = {1, 2, 2, 3};for (const auto& elem : ums) {std::cout << elem << " ";}return 0;
}

3.4 std::unordered_multimap

• 特点：键值对，允许重复键，不保证顺序。
• 适用场景：允许多个键映射到同一个值，但不需要有序性。
• 示例代码： 

#include <iostream>
#include <unordered_map>int main() {std::unordered_multimap<int, std::string> umm = {{1, "apple"}, {1, "orange"}, {2, "banana"}};for (const auto& [key, value] : umm) {std::cout << key << ": " << value << "\n";}return 0;
}

总结

        C++ 标准库中的容器类为开发者提供了强大的工具来管理数据。选择合适的容器类型取决于具体的应用需求，例如是否需要有序性、是否允许重复元素、是否需要快速的查找和插入等。通过合理选择和使用这些容器，可以编写出更高效、更易维护的代码。