当前位置：文江博客话题详情

STL 内部结构：双端队列实现

发布于 2024-11-02 04:45:53 字数 294 浏览 1 评论 0原文

我正在使用 std::deque用于存储大量项目。
我知道双端队列是作为向量列表实现的。这些向量的大小无法设置，但我想知道选择该大小的算法是什么。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

蓝海 2024-11-09 04:45:53

双端队列被实现为向量的向量（向量列表会阻碍恒定时间随机访问）。辅助向量的大小取决于实现，常见算法是使用以字节为单位的常量大小。

回复收藏 0 原文

野生奥特曼 2024-11-09 04:45:53

我的 deque 实现（来自 GNU 的实现，源自 HP/SGI 版本）不是一个向量列表；而是一个向量列表。至少，不是 std::vector 的 std::list。评论指出

*  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".)

My deque implementation, the one from GNU which is derived from the HP/SGI version, is not a list of vectors; at least, not an std::list of std::vectors. The comments state

*  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".)

回复收藏 0 原文

~没有更多了~