Я хотел бы использовать std:: forward_list
Потому что:
Переслать список - это контейнер, который поддерживает быструю вставку и удаление элементов из любого места из контейнера
Но не существует * std:: forward_list:: push_back *.
Есть ли высокопроизводительный способ добавления поддержки для одной или нет причин для этого?
std::forward_list поддерживает быструю вставку и удаление, но не обход конца. Чтобы реализовать .push_back, вам сначала нужно будет дойти до конца списка, то есть O (N), а не быстро, что, вероятно, поэтому не реализовано.
Вы можете найти итератор для последнего элемента, увеличив .before_begin N раз
auto before_end = slist.before_begin();
for (auto& _ : slist)
++ before_end;
а затем используйте .insert_after или .emplace_after для вставки элемента:
slist.insert_after(before_end, 1234);
Я рекомендую против std::forward_list, как я рекомендую против std::list практически во всех ситуациях. Лично я никогда не находил ситуацию в своем коде, где связанный список был лучшей структурой данных.
В С++ ваш сбор данных по умолчанию должен быть std::vector. Это дает вам эффективный push_back, если это то, что вам действительно нужно. Это технически не дает вам эффективного удаления и вставки из середины, если вы только посмотрите на абстрактные измерения сложности большой О из этой одной операции. Однако в реальном мире std::vector по-прежнему выигрывает даже для вставки и удаления в середине.
В качестве примера, Bjarne Stroustrup создал тест 100 000 элементов std::list vs. std::vector. Он будет искать каждый элемент и удалять его. Затем он найдет точку вставки и вставит в середину. Он мог использовать двоичный поиск в std::vector, но не сделал сравнение более справедливым.
Результаты показывают сильный выигрыш для std::vector, даже в этой ситуации, когда std::list должен быть сильным. Простое перемещение std::list занимает гораздо больше времени из-за того, насколько далеко друг от друга находятся в памяти все объекты. std::list не кэширует, что, возможно, является самым важным для современных процессоров.
Полный разговор Бьярна Страуструпа
Тщательное объяснение эффектов с помощью тестов с несколькими размерами
Обратите внимание, что эта вторая ссылка здесь дает некоторые ситуации, когда вы, возможно, захотите использовать std::list, например, когда размер элементов велик. Тем не менее, я был в ситуации, когда у меня много элементов в определенном порядке и вам нужно было удалить некоторые.
Эти элементы были больше, чем любой встроенный тип, но не огромный, возможно, 20-30 байтов каждый на 32-разрядном компьютере). Количество элементов было достаточно большим, так что вся моя структура данных составляла несколько сотен MiB. Сбор данных представлял собой набор значений, которые теоретически могли бы быть действительными на основе известной в настоящее время информации. Алгоритм повторяется по всем элементам и удаленным элементам, которые больше не могут быть действительными на основе новой информации, причем каждый проход, вероятно, удаляет около 80% оставшихся элементов.
Моя первая реализация была простым подходом std::vector, когда я удалил недопустимые элементы по мере прохождения. Это работало для небольших наборов тестовых данных, но когда я пытался делать настоящую вещь, было слишком медленно, чтобы быть полезным. Я переключился на std::list в качестве контейнера, но использовал тот же алгоритм, и я видел значительные улучшения производительности. Однако было слишком медленно, чтобы быть полезным. Победившее изменение состояло в том, чтобы вернуться к std::vector, но вместо удаления элементов, которые были плохими, я создал новый std::vector, и все найденные мной элементы, которые были хорошими, были помещены в это std::vector, а затем в конце функции я бы просто отказался от старого std::vector и использовал новый, и это дало мне примерно такую же скорость по сравнению с std::list, как std::list предоставил мне мой оригинальный std::vector и это было достаточно быстро, чтобы быть полезным.
Нет push_back, потому что список не отслеживает заднюю часть списка, только фронт.
Вы можете написать обертку вокруг списка, который поддерживает итератор для последнего элемента, и реализует push_back с помощью insert_after или push_front в зависимости от того, пуст ли список. Это будет довольно сложно, если вы хотите поддерживать более сложные операции (например, sort и splice_after).
В качестве альтернативы, если вам не нужно push_back быть быстрым, просто сделать это в линейном времени.
Если память не очень плотная, лучшим решением является использование list. Он имеет те же рабочие характеристики, что и forward_list, и двунаправлен, поддерживает push_back, а также push_front; стоимость - дополнительный указатель на элемент.
Точка std:: forward_list должна быть ультра-усеченной версией std:: list, поэтому она не хранит итератор для последнего элемента. Если вам это нужно, вам придется поддерживать его самостоятельно, например:
forward_list<int> a;
auto it = a.before_begin();
for(int i = 0; i < 10; ++i)
it = a.insert_after(it, i);
К сожалению, я не могу добавить комментарий (низкая репутация), но я просто хотел упомянуть, что один из преимуществ forward_list и list заключается в том, что операции insert-delete не делают недействительными итераторы. У меня было приложение, в котором коллекция элементов росла, итерации и обработки отдельных элементов. Отсутствие недействительности итератора позволило мне реализовать сегментное сканирование (начало списка как начало сегмента и начало последнего сегмента как конец).