Когда использовать C++ forward_list

Question

Я немного новичок в C++ и читаю книгу "Язык программирования C++ (4-е издание)". Когда вы читаете главу "Контейнеры STL", в книге есть введение в forward_list:

Forward_list (односвязный список) - это список, оптимизированный для пустых и очень коротких списков. Пустой forward_list занимает всего одно слово. Есть удивительно много применений для списков, где большинство пусто (а остальные очень короткие).

Мне интересно, насколько короткий список считается коротким? И кто-нибудь может привести простой пример, чтобы воспользоваться преимуществом forward_list?

Answer 1

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

В последний раз я использовал forward_list представлял разреженную матрицу со списком подходов. Это сэкономило много памяти, потому что только очень небольшое количество записей было ненулевым, а размеры матриц были очень большими.

Скажем, у вас есть граф с очень большим количеством вершин, но не большим числом ребер, возможно, есть миллионы вершин (узлов), но у каждого есть не более 5 ребер (связей). Если бы вы попытались сохранить этот граф в памяти, используя матрицу смежности (многомерный массив), размер хранилища был бы O(|v|^2) (где v - множество вершин). Если вы сохранили его как массив, который был длиной вершин, содержащих список ребер для каждой вершины, то размер будет O(|v|*|e|) (где е - множество ребер). Если ребер значительно меньше, чем вершин, как в случае многих графов, тогда подход со списком ребер может быть хорошим выбором. В этом случае упоминалось выше |e| максимум 5, поэтому экономия памяти огромна. Часто, когда вы находите интересующую вершину, вы загружаете связанные с ней ребра в память перед тем, как начать работу с ней. Идея в основном заключается в хранении, а не в итерациях с произвольным доступом в этом случае, поэтому вам не нужно платить за большое количество указателей в обратном направлении, если вы их не используете. За это forward_list будет подходящей структурой данных для использования.

Answer 2

Вот структура узла, используемая в std::list а также std::forward_list:

struct _List_node      // list node
{   
  _Voidptr _Next;      // successor node, or first element if head
  _Voidptr _Prev;      // predecessor node, or last element if head
  _Value_type _Myval;  // the stored value, unused if head
};

struct _Flist_node     // forward_list node
{   
  _Voidptr _Next;      // successor node
  _Value_type _Myval;  // the stored value
};

Расчет пространства:

sizeof(_List_node)  = 2 * sizeof(_Voidptr) + sizeof(_Value_type)
sizeof(_Flist_node) = 1 * sizeof(_Voidptr) + sizeof(_Value_type)

если sizeof(_Value_type) такое же или приблизительно равно sizeof(_Voidptr) тогда мы имеем:

sizeof(_List_node)  ~ 3 * sizeof(_Voidptr)
sizeof(_Flist_node) ~ 2 * sizeof(_Voidptr)

Если sizeof(_Value_type) >> sizeof(_Voidptr) тогда экономия незначительна. Но для хранения небольших объектов с помощью forward_list имеет ~1,5x экономию места (при условии, что вам не нужен обратный итератор).