vector<T, Allocator>
vector是一种Sequence，支持随机访问元素，常量时间内在尾端安插和移除元素，以及线性时间内在开头和中间安插或移除元素。vector的元素个数能够动态变更，内存管理行为完全自动。通常它的实现方式是把元素安排在连续的存储块中，这使得vector的iterator可以是一般的指针。典型的vector有三个memeber variables，三个都是指针：start、finish、end_of_storage。vector的所有元素位于[start,finish)之中，而[finish, end_of_storage)则包含了未初始化的存储空间。vector的大小为finish-start，容量为end_of_storage-start。可以使用member function reserve 来预先分配内存，来防止iterator的实效。
list<T, Allocator>
list是一种双向连接链表，其中每个元素都有一个predecessor和一个sucessor。能以amortized const time在list的开头、尾端、中间处安插及移除元素，并且list的iterator不会实效。
slist是一种单向连接链表，它是SGI STL对C++ Standard的扩展，链表中的每个元素都连接至下一个元素，但不连接至前一个元素。slist的insert与erase等函数是很耗时的，因为slist中的元素没有记录predecessor。
deque<T, Allocator>
deque类似于vector,它也是一种Sequence,支持元素的随机访问、常量时间内于尾端安插或移除元素、线性时间内于中间安插和移除元素。注意在deque开头或尾端安插一个元素，需要amortized constant time，在中间处安插元素的复杂度则与n成线性关系，此处n是安插点距离deque开头与尾端的最短距离。deque不具备类似vector的capacity()和reserve()之类的member functions，但它保证将元素安插于deque开头或尾端不会造成deque中现存的任何元素被复制，它不会发生内存重新分配的行为。
通常，deque是以动态区段化的数组实现出来的，deque通常内涵一个表头，指向一组节点，每个节点含有固定数量并且连续存储的元素。当deque增长时便增加新的节点。它比vector复杂的多，也要慢一些，对deque排序几乎不是一个好主意，可以考虑将deque的元素复制到vector中，然后对vector排序，最后复制回来较佳，所以应该尽量使用vector。
posted on 2008-02-11 21:26
RUI 阅读(308)
评论(0) 编辑 收藏 引用