Chinaunix

标题: 大家帮忙看看这句话应该怎么理解 [打印本页]

作者: liuwantao 时间: 2005-11-01 11:09
标题: 大家帮忙看看这句话应该怎么理解
C++ Primer (3rd edition) 第214页的第一行:
除非我们需要在容器首部插入和删除元素,否则 vector 比deque 好.

作者: renstone921 时间: 2005-11-01 11:33
这涉及到数据结构里面的两种存储结构，使用数组形式的和使用链表形式的。数组形式的，他的存取时间快，因为只需要知道下标；链表形式的，必须从链表头部开始，逐一进行判断。
但进行插入删除时，数组形式的，需要为待插入元素腾出一个空间，然后再插入元素，所以要将改位置后面的元素逐一进行向后复制操作，然后插入。
进行删除时，数组形式的，需要把该元素所在位置后的元素向前移动，仍旧代价不小。

链式结构的话，只涉及到查找，分配存储空间，链入等操作。所以相比较而言，经常进行插入、删除操作的话，使用链式存储结构的代价要小一些。

vector是数组的抽象,在数组中间进行插入删除的操作时,要涉及到为待插入的数据元素在数组中间的某个位置分配存储空间,这就涉及到一系列的数组元素拷贝操作,占用cpu时间。

deque可以视为是一个基于链式存储结构的抽象，在中间进行插入操作时，所进行的操作仅仅是查找到合适位置，为新元素分配存储空间，将新元素链入队列，从而没有元素拷贝复制的代价。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)