原文：http://blog.csdn.net/a809146548/article/details/51391893?locationNum=4&fps=1

笔记：

alloc：所有STL数据结构的内存分配基于一个alloc，STL 自定义一个alloc，是一个16条不同内存大小的内存链组成，每次申请都选择合适的内存链来取出空闲的内存块。vector，内部是一个数组，可动态增长空间，每次增长时都要copy所有的元素，可随机访问dequeue：内部是多个分段的数组，用额外的一个数组来标记各个分段数组信息，迭代器由于要考虑分段数组边界的问题，实现比较复杂。可在前面添加或后面添加。List：内部是一个双向环形链表，添加和删除不需要移动数据，不可随机访问。红黑树：类平衡树，每个路径的黑节点数量相同，一个红节点后面必须跟黑节点，这样保证不会有任何一条路径大于别的路径的2倍。没有平衡树那么严格平衡，减少插入和删除的开销。map，multiple_map：内部由红黑树组成set，multiple set：内部由红黑树组成

 

STL源码剖析

标签： C++C++11算法数据结构源码 2016-05-13 01:40  1101人阅读  评论(0)  收藏  举报   分类： C++基本知识（196） 

目录(?)[+]

STL源码剖析---空间配置器

看过STL空间配置器的源码，总结一下：       1、STL空间配置器：主要分三个文件实现，stl_construct.h  这里定义了全局函数construct()和destroy()，负责对象的构造和析构。stl_alloc.h文件中定义了一、二两级配置器，彼此合作，配置器名为alloc. stl_uninitialized.h 这里定义了一些全局函数，用来填充(fill)或复制(copy)大块内存数据，他们也都隶属于STL标准规划。       在stl_alloc.h中定义了两级配置器，主要思想是申请大块内存池，小块内存直接从内存池中申请，当不够用时再申请新的内存池，还有就是大块内存直接申请。当申请空间大于128字节时调用第一级配置器，第一级配置器没有用operator::new和operator::delete来申请空间，而是直接调用malloc/free和realloc，并且实现了类似c++中new-handler的机制。所谓c++ new handler机制是，你可以要求系统在内存配置需求无法被满足时，调用一个指定的函数。换句话说，一旦::operator::new无法完成任务，在丢出std::bad_alloc异常状态之前，会先调用由客端指定的处理例程，该处理例程通常称为new-handler.new-handler解决内存做法有特定的模式。SGI第一级配置器的allocate()和realloc都是在调用malloc和realloc不成功后，改调用oom_malloc()和oom_realloc()，后两者都有内循环，不断调用"内存不足处理例程"，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存不足处理例程“并未被客端设定，oom_malloc()和oom_realloc便调用_THROW_BAD_ALLOC, 丢出bad_alloc异常信息，或利用exit(1)硬生生中止程序。      在stl_alloc.h中定义的第二级配置器中，如果区块够大，超过128字节时，就移交给第一级配置器处理。当区块小于128字节时，则以内存池管理，此法又称为次层配置，每次配置一大块内存，并维护对应的自由链表(free-list)。下次若再有相同大小的内存需求，就直接从free-list中拔出。如果客端释还小额区块，就由配置器回收到free-lists中，另外，配置器除了负责配置，也负责回收。为了管理方便，SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数。并维护16个free-lists，各自管理大小分别为8，16，24，32，40，48，56，64，72，80，88，96，104， 112，120，128 字节的小额区块。当申请小于等于128字节时就会检查对应的free list，如果free-list中有可用的区块，就直接拿来，如果没有，就准备为对应的free-list 重新填充空间。新的空间将取自内存池，缺省取得20个新节点，如果内存池不足（还足以一个以上的节点），就返回的相应的节点数.如果当内存池中连一个节点大小都不够时，就申请新的内存池,大小为2*total_bytes+ROUND_UP(heap_size>>4)，totoal_bytes 为申请的空间大小，ROUND_UP调整为8的倍数，heap_size为当前总申请内存池的大小。如果申请该内存池成功就把原来内存池中剩下的空间分配给适当的free-list.万一山穷水尽，整个system heap空间都不够了（以至无法为内存池注入源头活水），malloc()行动失败，就会四处寻找有无"尚有未用区块，且区块足够大 "之free lists.找到了就挖一块交出，找不到就调用第一级配置器。第一级配置器其实也是使用malloc来配置内存。但它有out-of-memory处理机制（类似new-handler机制），或许有机会释放其他的内存拿来此处使用。如果可以就成功，否则发出bad_alloc异常。       2、STL的默认内存分配器       隐藏在这些容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板所定义的接口方法即可，然后通过将自定义的allocator作为模板参数传递给STL容器，创建一个使用自定义allocator的STL容器对象，如：     stl::vector<int, UserDefinedAllocator> array;       大多数情况下，STL默认的allocator就已经足够了。这个allocator是一个由两级分配器构成的内存管理器，当申请的内存大小大于128byte时，就启动第一级分配器通过malloc直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round up成8的倍数）从对应的空闲块列表取表头块给用户。 这种做法有两个优点：      (1)小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。      (2)避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。 实现时，allocator需要维护一个存储16个空闲块列表表头的数组free_list，数组元素i是一个指向块大小为8*(i+1)字节的空闲块列表的表头，一个指向内存池起始地址的指针start_free和一个指向结束地址的指针end_free。空闲块列表节点的结构如下：

[cpp]  view plain  copy union obj   {       union obj * free_list_link;       char client_data[1];   };         这个结构可以看做是从一个内存块中抠出4个字节大小来，当这个内存块空闲时，它存储了下个空闲块，当这个内存块交付给用户时，它存储的时用户的数据。因此，allocator中的空闲块链表可以表示成：     obj* free_list[16];       3、分配算法  [cpp]  view plain  copy // 算法：allocate   // 输入：申请内存的大小size   // 输出：若分配成功，则返回一个内存的地址，否则返回NULL   {       if(size 大于 128)           启动第一级分配器直接调用malloc分配所需的内存并返回内存地址；       else       {           将size向上round up成8的倍数并根据大小从free_list中取对应的表头free_list_head           if(free_list_head 不为空)           {               从该列表中取下第一个空闲块并调整free_list,返回free_list_head           }           else           {               调用refill算法建立空闲块列表并返回所需的内存地址           }       }   }         // 算法：refill   // 输入：内存块的大小size   // 输出：建立空闲块链表并返回第一个可用的内存地址   {       调用chunk_alloc算法分配若干个大小为size的连续内存区域并返回起始地址chunk和成功分配的块数nobj       if(块数为1)           直接返回 chunk;       else       {           开始在chunk地址块中建立free_list           根据size取free_list中对应的表头元素free_list_head            将free_list_head 指向chunk中偏移起始地址为size的地址处，即free_list_head = (obj*)(chunk+size)           再将整个chunk中剩下的nobj-1个内存块串联起来构成一个空闲列表           返回chunk，即chunk中第一个空闲的内存块       }   }         // 算法：chunk_alloc   // 输入：内存块的大小size,预分配的内存块数nobj(以引用传递)   // 输出：一块连续的内存区域的地址和该区域内可以容纳的内存块的块数   {       计算总共所需的内存大小total_bytes       if(内存池足以分配，即end_free-start_free >= total_bytes)       {           则更新start_free           返回旧的start_free       }       else if(内存池不够分配nobj个内存块，但至少可以分配一个)       {           计算可以分配的内存块数并修改nobj           更新start_free并返回原来的start_free       }       else     // 内存池连一个内存块都分配不了       {           先将内存池的内存块链入到对应的free_list中后           调用malloc操作重新分配内存池，大小为2倍的total_bytes为附加量，start_free指向返回的内存地址           if(分配不成功)           {               if(16个空闲列表中尚有空闲块)                   尝试将16个空闲列表中空闲块回收到内存池中再调用chunk_alloc(size,nobj)               else                   调用第一级分配器尝试out of memory机制是否还有用           }           更新end_free为start_free+total_bytes，heap_size为2倍的total_bytes           调用chunk_alloc(size,nobj)       }   }         // 算法：deallocate   // 输入：需要释放的内存块地址p和大小size   {       if(size 大于128字节)           直接调用free(p)释放       else       {           将size向上取8的倍数，并据此获取对应的空闲列表表头指针free_list_head           调整free_list_head将p链入空闲列表块中       }   }   假设这样一个场景，free_list[2]已经指向了大小为24字节的空闲块链表，如图1所示，当用户向allocator申请21字节大小的内存块时，allocaotr会首先检查free_list[2]并将free_list[2]所指的内存块分配给用户，然后将表头指向下一个可用的空闲块，如图2所示。注意，当内存块在链表上是，前4个字节是用作指向下一个空闲块，当分配给用户时，它是一块普通的内存区。                         图1 某时刻allocator的状态                                    图2 分配24字节大小的内存块  4、小结 STL中的内存分配器实际上是基于空闲列表(free list)的分配策略，最主要的特点是通过组织16个空闲列表，对小对象的分配做了优化。 1）小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。 2）避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。 3）尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域， 但是，这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的，比如上述：     stl::vector<int> array; array是知道它需要分配的对象大小为sizeof(int)。一个通用的内存分配器是不需要知道待释放内存的大小的，类似于free(p)。

STL源码剖析---vector

vector容器概述       vector的数据安排以及操作方式，与array非常相似。两者的唯一区别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变；要换个大（或小）一点的房子，可以，一切琐细都得由客户端自己来：首先配置一块新空间，然后将元素从旧址一一搬往新址，再把原来的空间释还给系统。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始要求一个大块头的array了，我们可以安心使用array，吃多少用多少。       vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧有空间满载，如果客户端每新增一个元素，vector的内部只是扩充一个元素的空间，实为不智。因为所谓扩充空间（不论多大），一如稍早所说，是”配置新空间/数据移动/释还旧空间“的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。稍后我们便可看到SGI vector的空间配置策略了。       另外，由于vector维护的是一个连续线性空间，所以vector支持随机存取。       注意：vector动态增加大小时，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心。 以下是vector定义的源代码摘录：

[cpp]  view plain  copy #include<iostream>   using namespace std;   #include<memory.h>        // alloc是SGI STL的空间配置器   template <class T, class Alloc = alloc>   class vector   {   public:       // vector的嵌套类型定义,typedefs用于提供iterator_traits<I>支持       typedef T value_type;       typedef value_type* pointer;       typedef value_type* iterator;       typedef value_type& reference;       typedef size_t size_type;       typedef ptrdiff_t difference_type;   protected:       // 这个提供STL标准的allocator接口       typedef simple_alloc <value_type, Alloc> data_allocator;          iterator start;               // 表示目前使用空间的头       iterator finish;              // 表示目前使用空间的尾       iterator end_of_storage;      // 表示实际分配内存空间的尾          void insert_aux(iterator position, const T& x);          // 释放分配的内存空间       void deallocate()       {           // 由于使用的是data_allocator进行内存空间的分配,           // 所以需要同样使用data_allocator::deallocate()进行释放           // 如果直接释放, 对于data_allocator内部使用内存池的版本           // 就会发生错误           if (start)               data_allocator::deallocate(start, end_of_storage - start);       }          void fill_initialize(size_type n, const T& value)       {           start = allocate_and_fill(n, value);           finish = start + n;                         // 设置当前使用内存空间的结束点           // 构造阶段, 此实作不多分配内存,           // 所以要设置内存空间结束点和, 已经使用的内存空间结束点相同           end_of_storage = finish;       }      public:       // 获取几种迭代器       iterator begin() { return start; }       iterator end() { return finish; }          // 返回当前对象个数       size_type size() const { return size_type(end() - begin()); }       size_type max_size() const { return size_type(-1) / sizeof(T); }       // 返回重新分配内存前最多能存储的对象个数       size_type capacity() const { return size_type(end_of_storage - begin()); }       bool empty() const { return begin() == end(); }       reference operator[](size_type n) { return *(begin() + n); }          // 本实作中默认构造出的vector不分配内存空间       vector() : start(0), finish(0), end_of_storage(0) {}             vector(size_type n, const T& value) { fill_initialize(n, value); }       vector(int n, const T& value) { fill_initialize(n, value); }       vector(long n, const T& value) { fill_initialize(n, value); }          // 需要对象提供默认构造函数       explicit vector(size_type n) { fill_initialize(n, T()); }          vector(const vector<T, Alloc>& x)       {           start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());           finish = start + (x.end() - x.begin());           end_of_storage = finish;       }          ~vector()       {           // 析构对象           destroy(start, finish);           // 释放内存           deallocate();       }          vector<T, Alloc>& operator=(const vector<T, Alloc>& x);          // 提供访问函数       reference front() { return *begin(); }       reference back() { return *(end() - 1); }                 // 向容器尾追加一个元素, 可能导致内存重新分配              //                          push_back(const T& x)       //                                   |       //                                   |---------------- 容量已满?       //                                   |       //               ----------------------------       //           No  |                          |  Yes       //               |                          |       //               ↓                          ↓       //      construct(finish, x);       insert_aux(end(), x);       //      ++finish;                           |       //                                          |------ 内存不足, 重新分配       //                                          |       大小为原来的2倍       //      new_finish = data_allocator::allocate(len);       <stl_alloc.h>       //      uninitialized_copy(start, position, new_start);   <stl_uninitialized.h>       //      construct(new_finish, x);                         <stl_construct.h>       //      ++new_finish;       //      uninitialized_copy(position, finish, new_finish); <stl_uninitialized.h>                 void push_back(const T& x)       {           // 内存满足条件则直接追加元素, 否则需要重新分配内存空间           if (finish != end_of_storage)           {               construct(finish, x);               ++finish;           }           else               insert_aux(end(), x);       }                    // 在指定位置插入元素              //                   insert(iterator position, const T& x)       //                                   |       //                                   |------------ 容量是否足够 && 是否是end()?       //                                   |       //               -------------------------------------------       //            No |                                         | Yes       //               |                                         |       //               ↓                                         ↓       //    insert_aux(position, x);                  construct(finish, x);       //               |                              ++finish;       //               |-------- 容量是否够用?       //               |       //        --------------------------------------------------       //    Yes |                                                | No       //        |                                                |       //        ↓                                                |       // construct(finish, *(finish - 1));                       |       // ++finish;                                               |       // T x_copy = x;                                           |       // copy_backward(position, finish - 2, finish - 1);        |       // *position = x_copy;                                     |       //                                                         ↓       // data_allocator::allocate(len);                       <stl_alloc.h>       // uninitialized_copy(start, position, new_start);      <stl_uninitialized.h>       // construct(new_finish, x);                            <stl_construct.h>       // ++new_finish;       // uninitialized_copy(position, finish, new_finish);    <stl_uninitialized.h>       // destroy(begin(), end());                             <stl_construct.h>       // deallocate();                 iterator insert(iterator position, const T& x)       {           size_type n = position - begin();           if (finish != end_of_storage && position == end())           {               construct(finish, x);               ++finish;           }           else               insert_aux(position, x);           return begin() + n;       }          iterator insert(iterator position) { return insert(position, T()); }          void pop_back()       {           --finish;           destroy(finish);       }          iterator erase(iterator position)       {           if (position + 1 != end())               copy(position + 1, finish, position);           --finish;           destroy(finish);           return position;       }             iterator erase(iterator first, iterator last)       {           iterator i = copy(last, finish, first);           // 析构掉需要析构的元素           destroy(i, finish);           finish = finish - (last - first);           return first;       }          // 调整size, 但是并不会重新分配内存空间       void resize(size_type new_size, const T& x)       {           if (new_size < size())               erase(begin() + new_size, end());           else               insert(end(), new_size - size(), x);       }       void resize(size_type new_size) { resize(new_size, T()); }          void clear() { erase(begin(), end()); }      protected:       // 分配空间, 并且复制对象到分配的空间处       iterator allocate_and_fill(size_type n, const T& x)       {           iterator result = data_allocator::allocate(n);           uninitialized_fill_n(result, n, x);           return result;       }          // 提供插入操作              //                 insert_aux(iterator position, const T& x)       //                                   |       //                                   |---------------- 容量是否足够?       //                                   ↓       //              -----------------------------------------       //        Yes   |                                       | No       //              |                                       |       //              ↓                                       |       // 从opsition开始, 整体向后移动一个位置                     |       // construct(finish, *(finish - 1));                    |       // ++finish;                                            |       // T x_copy = x;                                        |       // copy_backward(position, finish - 2, finish - 1);     |       // *position = x_copy;                                  |       //                                                      ↓       //                            data_allocator::allocate(len);       //                            uninitialized_copy(start, position, new_start);       //                            construct(new_finish, x);       //                            ++new_finish;       //                            uninitialized_copy(position, finish, new_finish);       //                            destroy(begin(), end());       //                            deallocate();                 template <class T, class Alloc>       void insert_aux(iterator position, const T& x)       {           if (finish != end_of_storage)    // 还有备用空间           {               // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值               construct(finish, *(finish - 1));               ++finish;               T x_copy = x;               copy_backward(position, finish - 2, finish - 1);               *position = x_copy;           }           else   // 已无备用空间           {               const size_type old_size = size();               const size_type len = old_size != 0 ? 2 * old_size : 1;               // 以上配置元素：如果大小为0，则配置1（个元素大小）               // 如果大小不为0，则配置原来大小的两倍               // 前半段用来放置原数据，后半段准备用来放置新数据                  iterator new_start = data_allocator::allocate(len);  // 实际配置               iterator new_finish = new_start;               // 将内存重新配置               try               {                   // 将原vector的安插点以前的内容拷贝到新vector                   new_finish = uninitialized_copy(start, position, new_start);                   // 为新元素设定初值 x                   construct(new_finish, x);                   // 调整水位                   ++new_finish;                   // 将安插点以后的原内容也拷贝过来                   new_finish = uninitialized_copy(position, finish, new_finish);               }               catch(...)               {                   // 回滚操作                   destroy(new_start, new_finish);                   data_allocator::deallocate(new_start, len);                   throw;               }               // 析构并释放原vector               destroy(begin(), end());               deallocate();                  // 调整迭代器，指向新vector               start = new_start;               finish = new_finish;               end_of_storage = new_start + len;           }       }                 // 在指定位置插入n个元素              //             insert(iterator position, size_type n, const T& x)       //                                   |       //                                   |---------------- 插入元素个数是否为0?       //                                   ↓       //              -----------------------------------------       //        No    |                                       | Yes       //              |                                       |       //              |                                       ↓       //              |                                    return;       //              |----------- 内存是否足够?       //              |       //      -------------------------------------------------       //  Yes |                                               | No       //      |                                               |       //      |------ (finish - position) > n?                |       //      |       分别调整指针                              |       //      ↓                                               |       //    ----------------------------                      |       // No |                          | Yes                  |       //    |                          |                      |       //    ↓                          ↓                      |       // 插入操作, 调整指针           插入操作, 调整指针           |       //                                                      ↓       //            data_allocator::allocate(len);       //            new_finish = uninitialized_copy(start, position, new_start);       //            new_finish = uninitialized_fill_n(new_finish, n, x);       //            new_finish = uninitialized_copy(position, finish, new_finish);       //            destroy(start, finish);       //            deallocate();                 template <class T, class Alloc>       void insert(iterator position, size_type n, const T& x)       {           // 如果n为0则不进行任何操作           if (n != 0)           {               if (size_type(end_of_storage - finish) >= n)               {      // 剩下的备用空间大于等于“新增元素的个数”                   T x_copy = x;                   // 以下计算插入点之后的现有元素个数                   const size_type elems_after = finish - position;                   iterator old_finish = finish;                   if (elems_after > n)                   {                       // 插入点之后的现有元素个数 大于 新增元素个数                       uninitialized_copy(finish - n, finish, finish);                       finish += n;    // 将vector 尾端标记后移                       copy_backward(position, old_finish - n, old_finish);                       fill(position, position + n, x_copy); // 从插入点开始填入新值                   }                   else                   {                       // 插入点之后的现有元素个数 小于等于 新增元素个数                       uninitialized_fill_n(finish, n - elems_after, x_copy);                       finish += n - elems_after;                       uninitialized_copy(position, old_finish, finish);                       finish += elems_after;                       fill(position, old_finish, x_copy);                   }               }               else               {   // 剩下的备用空间小于“新增元素个数”（那就必须配置额外的内存）                   // 首先决定新长度：就长度的两倍 ， 或旧长度+新增元素个数                   const size_type old_size = size();                   const size_type len = old_size + max(old_size, n);                   // 以下配置新的vector空间                   iterator new_start = data_allocator::allocate(len);                   iterator new_finish = new_start;                   __STL_TRY                   {                       // 以下首先将旧的vector的插入点之前的元素复制到新空间                       new_finish = uninitialized_copy(start, position, new_start);                       // 以下再将新增元素（初值皆为n）填入新空间                       new_finish = uninitialized_fill_n(new_finish, n, x);                       // 以下再将旧vector的插入点之后的元素复制到新空间                       new_finish = uninitialized_copy(position, finish, new_finish);                   }   #         ifdef  __STL_USE_EXCEPTIONS                   catch(...)                   {                       destroy(new_start, new_finish);                       data_allocator::deallocate(new_start, len);                       throw;                   }   #         endif /* __STL_USE_EXCEPTIONS */                   destroy(start, finish);                   deallocate();                   start = new_start;                   finish = new_finish;                   end_of_storage = new_start + len;               }           }       }   };   STL源码剖析---list

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。       list不仅是一个双向链表，而且还是一个环状双向链表。另外，还有一个重要性质，插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。 以下是list的节点、迭代器数据结构设计以及list的源码剖析：

[cpp]  view plain  copy    // list结点, 提供双向访问能力      //  --------           --------           --------           --------   //  | next |---------->| next |---------->| next |---------->| next |   //  --------           --------           --------           --------   //  | prev |<----------| prev |<----------| prev |<----------| prev |   //  --------           --------           --------           --------   //  | data |           | data |           | data |           | data |   //  --------           --------           --------           --------         template <class T>   struct __list_node   {       typedef void* void_pointer;       void_pointer next;       void_pointer prev;       T data;   };      // 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,   // 而作者又不想维护两份代码, 故不使用默认参数   template<class T, class Ref, class Ptr>   struct __list_iterator   {       typedef __list_iterator<T, T&, T*>             iterator;   // STL标准强制要求       typedef __list_iterator<T, Ref, Ptr>           self;          typedef bidirectional_iterator_tag iterator_category;       typedef T value_type;       typedef Ptr pointer;       typedef Ref reference;       typedef __list_node<T>* link_type;       typedef size_t size_type;       typedef ptrdiff_t difference_type;          link_type node;   //迭代器内部当然要有一个普通指针，指向list的节点          __list_iterator(link_type x) : node(x) {}       __list_iterator() {}       __list_iterator(const iterator& x) : node(x.node) {}          // 在STL算法中需要迭代器提供支持       bool operator==(const self& x) const { return node == x.node; }       bool operator!=(const self& x) const { return node != x.node; }          // 以下对迭代器取值（dereference）,取的是节点的数据值       reference operator*() const { return (*node).data; }          // 以下是迭代器的成员存取运算子的标准做法       pointer operator->() const { return &(operator*()); }          // 前缀自加，对迭代器累加1，就是前进一个节点       self& operator++()       {           node = (link_type)((*node).next);           return *this;       }          // 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本       self operator++(int)       {           self tmp = *this;           ++*this;           return tmp;       }          // 前缀自减       self& operator--()       {           node = (link_type)((*node).prev);           return *this;       }          self operator--(int)       {           self tmp = *this;           --*this;           return tmp;       }   };         // list不仅是个双向链表, 而且还是一个环状双向链表      //       end()              头结点             begin()   //         ↓                  ↓                  ↓   //      --------           --------           --------           --------   // ---->| next |---------->| next |---------->| next |---------->| next |------   // |    --------           --------           --------           --------     |   // |  --| prev |<----------| prev |<----------| prev |<----------| prev |<--| |   // |  | --------           --------           --------           --------   | |   // |  | | data |           | data |           | data |           | data |   | |   // |  | --------           --------           --------           --------   | |   // |  |                                                                     | |   // |  | --------           --------           --------           --------   | |   // ---|-| next |<----------| next |<----------| next |<----------| next |<--|--   //    | --------           --------           --------           --------   |   //    ->| prev |---------->| prev |---------->| prev |---------->| prev |----   //      --------           --------           --------           --------   //      | data |           | data |           | data |           | data |   //      --------           --------           --------           --------         // 默认allocator为alloc, 其具体使用版本请参照<stl_alloc.h>   template <class T, class Alloc = alloc>   class list   {   protected:       typedef void* void_pointer;       typedef __list_node<T> list_node;          // 专属之空间配置器，每次配置一个节点大小       typedef simple_alloc<list_node, Alloc> list_node_allocator;      public:       typedef T value_type;       typedef value_type* pointer;       typedef value_type& reference;       typedef list_node* link_type;       typedef size_t size_type;       typedef ptrdiff_t difference_type;          typedef __list_iterator<T, T&, T*>             iterator;      protected:       link_type node ;     // 只要一个指针，便可表示整个环状双向链表       // 分配一个新结点, 注意这里并不进行构造,       // 构造交给全局的construct, 见<stl_stl_uninitialized.h>       link_type get_node() { return list_node_allocator::allocate(); }          // 释放指定结点, 不进行析构, 析构交给全局的destroy       void put_node(link_type p) { list_node_allocator::deallocate(p); }          // 产生（配置并构造）一个节点, 首先分配内存, 然后进行构造       // 注: commit or rollback       link_type create_node(const T& x)       {           link_type p = get_node();           construct(&p->data, x);           return p;       }          // 析构结点元素, 并释放内存       void destroy_node(link_type p)       {           destroy(&p->data);           put_node(p);       }      protected:       // 用于空链表的建立       void empty_initialize()       {           node = get_node();   // 配置一个节点空间，令node指向它           node->next = node;   // 令node头尾都指向自己，不设元素值           node->prev = node;       }        // 创建值为value共n个结点的链表     // 注: commit or rollback       void fill_initialize(size_type n, const T& value)       {           empty_initialize();           __STL_TRY           {               // 此处插入操作时间复杂度O(1)               insert(begin(), n, value);           }           __STL_UNWIND(clear(); put_node(node));       }             public:       list() { empty_initialize(); }          iterator begin() { return (link_type)((*node).next); }          // 链表成环, 当指所以头节点也就是end       iterator end() { return node; }          // 头结点指向自身说明链表中无元素       bool empty() const { return node->next == node; }          // 使用全局函数distance()进行计算, 时间复杂度O(n)       size_type size() const       {           size_type result = 0;           distance(begin(), end(), result);           return result;       }          size_type max_size() const { return size_type(-1); }       reference front() { return *begin(); }       reference back() { return *(--end()); }                 // 在指定位置插入元素              //       insert(iterator position, const T& x)       //                       ↓       //                 create_node(x)       //                 p = get_node();-------->list_node_allocator::allocate();       //                 construct(&p->data, x);       //                       ↓       //            tmp->next = position.node;       //            tmp->prev = position.node->prev;       //            (link_type(position.node->prev))->next = tmp;       //            position.node->prev = tmp;                 iterator insert(iterator position, const T& x)       {           link_type tmp = create_node(x);   // 产生一个节点           // 调整双向指针，使tmp插入进去           tmp->next = position.node;           tmp->prev = position.node->prev;           (link_type(position.node->prev))->next = tmp;           position.node->prev = tmp;           return tmp;       }        // 指定位置插入n个值为x的元素, 详细解析见实现部分     void insert(iterator pos, size_type n, const T& x);     void insert(iterator pos, int n, const T& x)     {         insert(pos, (size_type)n, x);     }     void insert(iterator pos, long n, const T& x)     {         insert(pos, (size_type)n, x);     }        // 在链表前端插入结点     void push_front(const T& x) { insert(begin(), x); }     // 在链表最后插入结点     void push_back(const T& x) { insert(end(), x); }        // 移除迭代器position所指节点     iterator erase(iterator position)     {         link_type next_node = link_type(position.node->next);         link_type prev_node = link_type(position.node->prev);         prev_node->next = next_node;         next_node->prev = prev_node;         destroy_node(position.node);         return iterator(next_node);     }        // 擦除一个区间的结点, 详细解析见实现部分     iterator erase(iterator first, iterator last);        void resize(size_type new_size, const T& x);     void resize(size_type new_size) { resize(new_size, T()); }     void clear();        // 删除链表第一个结点     void pop_front() { erase(begin()); }     // 删除链表最后一个结点     void pop_back()     {         iterator tmp = end();         erase(--tmp);     }        list(size_type n, const T& value) { fill_initialize(n, value); }     list(int n, const T& value) { fill_initialize(n, value); }     list(long n, const T& value) { fill_initialize(n, value); }        ~list()     {       // 释放所有结点  // 使用全局函数distance()进行计算, 时间复杂度O(n)     size_type size() const     {       size_type result = 0;       distance(begin(), end(), result);       return result;     }     clear();     // 释放头结点     put_node(node);     }        list<T, Alloc>& operator=(const list<T, Alloc>& x);      protected:                 // 将[first, last)内的所有元素移动到position之前       // 如果last == position, 则相当于链表不变化, 不进行操作              // 初始状态       //                   first                             last       //                     ↓                                 ↓       //      --------   --------   --------     --------   --------   --------       //      | next |-->| next |-->| next |     | next |-->| next |-->| next |       //  ... --------   --------   -------- ... --------   --------   -------- ...       //      | prev |<--| prev |<--| prev |     | prev |<--| prev |<--| prev |       //      --------   --------   --------     --------   --------   --------       //       //                           position       //                               ↓       //      --------   --------   --------   --------   --------   --------       //      | next |-->| next |-->| next |-->| next |-->| next |-->| next |       //  ... --------   --------   --------   --------   --------   -------- ...       //      | prev |<--| prev |<--| prev |<--| prev |<--| prev |<--| prev |       //      --------   --------   --------   --------   --------   --------       //       // 操作完成后状态       //                           first       //                             |       //               --------------|--------------------------------------       //               | ------------|------------------------------------ |   last       //               | |           ↓                                   | |     ↓       //      -------- | |        --------   --------     --------       | |  --------   --------       //      | next |-- |  ----->| next |-->| next |     | next |-----  | -->| next |-->| next |       //  ... --------   |  |     --------   -------- ... --------    |  |    --------   -------- ...       //      | prev |<---  |  ---| prev |<--| prev |     | prev |<-- |  -----| prev |<--| prev |       //      --------      |  |  --------   --------     --------  | |       --------   --------       //                    |  |                                    | |       //                    |  ------                               | |       //                    ------- |  ------------------------------ |       //                          | |  |                              |       //                          | |  |  -----------------------------       //                          | |  |  |       //                          | |  |  |  position       //                          | |  |  |     ↓       //      --------   -------- | |  |  |  --------   --------   --------   --------       //      | next |-->| next |-- |  |  -->| next |-->| next |-->| next |-->| next |       //  ... --------   --------   |  |     --------   --------   --------   -------- ...       //      | prev |<--| prev |<---  ------| prev |<--| prev |<--| prev |<--| prev |       //      --------   --------            --------   --------   --------   --------              void transfer(iterator position, iterator first, iterator last)       {           if (position != last)   // 如果last == position, 则相当于链表不变化, 不进行操作           {               (*(link_type((*last.node).prev))).next = position.node;               (*(link_type((*first.node).prev))).next = last.node;               (*(link_type((*position.node).prev))).next = first.node;               link_type tmp = link_type((*position.node).prev);               (*position.node).prev = (*last.node).prev;               (*last.node).prev = (*first.node).prev;               (*first.node).prev = tmp;           }       }      public:       // 将链表x移动到position所指位置之前       void splice(iterator position, list& x)       {           if (!x.empty())               transfer(position, x.begin(), x.end());       }          // 将链表中i指向的内容移动到position之前       void splice(iterator position, list&, iterator i)       {           iterator j = i;           ++j;           if (position == i || position == j) return;           transfer(position, i, j);       }          // 将[first, last}元素移动到position之前       void splice(iterator position, list&, iterator first, iterator last)       {           if (first != last)               transfer(position, first, last);       }          void remove(const T& value);       void unique();       void merge(list& x);       void reverse();       void sort();      };      // 销毁所有结点, 将链表置空   template <class T, class Alloc>   void list<T, Alloc>::clear()   {     link_type cur = (link_type) node->next;     while (cur != node)     {       link_type tmp = cur;       cur = (link_type) cur->next;       destroy_node(tmp);     }     // 恢复node原始状态     node->next = node;     node->prev = node;   }      // 链表赋值操作   // 如果当前容器元素少于x容器, 则析构多余元素,   // 否则将调用insert插入x中剩余的元素   template <class T, class Alloc>   list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x)   {     if (this != &x)     {       iterator first1 = begin();       iterator last1 = end();       const_iterator first2 = x.begin();       const_iterator last2 = x.end();       while (first1 != last1 && first2 != last2) *first1++ = *first2++;       if (first2 == last2)         erase(first1, last1);       else         insert(last1, first2, last2);     }     return *this;   }         // 移除容器内所有的相邻的重复结点   // 时间复杂度O(n)   // 用户自定义数据类型需要提供operator ==()重载   template <class T, class Alloc>   void list<T, Alloc>::unique()   {     iterator first = begin();     iterator last = end();     if (first == last) return;     iterator next = first;     while (++next != last)     {       if (*first == *next)         erase(next);       else         first = next;       next = first;     }   }      // 假设当前容器和x都已序, 保证两容器合并后仍然有序   template <class T, class Alloc>   void list<T, Alloc>::merge(list<T, Alloc>& x)   {     iterator first1 = begin();     iterator last1 = end();     iterator first2 = x.begin();     iterator last2 = x.end();        // 注意：前提是，两个lists都已经递增排序     while (first1 != last1 && first2 != last2)       if (*first2 < *first1)       {         iterator next = first2;         transfer(first1, first2, ++next);         first2 = next;       }       else         ++first1;     if (first2 != last2)         transfer(last1, first2, last2);   }  

STL源码剖析---deque

一、deque的中控器       deque是连续空间（至少逻辑上看来如此），连续线性空间总令我们联想到array或vector。array无法成长，vector虽可成长，却只能向尾端成长，而且其所谓的成长原是个假象，事实上是（1）另觅更大空间；（2）将原数据复制过去；（3）释放原空间三部曲。如果不是vector每次配置新空间时都有留下一些余裕，其成长假象所带来的代价将是相当高昂。       deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的借口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。       受到分段连续线性空间的字面影响，我们可能以为deque的实现复杂度和vector相比虽不中亦不远矣，其实不然。主要因为，既是分段连续线性空间，就必须有中央控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。deque的实现代码分量远比vector或list都多得多。       deque采用一块所谓的map（注意，不是STL的map容器）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL 允许我们指定缓冲区大小，默认值0表示将使用512 bytes 缓冲区。 二、deque的迭代器       让我们思考一下，deque的迭代器应该具备什么结构，首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）。所以在迭代器中需要定义：当前元素的指针，当前元素所在缓冲区的起始指针，当前元素所在缓冲区的尾指针，指向map中指向所在缓区地址的指针。 在进行迭代器的移动时，需要考虑跨缓冲区的情况。 重载前加(减)，在实现后加(减)时，调用重载的前加(减)。 重载+=,实现+时，直接调用+=,实现-=时，调用+=负数，实现-时，调用-=. //当需要实现新的功能时，最好使用已经重载好的操作，即方便有安全。。。。 另外，deque在效率上来说是不够vector好的，因此有时候在对deque进行sort的时候，需要先将元素移到vector再进行sort，然后移回来。 构造函数：根据缓冲区设置大小和元素个数，决定map的大小；给map分配空间，根据缓冲区的个数，分配缓冲区，默认指定一个缓冲区；  设置start和finish迭代器，满足左闭右开的原则。  push_back:如果空间满足，直接插入；不满足，调用push_back_aux。  push_back_aux:先调用reverse_map_at_back,若符合某种条件，重换一个map；分配空间。  reserve_map_at_back:看看map有没有满，满的话，调用reallocate_map。  reallocate_map:如果前端或后端pop过多，就会导致大量的空闲空间，如果是这种情况，则不用新分配空间，调整一下start的位置即可；  如果不够，则需要重新申请空间。  pop：析构元素，如果是最后一块还需要删除空间。  erase：需要判断，前面的元素少还是后面的元素少，移动较少的部分。  insert：判断位置，如果为前端或后端直接调用push操作，否则，移动较少的一端。 deque的构造与内存管理： 由于deque的设计思想就是由一块块的缓存区连接起来的，因此它的内存管理会比较复杂。插入的时候要考虑是否要跳转缓存区、是否要新建map节点（和vector一样，其实是重新分配一块空间给map，删除原来空间）、插入后元素是前面元素向前移动还是后面元素向后面移动（谁小移动谁）。而在删除元素的时候，考虑是将前面元素后移覆盖需要移除元素的地方还是后面元素前移覆盖（谁小移动谁）。移动完以后要析构冗余的元素，释放冗余的缓存区。  三、deque的源码剖析

[cpp]  view plain  copy //   deque的特性:   //   对于任何一个迭代器i   //     i.node是map array中的某元素的地址. i.node的内容是一个指向某个结点的头的指针   //     i.first == *(i.node)   //     i.last  == i.first + node_size   //     i.cur是一个指向[i.first, i.last)之间的指针   //       注意: 这意味着i.cur永远是一个可以解引用的指针,   //            即使其是一个指向结尾后元素的迭代器   //   //   起点和终点总是非奇异(nonsingular)的迭代器.   //     注意: 这意味着空deque一定有一个node, 而一个具有N个元素的deque   //          (N是Buffer Size)一定有有两个nodes   //   //   对于除了start.node和finish.node之外的每一个node, 每一个node中的元素   //   都是一个初始化过的对象. 如果start.node == finish.node,   //   那么[start.cur, finish.cur)都是未初始化的空间.   //   否则, [start.cur, start.last)和[finish.first, finish.cur)都是初始化的对象,   //   而[start.first, start.cur)和[finish.cur, finish.last)是未初始化的空间   //   //   [map, map + map_size)是一个合法的非空区间   //   [start.node, finish.node]是内含在[map, map + map_size)区间的合法区间   //   一个在[map, map + map_size)区间内的指针指向一个分配过的node,   //   当且仅当此指针在[start.node, finish.node]区间内      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));     }      // __deque_iterator的数据结构   template <class T, class Ref, class Ptr, size_t BufSiz>   struct __deque_iterator   {       typedef __deque_iterator<T, T&, T*>             iterator;       typedef __deque_iterator<T, const T&, const T*> const_iterator;       static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }          typedef random_access_iterator_tag iterator_category;       typedef T value_type;       typedef Ptr pointer;       typedef Ref reference;       typedef size_t size_type;       typedef ptrdiff_t difference_type;       typedef T** map_pointer;          typedef __deque_iterator self;          // 保持与容器的联结       T* cur;       // 此迭代器所指之缓冲区中的现行元素       T* first;     // 此迭代器所指之缓冲区的头       T* last;      // 此迭代器所指之缓冲区的尾（含备用空间）       map_pointer node;    // 指向管控中心         // 这个是deque内存管理的关键, 其模型如下      //   //       ---------------------------------------------   // map-->|   |   |   |   |   |   | ..... |   |   |   |<------------------   //       ---------------------------------------------                  |   //             |                                                        |   //             |                                                        |   //             |   node                                                 |   //             |   缓冲区buffer, 这里实际存储元素                          |   //             |   ---------------------------------------------        |   //             --->|   |   |   |   |   |   | ..... |   |   | X |        |   //                 ---------------------------------------------        |   //                   ↑       ↑                             ↑            |   //             ------        |                             |            |   //             |             |                             |            |   //             |   -----------   ---------------------------            |   //             ----|-----        |                                      |   //                 |    |        |                                      |   //                 |    |        |                                      |   //                 |    |        |                                      |   //              ---------------------------                             |   //              | cur | first | end | map |------------------------------   //              ---------------------------   //              迭代器, 其内部维护着一个缓冲区状态          __deque_iterator(T* x, map_pointer y)           : cur(x), first(*y), last(*y + buffer_size()), node(y) {}       __deque_iterator() : cur(0), first(0), last(0), node(0) {}       __deque_iterator(const iterator& x)           : cur(x.cur), first(x.first), last(x.last), node(x.node) {}          reference operator*() const { return *cur; }          // 判断两个迭代器间的距离       difference_type operator-(const self& x) const       {           return difference_type(buffer_size()) * (node - x.node - 1) +               (cur - first) + (x.last - x.cur);       }         // 下面重载的这些运算符是让deque从外界看上去维护的是一段连续空间的关键!!!      // 前缀自增      // 如果当前迭代器指向元素是当前缓冲区的最后一个元素,   // 则将迭代器状态调整为下一个缓冲区的第一个元素      // 不是当前缓冲区最后一个元素   //   // 执行前缀自增前的状态   // first          cur                     end   // ↓               ↓                       ↓   // ---------------------------------------------   // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区   // ---------------------------------------------   //   // 执行完成后的状态   // first              cur                 end   // ↓                   ↓                   ↓   // ---------------------------------------------   // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区   // ---------------------------------------------   //      // 当前元素为当前缓冲区的最后一个元素   //   // 执行前缀自增前的状态   // first                              cur end   // ↓                                   ↓   ↓   // ---------------------------------------------   // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区   // ---------------------------------------------   //   // 执行完成后的状态   // first                                  end   // ↓                                       ↓   // ---------------------------------------------   // |   |   |   |   |   |   | ..... |   |   | X | <----- 下一缓冲区   // ---------------------------------------------   // ↑   // cur   //          self& operator++()       {           ++cur;    // 切换至下一个元素           if (cur == last)    // 如果已达到缓冲区的尾端           {               set_node(node + 1);    // 就切换至下一节点（亦即缓冲区）               cur = first;           // 的第一个元素           }           return *this;       }          // 后缀自增       // 返回当前迭代器的一个副本, 并调用前缀自增运算符实现迭代器自身的自增       self operator++(int)       {           self tmp = *this;           ++*this;           return tmp;       }          // 前缀自减, 处理方式类似于前缀自增       // 如果当前迭代器指向元素是当前缓冲区的第一个元素       // 则将迭代器状态调整为前一个缓冲区的最后一个元素       self& operator--()       {           if (cur == first)    // 如果已达到缓冲区的头端           {               set_node(node - 1);    // 就切换至前一节点（亦即缓冲区）               cur = last;            // 的最后一个元素           }           --cur;           return *this;       }          self operator--(int)       {           self tmp = *this;           --*this;           return tmp;       }         // 将迭代器向前移动n个元素, n可以为负      //                     operator+=(difference_type n)   //                                   ↓   //                      offset = n + (cur - first)   //                                   |   //                                   |---------- offset > 0 ? &&   //                                   |           移动后是否超出当前缓冲区?   //               ----------------------------   //           No  |                          |  Yes   //               |                          |   //               ↓                          |---------- offset > 0?   //           cur += n;                      |   //                              ----------------------------   //                          Yes |                          | No   //                              |                          |   //                              ↓                          |   //                   计算要向后移动多少个缓冲区                |   //                   node_offset =                         |   //                   offset / difference_type              |   //                   (buffer_size());                      ↓   //                              |           计算要向前移动多少个缓冲区   //                              |           node_offset = -difference_type   //                              |           ((-offset - 1) / buffer_size()) - 1;   //                              |                          |   //                              ----------------------------   //                                           |   //                                           |   //                                           ↓   //                                       调整缓冲区   //                              set_node(node + node_offset);   //                                    计算并调整cur指针          // 以下实现随机存取。迭代器可以直接跳跃n个距离       self& operator+=(difference_type n)       {           difference_type offset = n + (cur - first);           if (offset >= 0 && offset < difference_type(buffer_size()))               cur += n;        // 目标位置在同一缓冲区内           else           {           // 目标位置不在同一缓冲区内               difference_type node_offset =                   offset > 0 ? offset / difference_type(buffer_size())                   : -difference_type((-offset - 1) / buffer_size()) - 1;               // 切换至正确的节点（亦即缓冲区）               set_node(node + node_offset);               // 切换至正确的元素               cur = first + (offset - node_offset * difference_type(buffer_size()));           }           return *this;       }          self operator+(difference_type n) const       {           self tmp = *this;              // 这里调用了operator +=()可以自动调整指针状态           return tmp += n;       }          // 将n变为-n就可以使用operator +=()了,       self& operator-=(difference_type n) { return *this += -n; }          self operator-(difference_type n) const       {           self tmp = *this;           return tmp -= n;       }          reference operator[](difference_type n) const { return *(*this + n); }          bool operator==(const self& x) const { return cur == x.cur; }       bool operator!=(const self& x) const { return !(*this == x); }       bool operator<(const self& x) const       {           return (node == x.node) ? (cur < x.cur) : (node < x.node);       }          void set_node(map_pointer new_node)       {           node = new_node;           first = *new_node;           last = first + difference_type(buffer_size());       }   };         // deque的数据结构   template <class T, class Alloc = alloc, size_t BufSiz = 0>   class deque   {   public:                         // Basic types       typedef T value_type;       typedef value_type* pointer;       typedef value_type& reference;       typedef size_t size_type;       typedef ptrdiff_t difference_type;      public:                         // Iterators       typedef __deque_iterator<T, T&, T*, BufSiz>       iterator;      protected:                      // Internal typedefs          typedef pointer* map_pointer;          // 这个提供STL标准的allocator接口, 见<stl_alloc.h>       typedef simple_alloc<value_type, Alloc> data_allocator;       typedef simple_alloc<pointer, Alloc> map_allocator;          // 获取缓冲区最大存储元素数量       static size_type buffer_size()       {           return __deque_buf_size(BufSiz, sizeof(value_type));       }          static size_type initial_map_size() { return 8; }      protected:                      // Data members       iterator start;               // 起始缓冲区       iterator finish;              // 最后一个缓冲区          // 指向map, map是一个连续的空间, 其每个元素都是一个指针，指向一个节点（缓冲区）       map_pointer map;       size_type map_size;   // map容量      public:       iterator begin() { return start; }       iterator end() { return finish; }          // 提供随机访问能力, 其调用的是迭代器重载的operator []       // 其实际地址需要进行一些列的计算, 效率有损失       reference operator[](size_type n) { return start[difference_type(n)]; }          reference front() { return *start; }       reference back()       {           iterator tmp = finish;           --tmp;           return *tmp;       }          // 当前容器拥有的元素个数, 调用迭代器重载的operator -       size_type size() const { return finish - start;; }       size_type max_size() const { return size_type(-1); }          // deque为空的时, 只有一个缓冲区       bool empty() const { return finish == start; }      public:                         // Constructor, destructor.       deque() : start(), finish(), map(0), map_size(0)       {           create_map_and_nodes(0);       }          deque(size_type n, const value_type& value)           : start(), finish(), map(0), map_size(0)       {           fill_initialize(n, value);       }          deque(int n, const value_type& value)           : start(), finish(), map(0), map_size(0)       {           fill_initialize(n, value);       }             ~deque()       {           destroy(start, finish);     // <stl_construct.h>           destroy_map_and_nodes();       }          deque& operator= (const deque& x)       {           // 其实我觉得把这个操作放在if内效率更高           const size_type len = size();           if (&x != this)           {               // 当前容器比x容器拥有元素多, 析构多余元素               if (len >= x.size())                   erase(copy(x.begin(), x.end(), start), finish);               // 将x所有超出部分的元素使用insert()追加进去               else {                   const_iterator mid = x.begin() + difference_type(len);                   copy(x.begin(), mid, start);                   insert(finish, mid, x.end());               }           }           return *this;       }      public:       void push_back(const value_type& t)       {           // 最后缓冲区尚有两个（含）以上的元素备用空间           if (finish.cur != finish.last - 1)           {               construct(finish.cur, t);     // 直接在备用空间上构造元素               ++finish.cur;     // 调整最后缓冲区的使用状态           }           // 容量已满就要新申请内存了           else               push_back_aux(t);       }          void push_front(const value_type& t)       {           if (start.cur != start.first)      // 第一缓冲区尚有备用空间           {               construct(start.cur - 1, t);   // 直接在备用空间上构造元素               --start.cur;     // 调整第一缓冲区的使用状态           }           else    // 第一缓冲区已无备用空间               push_front_aux(t);       }          void pop_back()       {           if (finish.cur != finish.first)    // 最后缓冲区有一个（或更多）元素           {               --finish.cur;    // 调整指针，相当于排除了最后元素               destroy(finish.cur);    // 将最后元素析构           }           else               // 最后缓冲区没有任何元素               pop_back_aux();    // 这里将进行缓冲区的释放工作       }          void pop_front()       {           if (start.cur != start.last - 1)    // 第一缓冲区有两个（或更多）元素           {               destroy(start.cur);    // 将第一元素析构               ++start.cur;           //调整指针，相当于排除了第一元素           }           else               // 第一缓冲区仅有一个元素               pop_front_aux();    // 这里将进行缓冲区的释放工作       }      public:                         // Insert         // 在指定位置前插入元素      //             insert(iterator position, const value_type& x)   //                                   |   //                                   |---------------- 判断插入位置   //                                   |   //               -----------------------------------------------   // deque.begin() |          deque.emd() |                      |   //               |                      |                      |   //               ↓                      ↓                      |   //         push_front(x);         push_back(x);                |   //                                                             ↓   //                                                 insert_aux(position, x);   //                                                 具体剖析见后面实现             iterator insert(iterator position, const value_type& x)       {           // 如果是在deque的最前端插入, 那么直接push_front()即可           if (position.cur == start.cur)           {               push_front(x);               return start;           }           // 如果是在deque的末尾插入, 直接调用push_back()           else if (position.cur == finish.cur)           {               push_back(x);               iterator tmp = finish;               --tmp;               return tmp;           }           else           {               return insert_aux(position, x);           }       }          iterator insert(iterator position) { return insert(position, value_type()); }          // 详解见实现部分       void insert(iterator pos, size_type n, const value_type& x);          void insert(iterator pos, int n, const value_type& x)       {           insert(pos, (size_type) n, x);       }       void insert(iterator pos, long n, const value_type& x)       {           insert(pos, (size_type) n, x);       }          void resize(size_type new_size) { resize(new_size, value_type()); }      public:                         // Erase          iterator erase(iterator pos)       {           iterator next = pos;           ++next;              // 清除点之前的元素个数           difference_type index = pos - start;              // 如果清除点之前的元素个数比较少, 哪部分少就移动哪部分           if (index < (size() >> 1))           {               // 就移动清除点之前的元素               copy_backward(start, pos, next);               pop_front();   // 移动完毕，最前一个元素冗余，去除之           }           else   // 如果清除点之后的元素个数比较少           {               copy(next, finish, pos);  // 就移动清除点之后的元素               pop_back();   // 移动完毕，最后一个元素冗余，去除之           }           return start + index;       }          iterator erase(iterator first, iterator last);       void clear();      protected:          // 详解见实现部分       void push_back_aux(const value_type& t);       void push_front_aux(const value_type& t);       void pop_back_aux();       void pop_front_aux();          iterator insert_aux(iterator pos, const value_type& x);       void insert_aux(iterator pos, size_type n, const value_type& x);          // 分配内存, 不进行构造       pointer allocate_node() { return data_allocator::allocate(buffer_size()); }          // 释放内存, 不进行析构       void deallocate_node(pointer n)       {           data_allocator::deallocate(n, buffer_size());       }      };            // 清除[first, last)区间的所有元素      //                  erase(iterator first, iterator last)   //                                   |   //                                   |---------------- 是否要删除整个区间?   //                                   |   //               ------------------------------------------   //           Yes |                                        | No   //               |                                        |   //               ↓                                        | --- 判断哪侧元素少   //            clear();                                    ↓   //       -----------------------------------------------------------------   // 左侧少 |                                                         右侧少 |   //       |                                                               |   //       ↓                                                               ↓   //   copy_backward(start, first, last);            copy(last, finish, first);   //   new_start = start + n;                        new_finish = finish - n;   //   析构多余的元素                                  析构多余的元素   //   destroy(start, new_start);                    destroy(new_finish, finish);   //   释放多余内存空间                                释放多余内存空间   //   for (...)                                     for (...)   //      ...                                             ...   //   更新map状态                                    更新map状态      template <class T, class Alloc, size_t BufSize>   deque<T, Alloc, BufSize>::iterator   deque<T, Alloc, BufSize>::erase(iterator first, iterator last)   {       if (first == start && last == finish)   // 如果清除区间是整个deque       {           clear();              // 直接调用clear()即可           return finish;       }       else       {           difference_type n = last - first;   // 清除区间的长度           difference_type elems_before = first - start;   // 清除区间前方的元素个数           if (elems_before < (size() - n) / 2)   // 如果前方的元素个数比较少           {               copy_backward(start, first, last);  // 向后移动前方元素（覆盖清除区间）               iterator new_start = start + n;     // 标记deque的新起点               destroy(start, new_start);          // 移动完毕，将冗余的元素析构               // 以下将冗余的缓冲区释放               for (map_pointer cur = start.node; cur < new_start.node; ++cur)                   data_allocator::deallocate(*cur, buffer_size());               start = new_start;   // 设定deque的新起点           }           else    // 如果清除区间后方的元素个数比较少           {               copy(last, finish, first);  // 向前移动后方元素（覆盖清除区间）               iterator new_finish = finish - n;     // 标记deque的新尾点               destroy(new_finish, finish);          // 移动完毕，将冗余的元素析构               // 以下将冗余的缓冲区释放               for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)                   data_allocator::deallocate(*cur, buffer_size());               finish = new_finish;   // 设定deque的新尾点           }           return start + elems_before;       }   }      template <class T, class Alloc, size_t BufSize>   void deque<T, Alloc, BufSize>::clear()   {       // 以下针对头尾以外的每一个缓冲区       for (map_pointer node = start.node + 1; node < finish.node; ++node)       {           // 将缓冲区内的所有元素析构           destroy(*node, *node + buffer_size());           // 释放缓冲区内存           data_allocator::deallocate(*node, buffer_size());       }          if (start.node != finish.node)   // 至少有头尾两个缓冲区       {           destroy(start.cur, start.last);  // 将头缓冲区的目前所有元素析构           destroy(finish.first, finish.cur);  // 将尾缓冲区的目前所有元素析构           // 以下释放尾缓冲区。注意：头缓冲区保留           data_allocator::deallocate(finish.first, buffer_size());       }       else   // 只有一个缓冲区           destroy(start.cur, finish.cur);   // 将此唯一缓冲区内的所有元素析构           // 注意：并不释放缓冲区空间，这唯一的缓冲区将保留          finish = start;   // 调整状态   }         // 只有当finish.cur == finish.last - 1 时才会被调用   // 也就是说，只有当最后一个缓冲区只剩下一个备用元素空间时才会被调用   template <class T, class Alloc, size_t BufSize>   void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t)   {       value_type t_copy = t;       reserve_map_at_back();       *(finish.node + 1) = allocate_node();    // 配置一个新节点（缓冲区）       __STL_TRY       {           construct(finish.cur, t_copy);         // 针对标的元素设值           finish.set_node(finish.node + 1);      // 改变finish，令其指向新节点           finish.cur = finish.first;             // 设定finish的状态       }       __STL_UNWIND(deallocate_node(*(finish.node + 1)));   }      // Called only if start.cur == start.first.   template <class T, class Alloc, size_t BufSize>   void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t)   {       value_type t_copy = t;       reserve_map_at_front();       *(start.node - 1) = allocate_node();       __STL_TRY       {           start.set_node(start.node - 1);        // 改变start，令其指向新节点           start.cur = start.last - 1;            // 设定start的状态           construct(start.cur, t_copy);          // 针对标的元素设值       }       catch(...)       {           start.set_node(start.node + 1);           start.cur = start.first;           deallocate_node(*(start.node - 1));           throw;       }   }      // 只有当 finish.cur == finish.first 时才会被调用   template <class T, class Alloc, size_t BufSize>   void deque<T, Alloc, BufSize>:: pop_back_aux()   {       deallocate_node(finish.first);      // 释放最后一个缓冲区       finish.set_node(finish.node - 1);   // 调整finish状态，使指向       finish.cur = finish.last - 1;       // 上一个缓冲区的最后一个元素       destroy(finish.cur);                // 将该元素析构   }      // 只有当 start.cur == start.last - 1 时才会被调用   template <class T, class Alloc, size_t BufSize>   void deque<T, Alloc, BufSize>::pop_front_aux()   {       destroy(start.cur);    // 将第一个缓冲区的第一个（也是最后一个、唯一一个）元素析构       deallocate_node(start.first);    // 释放第一缓冲区       start.set_node(start.node + 1);  // 调整start状态，使指向       start.cur = start.first;         // 下一个缓冲区的第一个元素   }            // 在指定位置前插入元素      //              insert_aux(iterator pos, const value_type& x)   //                                   |   //                                   |----------- 判断pos前端元素少还是后端元素少   //                                   |   //               -----------------------------------------------   //         前端少 |                                       后端少 |   //               |                                             |   //               ↓                                             |   //           进行相关操作                                   进行相关操作      // 下面以pos前面元素少的情形进行说明, 为了简化, 假设操作不会超过一个缓冲区区间   //   // 插入前状态   //           start            pos                                 end   //             ↓               ↓                                   ↓   // ---------------------------------------------------------------------   // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |   // ---------------------------------------------------------------------   //   // 需要进行操作的区间   //                需要拷贝的区间   //                 -------------   //       start     |           |                                  end   //         ↓       ↓           ↓                                   ↓   // ---------------------------------------------------------------------   // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |   // ---------------------------------------------------------------------   //             ↑   ↑       ↑   ↑   //        front1   |       |   |   //                 |       |   |   //            front2       |   |   //                         |   |   //                       pos   |   //                             |   //                          pos1   // 拷贝操作完成后   //   //         这是[front2, pos1)   //             ------------- --------- 这里是给待插入元素预留的空间   //       start |           | |                                    end   //         ↓   ↓           ↓ ↓                                     ↓   // ---------------------------------------------------------------------   // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |   // ---------------------------------------------------------------------   //         ↑   //   这里存储的是原来的front()   //         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;   // 插入点之前的元素个数       value_type x_copy = x;          // 前面的时候用的移位操作, 这里怎么不用了呢^_^?       if (index < size() / 2)    // 如果插入点之前的元素个数比较少       {           push_front(front());       // 在最前端加入与第一元素同值的元素           iterator front1 = start;   // 以下标示记号，然后进行元素移动           ++front1;           iterator front2 = front1;           ++front2;           pos = start + index;           iterator pos1 = pos;           ++pos1;           copy(front2, pos1, front1);    // 元素移动       }       else    // 插入点之后的元素个数比较少       {           push_back(back());         // 在最尾端加入与最后元素同值的元素           iterator back1 = finish;   // 以下标示记号，然后进行元素移动           --back1;           iterator back2 = back1;           --back2;           pos = start + index;           copy_backward(pos, back2, back1);    // 元素移动       }       *pos = x_copy;    // 在插入点上设定新值       return pos;   }  

STL源码剖析---迭代器失效小结

迭代器（iterator）是一个可以对其执行类似指针的操作（如：解除引用（operator*()）和递增（operator++()））的对象，我们可以将它理解成为一个指针。但它又不是我们所谓普通的指针，我们可以称之为广义指针，你可以通过sizeof（vector::iterator）来查看，所占内存并不是4个字节。      首先对于vector而言，添加和删除操作可能使容器的部分或者全部迭代器失效。那为什么迭代器会失效呢？vector元素在内存中是顺序存储，试想：如果当前容器中已经存在了10个元素，现在又要添加一个元素到容器中，但是内存中紧跟在这10个元素后面没有一个空闲空间，而vector的元素必须顺序存储一边索引访问，所以我们不能在内存中随便找个地方存储这个元素。于是vector必须重新分配存储空间，用来存放原来的元素以及新添加的元素：存放在旧存储空间的元素被复制到新的存储空间里，接着插入新的元素，最后撤销旧的存储空间。这种情况发生，一定会导致vector容器的所有迭代器都失效。      我们看到实现上述所说的分配和撤销内存空间的方式以实现vector的自增长性，效率是极其低下的。为了使vector容器实现快速的内存分配，实际分配的容器会比当前所需的空间多一些，vector容器预留了这些额外的存储区，用来存放新添加的元素，而不需要每次都重新分配新的存储空间。你可以从vector里实现capacity和reserve成员可以看出这种机制。     capacity和size的区别：size是容器当前拥有的元素个数，而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。     vector迭代器的几种失效的情况：  1、当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。 2、当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。 3、当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。     deque迭代器的失效情况： 在C++Primer一书中是这样限定的：  1、在deque容器首部或者尾部插入元素不会使得任何迭代器失效。  2、在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。 3、在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。但是：我在vs2005测试发现第一条都不满足，不知为何？等以后深入STL以后慢慢的领会吧！      只有list的迭代器好像很少情况下会失效。也许就只是在删除的时候，指向被删除节点的迭代器会失效吧，其他的还没有发现。 先看两条规制： 1、对于节点式容器(map, list, set)元素的删除，插入操作会导致指向该元素的迭代器失效，其他元素迭代器不受影响。 2、对于顺序式容器(vector)元素的删除、插入操作会导致指向该元素以及后面的元素的迭代器失效。 众所周之当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效，因此很多建议都是让我们获取insert或者erase返回的迭代器，以便用重新获取新的有效的迭代器进行正确的操作： 代码如下：

[cpp]  view plain  copy iter = vec.insert(iter);   iter = vec.erase(iter);  

 

STL源码剖析---STL容器特征总结（含迭代器失效）

 

Vector

1、内部数据结构：连续存储，例如数组。 2、随机访问每个元素，所需要的时间为常量。 3、在末尾增加或删除元素所需时间与元素数目无关，在中间或开头增加或删除元素所需时间随元素数目呈线性变化。 4、可动态增加或减少元素，内存管理自动完成，但程序员可以使用reserve()成员函数来管理内存。 5、迭代器失效 插入：vector的迭代器在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）。当把超过capacity()-size()个元素插入vector中时，内存会重新分配，所有的迭代器都将失效； 删除：当进行删除操作（erase，pop_back）后，指向删除点及其后元素的迭代器全部失效。 建议：使用vector时，用reserve()成员函数预先分配需要的内存空间，它既可以保护迭代器使之不会失效，又可以提高运行效率。

deque

1、内部数据结构：连续存储或者分段连续存储，具体依赖于实现，例如数组。 2、随机访问每个元素，所需要的时间为常量。 3、在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化。 4、可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。 5、迭代器失效 插入：增加任何元素都将使deque的迭代器失效。 删除：在deque的中间删除元素将使迭代器失效。在deque的头或尾删除元素时，只有指向该元素的迭代器失效。

list

1、内部数据结构：双向环状链表。 2、不能随机访问一个元素。 3、可双向遍历。 4、在开头、末尾和中间任何地方增加或删除元素所需时间都为常量。 5、可动态增加或减少元素，内存管理自动完成。 6、迭代器失效 插入：增加任何元素都不会使迭代器失效。 删除：删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。

slist

1、内部数据结构：单向链表。 2、不可双向遍历，只能从前到后地遍历。 3、其它的特性同list相似。 建议：尽量不要使用slist的insert，erase，previous等操作。因为这些操作需要向前遍历，     但是slist不能直接向前遍历，所以它会从头开始向后搜索，所需时间与位于当前元      素之前的元素个数成正比。slist专门提供了insert_after，erase_after等函数进行优化。         但若经常需要向前遍历，建议选用list。

Stack

1、适配器，它可以将任意类型的序列容器转换为一个堆栈，一般使用deque作为支持的序列容器。 2、元素只能后进先出（LIFO）。 3、不能遍历整个stack。 4、适配器，它可以将任意类型的序列容器转换为一个队列，一般使用deque作为支持的序列容器。 5、元素只能先进先出（FIFO）。 6、不能遍历整个queue。 7、适配器，它可以将任意类型的序列容器转换为一个优先级队列，一般使用vector作为底层存储方式。 8、只能访问第一个元素，不能遍历整个priority_queue。 9、第一个元素始终是优先级最高的一个元素。

queue

priority_queue

建议：当需要stack，queue，或priority_queue这种数据结构时，直接使用对应的容器类，     不要使用deque去做它们类似的工作。

Set

1、键和值相等。 2、键唯一。 3、元素默认按升序排列。 4、迭代器失效 删除：如果迭代器所指向的元素被删除，则该迭代器失效。

map

1、键唯一。 2、元素默认按键的升序排列。 3、迭代器失效 删除：如果迭代器所指向的元素被删除，则该迭代器失效。

hash与set、multiset、map、multimap的结合

       它里面的元素不一定是按键值排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当前和hash函数有关）。 建议：当元素的有序比搜索更重要时，应选用set，multiset，map或multimap。否则，选用   hash_set，hash_multiset，hash_map或hash_multimap 建议：往容器中插入元素时，若元素在容器中的顺序无关紧要，请尽量加在最后面。若经常         需要在序列容器的开头或中间增加或删除元素时，应选用list。 建议：对关联容器而言，尽量不要使用C风格的字符串（即字符指针char*）作为键值。如果非用不可，应显示地定义字符串比较运算符，即operator<，operator==，operator<=     等。 建议：当容器作为参数被传递时，请采用引用传递方式。否则将调用容器的拷贝构造函数，其开销是难以想象的。       STL组建与平台无关，与应用无关，与数据类型无关。 代码如下： [cpp]  view plain  copy vector<int> vec;   vector<int>::iterator iter = vec.begin();      int main(void)   {       while(iter != vec.end())       {           iter = vec.erase(iter);    //vector删除时迭代器失效，要重新获取迭代器。       }       return 0;   }  

STL源码剖析---红黑树原理详解上

一、红黑树概述

     红黑树和我们以前学过的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。不过自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。这一点在我们了解了红黑树的实现原理后，就会有更加深切的体会。      红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫，红黑树才是真正的变态级数据结构。      由于STL中的关联式容器默认的底层实现都是红黑树，因此红黑树对于后续学习STL源码还是很重要的，有必要掌握红黑树的实现原理和源码实现。      红黑树是AVL树的变种，红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍，因而达到接近平衡的目的。所谓红黑树，不仅是一个二叉搜索树，而且必须满足一下规则：      1、每个节点不是红色就是黑色。      2、根节点为黑色。      3、如果节点为红色，其子节点必须为黑色。      4、任意一个节点到到NULL（树尾端）的任何路径，所含之黑色节点数必须相同。 上面的这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4，新增节点必须为红色；根据规则3，新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时，却未能符合上述条件时，就必须调整颜色并旋转树形，如下图： 假设我们为上图分别插入节点3、8、35、75，根据二叉搜索树的规则，插入这四个节点后，我们会发现它们都破坏了红黑树的规则，因此我们必须调整树形，也就是旋转树形并改变节点的颜色。

二、红黑树上结点的插入

      在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时（如下图所示），将会违反红黑树的性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。       为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况： 1、黑父      如下图所示，如果新节点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。 2、红父      如果新节点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。 2.1 红叔 当叔父结点为红色时，如下图所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上（迭代）进行平衡操作。 需要注意的是，无论“父节点”在“叔节点”的左边还是右边，无论“新节点”是“父节点”的左孩子还是右孩子，它们的操作都是完全一样的（其实这种情况包括4种，只需调整颜色，不需要旋转树形）。 2.2 黑叔 当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能： Case 1: Case 2: Case 3:

Case 4:

      可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。       其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。红黑树的插入操作源代码如下： [cpp]  view plain  copy // 元素插入操作  insert_unique()   // 插入新值：节点键值不允许重复，若重复则插入无效   // 注意，返回值是个pair，第一个元素是个红黑树迭代器，指向新增节点   // 第二个元素表示插入成功与否   template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>   pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>   rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)   {       rb_tree_node* y = header;    // 根节点root的父节点       rb_tree_node* x = root();    // 从根节点开始       bool comp = true;       while(x != 0)       {           y = x;           comp = key_compare(KeyOfValue()(v) , key(x));    // v键值小于目前节点之键值？           x = comp ? left(x) : right(x);   // 遇“大”则往左，遇“小于或等于”则往右       }       // 离开while循环之后，y所指即插入点之父节点（此时的它必为叶节点）       iterator j = iterator(y);     // 令迭代器j指向插入点之父节点y       if(comp)     // 如果离开while循环时comp为真（表示遇“大”，将插入于左侧）       {           if(j == begin())    // 如果插入点之父节点为最左节点               return pair<iterator , bool>(_insert(x , y , z) , true);           else     // 否则（插入点之父节点不为最左节点）               --j;   // 调整j，回头准备测试       }       if(key_compare(key(j.node) , KeyOfValue()(v) ))           // 新键值不与既有节点之键值重复，于是以下执行安插操作           return pair<iterator , bool>(_insert(x , y , z) , true);       // 以上，x为新值插入点，y为插入点之父节点，v为新值          // 进行至此，表示新值一定与树中键值重复，那么就不应该插入新值       return pair<iterator , bool>(j , false);   }      // 真正地插入执行程序 _insert()   template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>   typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)   {       // 参数x_ 为新值插入点，参数y_为插入点之父节点，参数v为新值       link_type x = (link_type) x_;       link_type y = (link_type) y_;       link_type z;          // key_compare 是键值大小比较准则。应该会是个function object       if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))       {           z = create_node(v);    // 产生一个新节点           left(y) = z;           // 这使得当y即为header时，leftmost() = z           if(y == header)           {               root() = z;               rightmost() = z;           }           else if(y == leftmost())     // 如果y为最左节点               leftmost() = z;          // 维护leftmost()，使它永远指向最左节点       }       else       {           z = create_node(v);        // 产生一个新节点           right(y) = z;              // 令新节点成为插入点之父节点y的右子节点           if(y == rightmost())               rightmost() = z;       // 维护rightmost()，使它永远指向最右节点       }       parent(z) = y;      // 设定新节点的父节点       left(z) = 0;        // 设定新节点的左子节点       right(z) = 0;       // 设定新节点的右子节点       // 新节点的颜色将在_rb_tree_rebalance()设定（并调整）       _rb_tree_rebalance(z , header->parent);      // 参数一为新增节点，参数二为根节点root       ++node_count;       // 节点数累加       return iterator(z);  // 返回一个迭代器，指向新增节点   }         // 全局函数   // 重新令树形平衡（改变颜色及旋转树形）   // 参数一为新增节点，参数二为根节点root   inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)   {       x->color = _rb_tree_red;    //新节点必为红       while(x != root && x->parent->color == _rb_tree_red)    // 父节点为红       {           if(x->parent == x->parent->parent->left)      // 父节点为祖父节点之左子节点           {               _rb_tree_node_base* y = x->parent->parent->right;    // 令y为伯父节点               if(y && y->color == _rb_tree_red)    // 伯父节点存在，且为红               {                   x->parent->color = _rb_tree_black;           // 更改父节点为黑色                   y->color = _rb_tree_black;                   // 更改伯父节点为黑色                   x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色                   x = x->parent->parent;               }               else    // 无伯父节点，或伯父节点为黑色               {                   if(x == x->parent->right)   // 如果新节点为父节点之右子节点                   {                       x = x->parent;                       _rb_tree_rotate_left(x , root);    // 第一个参数为左旋点                   }                   x->parent->color = _rb_tree_black;     // 改变颜色                   x->parent->parent->color = _rb_tree_red;                   _rb_tree_rotate_right(x->parent->parent , root);    // 第一个参数为右旋点               }           }           else          // 父节点为祖父节点之右子节点           {               _rb_tree_node_base* y = x->parent->parent->left;    // 令y为伯父节点               if(y && y->color == _rb_tree_red)    // 有伯父节点，且为红               {                   x->parent->color = _rb_tree_black;           // 更改父节点为黑色                   y->color = _rb_tree_black;                   // 更改伯父节点为黑色                   x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色                   x = x->parent->parent;          // 准备继续往上层检查               }               else    // 无伯父节点，或伯父节点为黑色               {                   if(x == x->parent->left)        // 如果新节点为父节点之左子节点                   {                       x = x->parent;                       _rb_tree_rotate_right(x , root);    // 第一个参数为右旋点                   }                   x->parent->color = _rb_tree_black;     // 改变颜色                   x->parent->parent->color = _rb_tree_red;                   _rb_tree_rotate_left(x->parent->parent , root);    // 第一个参数为左旋点               }           }       }//while       root->color = _rb_tree_black;    // 根节点永远为黑色   }         // 左旋函数   inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)   {       // x 为旋转点       _rb_tree_node_base* y = x->right;          // 令y为旋转点的右子节点       x->right = y->left;       if(y->left != 0)           y->left->parent = x;           // 别忘了回马枪设定父节点       y->parent = x->parent;          // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来）       if(x == root)    // x为根节点           root = y;       else if(x == x->parent->left)         // x为其父节点的左子节点           x->parent->left = y;       else                                  // x为其父节点的右子节点           x->parent->right = y;       y->left = x;       x->parent = y;   }         // 右旋函数   inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)   {       // x 为旋转点       _rb_tree_node_base* y = x->left;          // 令y为旋转点的左子节点       x->left = y->right;       if(y->right != 0)           y->right->parent = x;           // 别忘了回马枪设定父节点       y->parent = x->parent;          // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来）       if(x == root)           root = y;       else if(x == x->parent->right)         // x为其父节点的右子节点           x->parent->right = y;       else                                  // x为其父节点的左子节点           x->parent->left = y;       y->right = x;       x->parent = y;   }  

STL源码剖析---红黑树原理详解下

算法导论书上给出的红黑树的性质如下，跟STL源码剖析书上面的4条性质大同小异。       1、每个结点或是红色的，或是黑色的       2、根节点是黑色的       3、每个叶结点（NIL）是黑色的       4、如果一个节点是红色的，则它的两个儿子都是黑色的。       5、对于每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑色结点。       从红黑树上删除一个节点，可以先用普通二叉搜索树的方法，将节点从红黑树上删除掉，然后再将被破坏的红黑性质进行恢复。       我们回忆一下普通二叉树的节点删除方法：Z指向需要删除的节点，Y指向实质结构上被删除的结点，如果Z节点只有一个子节点或没有子节点，那么Y就是指向Z指向的节点。如果Z节点有两个子节点，那么Y指向Z节点的后继节点（其实前趋也是一样的），而Z的后继节点绝对不可能有左子树。因此，仅从结构来看，二叉树上实质被删除的节点最多只可能有一个子树。 现在我们来看红黑性质的恢复过程：       如果Y指向的节点是个红色节点，那么直接删除掉Y以后，红黑性质不会被破坏。操作结束。       如果Y指向的节点是个黑色节点，那么就有几条红黑性质可能受到破坏了。首先是包含Y节点的所有路径，黑高度都减少了一（第５条被破坏）。其次，如果Y的有红色子节点，Y又有红色的父节点，那么Y被删除后，就出现了两个相邻的红色节点（第４条被破坏）。最后，如果Y指向的是根节点，而Y的子节点又是红色的，那么Y被删除后，根节点就变成红色的了（第２条被破坏）。       其中，第５条被破坏是让我们比较难受的。因为这影响到了全局。这样动作就太大太复杂了。而且在这个条件下，进行其它红黑性质的恢复也很困难。所以我们首先解决这个问题：如果不改变含Y路径的黑高度，那么树的其它部分的黑高度就必须做出相应的变化来适应它。所以，我们想办法恢复原来含Y节点的路径的黑高度。做法就是：无条件的把Y节点的黑色，推到它的子节点X上去。（X可能是NIL节点）。这样，X就可能具有双重黑色，或同时具有红黑两色，也就是第１条性质被破坏了。       但第１条性质是比较容易恢复的：一、如果X是同时具有红黑两色，那么好办，直接把X涂成黑色，就行了。而且这样把所有问题都解决了。因为将X变为黑色，２、４两条如果有问题的话也会得到恢复，算法结束。二、如果X是双黑色，那么我们希望把这种情况向上推一直推到根节点（调整树结构和颜色，X的指向新的双黑色节点，X不断向上移动），让根节点具双黑色，这时，直接把X的一层黑色去掉就行了（因为根节点被包含在所有的路径上，所以这样做所有路径同时黑高减少一，不会破坏红黑特征）。       下面就具体地分析如何恢复1、２、４三个可能被破坏的红黑特性：我们知道，如果X指向的节点是有红黑两色，或是X是根节点时，只需要简单的对X进行一些改变就行了。要对除X节点外的其它节点进行操作时，必定是这样的情况：X节点是双层黑色，且X有父节点P。由知可知，X必然有兄弟节点W，而且这个W节点必定有两个子节点。（因为这是原树满足红黑条件要求而自然具备的。X为双黑色，那么P的另一个子节点以下一定要有至少两层的节点，否则黑色高度不可能和X路径一致）。所以我们就分析这些节点之间如何变形，把问题限制在比较小的范围内解决。另一个前提是：X在一开始，肯定是树底的叶节点或是NIL节点，所以在递归向上的过程中，每一步都保证下一步进行时，至少 X的子树是满足红黑特性的。因此子树的情况就可以认为是已经正确的了，这样，分析就只限制在X节点，X的父节点P和X的兄弟节点W，以及W的两个子节点中。       下面仅仅考虑X原本是黑色的情况即可。       在这种情况下，X此时应该具有双重黑色，算法的过程就是将这多出的一重黑色向上移动，直到遇到红节点或者根节点。       接着往下分析， 会遇到4种情况，实际上是8种， 因为其中4种是相互对称的，这可以通过判断X是其父节点的右孩子还是左孩子来区分。下面我们以X是其父节点的左孩子的情况来分析这4种情况，实际上接下来的调整过程，就是要想方设法将经过X的所有路径上的黑色节点个数增加1。       具体分为以下四种情况：（下面针对x是左儿子的情况讨论，右儿子对称）       Case1：X的兄弟W是红色（想办法将其变为黑色）        由于W是红色的，因此其儿子节点和父节点必为黑色，只要将W和其父节点的颜色对换，在对父节点进行一次左旋转，便将W的左子节点放到了X的兄弟节点上，X的兄弟节点变成了黑色，且红黑性质不变。但还不算完，只是暂时将情况1转变成了下面的情况2或3或4。

    Case2：X的兄弟节点W是黑色的，而且W的两个子节点都是黑色的。此时可以将X的一重黑色和W的黑色同时去掉，而转加给他们的父节点上，这是X就指向它的父节点了，因此此时父节点具有双重颜色了。这一重黑色节点上移。       如果父节点原来是红色的，现在又加一层黑色，那么X现在指向的这个节点就是红黑两色的，直接把X（也就是父节点）着为黑色。问题就已经完整解决了。      如果父节点现在是双层黑色，那就以父节点为新的X进行向上的下一次的递归。     Case3：X的兄弟节点W是黑色的，而且W的左子节点是红色的，右子节点是黑色的。此时通过交换W和其左子节点的颜色并进行一次向右旋转就可转换成下面的第四种情况。注意，原来L是红色的，所以L的子节点一定是黑色的，所以旋转中L节点的一个子树挂到之后着为红色的W节点上不会破坏红黑性质。变形后黑色高度不变。     Case4： X的兄弟节点W是黑色的，而且W的右子节点是红色的。这种情况下，做一次左旋，W就处于根的位置，将W保持为原来的根的位置的颜色，同时将W的两个新的儿子节点的颜色变为黑色，去掉X的一重黑色。这样 整个问题也就得到了解决。递归结束。（在代码上，为了标识递归结束，我们把X指向根节点）       因此，只要按上面四种情况一直递归处理下去，X最终总会指向根结点或一个红色结点，这时我们就可以结束递归并把问题解决了。       以上就是红黑树的节点删除全过程。       总结：       如果我们通过上面的情况画出所有的分支图，我们可以得出如下结论       插入操作：解决的是 红-红 问题       删除操作：解决的是 黑-黑 问题       即你可以从分支图中看出，需要往上遍历的情况为红红(插入)，或者为黑黑黑（删除）的情况，如果你认真分析并总结所有的情况后，并坚持下来，红黑树也就没有想象中的那么恐怖了，并且很美妙；       详细的红黑树删除节点的代码如下： [cpp]  view plain  copy #include<iostream>   using namespace std;      // 定义节点颜色     enum COLOR   {         BLACK = 0,         RED     };          // 红黑树节点     typedef struct RB_Tree_Node   {         int key;         struct RB_Tree_Node *left;         struct RB_Tree_Node *right;         struct RB_Tree_Node *parent;         unsigned char RB_COLOR;     }RB_Node;      // 红黑树，包含一个指向根节点的指针     typedef struct RBTree   {         RB_Node* root;   }*RB_Tree;      // 红黑树的NIL节点     static RB_Tree_Node NIL = {0, 0, 0, 0, BLACK};       #define PNIL (&NIL)   // NIL节点地址       void Init_RBTree(RB_Tree pTree) // 初始化一棵红黑树     {         pTree->root = PNIL;     }         // 查找最小键值节点     RB_Node* RBTREE_MIN(RB_Node* pRoot)     {         while (PNIL != pRoot->left)       {           pRoot = pRoot->left;       }         return pRoot;   }         /*                            15                          /    \                         /      \                        /        \                       6          18                      /  \       /  \                     /    \     /    \                    3      7   17    20                   /  \     \                  /    \     \                 2      4     13                              /                             /                            9  */   // 查找指定节点的后继节点     RB_Node* RBTREE_SUCCESSOR(RB_Node*  pRoot)     {         if (PNIL != pRoot->right)    // 查找图中6的后继节点时就调用RBTREE_MIN函数       {             return RBTREE_MIN(pRoot->right);         }       // 节点没有右子树的时候，进入下面的while循环（如查找图中13的后继节点时，它的后继节点是15）       RB_Node* pParent = pRoot->parent;         while((PNIL != pParent) && (pRoot == pParent->right))       {             pRoot = pParent;           pParent = pRoot->parent;             }       return pParent;   }      // 红黑树的节点删除   RB_Node* Delete(RB_Tree pTree , RB_Node* pDel)     {         RB_Node* rel_delete_point;       if(pDel->left == PNIL || pDel->right == PNIL)           rel_delete_point = pDel;       else           rel_delete_point = RBTREE_SUCCESSOR(pDel);     // 查找后继节点          RB_Node* delete_point_child;         if(rel_delete_point->right != PNIL)         {             delete_point_child = rel_delete_point->right;         }         else if(rel_delete_point->left != PNIL)         {             delete_point_child = rel_delete_point->left;         }         else         {             delete_point_child = PNIL;         }         delete_point_child->parent = rel_delete_point->parent;         if(rel_delete_point->parent == PNIL)    // 删除的节点是根节点       {             pTree->root = delete_point_child;       }         else if(rel_delete_point == rel_delete_point->parent->right)       {             rel_delete_point->parent->right = delete_point_child;         }         else         {             rel_delete_point->parent->left = delete_point_child;         }       if(pDel != rel_delete_point)       {           pDel->key = rel_delete_point->key;       }       if(rel_delete_point->RB_COLOR == BLACK)         {             DeleteFixUp(pTree , delete_point_child);         }       return rel_delete_point;     }                        /*  算法导论上的描述如下：  RB-DELETE-FIXUP(T, x)   1 while x ≠ root[T] and color[x] = BLACK   2     do if x = left[p[x]]   3           then w ← right[p[x]]   4                if color[w] = RED   5                   then color[w] ← BLACK                           Case 1   6                        color[p[x]] ← RED                          Case 1   7                        LEFT-ROTATE(T, p[x])                       Case 1   8                        w ← right[p[x]]                            Case 1   9                if color[left[w]] = BLACK and color[right[w]] = BLACK   10                   then color[w] ← RED                            Case 2   11                        x p[x]                                    Case 2   12                   else if color[right[w]] = BLACK   13                           then color[left[w]] ← BLACK            Case 3   14                                color[w] ← RED                    Case 3   15                                RIGHT-ROTATE(T, w)                Case 3   16                                w ← right[p[x]]                   Case 3   17                         color[w] ← color[p[x]]                   Case 4   18                         color[p[x]] ← BLACK                      Case 4   19                         color[right[w]] ← BLACK                  Case 4   20                         LEFT-ROTATE(T, p[x])                     Case 4   21                         x ← root[T]                              Case 4   22        else (same as then clause with "right" and "left" exchanged)   23 color[x] ← BLACK    */     //接下来的工作，很简单，即把上述伪代码改写成c++代码即可     void DeleteFixUp(RB_Tree pTree , RB_Node* node)     {         while(node != pTree->root && node->RB_COLOR == BLACK)         {             if(node == node->parent->left)             {                 RB_Node* brother = node->parent->right;                 if(brother->RB_COLOR==RED)   //情况1：x的兄弟w是红色的。                 {                     brother->RB_COLOR = BLACK;                     node->parent->RB_COLOR = RED;                     RotateLeft(node->parent);                 }                 else     //情况2：x的兄弟w是黑色的，                 {                     if(brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)  //w的两个孩子都是黑色的                     {                         brother->RB_COLOR = RED;                         node = node->parent;                     }                     else                   {                       if(brother->right->RB_COLOR == BLACK)   //情况3：x的兄弟w是黑色的，w的右孩子是黑色（w的左孩子是红色）。                         {                           brother->RB_COLOR = RED;                           brother->left->RB_COLOR = BLACK;                           RotateRight(brother);                           brother = node->parent->right;      //情况3转换为情况4                       }                       //情况4：x的兄弟w是黑色的，且w的右孩子时红色的                       brother->RB_COLOR = node->parent->RB_COLOR;                         node->parent->RB_COLOR = BLACK;                         brother->right->RB_COLOR = BLACK;                         RotateLeft(node->parent);                         node = pTree->root;                   }//else               }//else           }             else   //同上，原理一致，只是遇到左旋改为右旋，遇到右旋改为左旋即可。其它代码不变。             {                 RB_Node* brother = node->parent->left;                 if(brother->RB_COLOR == RED)                 {                     brother->RB_COLOR = BLACK;                     node->parent->RB_COLOR = RED;                     RotateRight(node->parent);                 }                 else                 {                     if(brother->left->RB_COLOR==BLACK && brother->right->RB_COLOR == BLACK)                     {                         brother->RB_COLOR = RED;                         node = node->parent;                     }                     else                   {                       if(brother->left->RB_COLOR==BLACK)                         {                             brother->RB_COLOR = RED;                             brother->right->RB_COLOR = BLACK;                             RotateLeft(brother);                           brother = node->parent->left;      //情况3转换为情况4                       }                       brother->RB_COLOR = node->parent->RB_COLOR;                         node->parent->RB_COLOR = BLACK;                         brother->left->RB_COLOR = BLACK;                         RotateRight(node->parent);                         node = pTree->root;                     }                 }             }         }//while        node->RB_COLOR = BLACK;    //如果X节点原来为红色，那么直接改为黑色     }   上文来自：http://blog.csdn.net/Hackbuteer1/article/category/1181402