STL与泛型编程第三周

本页内容是作为 Boolan C++ 开发工程师培训系列的笔记。
因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！

Deque概述

Deque 是一种分段连续的容器。这个容器的特点是双向开口，并通过一个控制器来串联一系列的缓冲区（Buffer），达到逻辑上的连续效果。Deque 的详细组成如图所示：

<html>

</html>

从上图我们可以看出 Deque 的大体结构：

数据结构部分：
- 数据单元：Buffer，默认大小为 512kb，是 Deque 中实际连续的部分。
- 数据控制中心：由一个 Vector 实现。 Deque 通过该区域存储一系列指向不同 Buffer 的指针，将 Buffer 从逻辑上串联起来。
迭代器部分：
- 迭代器的组成：
  - cur：指向当前元素的迭代器。
  - first：指向当前 Buffer 第一个元素的迭代器。
  - last：指向当前 Buffer 最后一个元素的迭代器。
  - node：指向数据控制中心对应的位置，表明了当前 Buffer 在整个 Deque 中的位置。
- 首尾迭代器 start 和 finish：用于统一容器接口的两个迭代器，对应 begin() 和 end()。

下面来看看这些结构和功能都是如何实现的。

Deque的基础结构实现

控制器

我们知道，Deque 通过一个 Vector 在维护自身的控制器；在具体的实现过程中， Deque 使用了一个指向指针的指针来指向这个 Vector 的首地址：

class deque {
public:
typedef T value_type;
....
protected:
    typedef pointer* map_pointer; //T**
protected:
    map_pointer map;
    size_type map_size;
....
};

因为我们在控制器中存储的是指向 Buffer 的指针，因此我们需要指向指针的指针这种类型。同时，我们也需要维护一个 T 类型的数据 map_size 来表示控制器中 Buffer 的数量。

迭代器

为了匹配接口，我们需要两个迭代器：start 和 finish。这两个迭代器在类中的声明如下：

class deque {
public:
     typedef _deque_iterator<T, T&, T*, BufSiz> iterator;
protect:
     iterator start;
     iterator finish;
....
};

这两个迭代器一个指向 Deque 的开头元素，另外一个指向 Deque 的末尾元素的后一位。跟别的容器一样，Deque 也是通过这两个迭代器来定义了三个基本方法：

iterator begin() { return start; }
iterator end() { return finish; }
iterator size() { return finish - start; }

迭代器的结构实现

迭代器在 Deque 中扮演了非常重要的角色。我们知道 Deque 在物理上不是完全连续的；为了像维护顺序容器一样维护 Deque，我们不但需要采用 random access 类型的迭代器，同时还需要对该迭代器的一系列相关运算进行重载。

除了C++要求的五条基本信息以外，根据本节开头的图示，我们还需要使用迭代器来维护当前的 Buffer。因此，我们需要定义前面提到过的四个指针：

T* cur;
T* first;
T* last;
map_pointer node; //T**

同时，迭代器类也定义了两个类型，方便以后重载使用：

typedef size_t size_type;
typedef _deque_iterator self;

Buffer大小的计算方法

在 G 2.9 的版本中，Buffer 的大小（也就是 Buffer 包含的元素个数）是通过参数传递到 Deque 中的。我们发现默认的语句中有这么一句：

size_t BuffSiz = 0;

这里的 0 实际上并不是指代的 Buffer 的大小。在 Deque 中， Buffer 的大小控制是通过下面的函数来判断的：

inline size_t _deque_buf_size(size_t n, size_t sz) {
    return n != 0 ? n :
                    (sz < 512 ? size_t(512 / sz) : size_t(1));
}

上面的代码主要分如下几个步骤：

如果 n 不为 0，返回 n, 也就是使用自定义大小的 Buffer。
如果 n 为 0，则表示使用默认值 512.
在 n 为 0 的情况下，如果元素的大小小于 512，则返回的大小为 Buffer 的大小除以元素的个数，即 512 / sz。
如果元素大小大于 512，则返回 1，即该 Buffer 只有一个元素。

Insert操作的实现

Insert 可以作为一个典型的例子来说明 Deque 的数据结构的另外一个特性：双头开口。因为插入的元素可以处于 Deque 的任何一个位置，因此根据不同的位置决定不同的操作，会显著的提高写效率。STL 对 insert 的实现分为如下几个步骤：

首先判断插入点是否在容器的头部或者尾部
- 如果在头部，使用 push_front()
- 如果在尾部，使用 push_back()
如果不在头部或者尾部，调用函数 insert_aux。该函数会求出当前位置和起点和终点的距离
- 如果在插入点前面的元素个数较少（距离小于 size() 的一半），则使用 push_front()
- 否则使用 push_back()

具体的实现代码如下：

iterator insert(iterator position, const value_type& x） {
    //if insert at start
    if (position.cur == start.cur) {
        push_front(x);
        return start;
    //if insert at end
    } else if (position.cur == finish.cur) {
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp; //return the iterator that point to the last element 
    } else {
        return insert_aux(position, x);
}

/* insert_aux */
template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {
    difference_type index = pos - start; // get the distance from insert position to start
    value_type x+copy = x;
    //distance < size() / 2 means the insert point is closer to the start
    if (index < size() / 2) {
        push_front(front()); //add a new space
        ...
        copy(front2, pos1, front1); //move other elements, make a empty space for the insert emelent
    } else {
        push_back(back());
        ...
        copy_backward(pos, back2, back1);
    }
    *pos = x_copy;
    return pos;
}

Deque如何模拟连续空间

Deque 的迭代器是随机访问类型的，但其数据结构并不是物理连续的。因此，我们需要对 Deque 的迭代器的某些功能进行某些运算的重载，以让其达到随机访问的效果。由于 Deque 是由一个个缓冲区组成的，而这些缓冲区并不连续。因此，Deque 迭代器最重要的操作，就是判断迭代器移动以后，指向的元素是否还在当前的 Buffer 中。如果进行了跨区访问，我们则需要更新迭代器的 node 的信息。

作为一个随机访问的迭代器，是应该具有以下的功能的：

* / →，基本的指针功能。
自增 / 自减功能。
+= / -= / + / -，即迭代器的随机移位功能。

指针基本功能的实现

Deque 中 * 和 → 的实现与其他容器一致：

reference operator* () const { return *cur; }
pointer operator->() const {} return &(operator*()); }

“-”的重载

注：这里的相减操作是指的两个迭代器之间的相减操作，与迭代器移位操作的重载不同，请勿混淆！

在 STL 中，迭代器相减代表了两个迭代器之间的距离。对于 Deque 来说，判断其两个迭代器之间的距离要稍微复杂一些。作为分段连续的容器，我们不仅要考虑两个迭代器在同一个 Buffer 里的情况，同时也要考虑两个迭代器分别处于不同的 Buffer 中的情况。我们可以将该距离的计算分为两步：

计算出两个迭代器中包含了多少个完整的 Buffer
计算出两个迭代器所在 Buffer 中剩余的元素个数

综合起来可以用下面的代码实现：

operator - (const self& x) const {
    return difference_type(buffer_size()) * (node - x.node -1) + (cur - first) + (x.last - x.cur);
}

这里的 difference_type(buffer_size()) 代表了 Buffer 的长度，node 是控制器用于指向 Buffer 的指针，因此 (node - x.node -1) 代表了两个迭代器之间相隔了多少 Buffer。cur - first 实际上是 this.cur - this.first，代表了起始迭代器所在 Buffer 中包含的元素个数。

“++”和“--”的重载

自增 / 自减运算也是迭代器必要的运算之一。在 Deque 中，重载自增运算有一个很重要的问题需要考虑：自增 / 自减操作是否越界（跨区）。试想一下，如果一个迭代器正处于第一个 Buffer 的末尾位置，它的自增操作就会让其指向下一个 Buffer 的首位。这个过程需要通过控制器来实现，大致的步骤如下：

切换迭代器至下一位
如果此时迭代器处于最后一个元素的后一位 last，则证明该自增操作需要进行跨区操作处理
通过控制器执行跨区操作
将当前迭代器指向新区的起点

整个流程用代码表现出来就是：

self& operator++() {
    ++cur;
    if(cur == last) {
        set_node(node + 1); // jump to the next Buffer
        cur == first; //set cur iterator to the first
    }
    return *this;
}

这里的跨区操作通过 set_node 函数来实现，需要的参数是一个指向 Buffer 的指针。该函数通过改变迭代器中的 node、first 和 last 来实现跨区：

void set_node(map_pointer new_node) {
    node = new_node; //switch to the new buffer
    first = *new_node; // set first, make it points to the start of the new buffer
    last = first + difference_type(buffer_size()); //last = address of first + buffer size
}

上面说到的是前自增版本。后自增版本与 list 的实现一致，就不再赘述。自减的重载与自增非常类似，因此也不再赘述。

“+=”和“-=”的重载

+=操作与 - 操作很类似，也需要判断是否跨区。而相比 - 操作，因为 += 是一个包含了赋值操作的运算，因此 += 不但需要知道是否跨区，而且需要知道具体跨了多少区。如果知道了跨区的大小，我们可以利用上一小节中的 set_node 函数来实现迭代器的重定位。该重载的大概实现流程如下：

判断当前位置与移位操作量相加后是否在同一 Buffer 中
1. 如果是，直接进行 += 运算
2. 如果不是
  1. 计算相隔的 Buffer
  2. 切换到正确的 Buffer
  3. 切换到正确的元素

上述流程可以用以下代码实现：

self& operator += (difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset >= 0 && offset < difference_type(buffer_size())) // offset in buffer
        cur += n;
    //offset out of current buffer
    else {
        //whether the offset is going forward or backward (using this condition to represent both += and -=) 
        difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()))
                                                 :-difference_type((-offset - 1) / buffer_size() - 1; 
        //switch to the right buffer
        set_node(node + node_offset);
        //move iterator to the right position
        cur = fist + (offset - node_offset * difference_type(buffer_size()));
     }
     return *this;

还有一些有趣的事情：

-= 其实是可以用 += 实现的，将 n 变为 -n 就可以了
+ 也是可以用 += 实现的。因为 + 不做赋值，不修改现有迭代器，因此返回的值可以用 tmp += n; 表示， tmp 表示的是当前迭代器的位置，也就是 *this;
而取下标 [] 这个经典的顺序容器操作，则可以用 + 来实现了： return *(*this + n)

控制器的扩充

前面说到过 Deque 的控制器使用了 Vector 来实现。那么当 Buffer 的数量超过了原有的控制器大小，控制器也是会自动扩充的。不过控制器的扩充则做了一点点小小的变化：每次扩充的时候，都会把现有的控制器元素拷贝到新控制器的中间区域。这样做有一个很明显的好处：我们知道 Vector 中如果插入新元素导致现有元素移位，都需要调用构造 / 析构函数。而 Deque 是一个双向开口的容器。因此如果我们将开口附近的区域留空，这样即使插入新的 Buffer，控制器在一定程度内是不需要移动现有元素的，这样效率会更高一些。

Queue和Stack

严格意义上来说， Queue 和 Stack 应该被称为容器适配器，因为他们是依托基本的容器来实现的。之所以放到 Deque 章节讨论，是因为依托 Deque 实现的方式效率最高。

首先来看看 Queue 和 Stack 都需要什么样的功能：

Queue 是先进先出的数据结构，因此需要实现的函数主要有：

查看元素：front(), back()
操作元素： push() 和 pop()

Deque 和 List 都可以通过自身的函数front() 、back()、push_front() 和 push_back() ，因此他们都可以做为 Queue 的底层容器。

而 Stack 因为是先进先出，因此需要实现的主要函数有：

查看元素：top()
操作元素：push() 和 pop()

top() 操作可以通过 back 来完成，因此不但 Deque 和 List 可以作为 Stack 的底层容器，连 Vector 也可以。

因此我们可以得出一个结论：不管什么样的容器，只要其操作可以实现 Queue 和 Stack 的数据结构操作，那这些容器都可以作为 Queue 和 Stack 的底层容器。由这个结论我们可以推一些反例出来：

关系容器是没法实现 Queue 和 Stack 的
Vector 只能实现 Stack

不过这里比较 tricky 的是，尽管 Vector 不能实现 Queue，但可以实现其中的某一些操作，比如需要 push_back() 的操作都是可以实现的。这是因为编译器在编译过程中，只会针对调用的方法进行检测；如果没有调用到不能实现的方法，那么是不会报错的。

除此之外，Queue 和 Stack 还有两个非常重要的特性：

不允许遍历
不允许使用迭代器

因为以上两种方式都可能破坏这两种数据结构的特性（先进先出，先进后出）。

红黑树作为容器的使用

本系列第一周课程中提到过关系容器的底层实现都是红黑树。为了了解关系容器，我们需要先明白红黑树这个数据结构的一些特点。

红黑树是平衡搜索二叉树的一种，通过节点的红黑属性来达到平衡的效果。所谓的平衡，就是指在树不会有远比其他的分支长的分支导致影响搜索的效率。

<html>

</html>

图片来源：Cburnett，链接

红黑树的遍历

红黑树默认的遍历顺序是从左到右的；按照该方法做完遍历以后，红黑树中所有的元素会呈现已经排序的状态。红黑树是有迭代器的；在 STL 中，最左端的元素被 begin() 代表，最右端的元素被 end() 代表。但我们需要注意的是，我们不应该使用红黑树的迭代器去修改红黑树的元素值，准确的说，是 Key 值。红黑树是有序的；这个顺序是通过 Key 值来维护的。一旦改变了 Key 值，那么红黑树的结构就可能被破坏，必须经过新一轮的遍历才能达到稳定。

但是在编程层面中，该操作是允许的。Map 这种容器是用红黑树实现的，它的数据组成部分有 key 和 value。我们在不改变 key 的情况下对 value 的修改是合法的；但这也需要迭代器的支持。因此，迭代器修改元素的功能，在红黑树这种容器中是保留了的，但并不代表我们就可以滥用。

红黑树的插入

在红黑树中，我们可以根据 Key 值来决定是否插入元素：

insert_unique()，插入的元素的 key 必须是独一无二的，否则插入无效。
insert_equal()，如果插入的元素 key 已经在表里存在，也允许该元素的插入。

红黑树的结构

红黑树作为一种较为底层的容器，并不是经常拿到台面上来使用的。然而红黑树也具有自身的 API：

template<class Key, class value, class KeyOfValue, class Compare, class Alloc = alloc>

从上面的代码我们发现红黑树需要五种类型的数据：

key 用于表示元素的 Key 值。有些元素是没有 data 的，因此自身也又是 key 又是 data (比如 Set)。
value 在 Set 里等于 key，在 Map 里等于 key + data。
KeyofValue 定义了如何获取指定元素。
header 类似于 List 中的空节点，是为了更方便的实现数据结构而设计的。
alloc 是分配器。

上述的类型通过下面的代码组成了红黑树这个类的结构：

class rb_tree {
....
protected:
typedef _rb_tree_node<Value> rb_tree_node; // key + data
size_type node_count; // elements count in rb_tree
link_type header;
Compare key_compare; //condition for sorting
};

红黑树的使用

根据上述的信息我们可以很简单的建立一个红黑树：

rb_tree<int, int, identity<int>, less<int>, alloc> myTree;

第一个 int 表示了 key 的类型
第二个 int 表示了 value 的类型
第三个 identity<int> 是 GNU 自带的函数。它继承了一个单目类，返回和参数相同的值，在这里被视作取回元素的方法。
第四个 less<int> 是标准库中定义比大小。本例中元素都为 int 类型，因此使用默认的规则即可。如果元素为抽象类型，则我们必须提供比较大小的规则。

除此之外，红黑树还有几个成员函数：empty(), size(), count() 等可供使用。

G4.9的改动

和其他容器一样，G4.9版本也将单一的红黑树类分成了一堆有关系的类。不过在此处，红黑树容器的设计体现出了 Handle & Body 设计模式，这是面向对象设计的一种体现，也可以算作该改动的一个优点了。（然后就是依然被吐槽到死的 public 继承 allocator ）。

关系容器的详解

Set / Multiset

Set / Multiset 是以红黑树为底层结构实现的容器，其拥有以下特点：

元素自动排序。
排序的依据是 Key 值，在 Set / Multiset 中，Key 值即元素的 value。
Set / Multiset 提供迭代器遍历，遍历过后容器元素处于排序状态。
Set / Multiset 本身禁止使用迭代器修改元素值。
Set 和 Multiset 分别使用 insert_unique 和 insert_equal 作为插入方法。

Set实现中的相关注意事项

Set 一共需要三个参数：Key，比较规则，分配器。
Set 类中唯一使用的数据类型是 rep_type，也就是红黑树。
Set 中的操作都会最终转化为红黑树的操作。
GNU 使用了 identity() 函数作为取元素的方法，而其他编译器都是自己定义的类来解决这个参数问题。
Set 中的迭代器类型为 const，因此有效的防止了使用迭代器修改 Set 中的元素。

Map / Multimap

Map / Multimap 也是基于以红黑树实现的容器。但不同于 Set 的是，Map 的元素分为 key 和 data 两部分；Map 通过数据类型 pair 将这两部分整合在一起作为整个元素存入容器中。因此，比起 Set，Map 需要的参数会多一个，也就是 data 的类型。而这个类型是需要在定义 Map 对象的时候指定的：

map<int, string> myMap; // a map with elements that have int key and string data

因为 Map 其元素独特的结构，对于取值函数，则不能使用 identity() 了；取而代之的是 selcet1st()。该函数可以将 pair 中的第一个数据取出，也就是 key。需要注意的是这个函数也是 GNU 独有的；但其他编译器也有类似的实现方法。该函数接收一个 pair 类型，返回该类型的 first 值。

由于 Map 中涉及到修改元素的 data 部分，因此 Map 的迭代器部分并没有设计成 const 类型。取而代之的是，Map 将作为元素的 pair 设计成了 <const key, T data>，通过指定 key 为 const 类型来保证 Key 值不被更改。

Operator“[]”的重载

运算符 [] 的重载是 Map 和 Multimap 的最大区别之一。 [] 运算在 Map 中的运算就是通过 Key 来取的对应的 data 值。该重载的实现分为如下几步：

首先检测 key 是否存在。
如果 key 存在，返回所在位置的迭代器。
如果不存在，在恰当的位置建立一个指定 key 的元素，该元素拥有默认的 data 值。

在实现中，STL 使用了标准库函数 lower_bound() 来实现这一过程 lower_bound() 是二分查找的一种版本。这个函数在没有查找到指定值的时候，会返回一个假设该元素存在时应该出现的位置，即其返回的迭代器指向第一个不小于 value 的元素。如果该 value 大于范围内任何元素，则返回 last。换句话说， lower_bound() 返回的是不通过破坏排序就可以安插 value 的第一个位置。

因为返回值必须是一个迭代器，因此 [] 不能做到一对多的关系，也就是说，如果要使用 []，key 必须唯一。因此，Multimap 是不能使用 [] 的。

HashTable详解

哈希表（Hash Table）是数据结构中很有趣的一个例子。

<html>

</html>

设想我们有一大堆的物品，每个物品都有自己的编号。某一天，我们希望把这些物品按照编号一个一个的存到集装箱中对应编号储物柜里。假设我们有 $2^{32}$ 这么多件物品，那我们就需要设计数量相同的储物柜来存放这些物品。

这样的设计其实是很浪费的；很可能你的储物柜根本就没有存满，只是因为编号要求一一对应，不得不只装一个物品。而有没有可能用小于物品数量的空间来表示这么多物品呢？答案就是按类存储。而哈希表恰恰就是做的这件事情。

还是那 $2^{32}$ 的物品，如果要用小于 $2^{32}$ 的储物柜去装，那该怎么办？当然是一个柜子里装好几个物品啦。不过这样又带来了一个麻烦，找物品的时候我应该怎么办？

哈希表最终采取了编号表加链表的形式来处理这个问题。我们将物品的编号按照 编号 % 编号表的大小 的结果来进行分组。由于编号数量大于编号空间的大小，因此一定会有不同的物品存储在同一个桶（Bucket）；哈希表将这一个单元里的所有元素串接成了一个链表，从而实现了存储。这种方法被称之为 Separate Chaining。

Rehashing

上面的方法通过纵向扩展解决了存储问题。但当我们想要找某个物品的时候，假如一个单元里的物品特别多，如果按照从前到后的模式寻找下去，那效率岂不是太低了？

为了解决这个问题，哈希表采用了 Rehashing 的策略。链表太长了？增加一些桶把这些元素再装一遍就好了：

<html>

</html>

我们来看看 GNU 的哈希表是怎样施行上图的策略的：

桶容器的增长条件：元素大于桶的数量（经验，无数学依据）。
桶的元素增长策略：起始元素是 53，之后在当前元素两倍的数值附近寻找一个素数作为新的桶容器大小。GNU 中并不在 rumtime 计算该大小，而是事先将其存入了数组 stl_prime_list 中。
增长完毕之后，哈希表将对所有元素按照末除的策略进行重新分桶。

我们把这整个过程称为 Rehashing ，也称为打散（哈希表也称散列表）。用这种方法，我们可以将哈希表中的链表查找复杂度控制在可以容忍的范围内。同时需要注意的是，该过程根据元素的 Key 值进行排列，因此我们也不能使用迭代器修改其 Key 值。

哈希表的结构实现

相对于红黑树，哈希表的实现需要额外解决几个具体的问题：转换编号的策略，分桶（即元素的相等规则）策略。STL 的实现中需要以下参数：

value / key，和红黑树相同。
hashFcn，转换对象到编号的函数。
ExtractKey，取出哈希表对应元素的 key。
EqualKey，元素相等的规则
alloc，分配器。

具体的实现如下：

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>

上述的参数作为类型具体表现在哈希表类中的情况：

hasher hash; // HashFcn
key_equal equals; // EqualKey
ExtractKey get_key;
typedef _hashtable_node<Value> node; //unit of linklist
vector<node*, Alloc> buckets; //bucket conatiner
size_type num_elements; //size of hashtable

值得注意的是，node 类型在这里除了表示元素的值以外，结构中还附带了一个指针指向下一个元素：

_hastable_node* next;
Value val;

当然，需要维护这些数据，哈希表也需要有迭代器。哈希表中的迭代器通过自增和自减遍历整个哈希表。但因为哈希表是以桶来存储元素的，因此经常会出现跨桶移动迭代器的情况。为此，哈希表中的迭代器额外设置了一个指向桶容器的指针 hashtable，用于在跨桶访问的情况下顺利返回桶容器：

_hastable_node* next;
node* cur;
hashtable* ht; //point to bucket vector

哈希函数

哈希函数的作用就是利用元素的某个属性来生成元素的编号，这个编号我们也称为 Hash Code。在哈希表中，使用怎么样的策略来对元素生成编号，实际上是一件非常困难的事，因为这必须依靠你自身的经验。你自己设计的元素类型和内容，你要如何设定策略，这是没有一个共通的方法的。

当然，哈希表对不同的 built-in 类型，甚至 C-string 的编号分配策略都是有预先实现的。该策略集合通过模板的偏特化来实现：

//Generic
template<class Key> hash {};
__STL_TEMPLATE_NULL struct hash<char> {
    size_t operator() (char x) const { return x; };

对于基本的可以用数值表示的类型，哈希函数的处理策略都是返回其本身的值作为元素的编号。而对C字符串来说，则有如下的计算方式：

inline size_t _stl_hash_string(const char* s) {
    unsigned long h = 0; //h is hash_code
    for (; *s, ++s)
        h = 5*h + *s; // h of "abc" is 5*(5*'a' + 'b') + ''c''

上面这个方法也同样没有什么数学含义。这个方法的唯一目的在于希望尽可能的使编号离散化。因为编号越离散，越杂乱，越不容易发生重叠，这样造成单元链表变长的几率则越少。理论上来说，一个哈希表的最优情况是做到单元链表的平衡。

注：G.2.9并未提供 STL String 的哈希函数，G.4.9 则提供了。

Unordered容器

本节内容并无新内容。具体详情请参考STL与泛型编程第一周

~~DISQUS~~

目录

STL与泛型编程 第三周