станд :: forward_list и станд :: forward_list :: push_back

Question

Я хотел бы использовать std::forward_list

Потому что:

Forward список представляет собой контейнер, который поддерживает быструю вставку и удаление элементов из любого места от контейнера

Но нет * std :: forward_list :: push_back * реализация.

Существует ли высокоэффективный способ добавления поддержки по той или иной причине?

Answer 1

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); 

Answer 2

Там есть нет push_back, потому что список не отслеживает заднюю часть списка , только фронт.

Вы можете написать обертку вокруг списка, который поддерживает итератор для последнего элемента, и реализует push_back с использованием либо insert_after или push_front в зависимости от того, список пуст. Это будет довольно сложно, если вы хотите поддерживать более сложные операции (например, sort и splice_after).

В качестве альтернативы, если вам не нужно push_back, чтобы быть быстрым, это легко сделать в линейном режиме.

Если память не очень плотная, лучшим решением является использование list. Он имеет те же рабочие характеристики, что и forward_list, и двунаправленный, поддерживающий push_back, а также push_front; стоимость - дополнительный указатель на элемент.

Answer 3

Точка 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); 

Answer 4

Я рекомендую против std::forward_list так же, как я рекомендую против std::list практически во всех ситуациях. Лично я никогда не обнаружил ситуации в моем коде, где связанный список был лучшей структурой данных.

В C++ ваш сбор данных по умолчанию должен быть std::vector. Это дает вам push_back, если это то, что вам действительно нужно. Это технически не дает вам эффективного удаления и вставки из середины, если вы только посмотрите на абстрактные измерения сложности большой О из этой одной операции.В реальном мире, однако, std::vector по-прежнему выигрывает даже для вставки и удаления в середине.

В качестве примера, Bjarne Stroustrup создал тест из 100 000 элементов std::list против std::vector. Он будет искать каждый элемент и удалять его. Затем он найдет точку вставки и вставит в середину. Он мог бы использовать двоичный поиск на std::vector, но не сделал сравнение «более справедливым».

Результаты показывают сильную победу для std::vector, даже в этой ситуации, когда std::list должен быть сильным. Простое перемещение std::list занимает намного больше времени, так как далеко друг от друга в памяти находятся все объекты. std::list не относится к кэшу, что, возможно, является самым важным для современных процессоров.

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

Обратите внимание, что эта вторая ссылка здесь приведены некоторые ситуации, где вы, возможно, захотите использовать 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, и это было достаточно быстро, чтобы быть полезным.

Answer 5

Unfortunatelly Я не могу добавить комментарий (низкая репутация), но я просто хотел упомянуть, что одним из преимуществ списка forward_list & является то, что операции вставки-удаления не делают недействительными итераторы. У меня было приложение, в котором коллекция элементов росла, итерации и обработки отдельных элементов. Отсутствие недействительности итератора позволило мне реализовать сегментное сканирование (начало списка как начало сегмента и начало последнего сегмента как конец).