怎样使用C++标准库容器 vector map set核心操作

c++++标准库中的vector、map和set分别适用于动态数组、键值对存储和唯一元素集合场景。1. vector支持动态大小数组，常用操作包括push_back、emplace_back添加元素，at或下标访问，erase删除元素，reserve预分配内存而不改变大小，resize则改变元素数量并初始化；2. map基于红黑树实现，键唯一且有序，通过insert、emplace插入，find查找，erase删除，支持自定义排序如使用函数对象或lambda表达式；3. set存储唯一有序元素，操作与map类似，插入重复元素会被忽略；4. 选择容器时，若需随机访问和尾部操作选vector，若需键值对且有序选map，若需快速查找唯一元素且有序选set；5. 对性能要求高且无需排序时，可选用unordered_map或unordered_set，其基于哈希表，平均查找时间复杂度为o(1)；6. 自定义排序需满足严格弱排序规则，可通过函数对象、lambda或函数指针实现。正确选择容器能显著提升程序效率和代码质量。

C++标准库容器

vector

、

map

、

set

提供了高效的数据存储和管理方式。掌握它们的核心操作，能显著提升C++编程效率和代码质量。下面我们深入探讨这些容器的使用方法。

解决方案

vector

、

map

和

set

是C++ STL (Standard Template Library) 中最常用的容器。它们分别代表了动态数组、键值对映射和集合这三种基本的数据结构。

立即学习“C++免费学习笔记（深入）”；

• vector

  : 动态数组，可以动态地调整大小。

• map

  : 存储键值对，其中键是唯一的，并且按照某种顺序排列。

• set

  : 存储唯一的元素，并且按照某种顺序排列。

以下是一些核心操作的示例和解释：

vector

• 包含头文件:

  #include <vector>

• 创建

  vector

  :

  std::vector<int> myVector; // 创建一个存储int类型的空vector std::vector<int> myVector2(10); // 创建一个包含10个int元素的vector，默认值为0 std::vector<int> myVector3(10, 5); // 创建一个包含10个int元素的vector，每个元素的值为5 std::vector<int> myVector4 = {1, 2, 3, 4, 5}; // 使用初始化列表

• 添加元素:

  myVector.push_back(10); // 在vector末尾添加一个元素 myVector.emplace_back(20); // 类似于push_back，但是更高效，尤其是在添加对象时

• 访问元素:

  int firstElement = myVector[0]; // 使用下标访问（不进行边界检查） int secondElement = myVector.at(1); // 使用at()访问（进行边界检查，越界会抛出异常） int lastElement = myVector.back(); // 访问最后一个元素 int* dataPtr = myVector.data(); // 获取指向内部数组的指针（C++11）

• 删除元素:

  myVector.pop_back(); // 删除最后一个元素 myVector.erase(myVector.begin() + 2); // 删除索引为2的元素 myVector.erase(myVector.begin(), myVector.begin() + 3); // 删除一个范围内的元素 myVector.clear(); // 删除所有元素

• 大小和容量:

  size_t size = myVector.size(); // 获取vector中元素的数量 size_t capacity = myVector.capacity(); // 获取vector分配的内存大小 myVector.reserve(100); // 预分配100个元素的空间，避免频繁重新分配 myVector.shrink_to_fit(); // 释放多余的内存空间（C++11）

• 迭代:

  for (size_t i = 0; i < myVector.size(); ++i) {     std::cout << myVector[i] << " "; }  for (auto it = myVector.begin(); it != myVector.end(); ++it) {     std::cout << *it << " "; }  for (int element : myVector) { // 范围for循环 (C++11)     std::cout << element << " "; }

map

• 包含头文件:

  #include <map>

• 创建

  map

  :

  std::map<std::string, int> myMap; // 创建一个键为string，值为int的map std::map<int, std::string, std::greater<int>> myMap2; // 创建一个键为int，值为string的map，并使用std::greater<int>排序（降序）

• 插入元素:

  myMap["apple"] = 1; // 使用下标插入 myMap.insert({"banana", 2}); // 使用insert插入pair myMap.emplace("cherry", 3); // 使用emplace直接构造元素（更高效）

• 访问元素:

  int appleCount = myMap["apple"]; // 使用下标访问（如果键不存在，会插入一个默认值） int bananaCount = myMap.at("banana"); // 使用at()访问（如果键不存在，会抛出异常）

• 查找元素:

  auto it = myMap.find("apple"); if (it != myMap.end()) {     std::cout << "Found apple: " << it->second << std::endl; } else {     std::cout << "Apple not found" << std::endl; }

• 删除元素:

  myMap.erase("apple"); // 删除键为"apple"的元素 myMap.erase(myMap.find("banana")); // 使用迭代器删除元素 myMap.clear(); // 删除所有元素

• 大小:

  size_t size = myMap.size(); // 获取map中元素的数量

• 迭代:

  for (auto it = myMap.begin(); it != myMap.end(); ++it) {     std::cout << it->first << ": " << it->second << std::endl; }  for (auto const& [key, val] : myMap) { // 范围for循环 (C++17)     std::cout << key << ": " << val << std::endl; }

set

• 包含头文件:

  #include <set>

• 创建

  set

  :

  std::set<int> mySet; // 创建一个存储int类型的set std::set<int, std::greater<int>> mySet2; // 创建一个存储int类型的set，并使用std::greater<int>排序（降序）

• 插入元素:

  mySet.insert(10); mySet.insert(20); mySet.insert(10); // 插入重复元素会被忽略 mySet.emplace(30); // 使用emplace直接构造元素（更高效）

• 查找元素:

  auto it = mySet.find(20); if (it != mySet.end()) {     std::cout << "Found 20" << std::endl; } else {     std::cout << "20 not found" << std::endl; }

• 删除元素:

  mySet.erase(20); // 删除值为20的元素 mySet.erase(mySet.find(30)); // 使用迭代器删除元素 mySet.clear(); // 删除所有元素

• 大小:

  size_t size = mySet.size(); // 获取set中元素的数量

• 迭代:

  for (auto it = mySet.begin(); it != mySet.end(); ++it) {     std::cout << *it << " "; }  for (int element : mySet) { // 范围for循环 (C++11)     std::cout << element << " "; }

如何选择合适的C++容器：vector, map, set？

选择容器取决于你的具体需求。

• vector

  : 当你需要一个动态数组，并且需要频繁地在末尾添加或删除元素时，

  vector

  是一个很好的选择。它提供快速的随机访问，但在中间插入或删除元素效率较低。

• map

  : 当你需要存储键值对，并且需要根据键快速查找值时，

  map

  是理想的选择。

  map

  内部使用红黑树实现，保证了插入、删除和查找操作的对数时间复杂度。

• set

  : 当你需要存储唯一的元素，并且需要快速查找元素是否存在时，

  set

  是合适的选择。

  set

  也使用红黑树实现，保证了插入、删除和查找操作的对数时间复杂度。另外，

  set

  会自动排序元素。

如果需要保持插入顺序，

std::unordered_map

和

std::unordered_set

(基于哈希表) 提供了平均常数时间的查找，但牺牲了排序特性。

vector

的

reserve

和

resize

有什么区别？何时使用？

reserve

和

resize

都是

vector

中用于管理内存的函数，但它们的作用不同。

• reserve(n)

  : 预分配至少能容纳

  n

  个元素的内存空间，但不会改变

  vector

  的大小(

  size

  )。这意味着

  vector

  仍然是空的，不能通过下标访问这些预留的空间。

  reserve

  主要用于避免

  vector

  在添加元素时频繁地重新分配内存，从而提高性能。

• resize(n)

  : 改变

  vector

  的大小(

  size

  )为

  n

  。如果

  n

  小于当前大小，则删除多余的元素；如果

  n

  大于当前大小，则添加新的元素，并使用默认值初始化。

  resize

  会直接影响

  vector

  中元素的数量。

何时使用？

• 当你预先知道

  vector

  需要存储多少个元素，但还没有元素数据时，使用

  reserve

  可以避免不必要的内存重新分配。

• 当你需要改变

  vector

  中元素的数量，并且需要初始化新增的元素时，使用

  resize

  。

举例：

std::vector<int> myVector; myVector.reserve(100); // 预分配100个int的空间，size仍然为0  for (int i = 0; i < 100; ++i) {     myVector.push_back(i); // 添加元素，不会触发重新分配 }  std::vector<int> myVector2; myVector2.resize(100); // size变为100，所有元素初始化为0  for (int i = 0; i < myVector2.size(); ++i) {     myVector2[i] = i; // 可以直接通过下标访问元素 }

map

和

unordered_map

的区别？如何选择？

map

和

unordered_map

都是C++中用于存储键值对的容器，但它们的实现方式和性能特点不同。

• map

  : 基于红黑树实现，键是有序的。插入、删除和查找操作的时间复杂度为O(log n)，其中n是

  map

  中元素的数量。

  map

  的优点是键是有序的，可以方便地进行范围查找。

• unordered_map

  : 基于哈希表实现，键是无序的。平均情况下，插入、删除和查找操作的时间复杂度为O(1)，但在最坏情况下可能退化为O(n)。

  unordered_map

  的优点是平均查找速度快，但缺点是键是无序的，且需要额外的内存空间来存储哈希表。

如何选择？

• 如果你需要键是有序的，或者需要进行范围查找，那么选择

  map

  。

• 如果你对键的顺序没有要求，并且需要尽可能快的查找速度，那么选择

  unordered_map

  。

• 如果数据量很小，

  map

  和

  unordered_map

  的性能差异可能不明显。

• unordered_map

  对哈希函数的要求较高，需要选择合适的哈希函数来避免哈希冲突，从而保证性能。

总的来说，

unordered_map

在大多数情况下比

map

更快，但

map

在某些特定场景下仍然有其优势。选择哪个容器取决于你的具体需求。

set

和

unordered_set

的区别？如何选择？

set

和

unordered_set

类似于

map

和

unordered_map

， 它们都是存储唯一元素的容器，区别在于底层实现和性能特性。

• set

  : 基于红黑树实现，元素是有序的。插入、删除和查找操作的时间复杂度为O(log n)。

• unordered_set

  : 基于哈希表实现，元素是无序的。平均情况下，插入、删除和查找操作的时间复杂度为O(1)，最坏情况下可能退化为O(n)。

如何选择？

• 如果你需要元素是有序的，或者需要进行范围查找，那么选择

  set

  。

• 如果你对元素的顺序没有要求，并且需要尽可能快的查找速度，那么选择

  unordered_set

  。

选择原则与

map

和

unordered_map

类似， 考虑是否需要排序以及对查找速度的要求。

如何自定义排序规则用于

set

或

map

？

可以通过以下几种方式自定义排序规则：

1. 函数对象 (Functor): 创建一个类，重载

   operator()

   ，实现自定义的比较逻辑。

   struct MyComparator {     bool operator()(const int& a, const int& b) const {         return a > b; // 降序排列     } };  std::set<int, MyComparator> mySet; std::map<int, std::string, MyComparator> myMap;

2. Lambda 表达式 (C++11): 使用 lambda 表达式定义比较函数。

   auto myComparator = [](const int& a, const int& b) {     return a > b; // 降序排列 };  std::set<int, decltype(myComparator)> mySet(myComparator); std::map<int, std::string, decltype(myComparator)> myMap(myComparator);

3. 函数指针: 定义一个函数，然后将函数指针传递给

   set

   或

   map

   。 （不常用，因为不如函数对象或 lambda 灵活）

无论使用哪种方式，比较函数都必须满足严格弱排序 (strict weak ordering) 的要求。这意味着对于任意元素 a, b, c：

• comp(a, a)

  必须为

  false

  (非自反性)

• 如果

  comp(a, b)

  为

  true

  ，则

  comp(b, a)

  必须为

  false

  (反对称性)

• 如果

  comp(a, b)

  为

  true

  且

  comp(b, c)

  为

  true

  ，则

  comp(a, c)

  必须为

  true

  (传递性)

不满足严格弱排序会导致未定义行为。