5

早在 C++11 之前的日子里,许多书籍作者建议在需要deque具有随机访问的动态大小容器的情况下使用。这部分是因为它deque是一种移动通用的数据结构vector,但也因为vector在 C++11 之前的世界中没有提供一种方便的方法来通过“缩小到合身。” 通过方括号运算符和迭代器间接访问元素的更大开销deque似乎被更大vector的重新分配开销所包含。

另一方面,有些事情并没有改变。vector仍然使用几何(即大小*因子)方案进行重新分配,并且仍然必须将其所有元素复制(或移动,如果可能)到新分配的空间中。vector关于在前面和/或中间插入/删除元素,它仍然是旧的。另一方面,它提供了更好的参考局部性,尽管如果所使用的块deque是“好大”的大小,那么对于许多应用程序来说,缓存方面的好处是可以争论的。

所以,我的问题是,鉴于 C++11 带来的变化,deque是否应该继续保持动态大小/随机访问需求的 go to / first choice 容器。

4

2 回答 2

4

确实会产生影响的一种语言 + 库更改是当您具有不可复制 + 不可移动类型(例如包含 amutexatomic变量的类型)时。您可以将它们存储在 a 中deque(通过其中一种emplace_* 方法),但不能将它们存储在 a 中vector

于 2013-08-07T15:45:57.800 回答
4

Josuttis 的 C++ 标准库指出:(何时使用哪个容器Sec 7.12)

默认情况下,您应该使用vector。它具有最简单的内部数据结构并提供随机访问。因此,数据访问方便灵活,并且数据处理通常足够快。

如果您经常在序列的开头和结尾插入和/或删除元素,则应使用deque。如果在删除元素时容器使用的内部内存量很重要,您还应该使用双端队列。此外,由于向量通常使用一块内存存储其元素,因此双端队列可能能够包含更多元素,因为它使用多个块。

于 2013-08-07T15:49:21.610 回答