posts - 43,comments - 3,trackbacks - 0
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 阅读(299) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理