stl的实现原理简单讲解,通熟易懂

时间:2023-03-08 16:32:37

总结 
需要经常随机访问请用vector 
2.list 
list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。 
list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存. 
list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器. 但是访问list里面的元素时就开始和最后访问最快 
访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好 总结 
如果你喜欢经常添加删除大对象的话,那么请使用list 
要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替 
list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存 
 
3.deque 
deque是一个双端队列(double-ended queue),也是在堆中保存内容的.它的保存形式如下: [堆1] ... [堆2] ... [堆3] 
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品. 
它支持[]操作符,也就是支持随即存取,可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和vector的效率相差无几,它支持在两端的操作:
push_back,push_front,pop_back,pop_front等,并且在两端操作上与list的效率也差不多。 
在标准库中vector和deque提供几乎相同的接口,在结构上它们的区别主要在于这两种容器在组织内存上不一样,deque是按页或块来分配存储器的,每页包含固定数目的元素.相反vector分配一段连续的内存,vector只是在序列的尾段插