STL容器全解析：从通用能力到数组应用

### STL容器全解析：从通用能力到数组应用 #### 1. STL容器概述 STL（标准模板库）容器是C++编程中非常重要的一部分，它提供了多种数据结构来存储和管理数据。这些容器具有不同的特性和性能，适用于不同的场景。了解它们的通用能力、操作以及如何选择合适的容器，对于高效的C++编程至关重要。 #### 2. 通用容器能力与操作 ##### 2.1 容器能力 STL容器类通常需要满足以下三个核心能力： - **值语义**：容器在插入元素时会复制和/或移动元素，而不是管理元素的引用。因此，理想情况下，STL容器的每个元素都必须能够被复制和移动。如果要存储的对象没有公共的复制构造函数，或者复制操作不实用（例如耗时过长或元素需要同时存在于多个容器中），可以仅使用移动操作，或者容器元素必须是指向这些对象的指针或指针对象。 - **元素有序**：容器内的元素有特定的顺序，每种容器类型都提供了返回迭代器的操作，用于遍历元素。这是STL算法的关键接口。只要不插入或删除元素，多次遍历元素时顺序保持不变，即使是“无序容器”也是如此，只要不调用添加、删除元素或强制内部重组的操作。 - **操作非安全**：一般来说，操作不会检查所有可能的错误，调用者必须确保操作的参数满足操作的要求。违反这些要求（如使用无效索引）会导致未定义行为。通常，STL本身不会抛出异常，但如果STL容器调用的用户定义操作抛出异常，行为会有所不同。 ##### 2.2 容器操作 标准规定了一系列适用于所有STL容器的通用要求，但由于C++11提供了多种容器，可能存在例外情况，有些容器甚至不满足所有通用容器要求，并且所有容器还提供了额外的操作。以下是一些常见操作： **初始化操作** | 操作 | 是否为通用要求 | 效果 | | --- | --- | --- | | `ContType c` | 是 | 默认构造函数，创建一个空容器（`array<>`会得到默认元素） | | `ContType c(c2)` | 是 | 复制构造函数，创建一个新容器，作为`c2`的副本 | | `ContType c = c2` | 是 | 复制构造函数，创建一个新容器，作为`c2`的副本 | | `ContType c(rv)` | 是 | 移动构造函数，创建一个新容器，获取右值`rv`的内容（C++11起，`array<>`除外） | | `ContType c = rv` | 是 | 移动构造函数，创建一个新容器，获取右值`rv`的内容（C++11起，`array<>`除外） | | `ContType c(beg,end)` | 否 | 创建一个容器，并用`[beg,end)`范围内的所有元素的副本初始化（`array<>`除外） | | `ContType c(initlist)` | 否 | 创建一个容器，并用初始化列表`initlist`的值的副本初始化（C++11起，`array<>`除外） | | `ContType c = initlist` | 否 | 创建一个容器，并用初始化列表`initlist`的值的副本初始化（C++11起） | | `c.~ContType()` | 是 | 删除所有元素并释放内存（如果可能） | 初始化列表构造函数提供了一种方便的方式来指定初始值，特别适用于初始化常量容器。例如： ```cpp const std::vector<int> v1 = { 1, 2, 3, 5, 7, 11, 13, 17, 21 }; const std::vector<int> v2 { 1, 2, 3, 5, 7, 11, 13, 17, 21 }; std::unordered_set<std::string> w = { "hello", std::string(), "" }; ``` 给定范围的构造函数允许使用另一个容器的元素、C风格数组或标准输入来初始化容器。例如： ```cpp std::list<int> l; std::vector<float> c(l.begin(),l.end()); int carray[] = { 2, 3, 17, 33, 45, 77 }; std::set<int> c(std::begin(carray),std::end(carray)); std::deque<int> c{std::istream_iterator<int>(std::cin), std::istream_iterator<int>()}; ``` **赋值与交换操作** - **赋值**：赋值容器时，会复制源容器的所有元素，并删除目标容器中的所有旧元素，因此容器赋值相对昂贵。从C++11开始，可以使用移动赋值语义，内部只是交换指向值内存的指针，而不是复制所有值。 ```cpp std::vector<int> v1; std::vector<int> v2; v2 = std::move(v1); ``` - **交换**：所有容器从C++98开始提供`swap()`成员函数，用于交换两个容器的内容。实际上，它只交换一些指向数据的内部指针，因此`swap()`操作的复杂度是常数级的。对于`array<>`类型的容器，`swap()`的行为略有不同，它的复杂度是线性的，迭代器和引用仍然指向同一个容器，但指向不同的元素。 **大小操作** 几乎所有容器类都提供以下三种大小操作： - `empty()`：返回容器中的元素数量是否为零，建议优先使用它而不是`size()==0`，因为它可能比`size()`更高效，并且`forward_list<>`不提供`size()`操作。 - `size()`：返回容器当前的元素数量，`forward_list<>`不提供此操作。 - `max_size()`：返回容器可能包含的最大元素数量，该值由实现定义。 **比较操作** 对于除无序容器外的所有容器，定义了通常的比较运算符`==`、`!=`、`<`、`<=`、`>`和`>=`，遵循以下规则： - 两个容器必须是相同类型。 - 如果两个容器的元素相等且顺序相同，则它们相等，使用`==`运算符检查元素的相等性。 - 使用字典序比较来检查一个容器是否小于另一个容器。 对于无序容器，仅定义了`==`和`!=`运算符，当一个容器中的每个元素在另一个容器中都有相等的元素时，它们返回`true`，元素顺序无关紧要。 **元素访问** 所有容器都提供迭代器接口，支持基于范围的`for`循环。从C++11开始，访问所有元素的最简单方法是： ```cpp for (const auto& elem : coll) { std::cout << elem << std::endl; } ``` 如果要操作元素，可以去掉`const`： ```cpp for (auto& elem : coll) { elem = ...; } ``` 也可以使用迭代器进行读写访问： ```cpp for (auto pos=coll.cbegin(); pos!=coll.cend(); ++pos) { std::cout << *pos << std::endl; } for (auto po ```