C++ STL 容器与容器适配器

发表于 更新于 分类于 Disqus： 本文字数： 2.9k

前言

C++ STL 容器与容器适配器简记，这是一篇用法与底层实现思想的简记，不含源码解析。

顺序容器

主要有这些： 顺序容器

  • arrary:定长数组
  • vector：动态数组
  • deque ：双端队列
  • list：双向循环链表
  • forward_list：单向链表

STL 库中的容器（以及 String）有一些相似的方法和特点，例如使用operator=赋值或assign()赋值，用operator==可以判相等等等，下面是一些个人觉得常见的方法。不过这些方法也并不一定是对所有容器有效，应该根据实际容器的特点来。（例如对于一个定长的array，显然我们也没办法要求 resize()或者push） 迭代器：

  • begin()：指向开始的迭代器
  • end()：指向末尾的迭代器

容量：

  • size()：当前大小
  • empty()：是否为空
  • max_size：理论上的最大大小。例如对于vector是可用 RAM 大小，对 array 则是声明的大小。

元素访问：

  • operator[]：C风格的下标访问
  • at()：operator[]的不越界安全替代品
  • front：第一个元素
  • back()：最后一个元素

以及修改操作：

  • push(_back)：压入一个元素（到尾部）
  • pop(_back)：弹出一个元素（从尾部）
  • emplace()：原地构造一个元素放入（对于自定义类型，避免来回构造析构不必要的临时变量）
  • swap()：交换
  • insert()：在指定位置前插入元素
  • resize()：重整大小，小于原值就删去那些元素
  • clear()：清空所有
  • erase()：清空指定位置元素

Array

这是对 C 中的简单的 int a[] 这样的数组的替代品，提高了安全性。因此它也如原始数组一样不能变长等。

  • fill()：用指定元素赋值。

Vector

动态长度的数组。

  • 在中间和前方插入值会消耗较多的时间，因为要挨个挪后面的元素。
  • 内存结构：vector所采用的数据结构非常简单，线性连续空间（即数组），两个迭代器 Myfirst和 Mylast 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 _Myend 指向整块连续内存空间的尾端。
  • 扩容：扩充空间是“配置新空间-数据移动-释放旧空间”的大工程,时间成本很高。因此当容器满的时候，vector 会另辟一段空间（大小为 2^N ），将旧空间的内容复制到新空间然后释放旧空间。如果容器内存放的是自定义类型，那么C++会使用 move 将所有权转移到新空间内，而不是挨个调用构造函数。
  • 迭代失效：对 vector 的任何操作，一旦引起空间的重新分配，指向原 vector 的所有迭代器就都失效了。

Deque：双端队列

deque 容器可以对其两段的数据进行操作，支持随机访问。它不需要像 vector 那样重新配置空间来扩容，因此，deque 没有 capacity 属性，没有 reserve() 功能。

  • 在前端插入删除和后端插入删除一样方便，但是中间会需要挪元素。

deque 容器存储数据的空间是由一段一段等长的连续空间（数组）构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。为了管理这些连续空间，deque 容器用数组存储着各个连续空间的首地址。也就是说，容器中实际存储的都是指针，指向那些真正用来存储数据的各个连续空间。

这提高了在序列两端添加或删除元素的效率，但也使容器迭代器的底层实现变得更复杂。

为了实现遍历 deque 容器的功能，deque 迭代器定义了如下的结构(迭代的是那个指针数组的元素)：

1
2
3
4
5
6
7
8
template<class T,...>
struct __deque_iterator{
    ...
    T* cur;
    T* first;
    T* last;
    map_pointer node;//map_pointer 等价于 T**
}

迭代器内部包含 4 个指针，它们各自的作用为：

  • cur：指向当前正在遍历的元素；
  • first：指向当前连续空间的首地址；
  • last：指向当前连续空间的末尾地址；
  • node：指向指针数组中“指向当前连续空间的指针”。

其中：

  • start 迭代器记录着 map 数组中首个连续空间的信息。start 迭代器中的 cur 指针指向的是连续空间中首个元素；
  • finish 迭代器记录着 map 数组中最后一个连续空间的信息。 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//当迭代器处于当前连续空间边缘的位置时，如果继续遍历，就需要跳跃到其它的连续空间中，该函数可用来实现此功能
void set_node(map_pointer new_node){
    node = new_node;//记录新的连续空间在 map 数组中的位置
    first = *new_node; //更新 first 指针
    //更新 last 指针，difference_type(buffer_size())表示每段连续空间的长度
    last = first + difference_type(buffer_size());
}
//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重载前置 ++ 运算符
self & operator++(){
    ++cur;
    //处理 cur 处于连续空间边缘的特殊情况
    if(cur == last){
        //调用该函数，将迭代器跳跃到下一个连续空间中
        set_node(node+1);
        //对 cur 重新赋值
        cur = first;
    }
    return *this;
}
//重置前置 -- 运算符
self& operator--(){
    //如果 cur 位于连续空间边缘，则先将迭代器跳跃到前一个连续空间中
    if(cur == first){
        set_node(node-1);
        cur == last;
    }
    --cur;
    return *this;
}

内存调度策略

如果 deque 数组的总空间大于目前使用空间的两倍，那么不会重新分配内存。

否则会使用 reallocate_map()函数, 空间不足时：

  • deque空间实际足够：这种情况由总是在一个方向插值造成

    • deque内部进行调整 start , 和 finish

      当 deque 后端缓存耗尽时， deque 会将start复制到中间； 当 deque 前端缓存耗尽时， deque 会从后往前复制，将 start 复制到中间。（如果不从后向前复制，那么 start 移动后可能会落在之前的区间内，这时进行复制会覆盖尚未被复制的后部数据）。

  • deque空间真的不足
    • 申请更大的空间
    • 拷贝元素过去
    • 修改 map 和 start, finish 指向

如果 deque 数组总空间小于目前使用空间的两倍。那么其会根据下列公式计算扩增倍数。

1
__new_size = _M_size+max(_M_size,__nodes_to_add)+2

可以看出是至少 2 倍扩容，通过比较当前 deque 数组大小与插入节点数，同时还预留一个为 2 的常数，防止频繁map的重新分配。

List：双向循环链表

list 就是一个双向循环链表，list 节点有 prev 和 next 两个指针。对于任何位置的元素插入或元素移除， list 永远是常数时间。

既然是链表，因此它有一些链表的特点

  • 插入、接合操作，不会造成迭代器失效。即使删除操作，只有指向删除元素的那个迭代器失效。
  • 无法随机存取，但是方便随机插入删除。
  • 不预留空间，每分配一个就是内存中取一块地。

node 指向尾端的一个空白节点，就能符合 ”前闭后开“ 区间的要求。

Forward_list：单向链表

具有和 list 容器相同的特性，但是单链表只能从前向后遍历，而不支持反向遍历。

关联式容器

关联式容器大体可以分为 set 和 map ，有序的均是以RB-Tree（红黑树）为底层架构，无序的（ Unordered_ 前缀）以哈希表为底层架构。

  • set/multiset
  • map/multimap
  • unordered_set/map/multiset/multimap

关联容器插入删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。而是键-值映射。

除了顺序容器中提到的各种方法，关联式容器中还常有

  • count()：匹配指定键的元素个数。
  • find()：找指定键的元素。
  • merge()：从另一个容器合并结点。
  • equal_range()：等于给定键的元素范围（？）。
  • lower/upper_bound():首个不小于/大于指定键的元素的迭代器。（再次提醒是不小于，不是小于）。
  • contains()(c++20):是否包含指定键。
  • extract()（c++17）：从另一个容器提取结点。

Set/ Multiset：集合

  • 元素既是键(value)又是值(value)。
  • 键（即元素）是不可被修改的。
  • insert()函数插入之后会自行被排序，默认是升序
  • set 不可插入重复值，multiset 则可以；

Map/Multimap：映射（键值对）

  • 类比 python 中的字典，拥有键值（key）和实值（value）
  • 所有元素都会根据键值来自动排序，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效。
  • map 中不允许出现重复键值， multimap 中允许。
  • map 重载了operator[]，但是 multimap 没有，因为键是不唯一的。

由于 map 是键值对，因此定义了 pair，这是一个有两个值的简单模板结构体。其中第一个值（键）是 const，即键无法修改，值可以修改。它还重载了 operator== 、构造等。而 map 就是一个 pair 结构的红黑树。

Unordered_xxxx

上述四种容器在 C++11 后均增加了 unordered_ 类。其与上述四种容器的区别是底层实现原理为哈希表。

这造成了两点重要影响：

  1. 不支持排序，迭代器做范围访问时效率更低（迭代器自加自减的访问效率更低）；
  2. 直接访问元素的速度更快（尤其在规模很大时），因为直接计算 key 的哈希值是O(1)复杂度。

容器适配器

容器适配器是一个封装了序列容器的一个类模板，它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器，是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能

stack：栈

栈是什么就不必多说了。默认情况下 stack 底层容器是 deque 。也可以指定底层容器，标准容器 vector、deque、list 均符合需求。

stack 不提供遍历和随机访问功能，也不提供迭代器。只有 push 和 pop 操作。

queue：队列

默认情况下 queue 底层容器是 deque。

队列是一种 FIFO 的数据结构，允许从一端新增元素，从另一端移除元素。

queue不提供遍历功能，也不提供迭代器。

pripority_queue：优先队列/堆

优先队列的默认容器是 vector。

优先队列的核心特点在于其严格弱序特性（strict weak ordering）：也即 priority_queue 保证容器中的第一个元素始终是所有元素中最大的。为此，用户在实例化一个 priority_queue 时，必须为元素类型重载<运算符，以用于元素排序。

更进一步的认识

更进一步当然就是需要阅读源码，除了源代码，也可以参考