stl中顺序容器简介

今天来讲讲stl里面的序列容器，只讲主要vector， list， deque，剩下的stack和queue底层是靠deque或者list实现的，heap底层是靠vector实现的，prior_queue底层又是靠heap实现的，所以说呢，感觉掌握了上述三个，就应该没啥大问题了。

先来讲vector，这个应该是大家最熟悉的了，底层实现基本上就是数组，但是多了个动态分配的功能，基本思想就是每一次容量满了之后，都会另辟一块空间来存放其包含的所有内容，其容量增长顺序一般是2的n次幂的形式，2， 4， 8 …,其余的形式就跟数组没什么区别了，这里需要注意一点的是，如果插入元素之后再次调用原来的迭代器，是失效的，因为如果刚刚好该vector换了地址，并且扩容了，就不知道该怎么搞了~~~

list的实现是靠双向循环链表，之前一直以为是双向的，但是没有往循环链表上面去想，哎，被大神们的思想折服了，双向循环链表的话，其自身只需要一个节点的哨兵迭代器就可以搞定begin()和end()两个了，其形状如下图：

这里我最想提到的一点就是list由于其链式结构，没办法用sort算法来进行排序，只能自己手写，下是list的sort源代码：

template <class T, class Alloc>
void list<T, Alloc>::sort() {
  if (node->next == node || link_type(node->next)->next == node) return;
  list<T, Alloc> carry;
  list<T, Alloc> counter[64];
  int fill = 0;
  while (!empty()) {
    carry.splice(carry.begin(), *this, begin());
    int i = 0;
    while(i < fill && !counter[i].empty()) {
      counter[i].merge(carry);
      carry.swap(counter[i++]);
    }
    carry.swap(counter[i]);
    if (i == fill) ++fill;
  }

  for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
  swap(counter[fill-1]);
}

说实话，第一遍没看懂，自己跟着走了一组数之后慢慢的明了了，其中carry和counter[i]均是辅助list，每次从当前链表中取出一个元素，和之前的元素归并，注意，counter[i]在这里只存储2^i个有序数，所以这里，list总共可以排序2^64  -1 个数~~

deque：关于deque，我只想说一下它的内部存储结构à分段连续。有没有很懵逼~~哈哈，刚开始看到这里的时候，我也很懵逼，但是看下图就OK了，会让你想起fs当中一个叫inode的东西~~

其中map是一个存放指针的数组，即指针的指针~~，它的每一个元素指向一块缓冲区buffer，这是用来实际存放数据的地方，其初始化工作是建立map，初始化其中间几个元素的buffer用来放数据，这样做的好处是，两面都可以进行数据的增减操作，如果当前map所指的buffer全部放满之后，仍然有数据进来，就需要向vector一样来进行前一工作啦~~~