Разница между списком и показателями forward_list?
Как и в случае с ++11, у нас есть два типа списка:
std::list<int> lst = { 1, 2, 3, 4, 5 };
std::forward_list<int> flst = { 5, 4, 3, 2, 1};
Поскольку мы знаем, что список основан на двусвязном списке, а forward_list основан на односвязном списке.
Как мы должны решить, какой из них использовать? Есть ли какой-либо выигрыш в производительности любого из списка выше других?
2 ответа
Как мы должны решить, какой из них использовать?
Решите, нужна ли вам двунаправленная итерация. Если прямая итерация достаточно хороша, используйте std::forward_list, если вам не нужно поддерживать версии C++ старше C++11, которые могут иметь только std::list,
Есть ли какой-либо выигрыш в производительности любого из списка выше других?
std::forward_list устраняет указатель на узел (со всеми сопутствующими преимуществами для кеша данных и подсистемы памяти), в то время как std::list обеспечивает постоянное уменьшение итератора.
Но на практике ни один из этих контейнеров не используется так широко, как можно было бы поверить при посещении школы информатики. Реальная производительность std::vector лучше для многих приложений, и его использование памяти всегда меньше. Более требовательным приложениям, требующим списки, было бы полезно рассмотреть навязчивые списки, которые стандарт C++ не предоставляет.
В дополнение к тому, что сказал user4323 , если вам нужно использовать связанные списки, при принятии решения имейте в виду следующее:
не имеет функций модификаторов, работающих в конце, из-за своей природы:
push_back, pop_back, emplace_back
Кроме того, не предоставляет функцию-член для большей эффективности в соответствии с .
sizeфункция
std::listдает количество элементов в постоянное время по С++11. С другой стороны, для внутреннего счетчика требуется дополнительная память, что делает вставку и удаление немного менее эффективными. Для достижения размера
std::forward_list, алгоритм расстояния можно использовать с
begin()а также
end()функции, но эта операция занимает линейное время.