Indices instead of pointers in STL containers?

Question

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

Answer 1

Why are you using the STL list? Unless you have very specific requirements, you should be using vector or deque instead. If your reason for using the list was to increase insertion efficiency, you should note that a deque offers most of the advantages of both list and vector because 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 offering operator[] on a linked list requires linear time for each access, that's not efficient.

Answer 2

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.

Answer 3

We had to write our own list containers to get exactly this. It's about a half day's work.

Answer 4

If you're concerned about the memory overhead of the linked list for storing a large number of int values, you should definitely consider a vector or deque as Billy ONeal suggested.

The drawback to either of these containers when compared to a linked list comes when inserting elements. Either of deque or vector will have to copy elements if you insert items into the middle of the container (deque has 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 int elements after insertion is really not a whole lot more costly than scanning a linked list to find an element by index. Since deque and vector can 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 of deque or vector over a linked list of int that you access by index (even a custom version).

Answer 5

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)