我正在使用一个std::deque来存储大量的元素。
我知道deques是以向量列表的形式实现的。这些向量的大小无法设置,但我想知道选择该大小的算法。
我正在使用一个std::deque来存储大量的元素。
我知道deques是以向量列表的形式实现的。这些向量的大小无法设置,但我想知道选择该大小的算法。
deque被实现为向量的向量(列表会妨碍常数时间的随机访问)。辅助向量的大小取决于实现,一种常见的算法是使用固定大小的字节。
deque
的性能表现如此糟糕... - Matthieu M.N
是恒定的。如果 N
是十亿,第一个容器仍然只有大约50或100个元素(或者实现选择的任何数量)。如果 N
是5万亿,则不需要花费5000倍的时间。此外,如果通过将其分割为过大时保持第一个子向量的大小“更或多或少恒定”,则相对于该子向量的 N
也是“平摊常数”。 - Damon我的deque
实现是来自GNU的,它源于HP/SGI版本,不是std::list
的std::vector
列表。注释中说明:
* In previous HP/SGI versions of deque, there was an extra template
* parameter so users could control the node size. This extension turned
* out to violate the C++ standard (it can be detected using template
* template parameters), and it was removed.
*
* Here's how a deque<Tp> manages memory. Each deque has 4 members:
*
* - Tp** _M_map
* - size_t _M_map_size
* - iterator _M_start, _M_finish
*
* map_size is at least 8. %map is an array of map_size
* pointers-to-"nodes". (The name %map has nothing to do with the
* std::map class, and "nodes" should not be confused with
* std::list's usage of "node".)