stl — когда использовать C ++ forward_list
Я немного новичок в C ++ и читаю книгу «Язык программирования C ++ (4-е издание)». При чтении главы «Контейнеры STL» в книге есть введение в forward_list:
Forward_list (односвязный список) — это в основном список, оптимизированный
для пустых и очень коротких списков. Пустой forward_list занимает только
одно слово. Есть удивительно много применений для списков, где большинство
пусто (а остальные очень короткие).
Мне интересно, насколько короткий список считается коротким? И кто-нибудь может привести простой пример, чтобы воспользоваться преимуществом forward_list?
Решение
Вообще говоря, вы хотите использовать что-то вроде списка пересылки, когда вас больше беспокоит размер хранилища, чем итерации произвольного доступа.
Это структура данных, которую вы можете использовать для хранения различных типов разреженных данных. Когда у вас есть большое количество записей, которые имеют какое-то значение по умолчанию, становится дешевле (в отношении памяти) предполагать, что все записи являются значением по умолчанию, если явно не указано, что это не так.
В последний раз я использовал forward_list представлял разреженная матрица со списком подходов списка. Это сэкономило много памяти, потому что только очень небольшое количество записей было ненулевым, а размеры матриц были очень большими.
Скажем, у вас есть граф с очень большим количеством вершин, но не большим числом ребер, возможно, есть миллионы вершин (узлов), но у каждого есть не более 5 ребер (связей). Если бы вы попытались сохранить этот граф в памяти, используя матрицу смежности (многомерный массив), размер хранилища был бы O(|v|^2) (где v — множество вершин). Если вы сохранили его как массив, который был длиной вершин, содержащих список ребер для каждой вершины, то размер будет O(|v|*|e|) (где е — множество ребер). Если ребер значительно меньше, чем вершин, что имеет место во многих графах, тогда подход со списком ребер может быть хорошим выбором. В этом случае упоминалось выше |e| максимум 5, поэтому экономия памяти огромна. Часто, когда вы находите интересующую вершину, вы загружаете связанные с ней ребра в память перед тем, как начать работу с ней. Идея в основном заключается в хранении, а не в итерациях с произвольным доступом в этом случае, поэтому вам не нужно платить за большое количество указателей в обратном направлении, если вы ими не пользуетесь. За это forward_list будет подходящей структурой данных для использования.
Другие решения
Вот структура узла, используемая в 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 экономию места (при условии, что вам не нужен обратный итератор).