Разница между производительностью list и forward_list?
Как и в C++ 11, у нас есть два типа списков:
std::list<int> lst = { 1, 2, 3, 4, 5 };
std::forward_list<int> flst = { 5, 4, 3, 2, 1};
Как мы знаем, список основан на двусвязном списке, а forward_list основан на односвязном списке.
Как нам решить, какой из них использовать? Есть ли какое-либо преимущество в производительности у любого из перечисленных выше?
std::forward_list, тогда как если вам нужны возможности двунаправленной итерации, используйте std::list. Но прежде чем принять это решение, обязательно сравните, действительно ли вам нужен связанный список, и может ли непрерывное хранилище с произвольным доступом std::vector или std::array быть жизнеспособной альтернативой.
@Azeem обратите внимание, что принятый ответ в этом потоке очень надуманный (вплоть до введения в заблуждение) с использованием связанного списка для объектов размером 1 байт (в этом случае дополнительный указатель в std::list будет казаться чрезвычайно дорогостоящим для памяти). Непринятый ответ в связанных вопросах и ответах дает более правильное сравнение.
Решение простое. Никогда не используйте ни один из них. Всегда есть лучшая структура данных. Ну почти всегда. Если вы столкнулись с необходимостью использовать связанный список, вы делаете довольно эзотерические вещи, и SO вам не поможет.
@ n.m. Я бы не стал заходить так далеко, но да, из вас, ответивший на каждый вопрос о стандартном списке «не используйте стандартный список», у вас был бы уровень точности выше 99%.
Ответы 1
How should we decide which one to used?
Решите, нужна ли вам двунаправленная итерация. Если прямая итерация достаточно хороша, используйте std::forward_list, если вам не нужно поддерживать версии C++ старше C++ 11, которые могут иметь только std::list.
Is there any performance benefit of any of the list above other?
std::forward_list исключает указатель на узел (со всеми сопутствующими преимуществами для кэша данных и подсистемы памяти), в то время как std::list обеспечивает декремент итератора с постоянным временем.
Но на практике ни один из этих контейнеров не используется так широко, как можно было бы подумать в школе информатики. Реальная производительность std::vector выше для многих приложений, а использование памяти всегда меньше. Более требовательным приложениям, требующим списков, было бы хорошо рассмотреть навязчивые списки, которые стандарт C++ не предоставляет.
Для сравнения памяти см. Это: stackoverflow.com/questions/11545058/…