首页 > C++入门教程 > C++模板与标准模板库
C++基本序列式容器效率比较
前面介绍序列式的三种容器时,我们简单介绍了在容器各部位插入或删除元素时的处理效率,在此节我们做一个总结。
根据 STL 公布的容器各种操作效率,我们可以根据不同的需求来选择合适的容器。例如,我们需要频繁的在容器的任意位置插入或删除元素,则我们可以选择 list,而非 vector 和 deque。具体的总结见下表。
对于 vector 而言,它只是一个可以伸缩长度的数组,因此除了在尾部插入、删除数据外,在其它任何部位插入、删除数据都是线性的复杂度,容器长度越大,完成相应的操作也就越多。而访问元素则可以根据下标直接访问到,因此访问任何位置的元素,其效率都是恒定的。
对于 deque 而言,它是一个可以操作头部和尾部的并且可以伸缩长度的数组,因此它在头部和尾部插入、删除数据,效率是恒定的,但是在容器的中间插入元素,则它跟 vector 一样,同样是要移动其它元素的,因此在中部插入或删除元素效率是线性的。对于访问容器中的元素,它同样可以通过下标进行直接访问,因此效率也是恒定的。
对于 list 而言,它是一个双向链表,因此在任何位置插入或删除元素都不用移动其它元素,其效率始终是恒定的。对于访问元素,双向链表访问头尾元素都很方便,但是访问中间元素则需要逐一从头部或尾部一一遍历过去,因此访问容器中间的元素其效率是线性的。
在今后的程序设计过程中,如果需要使用容易,应该按照需求选择合适的容器,否则会大大降低程序的效率。如果我们只需要在容器尾部插入删除元素,则 vector 就够用了,如果还需要在头部也频繁的插入删除元素,则需要选择 deque。
声明:《C++系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。
根据 STL 公布的容器各种操作效率,我们可以根据不同的需求来选择合适的容器。例如,我们需要频繁的在容器的任意位置插入或删除元素,则我们可以选择 list,而非 vector 和 deque。具体的总结见下表。
基本操作 | vector | deque | list |
---|---|---|---|
在容器头部插入或删除元素 | 线性 | 恒定 | 恒定 |
在容器尾部插入或删除元素 | 恒定 | 恒定 | 恒定 |
在容器中部插入或删除元素 | 线性 | 线性 | 恒定 |
访问容器头部的元素 | 恒定 | 恒定 | 恒定 |
访问容器尾部的元素 | 恒定 | 恒定 | 恒定 |
访问容器中部的元素 | 恒定 | 恒定 | 线性 |
对于 vector 而言,它只是一个可以伸缩长度的数组,因此除了在尾部插入、删除数据外,在其它任何部位插入、删除数据都是线性的复杂度,容器长度越大,完成相应的操作也就越多。而访问元素则可以根据下标直接访问到,因此访问任何位置的元素,其效率都是恒定的。
对于 deque 而言,它是一个可以操作头部和尾部的并且可以伸缩长度的数组,因此它在头部和尾部插入、删除数据,效率是恒定的,但是在容器的中间插入元素,则它跟 vector 一样,同样是要移动其它元素的,因此在中部插入或删除元素效率是线性的。对于访问容器中的元素,它同样可以通过下标进行直接访问,因此效率也是恒定的。
对于 list 而言,它是一个双向链表,因此在任何位置插入或删除元素都不用移动其它元素,其效率始终是恒定的。对于访问元素,双向链表访问头尾元素都很方便,但是访问中间元素则需要逐一从头部或尾部一一遍历过去,因此访问容器中间的元素其效率是线性的。
在今后的程序设计过程中,如果需要使用容易,应该按照需求选择合适的容器,否则会大大降低程序的效率。如果我们只需要在容器尾部插入删除元素,则 vector 就够用了,如果还需要在头部也频繁的插入删除元素,则需要选择 deque。
声明:《C++系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。