What & How & Why

您在这里: start » cs » programming » cpp » boolan_cpp » stl_generic_3

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:programming:cpp:boolan_cpp:stl_generic_3 [2024/01/14 13:46] – 移除 - 外部编辑 (未知日期) 127.0.0.1cs:programming:cpp:boolan_cpp:stl_generic_3 [2024/01/14 13:47] (当前版本) – ↷ 链接因页面移动而自动修正 codinghare
行 1: 行 1:
 +======STL与泛型编程 第三周======
 +本页内容是作为 //Boolan// C++ 开发工程师培训系列的笔记。\\
 +<wrap em>因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！</wrap>
 +----
  
 +====Deque概述====
 +
 +//Deque// 是一种**分段连续**的容器。这个容器的特点是**双向开口**，并通过一个**控制器**来**串联**一系列的**缓冲区**（//Buffer//），达到**逻辑上的连续**效果。//Deque// 的详细组成如图所示：
 +\\
 +\\
 +<html><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/stldeque2.svg"  width="800"/>
 +</div>
 +</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// 的首地址：
 +<code cpp linenums:1>
 +class deque {
 +public:
 +typedef T value_type;
 +....
 +protected:
 +    typedef pointer* map_pointer; //T**
 +protected:
 +    map_pointer map;
 +    size_type map_size;
 +....
 +};
 +</code>
 +因为我们在控制器中存储的是指向 //Buffer// 的指针，因此我们需要**指向指针的指针**这种类型。同时，我们也需要维护一个 ''T'' 类型的数据 ''map_size'' 来表示控制器中 //Buffer// 的数量。
 +
 +==迭代器==
 +
 +为了匹配接口，我们需要两个迭代器：''start'' 和 ''finish''。这两个迭代器在类中的声明如下：
 +<code cpp linenums:1>
 +class deque {
 +public:
 +     typedef _deque_iterator<T, T&, T*, BufSiz> iterator;
 +protect:
 +     iterator start;
 +     iterator finish;
 +....
 +};
 +</code>
 +这两个迭代器一个指向 //Deque// 的开头元素，另外一个指向 //Deque// 的末尾元素的后一位。跟别的容器一样，//Deque// 也是通过这两个迭代器来定义了三个基本方法：
 +<code cpp linenums:1>
 +iterator begin() { return start; }
 +iterator end() { return finish; }
 +iterator size() { return finish - start; }
 +</code>
 +
 +===迭代器的结构实现===
 +
 +迭代器在 //Deque// 中扮演了非常重要的角色。我们知道 //Deque// 在物理上不是完全连续的；为了像维护顺序容器一样维护 //Deque//，我们不但需要采用 ''random access'' 类型的迭代器，同时还需要对该迭代器的一系列相关运算进行重载。
 +\\
 +\\
 +除了C++要求的五条基本信息以外，根据本节开头的图示，我们还需要使用迭代器来维护当前的 //Buffer//。因此，我们需要定义前面提到过的四个指针：
 +<code cpp linenums:1>
 +T* cur;
 +T* first;
 +T* last;
 +map_pointer node; //T**
 +</code>
 +同时，迭代器类也定义了两个类型，方便以后重载使用：
 +<code cpp linenums:1>
 +typedef size_t size_type;
 +typedef _deque_iterator self;
 +</code>
 +
 +===Buffer大小的计算方法===
 +
 +在 //G 2.9// 的版本中，//Buffer// 的大小（也就是 //Buffer// 包含的元素个数）是通过参数传递到 //Deque// 中的。我们发现默认的语句中有这么一句：
 +<code cpp linenums:1>
 +size_t BuffSiz = 0;
 +</code> 
 +这里的 ''0'' 实际上并不是指代的 //Buffer// 的大小。在 //Deque// 中， //Buffer// 的大小控制是通过下面的函数来判断的：
 +<code cpp linenums:1>
 +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));
 +}
 +</code>
 +上面的代码主要分如下几个步骤：
 +  - 如果 ''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()''
 +具体的实现代码如下：
 +<code cpp linenums:1>
 +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;
 +}
 +</code>
 +\\
 +
 +====Deque如何模拟连续空间====
 +
 +//Deque// 的迭代器是**随机访问**类型的，但其数据结构并不是物理连续的。因此，我们需要对 //Deque// 的迭代器的某些功能进行某些运算的重载，以让其达到随机访问的效果。由于 //Deque// 是由一个个缓冲区组成的，而这些缓冲区并不连续。因此，//Deque// 迭代器最重要的操作，就是判断迭代器移动以后，指向的元素是否还在当前的 //Buffer// 中。如果进行了跨区访问，我们则需要更新迭代器的 ''node'' 的信息。
 +\\
 +\\
 +作为一个随机访问的迭代器，是应该具有以下的功能的：
 +  * ''*'' / ''->''，基本的指针功能。
 +  * 自增 / 自减 功能。
 +  * ''+='' / ''-='' / ''+'' / ''-''，即迭代器的随机移位功能。
 +
 +===指针基本功能的实现===
 +
 +//Deque// 中 ''*'' 和 ''->'' 的实现与其他容器一致：
 +<code cpp linenums:1>
 +reference operator* () const { return *cur; }
 +pointer operator->() const {} return &(operator*()); }
 +</code>
 +===“-”的重载===
 +
 +<WRAP center round important 100%>
 +注：这里的相减操作是指的**两个迭代器之间的相减操作**，与迭代器移位操作的重载不同，请勿混淆！
 +</WRAP>
 +
 +\\
 +在 STL 中，迭代器相减代表了两个迭代器之间的距离。对于 //Deque// 来说，判断其两个迭代器之间的距离要稍微复杂一些。作为分段连续的容器，我们不仅要考虑两个迭代器在同一个 //Buffer// 里的情况，同时也要考虑两个**迭代器分别处于不同**的 //Buffer// 中的情况。我们可以将该距离的计算分为两步：
 +  - 计算出两个迭代器中包含了多少个完整的 //Buffer//
 +  - 计算出两个迭代器所在 //Buffer// 中剩余的元素个数
 +综合起来可以用下面的代码实现：
 +<code cpp linenums:1>
 +operator - (const self& x) const {
 +    return difference_type(buffer_size()) * (node - x.node -1) + (cur - first) + (x.last - x.cur);
 +}
 +</code>
 +这里的 ''difference_type(buffer_size())'' 代表了 //Buffer// 的长度，''node'' 是控制器用于指向 //Buffer// 的指针，因此 ''(node - x.node -1)'' 代表了 两个迭代器之间相隔了多少 //Buffer//。''cur - first'' 实际上是 ''this.cur - this.first''，代表了起始迭代器所在 //Buffer// 中包含的元素个数。
 +
 +===“++”和“--”的重载===
 +
 +自增  / 自减运算也是迭代器必要的运算之一。在 //Deque//  中，重载自增运算有一个很重要的问题需要考虑：**自增 / 自减操作是否越界（跨区）**。试想一下，如果一个迭代器正处于第一个 //Buffer// 的末尾位置，它的自增操作就会让其指向下一个 //Buffer// 的首位。这个过程需要通过控制器来实现，大致的步骤如下：
 +  - 切换迭代器至下一位
 +  - 如果此时迭代器处于最后一个元素的后一位 ''last''，则证明该自增操作需要进行跨区操作处理
 +  - 通过控制器执行跨区操作
 +  - 将当前迭代器指向新区的起点
 +整个流程用代码表现出来就是：
 +<code cpp linenums:1>
 +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;
 +}
 +</code>
 +这里的跨区操作通过 ''set_node'' 函数来实现，需要的参数是一个指向 //Buffer// 的指针。该函数通过改变迭代器中的 ''node''、''first'' 和 ''last'' 来实现跨区：
 +<code cpp linenums:1>
 +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
 +}
 +</code>
 +上面说到的是前自增版本。后自增版本与 ''list'' 的实现一致，就不再赘述。自减的重载与自增非常类似，因此也不再赘述。
 +
 +===“+=”和“-=”的重载===
 +
 +''+=''操作与 ''-'' 操作很类似，也需要判断是否跨区。而相比 ''-'' 操作，因为 ''+='' 是一个包含了赋值操作的运算，因此 ''+='' 不但需要知道是否跨区，而且需要知道**具体跨了多少区**。如果知道了跨区的大小，我们可以利用上一小节中的 ''set_node'' 函数来实现迭代器的重定位。该重载的大概实现流程如下：
 +  - 判断当前位置与移位操作量相加后是否在同一 //Buffer// 中
 +    - 如果是，直接进行 ''+='' 运算
 +    - 如果不是
 +      - 计算相隔的 //Buffer//
 +      - 切换到正确的 //Buffer//
 +      - 切换到正确的元素
 +上述流程可以用以下代码实现：
 +<code cpp linenums:1>
 +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;
 +</code>
 +还有一些有趣的事情： 
 +  * ''-='' 其实是可以用 ''+='' 实现的，将 ''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><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/red-black_tree_example.svg"  width="800"/>
 +</div>
 +</html>
 +\\
 +\\
 +//图片来源：Cburnett，[[https://commons.wikimedia.org/w/index.php?curid=1508398|链接]]//
 +
 +===红黑树的遍历===
 +
 +红黑树默认的遍历顺序是**从左到右**的；按照该方法做完遍历以后，红黑树中所有的元素会呈现**已经排序**的状态。红黑树是有迭代器的；在 //STL// 中，最左端的元素被 ''begin()'' 代表，最右端的元素被 ''end()'' 代表。但我们需要注意的是，**我们不应该使用红黑树的迭代器去修改红黑树的元素值**，准确的说，是 //Key// 值。红黑树是有序的；这个顺序是通过 //Key// 值来维护的。一旦改变了 //Key// 值，那么红黑树的结构就可能被破坏，必须经过新一轮的遍历才能达到稳定。
 +\\
 +\\
 +但是在编程层面中，该操作是允许的。//Map// 这种容器是用红黑树实现的，它的数据组成部分有 ''key'' 和 ''value''。我们在不改变 ''key'' 的情况下对 ''value'' 的修改是合法的；但这也需要迭代器的支持。因此，迭代器修改元素的功能，在红黑树这种容器中是保留了的，但并不代表我们就可以滥用。
 +
 +===红黑树的插入===
 +
 +在红黑树中，我们可以根据 //Key// 值来决定是否插入元素：
 +  * ''insert_unique()''，插入的元素的 ''key'' 必须是独一无二的，否则插入无效。
 +  * ''insert_equal()''，如果插入的元素 ''key'' 已经在表里存在，也允许该元素的插入。
 +
 +===红黑树的结构===
 +
 +红黑树作为一种较为底层的容器，并不是经常拿到台面上来使用的。然而红黑树也具有自身的 //API//：
 +<code cpp linenums:1>
 +template<class Key, class value, class KeyOfValue, class Compare, class Alloc = alloc>
 +</code>
 +从上面的代码我们发现红黑树需要五种类型的数据：
 +  * ''key'' 用于表示元素的 //Key// 值。有些元素是没有 ''data'' 的，因此自身也又是 ''key'' 又是 ''data'' (比如 //Set//)。
 +  * ''value'' 在 //Set// 里等于 ''key''，在 //Map// 里等于 ''key'' + ''data''。
 +  * ''KeyofValue'' 定义了如何获取指定元素。
 +  * ''header'' 类似于 //List// 中的空节点，是为了更方便的实现数据结构而设计的。
 +  * ''alloc'' 是分配器。
 +上述的类型通过下面的代码组成了红黑树这个类的结构：
 +<code cpp linenums:1>
 +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
 +};
 +</code>
 +===红黑树的使用===
 +
 +根据上述的信息我们可以很简单的建立一个红黑树：
 +<code cpp linenums:1>
 +rb_tree<int, int, identity<int>, less<int>, alloc> myTree;
 +</code>
 +  * 第一个 ''int'' 表示了 ''key'' 的类型
 +  * 第二个 ''int'' 表示了 ''value'' 的类型
 +  * 第三个 ''identity<int>'' 是 //GNU// 自带的函数。它继承了一个单目类，返回和参数相同的值，在这里被视作取回元素的方法。
 +  * 第四个 ''less<int>'' 是标准库中定义比大小。本例中元素都为 ''int'' 类型，因此使用默认的规则即可。如果元素为抽象类型，则我们必须提供比较大小的规则。
 +除此之外，红黑树还有几个成员函数：''empty()'', ''size()'', ''count()'' 等可供使用。
 +
 +===G4.9的改动===
 +
 +和其他容器一样，//G4.9//版本也将单一的红黑树类分成了一堆有关系的类。不过在此处，红黑树容器的设计体现出了 //Handle & Body// 设计模式，这是面向对象设计的一种体现，也可以算作该改动的一个优点了。（然后就是依然被吐槽到死的 public 继承 allocator :-o）。
 +
 +====关系容器的详解====
 +
 +===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// 对象的时候指定的：
 +<code cpp linenums:1>
 +map<int, string> myMap; // a map with elements that have int key and string data
 +</code>
 +因为 //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><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/stlhash.svg"  width="600"/>
 +</div>
 +</html>
 +\\
 +\\
 +设想我们有一大堆的物品，每个物品都有自己的编号。某一天，我们希望把这些物品按照编号一个一个的存到集装箱中对应编号储物柜里。假设我们有 $2^{32}$ 这么多件物品，那我们就需要设计数量相同的储物柜来存放这些物品。
 +\\
 +\\
 +这样的设计其实是很浪费的；很可能你的储物柜根本就没有存满，只是因为编号要求一一对应，不得不只装一个物品。而有没有可能用小于物品数量的空间来表示这么多物品呢？答案就是按类存储。而哈希表恰恰就是做的这件事情。
 +\\
 +\\
 +还是那 $2^{32}$ 的物品，如果要用小于  $2^{32}$ 的储物柜去装，那该怎么办？当然是一个柜子里装好几个物品啦。不过这样又带来了一个麻烦，找物品的时候我应该怎么办？
 +\\
 +\\
 +哈希表最终采取了**编号表加链表**的形式来处理这个问题。我们将物品的编号按照** //编号 % 编号表的大小//** 的结果来进行分组。由于编号数量大于编号空间的大小，因此一定会有不同的物品存储在同一个桶（//Bucket//）；哈希表将这一个单元里的所有元素串接成了一个链表，从而实现了存储。这种方法被称之为 **//Separate Chaining//**。
 +
 +===Rehashing===
 +
 +上面的方法通过纵向扩展解决了存储问题。但当我们想要找某个物品的时候，假如一个单元里的物品特别多，如果按照从前到后的模式寻找下去，那效率岂不是太低了？
 +\\
 +\\
 +为了解决这个问题，哈希表采用了 //Rehashing// 的策略。链表太长了？增加一些桶把这些元素再装一遍就好了：
 +\\
 +\\
 +<html><div align="center">
 +<img src="/_media/programming/cpp/boolan_cpp/rehashing.svg"  width="1000"/>
 +</div>
 +</html>
 +\\
 +\\
 +我们来看看 //GNU// 的哈希表是怎样施行上图的策略的：
 +  * 桶容器的增长条件：元素大于桶的数量（经验，无数学依据）。
 +  * 桶的元素增长策略：起始元素是 ''53''，之后在当前元素两倍的数值附近寻找一个**素数**作为新的桶容器大小。//GNU// 中并不在 rumtime 计算该大小，而是事先将其存入了数组 ''stl_prime_list'' 中。
 +  * 增长完毕之后，哈希表将对所有元素按照**末除**的策略进行**重新分桶**。
 +我们把这整个过程称为 //Rehashing// ，也称为**打散**（哈希表也称散列表）。用这种方法，我们可以将哈希表中的链表查找复杂度控制在可以容忍的范围内。同时需要注意的是，该过程根据元素的 //Key// 值进行排列，因此我们也不能使用迭代器修改其 //Key// 值。
 +
 +===哈希表的结构实现===
 +
 +相对于红黑树，哈希表的实现需要额外解决几个具体的问题：转换编号的策略， 分桶（即元素的相等规则）策略。//STL// 的实现中需要以下参数：
 +  * ''value'' / ''key''，和红黑树相同。
 +  * ''hashFcn''，转换对象到编号的函数。
 +  * ''ExtractKey''，取出哈希表对应元素的 ''key''。
 +  * ''EqualKey''，元素相等的规则
 +  * ''alloc''，分配器。
 +具体的实现如下：
 +<code cpp linenums:1>
 +template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>
 +</code>
 +上述的参数作为类型具体表现在哈希表类中的情况：
 +<code cpp linenums:1>
 +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
 +</code>
 +值得注意的是，''node'' 类型在这里除了表示元素的值以外，结构中还附带了一个指针指向下一个元素：
 +<code cpp linenums:1>
 +_hastable_node* next;
 +Value val;
 +</code>
 +当然，需要维护这些数据，哈希表也需要有迭代器。哈希表中的迭代器通过自增和自减遍历整个哈希表。但因为哈希表是以桶来存储元素的，因此经常会出现跨桶移动迭代器的情况。为此，哈希表中的迭代器额外设置了一个**指向桶容器的指针** ''hashtable''，用于在跨桶访问的情况下顺利返回桶容器：
 +<code cpp linenums:1>
 +_hastable_node* next;
 +node* cur;
 +hashtable* ht; //point to bucket vector
 +</code>
 +===哈希函数===
 +
 +哈希函数的作用就是利用元素的某个属性来生成元素的编号，这个编号我们也称为 //Hash Code//。在哈希表中，使用怎么样的策略来对元素生成编号，实际上是一件非常困难的事，因为这必须依靠你自身的经验。你自己设计的元素类型和内容，你要如何设定策略，这是没有一个共通的方法的。
 +\\
 +\\
 +当然，哈希表对不同的 //built-in// 类型，甚至 //C-string// 的编号分配策略都是有预先实现的。该策略集合通过模板的偏特化来实现：
 +<code cpp linenums:1>
 +//Generic
 +template<class Key> hash {};
 +__STL_TEMPLATE_NULL struct hash<char> {
 +    size_t operator() (char x) const { return x; };
 +</code>
 +对于基本的可以用数值表示的类型，哈希函数的处理策略都是返回其本身的值作为元素的编号。而对C字符串来说，则有如下的计算方式：
 +<code cpp linenums:1>
 +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''
 +</code>
 +上面这个方法也同样没有什么数学含义。这个方法的唯一目的在于希望尽可能的使编号离散化。因为编号越离散，越杂乱，越不容易发生重叠，这样造成单元链表变长的几率则越少。理论上来说，一个哈希表的最优情况是做到单元链表的平衡。
 +\\
 +\\
 +<WRAP center round help 100%>
 +注：G.2.9并未提供 //STL String// 的哈希函数，G.4.9 则提供了。
 +</WRAP>
 +
 +====Unordered容器====
 +
 +本节内容并无新内容。具体详情请参考[[cs:programming:cpp:boolan_cpp:stl_generic_1#关联容器|STL与泛型编程 第一周]]
 +\\
 +\\
 +\\
 +----
 +~~DISQUS~~