c++ - STL 容器中的索引而不是指针？

Question

由于特定要求 [*]，我需要一个使用整数索引而不是指向链接节点的指针的单链表实现。索引总是根据包含列表节点的 vector 来解释。

我想我可以通过定义我自己的分配器来实现这一点，但是查看 gcc 的实现，他们明确地使用指针作为列表节点中的链接字段(即，他们不使用分配器提供的指针类型) :

  struct _List_node_base
  {
    _List_node_base* _M_next;   ///< Self-explanatory
    _List_node_base* _M_prev;   ///< Self-explanatory
    ...
  }

(出于这个目的，分配器接口(interface)也有缺陷，因为它没有定义解引用函数；“解引用”整数索引总是需要指向底层存储的指针。)

你知道一个类似 STL 的数据结构库(我最需要的是单链表和双向链表)，它使用索引(wrt。一个基本 vector )而不是指向链接节点的指针吗？

[*] 节省空间:列表将包含许多 32 位整数。每个节点有两个指针(STL 列表是双向链接的)，开销是 200%，或者在 64 位平台上是 400%，不包括默认分配器的开销。

编辑:我正在寻找以下列方式定义节点的 SLL 实现:

  struct list_node
  {
    int _value;  ///< The value in the list
    int _next;   ///< Next node in the list
    ...
  }

_next 被解释为 wrt。隐式数组或 vector (必须在外部提供给在列表上运行的每个方法)。

EDIT2:经过更多搜索，我发现该标准实际上要求旨在与标准集合一起使用的分配器必须将指针类型定义为与 T* 等效。

Answer 1

为什么要使用 STL 列表？除非您有非常的特定要求，否则您应该改用vector 或deque。如果您使用列表的原因是为了提高插入效率，您应该注意到 deque 提供了 list 和 vector 的大部分优点因为它不需要维护连续存储，而是使用数组作为底层存储介质。

编辑:关于您希望提供 operator[] 的列表，这样的结构不存在(至少不存在并且仍然符合 STL)。 STL 的关键设计思想之一是算法和容器只提供它们可以高效 提供的内容。考虑到在链表上提供 operator[] 需要每次访问的线性时间，这是低效的。