Эффективность использования двунаправленного списка вместо однонаправленного
В чем состоит эффективность использования двунаправленного списка вместо однонаправленного с точки зрения системных ресурсов. То есть по отдельным видам ресурсов, какой вариант списка лучше, а какой хуже?
Ответы (1 шт):
Однонаправленный список лучше двунаправленного только тем, что у него один указатель, а не два. Если в списке хранятся мелкие объекты (4-8 байт), то это может быть существенно. Также, обновить два указателя и обновить один указатель может существенно сказаться на скорости.
Но двунаправленный список все же это хороший полноценный контейнер, а односвязный - очень сильно урезанный. К примеру, у него даже нет size().
Но если смотреть правде в глаза, то самый лучший список это std::vector. Да, да. Если он не очень большой (десяток-другой элементов), то по производительности сильно и сильно выигрывает. Если список побольше нужен, есть смысл посмотреть на std::deque.
Вот https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html люди меряют, что лучше.
И ещё - http://blog.davidecoppola.com/2014/05/cpp-benchmarks-vector-vs-list-vs-deque/