STL 容器中用索引代替指针？
由于特定要求 [*]，我需要一个使用整数索引而不是指向链接节点的指针的单链表实现。索引始终根据包含列表节点的向量进行解释。
我想我可以通过定义我自己的分配器来实现这一点，但是查看 gcc 的实现，他们显式地使用列表节点中链接字段的指针（即，他们不使用分配器提供的指针类型）：（
struct _List_node_base
{
_List_node_base* _M_next; ///< Self-explanatory
_List_node_base* _M_prev; ///< Self-explanatory
...
}
对于为此，分配器接口也有缺陷，因为它没有定义取消引用函数；“取消引用”整数索引总是需要一个指向底层存储的指针。）
您知道类似 STL 的数据结构库吗（我主要是 ）需要使用索引（基本向量）而不是指向链接节点的指针的单链表和双链表吗？
[*] 节省空间：列表将包含许多 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.隐式数组或向量（必须从外部提供给在列表上运行的每个方法）。
EDIT2：经过更多搜索后，我发现该标准实际上要求与标准集合一起使用的分配器必须将指针类型定义为与 T* 等效。
Due to specific requirements [*], I need a singly-linked list implementation that uses integer indices instead of pointers to link nodes. The indices are always interpreted with respect to a vector containing the list nodes.
I thought I might achieve this by defining my own allocator, but looking into the gcc's implementation of , they explicitly use pointers for the link fields in the list nodes (i.e., they do not use the pointer type provided by the allocator):
struct _List_node_base
{
_List_node_base* _M_next; ///< Self-explanatory
_List_node_base* _M_prev; ///< Self-explanatory
...
}
(For this purpose, the allocator interface is also deficient in that it does not define a dereference function; "dereferencing" an integer index always needs a pointer to the underlying storage.)
Do you know a library of STL-like data structures (i am mostly in need of singly- and doubly-linked list) that use indices (wrt. a base vector) instead of pointers to link nodes?
[*] Saving space: the lists will contain many 32-bit integers. With two pointers per node (STL list is doubly-linked), the overhead is 200%, or 400% on 64-bit platform, not counting the overhead of the default allocator.
EDIT: I'm looking for a SLL implementation that defines nodes in the following manner:
struct list_node
{
int _value; ///< The value in the list
int _next; ///< Next node in the list
...
}
_next is interpreted wrt. an implicit array or vector (must be provided externally to each method operating on the list).
EDIT2: After a bit more searching, I've found that the standard actually requires that allocators intended to be used with standard collections must define the pointer type to be equivalent with T*.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
为什么使用STL列表？除非您有非常特定要求，否则您应该使用
向量或deque。如果您使用列表的原因是为了提高插入效率，那么您应该注意到，deque提供了list和vector的大部分优点。因为它不需要维护连续的存储，而是使用数组作为底层存储介质。编辑：关于您对提供
operator[]的列表的渴望，这样的结构不存在（至少不存在并且仍然符合STL）。 STL 的关键设计思想之一是算法和容器仅提供它们能够高效的东西。考虑在链表上提供operator[]每次访问都需要线性时间，这效率不高。Why are you using the STL list? Unless you have very specific requirements, you should be using
vectorordequeinstead. If your reason for using the list was to increase insertion efficiency, you should note that adequeoffers most of the advantages of bothlistandvectorbecause it is not required to maintain contiguous storage, but uses arrays as it's underlying storage media.EDIT: And regarding your desire for a list that offers
operator[], such a structure does not exist (at least, does not exist and still conform to the STL). One of the key design ideas of the STL is that algorithms and containers offer only what they can efficiently. Considering offeringoperator[]on a linked list requires linear time for each access, that's not efficient.我们必须编写自己的列表容器才能准确地实现这一点。大约是半天的工作量。
We had to write our own list containers to get exactly this. It's about a half day's work.
Boost.Interprocess（容器）提供了 slist 容器，使用分配器的指针类型。也许这就是您正在寻找的:)
即使这些容器包含在 Boost.Interprocess 中，它们也可以在进程内内存上完美运行。此外，作者已经进行了分离并向机器人提出了 Boost.Containers (文档/源)
Boost.Interprocess (containers) provides slist container that uses the pointer type of the allocator. Maybe this is what you are looking for :)
Even if these containers are included in Boost.Interprocess they work perfectly on intraprocess memory. In addition the author has already made the separation and proposed to bots as Boost.Containers (Documentation/Source)
一种不太可行的选择是使用 Judy Arrays。它们提供高效的存储和计算效率。它们适合存储整数集；我不知道这是否适合你的问题。
One option that is a bit out there is to use Judy Arrays. They provide highly efficient storage and are computationally efficient. They are good for storing sets of integers; I don't know if that suits your problem.
如果您担心存储大量
int值的链表的内存开销，那么您绝对应该考虑vector或deque> 按照比利·奥尼尔的建议。与链表相比，这些容器的缺点都出现在插入元素时。如果将项目插入到容器的中间，则
deque或vector都必须复制元素（如果您将在容器的开头插入，甚至在添加到容器的末尾时也有优势）。然而，插入后复制 int 元素实际上并不比扫描链表通过索引查找元素的成本高很多。由于
deque和vector可以在恒定时间内通过索引定位元素，并且数据结构的读取次数通常远多于修改次数，因此您可能会看到一个网络在通过索引访问的int链接列表（甚至是自定义版本）上使用deque或vector获得增益。If you're concerned about the memory overhead of the linked list for storing a large number of
intvalues, you should definitely consider avectorordequeas Billy ONeal suggested.The drawback to either of these containers when compared to a linked list comes when inserting elements. Either of
dequeorvectorwill have to copy elements if you insert items into the middle of the container (dequehas a big advantage over vector if you're going to insert at the beginning of the container, and even has an advantage when adding to the end of the container).However, copying
intelements after insertion is really not a whole lot more costly than scanning a linked list to find an element by index. Sincedequeandvectorcan locate an element by index in constant time and since data structures are generally read far more often than they're modified, you'll probably see a net gain using either ofdequeorvectorover a linked list ofintthat you access by index (even a custom version).