std :: forward_list и std :: forward_list :: push_back

Question

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

Потому что:

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

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

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

Answer 1

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

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

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

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

Полный доклад Бьярна Страуструпа

Точное объяснение эффектов, с эталонными показателями для нескольких размеров

Обратите внимание, что эта вторая ссылка здесь дает некоторые ситуации, когда вы, возможно, захотите использовать std::list, например, когда размер элементов велик. Однако я был в ситуации, когда у меня было много элементов в определенном порядке, и мне нужно было их удалить.

Эти элементы были больше, чем любой встроенный тип, но не очень большие (возможно, по 20-30 байт каждый на 32-битном компьютере). Количество элементов было достаточно большим, так что вся моя структура данных составляла несколько сотен МБ. Сбор данных представлял собой набор значений, которые теоретически могут быть действительными на основе известной в настоящее время информации. Алгоритм итерировал по всем элементам и удалял элементы, которые больше не могли быть действительными, основываясь на новой информации, причем каждый проход, вероятно, удалял где-то около 80% оставшихся элементов.

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

Answer 2

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

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

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

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

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

Answer 5

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