先来看一下 c++标准模板库中,容器类vector、list 、deque都属于顺行性容器(所谓顺序性容器是一种各元素之间有顺序关系的线性表,是一种线性结构的可序群集,每个元素都有固定的位置,这个位置与元素无关,只与插入删除的先后顺序有关);都可以用来存储一组类型相同的对象;不同于内置数据类型数组的是,vector、list、deque的大小不是固定的,他们支持动态增长。
之所以设计 vector、list、deque不同的容器类,是因为它们适用于不同的情况。 (详细可参考http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)
vector
|
从后面快速的插入与删除,直接访问任何元素
|
deque
|
从前面或后面快速的插入与删除,直接访问任何元素
|
list
|
双链表,从任何地方快速插入与删除
|
单从上面适用情况来看,似乎deque完全可以代替vector和list的,后者没有存在的必要,但是,情况并不是这样的,还要看一下他们的性能。有人曾专门对各种情况性能做过对比,里面有些数值似乎不准确,但能说明一定的问题 (http://www.cnblogs.com/kingcat/archive/2012/04/13/2446186.html)
比赛项目/参赛选手
|
Vector
|
Deque
|
List
|
内存管理
|
Poor
|
Good
|
perfect
|
使用[ ]和at() 操作访问数据
|
Very good
|
Normal
|
N/A
|
Iterator的访问速度
|
Good
|
Very good
|
Good
|
Push_back操作(后插入)
|
Good
|
Good
|
Good
|
Push_front操作(前插入)
|
N/A
|
Very good
|
Good
|
Insert(中间插入)
|
Poor
|
Perfect
|
Perfect
|
Erase(中间删除)
|
Poor
|
Perfect
|
Perfect
|
Pop_back(后部删除)
|
Perfect
|
Perfect
|
Normal
|
Swap(交换数据)
|
Perfect
|
Very good
|
Good
|
遍历
|
Perfect
|
Good
|
Normal
|
从表中可以总结出一下几点:
(1)vector适用于随机存取,支持[],随机存取时间为常数;但是在非末尾删除插入数据时,效率极低。
(2)list适用于数组中间频繁插入删除数据,其插入删除开销低,但是不支持随机存取。
(3)deque界于vector和list两者之间,支持随机存取,队首队尾插入删除操作开销极小。随机存取效率接近于vector,队首队尾插入删除接近于list。
接下来,从它们的内部机制来分析原因:
vector事实上表示的是一块连续的内存,当数据超过数组大小,需要申请新的内存,这时,vector会申请一块足够大的连续内存,把原来数据复制到新的内存,并释放原来vector占用的内存。所谓随机存取,就是可以通过公式直接计算出元素地址的方式,而不需要挨个查找。vector的计算公式类似于 a0+(i-1)*d (a0为vector地址,i为第i个元素,d为每个元素占用的地址个数。
list是双向链式表,在内存中不一定连续。如果要实现随机访问,需要遍历整个数组,在c++标准库模版索性没有提供随机存储([]操作)。但是链式存储有一个好处,就是在表中间插入和删除元素特别方便。
deque事实上是有多个连续块组成,是c++中的双向队列,因此在两端插入删除元素特别方便,(其内存结构如下:
http://blog.csdn.net/yfkiss/article/details/6559149)
对于deque的工作机制,有几点没得到确认的猜测:
(1)因为可以再队列两头快速的插入元素,则说明,元素的第一个位置并不在申请内存的第一个位置,其前面应该还有连续的空间待用
(2)因为deque的随机访问时间为常数,所以可推测其其随机访问公式为 一分段函数
if(i<s0)
addr=a0+d*(i-1)
else if(i>s0&&i<s1)
addr=a1+d*(i-s0)
else if(i>s1 && i<s2)
addr=a2+d*(i-s0-s1)
else
....
(3)因为中间插入删除元素逊于list,优于vector,可推测:对于中间插入删除时这样的,给待插入(删除)元素所在的连续块重新分配内存,插入(删除)新元素,其他连续快不动。
下图为vector、list、deque的无理存储结构。(http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)
待继续完善.......
分享到:
相关推荐
STL中vector、list、deque和map的区别
在实验报告"vector和deque使用方法"中,我们将深入探讨这两种容器的用法、实现原理以及它们的优缺点。 **1. `vector`容器** `vector`是一种动态数组,它允许在任何位置插入和删除元素。在`vector`中,元素是连续...
在 C++ 中,容器是指可以存储多个元素的数据结构,例如 vector、deque 等。这些容器提供了多种操作,例如插入、删除、访问等。今天,我们将详细介绍容器中的 vector 和 deque,以及指针的使用。 容器概述 容器是 ...
在这个"STL.zip"压缩包中,包含了对vector和deque两种重要容器的自定义实现,以及一系列用于测试这些数据结构的用例。下面我们将深入探讨这两个容器及其相关的编程概念。 首先,`vector`是STL中最常见的动态数组,...
本资源包含对STL中多种关键容器的详细讲解,包括Vector、Deque、sort、set、map等,这些都是C++程序员在实际开发中不可或缺的工具。 1. **Vector**:Vector是一个动态数组,它允许在任何位置插入和删除元素。其底层...
案例-评委打分 ...遍历vector容器,取出来每一个选手,执行for循环,可以把10个评分打分存到deque容器中 sort算法对deque容器中分数排序,去除最高和最低分 deque容器遍历一遍,累加总分 获取平均分
### Vector与Deque详解 #### Vector概述 在C++标准模板库(STL)中,`vector`是一个重要的容器类型,它本质...通过理解这两种容器的特点和差异,开发者可以选择最适合特定需求的数据结构,从而提高程序的性能和效率。
本文将对`std::deque`进行深入剖析,探讨其内存管理和性能特性,并通过对比`std::vector`来帮助读者理解何时以及为什么应当选择`std::deque`。 #### 内存管理与性能 `std::deque`和`std::vector`虽然在使用上有很...
【大数据——数据结构】 在计算机科学中,数据结构是组织和管理大量数据的方式,而堆与栈是两种关键的数据结构,特别是在处理大数据时显得尤为重要。它们在内存中的工作方式直接影响到程序的性能和效率。 一、堆与...
这篇深入研究C++中的STL `deque`容器的文章旨在探讨在什么情况下`deque`比`vector`更合适,并分析两者在内存管理和性能上的差异。 首先,`deque`和`vector`都允许动态存储和访问元素。然而,它们在内存分配上有显著...
在这个主题中,我们将深入探讨vector、list、map、set和deque这五个主要的STL容器,并通过具体的例子和PPT讲解来理解它们的应用。 1. **vector**:vector是动态数组,它可以方便地在任何位置插入和删除元素,但主要...
Python中的`collections`模块提供了一个高效且功能丰富的数据结构,其中`deque`(双端队列)是一个重要的部分。双端队列允许我们在其两端进行插入和删除操作,这使得它在很多场景下比列表更加实用,特别是对于需要...
- **内存连续性**:vector的元素是连续存储的,而deque的元素可能分散在内存中,这可能影响对连续内存有要求的算法(如memcpy)的效率。 ### 应用场景 - 当你需要频繁在容器的两端进行插入和删除操作时,deque是一...
在C++中,标准模板库(STL)提供了一套丰富的数据结构和算法,如vector、list、deque、set、map等,它们都基于上述数据结构实现,大大简化了开发工作。例如,vector相当于动态数组,提供了高效且灵活的内存管理;list...
本篇文章将专注于一种重要的Sequence容器——`vector`,并探讨其与其他Sequence容器如`list`和`deque`的使用、性能差异以及内部实现原理。 首先,`vector`是一种动态数组,它支持随机访问和连续存储。在构造`vector...
与`vector`类似,`deque`内部也是通过动态分配内存来存储元素,但与`vector`不同的是,`deque`的数据不是连续存储的,而是分成多个块(chunk)存放,每个块内部元素是连续的。这样的设计使得在两端进行插入和删除...
标题中的“6-3 Deque”指...总之,这个PTA练习旨在帮助学习者深入理解双端队列的概念,熟悉C++中的`std::deque`容器,并能够熟练地在实际问题中应用它。通过这个练习,不仅可以增强数据结构知识,还能提高C++编程技能。
在C++中,这些数据结构可以通过自定义类或结构体来实现,也可以利用STL(标准模板库)中的容器,如vector、list、deque、set和map等。 例如,数组是最基本的数据结构,它提供了一种在内存中连续存储元素的方法。...
在C++编程中,`list`和`deque`是两种重要的容器,它们属于STL(Standard Template Library,标准模板库)的一部分。这两种容器都用于存储和管理动态大小的元素序列,但它们各自有不同的特性和使用场景。 `list`是一...
数据结构是计算机科学中的核心概念,它涉及到如何有效地组织和管理数据,以便于高效地进行存储、检索和操作。...通过本书的源代码实例,读者可以得到宝贵的实践经验和对C++数据结构及STL的深入理解。