2015-11-21

STL之list

• 头文件及声明

  #include <list>
  namespace std
  {
      template <typename T, typename Allocator = allocator<T>>
      class list;
  }

• 内部结构及其特性

list内部使用的是循环双链表，有一个被称为锚点(anchors)，分别链接头尾节点。

链表并不支持随机存取，所以读写任意一个元素较慢，除了两端的元素；插入和删除很快，几乎是常数时间内完成；插入和删除并不会让指针，引用，迭代器失效；

对于移除元素，list提供了自己的成员函数，remove和remove_if，如移除所有的val，coll.remove(val)，remove_if(op)接受一个函数或函数对象或lambda表达式来移除使op产生true的值。

list提供了一系列自己特有的函数，列举如下：

1. c.unique(),c.unique(op) 去掉重复的元素
2. c.splice(pos, c2), c.splice(pos, c2, c2pos), c.splice(pos, c2, c2beg, c2end)这些都是将c2中的值移动到c1的pos之前，注意是移动，c2移动后就没有了。
3. c.sort(),c.sort(op)排序，前者用<，后者用op。
4. c.merge(c2),c.merge(c2, op)将c2合并到c中，并且会排序。
5. c.reverse()反转list。

c艹