STL容器总览

发表于 |

本章主要介绍STL容器，包括各类型容器的内部数据结构，常用操作以及性能差异。

STL容器提供了各种满足使用者需求的功能，其中有三种核心特性：

  • 所有容器提供值传递而不是引用传递语义。当一个元素被插入到容器中时，容器内部会拷贝和移动已有元素而不是通过管理元素的引用。
  • 容器中的元素是按照一定顺序分布的。每种类型的容器均提供了返回指向元素的迭代器的方法。而迭代器作为STL算法相关函数的主要入参，友好的将STL容器和算法串联起来。
  • 通常情况下，容器上的操作并不是安全的。它们并没有办法检测到所有错误或异常。因此需要调用者来保证以正确的方式来使用容器。

操作

C++标准定义一系列的标准（需求）来要求所有的STL容器需要遵循。不过由于C++11中提供了多样化的容器，而且可能在某些操作上，会存在异常情况，因此并不是所有容器都实现了标准定义的需求。同时，也不仅仅受限于标准，部分容器还提供了标准以外的接口支持。

以下列出大部分容器均支持的操作,其中Req一列标识着对应的操作为C++标准中所提出。

Operation Req Effect
ContType c Yes 缺省构造函数，创建一个空的容器
ContType c(c2) Yes 拷贝构造函数，通过c2拷贝一个新的容器
ContType c = c3 Yes 拷贝构造函数
ContType c(rv) Yes 移动构造函数，创建一个新的容器，接管右值引用类型rv中的元素（C++ 11）
ContType c = rv Yes 移动构造函数
ContType c(beg, end) - 创建一个新的容器并以[beg, end)区间内的元素初始化(Array不支持)
ContType c(initlist) - 通过initlist进行初始化（C++ 11）
ContType c = initlist - 同上
c.~ContType() Yes 析构函数，释放所有资源
c.empty() Yes 返回容器是否为空（性能优于size()==0）
c.size() Yes 返回当前容器中的元素个数（forward_list<>不支持）
c1.swap(c2) Yes 交换c1和c2的元素
c.clear() - 清除容器中所有的元素（并不会释放容器所占用的内存）

自C++11之后，用户可以通过移动构造来初始化一个容器

1
2
3
4
std::vector<int> v1;
//move contents of v1 into v2, state of v1 undefined afterward
std::vector<int> v2 = std::move(v1);

v2创建并且以v1内元素进行了初始化，这之后v1的行为将变得undefined,原因是这是一种移动构造，v1内的元素通过指针交换的形式，赋给了v2,使得v2可以通过指针来访问原本属于v1的元素。元素本身占用的内存并没有发生变化，v1内的指针值变成了NULL。也正因为如此，不存在任何拷贝元素的操作，使得性能大幅度提升。所以，当你确定某个容器不在需要时，可以使用move构造。

赋值操作：需要拷贝所有源容器内元素并且移除目标容器内已有的元素，因此该操作代价相当的昂贵

谢天谢地，我们有移动语义（Since C++11）

C++98中提供了swap()接口，同样的仅仅是在内部进行指针的交换。所以swap可以保证是常数时间复杂度，而不像拷贝操作的线性复杂度。需要注意的是，array<>在swap上的表现不像其他容器。++原因将在后面单独分析array时补充++。

所有容器都提供了一些通用类型的定义，详见下表

Type Req Effect
size_type Yes Unsigned integral type for size values
difference_type Yes Signed integral type for difference values
value_type Yes Type of the elements
reference Yes Type of element reference
const_reference Yes Type of constant element reference
iterator Yes Type of iterators
const_iterator Yes Type of constant iterators
pointer - Type of pointers to elements(since C++11)
const_pointer - Type of pointers to read-only elements(since C++11)