Индексы вместо указателей в контейнерах STL?

Question

В связи с особыми требованиями [*] мне нужна реализация односвязного списка, которая использует целочисленные индексы вместо указателей для связи узлов. Индексы всегда интерпретируются относительно вектора, содержащего узлы списка.

Я думал, что мог бы достичь этого, определив свой собственный распределитель, но, глядя на реализацию gcc, они явно используют указатели для полей ссылки в узлах списка (то есть они не используют тип указателя, предоставленный распределителем) :

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

(Для этой цели интерфейс распределителя также несовершенен в том смысле, что он не определяет функцию разыменования; для разыменования целочисленного индекса всегда требуется указатель на базовое хранилище.)

Знаете ли вы библиотеку STL-подобных структур данных (я в основном нуждаюсь в одно- и двусвязных списках), которые используют индексы (относительно базового вектора) вместо указателей для связи узлов?

[*] Экономия места: списки будут содержать много 32-битных целых чисел. С двумя указателями на узел (список STL имеет двойную связь), накладные расходы составляют 200% или 400% на 64-разрядной платформе, не считая накладных расходов распределителя по умолчанию.

РЕДАКТИРОВАТЬ: Я ищу реализацию SLL, которая определяет узлы следующим образом:

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

_next интерпретируется по отношению к. неявный массив или вектор (должен быть предоставлен извне каждому методу, работающему в списке).

EDIT2: После небольшого поиска я обнаружил, что стандарт фактически требует, чтобы распределители, предназначенные для использования со стандартными коллекциями, определяли тип указателя, эквивалентный T *.

Answer 1

Почему вы используете список STL? Если у вас нет очень особых требований, вы должны использовать vector или deque. Если ваша причина использования списка заключалась в том, чтобы повысить эффективность вставки, вы должны заметить, что deque предлагает большинство преимуществ как list, так и vector, поскольку он не требуется для поддержки непрерывного хранения, но использует массивы, так как базовый носитель.

РЕДАКТИРОВАТЬ: А что касается вашего желания для списка, который предлагает operator[], такая структура не существует (по крайней мере, не существует и все еще соответствует STL). Одна из ключевых идей проекта STL состоит в том, что алгоритмы и контейнеры предлагают только то, что они могут эффективно . Учитывая, что для предложения operator[] в связанном списке требуется линейное время для каждого доступа, это неэффективно.

Answer 2

Нам пришлось написать собственный список контейнеров, чтобы получить именно это.Это примерно полдня работы.

Answer 3

Boost.Interprocess (контейнеры) предоставляет контейнер слайста, который использует тип указателя распределителя. Может быть, это то, что вы ищете :)

Даже если эти контейнеры включены в Boost.Interprocess, они отлично работают во внутрипроцессной памяти. Кроме того, автор уже сделал разделение и предложил ботов как Boost.Containers ( Документация / Источник )

Answer 4

Если вас беспокоит нехватка памяти в связанном списке для хранения большого количества int значений, вам определенно следует учитывать vector или deque , как предложил Billy ONeal .

Недостаток любого из этих контейнеров по сравнению со связанным списком возникает при вставке элементов. deque или vector придется копировать элементы, если вы вставляете элементы в середину контейнера (deque имеет большое преимущество перед вектором, если вы собираетесь вставить в начало контейнера, и даже имеет преимущество при добавлении в конец контейнера).

Однако копирование int элементов после вставки на самом деле не намного дороже, чем сканирование связанного списка для поиска элемента по индексу. Поскольку deque и vector могут определять местоположение элемента по индексу в постоянное время, а структуры данных обычно читаются гораздо чаще, чем изменяются, вы, вероятно, увидите чистый выигрыш, используя либо deque, либо * 1017. * по связанному списку int, к которому вы обращаетесь по индексу (даже пользовательской версии).

Answer 5

Один из вариантов, который немного ограничен - это использовать Judy Arrays . Они обеспечивают высокоэффективное хранение и вычислительно эффективны. Они хороши для хранения наборов целых чисел; Я не знаю, подходит ли это вашей проблеме.