指数而不是STL容器中的指针？

Question

由于特定的要求[*],我需要一个单链表实现,它使用整数索引而不是链接节点的指针.索引始终根据包含列表节点的向量进行解释.

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

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

(为此目的,分配器接口也缺点在于它没有定义解引用函数;"解除引用"整数索引总是需要指向底层存储的指针.)

您是否知道使用索引(wrt.基本向量)而不是链接节点指针的STL类数据结构库(我主要需要单链和双链表)？

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

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

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

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

EDIT2:经过一番搜索后,我发现标准实际上要求与标准集合一起使用的分配器必须将指针类型定义为与T*等效.

Answer 1

你为什么使用STL列表？除非您有非常具体的要求,否则您应该使用vector或deque代替.如果你的理由使用列表是增加插件效率,你应该注意,deque提供最两者的优点list,并vector因为它不要求保持连续的存储,但使用数组作为它的底层存储介质.

编辑:关于您对提供的列表的期望operator[],这样的结构不存在(至少,不存在并且仍然符合STL).STL的一个关键设计思想是算法和容器只提供它们能够有效的方法.考虑operator[]在链表上提供每个访问需要线性时间,这是无效的.