STL之容器初窥

STL介绍

为了建立数据结构和算法的一套标准，并且降低其间的耦合（coupling）关系以提升各自的独立性、弹性、交互操作性，C++社群里诞生了STL。

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

• 容器：各种数据结构，如vector，list，deque，set，map等用来存放数据。
• 算法：各种常用算法如sort，search，copy，erase等等
• 迭代器：扮演容器与算法之间的胶合器，是所谓的泛型指针，共有五种类型。每种容器都有自己的迭代器
• 仿函数：行为类似函数，可作为算法的某种策略
• 配接器：一种用来修饰容器或仿函数或迭代器接口的东西。例如STL提供的queue和stack，虽然看似容器，其实只是容器的配接器，因为它们的底层完全借助deque，所有的操作都有底层的deque提供。
• 配置器：负责空间配置与管理。

STL六大组件的交互关系：Container 通过 Allocator 获取数据存储空间，Algorithm 通过 Iterator 操纵 Container 内容，Functor 可以协助 Algorithm 完成不同的策略，Adapter 可以修饰或套接 Functor。

注意：STL不仅包含面向对象的编程，还包含了一种不同的编程模式——泛型编程（generic programming）。

STL的版本很多，常见的有HP STL、PJ STL、 SGI STL等。

在C++标准中，STL被组织为下面的13个头文件：< algorithm >、< deque >、< functional >、< iterator >、< vector >、< list >、< map >、< memory.h >、< numeric >、< queue >、< set >、< stack >和< utility >。

迭代器

理解迭代器是理解 STL 的关键所在。模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。因此，它们都是 STL 通用方法的重要组成部分。迭代器的部分下次再研究，这次就研究容器了。

容器

STL 中容器分为序列式（sequence）和关联式（associative）两种。序列式容器包括：

• array（C++内建）
• vector（类似array，但有自动扩容）
• heap（以算法形式 xxx_heap 呈现）
• priority_queue（底层实现是vector+heap算法）
• list（环状链表，有伪头结点）
• slist（非标准，单向链表，有伪头结点）
• deque（双向开口容器，数组和链表结合）
• stack（配接器，底层实现为deque封住头部开口）
• queue（配接器，底层实现为deque封住头部的插入和尾部的弹出，只能头部弹出、尾部插入）

关联式容器包括：

• RB_tree（非公开）
• set（以 RB-tree为底层实现）
• map（以 RB-tree为底层实现）
• multiset（以 RB-tree为底层实现）
• multimap（以 RB-tree为底层实现）
• hashtable（非标准）
• hash_set（非标准，以hashtable为底层实现）-> unordered_set
• hash_map（非标准，以hashtable为底层实现） -> unordered_map
• hash_multiset（非标准，以hashtable为底层实现） -> unordered_multiset
• hash_multimap（非标准，以hashtable为底层实现） -> unordered_multimap

序列式容器

vector

• vector和array类似，都是连续的存储空间。但是array空间固定了就不能自动更改，而vector空间可以。如果当前的数据超过了当前容量，那么vector将会扩容。

• vector的内部都是由迭代器控制，共有5个迭代器，其中3个是底层的protected的迭代器，分别是start，finish，end_of_storage，分别表示目前使用空间的头，目前使用空间的尾，目前可用空间的尾。另外两个迭代器就是我们熟知的public 的 begin 和 end，begin 就等于start，end就等于finish。容器的行为如size()，capacity()，back()等就是基于上述几个迭代器的加减运算而来。
• erase 函数是有返回值的，返回类型是迭代器，erase 函数删除当前迭代器后后面迭代器会往前移动一个单位，然后函数返回移动到当前位置的迭代器（也就是删除迭代器的下一个迭代器），vector删除元素后会造成后面的迭代器失效，实际上失效有两种可能：一种是删除元素导致后面元素前移，但是迭代器指向的内存空间位置还是没变，所以迭代器指向的内容就发生了变化，原来最后一个元素的迭代器变成了end()。另一种可能是添加元素，导致重新配置内存空间，配置到另一个不同的内存空间，这时原来元素全都被复制，原来内存空间被释放，因此迭代器失效（但是我没遇到过）
• vector的迭代器就是普通指针。因为vector维护的是一个连续的线性空间，普通指针就可以满足其迭代器的要求，如operator*，operator+，operator-，operator++，operator–，operator+=，operator-=，operator->。
• vector 扩容：如果当前插入元素后元素数量大于当前capacity，那么就会发生扩容。系统会找到一块大小为当前capacity 两倍的连续存储空间，再将原来空间的数据一一复制上去，最后还要释放原来空间。总的来说就是重新配置、元素复制、释放原空间的过程。

list

• list 是链式存储空间，因此对于任何位置的插入和删除时间都是常数时间，空间也毫不浪费。删除元素也不会造成其它迭代器失效
• list 的迭代器不能使用普通指针，因为普通指针在链式存储空间里没有递增递减功能。list是双向链表（还是环状的！），因此其迭代器可以进行加减运算。
• list 环状中有一个空结点node，用于表示最后一个元素的下一个元素（end()）,这样就符合了 STL 前闭后开的区间要求，由于是双向链表，因此迭代器begin就是空结点下一个结点node->next(迭代器有自己的实现)，end()就是该空结点。
• list 内部提供了一个transfer(position, first, last)操作，用于将区间[first, last)内的连续结点移动到position之前。这个操作为其它的复杂操作如splice、sort、merge等奠定了良好的基础。
• list不能使用STL的sort函数，因为其迭代器不是可以随机存取的，所以list只能使用自己的sort()函数(使用quick sort)

deque

• vector是一种单向开口容器，而deque是一种双向开口容器，意思是在头尾两端都能做元素的插入和删除操作（常数时间，vector那种靠移动元素的就不说了，效率奇差）。
• deque也是连续线性存储空间，其迭代器也支持随机访问，但是其迭代器不是简单的普通指针，除非必要，通常选择vector而不是deque。
• 对deque做排序：通常为了最大效率，是将其完整复制到一个vector上做sort，然后再复制回来。
• 为什么deque效率低呢？因为它是分段连续存储空间，结合了数组和链表的优点。每一个段或者说是缓冲区有一个默认大小，根据插入元素来计算需要多少个缓冲区，这些缓冲区都连续，但缓冲区之间不连续，因此需要一个中控机构map（此map非彼map）来控制。map相当于一个vector，里面存储着指向缓冲区首地址的指针。map最少为8个结点，最多为元素数量除以缓冲区大小再加上2。deque插入第一个元素时一定是用map中最中间的结点，如果中间结点指向的缓冲区已满，那么再在尾部插入元素的话，会在中控机构map中该结点右边获取结点，在新的缓冲区中从左到右添加新元素；如果缓冲区已满再在首部插入元素，那么会在中控机构map中该结点左边获取结点，在新的缓冲区中从右到左添加元素。如果map中所有结点已满，那么会像vector一样扩容得到一个新的中控机构map。
• 插入和删除比较复杂。插入或删除中间结点，会比较deque中所有元素，位于该结点前面的元素多还是位于该结点后面的元素多。如果是前面多，那么就固定前面，将后面的结点都向前移动一个单位，或者将后面结点向后移动一个单位使得空出一个单位以插入结点。反之则固定后面移动前面。

stack

• stack 是以 deque 为底层结构，并封闭其头部而形成。
• stack 只允许从其顶部获取元素，也就是说不允许被遍历，因此也就没有迭代器
• stack 遵循先进后出原则

queue

• queue 是一种先进先出的数据结构
• queue 只允许从其首部或者尾部获取元素，不可直接取中间元素，也是不可被遍历，没有迭代器
• SGI STL 默认以 deque 为底层结构并封闭其前端的入口和后端的出口，保留前端的出口和后端的入口。因此是先进先出。
• 和 deque 类似，list 也是双向开口的数据结构，因此也可以用作 queue 的底层结构。

heap算法

• heap，即堆，是一种数据结构，但是其底层是建立在顺序存储结构上，如array，vector等。heap是一棵完全二叉树，即每一层结点都是满的，除了最后一层，最后一层结点中也没有空隙。这样的特点使得heap可以很容易在数组上实现：假设一个结点为i，那么其左结点就为2 * i，其右结点为2 * i + 1，其根结点为i / 2。heap支持以下算法：

  • push_heap(first, last)：数组原来是一个堆，现在要在尾部插入一个元素。先把元素插入到数组结尾，再调用push_heap使之保持一个堆
  • pop_heap(first, last)：弹出堆首，堆大小减一。交换堆首和堆尾(数组首尾)，并重新调整堆[first, last-1)使之重新成为一个堆
  • sort_heap(first, last)：对一个数组[first, last)堆排序。即不断调用pop_heap，每次将范围从后向前缩减一个元素
  • make_heap(first, last)：将一个数组[first, last)转化成一个堆（调整数组中元素位置使之满足一个堆的条件）

  heap 的所有元素都遵循完全二叉树规则，所以 heap 提供遍历功能，但不提供迭代器。但是不妨碍其底层结构 vector 使用迭代器。

priority_queue

• 优先队列，不是先进先出，而是以权值排列元素，每次出来的都是最大值或者最小值。与普通queue相同的是，priority_queue 也只能从队首取出元素，从队尾加入元素（宏观上）。
• priority_queue 也不是容器，那么它是改造自什么容器呢？默认是vector，在vector上面还有一层算法层，即heap算法。priority_queue 通过调用heap 算法来操纵 vector 达到优先队列的效果
• empty()、size()、top()都是直接操纵vector
• push(v)，先调用 vector 的 push_back() 将新元素加入尾端，再调用 push_heap 重排heap
• pop()，先调用 pop_heap() 重排堆，然后底层 vector 再调用 pop_back() 弹出元素
• priority_queue 也不提供遍历功能，没有迭代器

slist

• list 是双向环状链表，而slist(single linked list)则是单向无环链表。该容器不在标准内
• slist 和 list 一样，插入、移除、结合(splice)等操作并不会造成原有的迭代器失效
• 基于效率的考虑，slist 没有 push_back，只有 push_front。
• slist 有一个 伪头结点 head，head.next 为 slist 中第一个结点。因此 begin() 和empty() 都由 head.next 来判断。而size 则是遍历链表计数得到，end()是直接返回一个空的迭代器。
• slist 迭代器没有减减– 操作，因为是单链表嘛。

关联式容器

所谓关联式容器，实际上就是每个元素都有一个键值key(和一个实值value)，根据元素大小将元素插入到对应的位置。没有所谓的头和尾，因此也就没有push_back()、push_front()、pop_back()、pop_front()、begin()、end()等行为。

set

• set 中元素会自动排序，但不允许两个相同的值出现，没有key和value之分
• set 中的值无法通过迭代器更改，因为迭代器是const类型
• 和list类似，新增或删除元素时，其它迭代器不受影响
• set 以 RB-tree为底层实现，几乎所有set操作都是直接转调RB-tree的相关操作
• 面对关联式容器，应该使用其自身提供的find()函数而不是STL的find()算法，因为后者只是循序搜寻，效率很低。

map

• 具有实值和键值，即key-value，所有元素都会根据键值排序
• map的所有元素都是pair，pair的第一元素就是key键值，第二元素为value实值。map不允许两个元素有相同的键值
• 可以通过迭代器修改map中元素的实值value，但是不能修改键值key，因为会影响排序。
• 和list 以及 set 类似，新增或删除元素时，其它迭代器不受影响
• map 以 RB-tree为底层实现，几乎所有map操作都是直接转调RB-tree的相关操作
• 面对关联式容器，应该使用其自身提供的find()函数而不是STL的find()算法，因为后者只是循序搜寻，效率很低。

multiset

• multiset 与 set 用法几乎完全相同，唯一不同在于multiset 允许元素重复
• multiset 以 RB-tree为底层实现，几乎所有multiset操作都是直接转调RB-tree的相关操作

multimap

• multimap 与 map 用法几乎完全相同，不同之处有multimap 允许键值重复，其废除了[]的重载，因此不能通过[]来访问元素。
• multimap 以 RB-tree为底层实现，几乎所有multimap操作都是直接转调RB-tree的相关操作

hashtable

C++11之后将hash_table加入标准中，并改为unordered_+容器名，即hash_set不可用了，取而代之的是unordered_set，其它容器同理。参考：https://stackoverflow.com/questions/1646266/difference-between-hash-map-and-unordered-map

hash_set -> unordered_set

• hash_set 以 hashtable为底层实现，几乎所有hash_set操作都是直接转调hashtable的相关操作
• hash_set 的使用方式和set完全相同
• 这里的hashtable默认大小为100，但底层将由hashtable调整为下一个质数193

hash_map -> unordered_map

• hash_map 以 hashtable为底层实现，几乎所有hash_map操作都是直接转调hashtable的相关操作
• hash_map 的使用方式和map完全相同，除了一点，map中元素有自动排序功能，而hash_map则没有
• 这里的hashtable默认大小为100，但底层将由hashtable调整为下一个质数193

hash_multiset -> unordered_multiset

• hash_multiset 的特性和multiset完全相同，除了hash_multiset的底层是hashtable，其中的元素并不会自动排序。
• 这里的hashtable默认大小为100，但底层将由hashtable调整为下一个质数193

hash_multimap -> unordered_multimap

• hash_multimap 的特性和multimap完全相同，除了hash_multimap的底层是hashtable，其中的元素并不会自动排序。
• 这里的hashtable默认大小为100，但底层将由hashtable调整为下一个质数193

参考资料

• 《STL源码剖析》

• https://baike.baidu.com/item/STL/70103?fr=aladdin
• https://stackoverflow.com/questions/1646266/difference-between-hash-map-and-unordered-map