首页 > 代码库 > 重温《STL源码剖析》笔记 第四章

重温《STL源码剖析》笔记 第四章

                  源码之前,了无秘密  ——侯杰

第四章:序列式容器

  C++语言本身提供了一个序列式容器array

  array:分配静态空间,一旦配置了就不能改变。

  vector:

    分配动态空间。维护一个连续线性空间,迭代器类型为:Random Access Iterators

    空间配置 typedef simple_alloc<value_type, Alloc> data_allocator

    所谓动态增加空间大小,并不是在原空间之后接续新空间,而是以原大小的两倍另外配置一块较大

    的空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此,

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

    这是程序员易犯的一个错误。

    可用的方法或函数:begin, end, size, capacity, empty, front, back, find, erase, clear, insert,

    push_back, pop_back

  list:非连续空间

//配置,释放,构造,销毁一个节点protected:    //配置一个节点并传回    link_type get_node() {        return list_node_allocator::allocate();    }    //释放一个节点    void put_node(link_type) {        list_node_allocator::deallocate(p);    }    //产生(配置并构造)一个节点,带有元素值    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(&->data);        put_node(p);    }

  remove(const T& value) -> 将数值为values的所有元素移除

  void list<T,Alloc>::unique() ->移除数值相同的连续元素。注意是“连续”

  list的方法和函数: begin, end, empty, size, front, back,  find, insert, erase, clear, remove, 

  push_front, push_back, pop_front, pop_back, unique, [ sort, splice, merge, reverse -> transfer

 

  deque:双向开口的连续线性空间,迭代器类型Random Access Iterator, 但是迭代器非常复杂,

  要维护一个地址队列

  与vector的差异:

      一在于deque可以常数时间内对起头端进行插入或移除操作

      二在于deque没有所谓容量的观念,动态的以分段连续空间组合而成,随时可以增加一段新的

      空间并链接起来。

  deque的最大任务,便是在这些分段的定量连续空间上,维护其整体连续的假象,并提供随机存取的接口,

  避开了重新配置,复制,释放的轮回,代价则是复杂的迭代器架构。

  deque的方法和函数:

  begin,end, empty, size, front, back, find, insert, erase, clear, push_front, push_back,

  pop_front, pop_back, reverse_map_at_back(size-type,node_to_add=1)

  reverse_map_at_front(size_type, node_to_add=1)

 

  stack:没有迭代器

  方法或函数:empty, size, top, push, pop     stack<int, list<int>> istack

 

  queue:empty, size, front, back, push, pop         queue<int, list<int>> iqueue

  heap:扮演priority queue的助手 使用binary max heap

  方法或函数:push_heap, pop_heap(first, last), sort_heap, make_heap

  

  priority_queue: empty,size, top, push, pop

  slist:单向链表

  方法或函数:size,begin,end, find, insert

 

重温《STL源码剖析》笔记 第四章