最近看stl,记录一下其中的数据结构和常见用法.

首先来介绍序列式容器:

vector: 是用线性连续空间存储的,值得一提的是它的空间配置策略,当元素超过已有空间,会已2倍的方式重新分配空间.

任何对vector的操作一旦引起了空间重新配置,指向原vector的所有迭代器就都失效了.

调用erase 函数时，返回的迭代器指向下一个元素。

list: 双向链表,stl中将尾端设置一个空白节点,以符合"前闭后开"区间要求,可以形成一个环状结构.list只用保存空白节点的指针当做head.

list一些特别操作:

   unique:连续相同的元素会被移剩一个

   下面这三个函数都基于list内部提供的一个迁移操作(transfer),将连续范围的元素迁移到某个特定位置.

    splice:将连续范围的元素从一个list迁移到另一个list的特定位置.

   list<int>::iterator ite = find(iv.begin(),iv.end(),9);
     list<int> iv3 = {8,8};
     iv.splice(ite,iv3);

    merge:只能将两个已经过递增排序的list merge

    iv.merge(iv2);
    sort:不能用STL算法的sort(),必须使用自己的sort,其中书中介绍的是一种非递归的归并排序.(只是因为stl的sort算法要求迭代器是RandomAccessIterators而list是BidirectionalIterator).

  iv.sort();

deque:双端队列,特别之处在于:

    1, 双向开口的连续线性空间,vector也可以在头部操作,但是效率极差,deque就解决了这一问题.

    2, 没用容量的观念,动态的以分段连续空间组合而成,随时增加一段新空间并链接起来.正是因为这种机制,它的迭代器,各个运算层面都较vector复杂得多,如非必要,尽量使用vector.

deque是由一段一段定量连续空间构成的,所以必须有中央控制.deque有一段中控的连续空间(一个名叫map的指针的指针指向一段连续空间),每一个节点都是一个指针,指向另一端连续线性空间称为缓冲区,缓冲区才是deque储存的主体.

   deque的迭代器也非常复杂:

     要用4个指针实现,当前元素,当前元素所在缓冲区的头尾,指向中控中心的指针.

  当map节点空间不足,要重新配置一块更大的map.

  deque<int,alloc,8> ideq(20,9); //每一个缓冲区的大小是8,alloc只适用G++,它是一个空间配置的模板.

  deque<int>  d2;

stack:先进后出.它与queue都是配接器(修改某物接口,形成另一种风貌),都默认用deque作为底层容器,也可以选择用list作为底层容器.与queue一样,都不能走访,所以不提供迭代器.

  stack<int> s1;

  stack<int,list<int>> s2;//第二个templete指明底层容器

queue:先进先出

heap:是一个幕后英雄,是priority_queue的助手,以一个首元素是负无穷的vector存储(2*i,2*i+1必是左右子节点,i/2必是父节点),始终保持完全二叉树的形式.默认是大根堆.

       插入:新元素插在vector的end()处,然后不断上溯,如比父节点大,父子对换,直到不需对换.push_heap(RandomAcsessIterator first, RandomAcsessIterator last) 必须要保证,执行这个函数时,新插入已经在vector的尾端.

      vector<int> ivec = {0,1,2,3,4,8,9,3,5};

       make_heap(ivec.begin(),ivec.end());

       ivec.push_back(7);

       push_heap(ivec.begin(),ivec.end());  

       删除:将首尾值对调,然后对此时的首值进行下溯,到叶节点再上溯.

       pop_heap(ivec.begin(),ivec.end()); //没有删除任何元素,只是将原来的根节点放在vector的最后了.heap操作范围变少了一个

       ivec.pop_back();//从vector中取出最后一个元素

       排序:sort_heap不断调用pop_heap()即可实现,每次会减小heap的操作范围(人为控制操作范围),若是不将从vector中取出就实现了堆排序.

       建堆：从下往上对每一个子树执行调整堆算法先进行下溯,到叶节点再上溯，O(NlogN)

       heap并不是一个容器,而是一种处理规则,默认vector做底部容器.

priority_queue:缺省以vector为底部容器,默认为大根堆，加上heap的处理规则,被归类为适配器.

template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >

class priority_queue {...};

vector<int> iv = {9,8,1,2,3,4,5,9,7,6};
  priority_queue<int> ipq(iv.begin(),iv.end());//后两个使用默认模板参数，等价于ipq2的定义
  priority_queue<int,vector<int>,less<int> > ipq2(iv.begin(),iv.end());

 int ia[10] = {9,8,1,2,3,4,5,9,7,6};
  priority_queue<int,vector<int>,greater<int> > ipq3(ia,ia+10);//优先队列的底层容器似乎改不了，和函数一样，要想指定第三个模板参数，要先指定前俩个

//这个用greater实现的是小根堆

slit:单向链表，每次从头处插入，插入序列顺序会在slist中逆序．

基本操作：front,push_front,pop_front,insert插入给定的迭代器之前,erase删除迭代器指定的元素;

特别之处在于架构设计，还不太理解采用这种模式的原因．