std::forward_list и std::forward_list::push_back
Я хотел бы использовать std::forward_list
Так как:
Forward list - это контейнер, который поддерживает быструю вставку и удаление элементов из любой точки контейнера.
Но нет *std::forward_list::push_back* реализации.
Есть ли высокопроизводительный способ добавить поддержку для одной или нет причин для этого?
5 ответов
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 почти во всех ситуациях. Лично я никогда не встречал в своем коде ситуацию, в которой связанный список был лучшей структурой данных.
В C++ ваш сбор данных по умолчанию должен быть std::vector, Это дает вам эффективный push_back, если это то, что вам действительно нужно. Технически это не дает вам эффективного удаления и вставки с середины, если вы только посмотрите на абстрактные измерения сложности big-O этой одной операции. В реальном мире, однако, std::vector все еще выигрывает даже для вставки и удаления в середине.
Например, Бьярн Страуструп создал тест на 100000 элементов 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 реализация, и это было достаточно быстро, чтобы быть полезным.
Смысл 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);
Здесь нет push_back потому что список не отслеживает заднюю часть списка, только переднюю.
Вы можете написать обертку вокруг списка, которая поддерживает итератор для последнего элемента и реализует push_back используя либо insert_after или же push_front в зависимости от того, пуст ли список. Это будет довольно сложно, если вы хотите поддерживать более сложные операции (например, sort а также splice_after).
В качестве альтернативы, если вам не нужно push_back чтобы быть быстрым, это просто сделать это за линейное время.
Если память не очень ограничена, лучшим решением является использование list, Это имеет те же характеристики производительности, что и forward_listи является двунаправленным, поддерживающим push_back так же как push_front; стоимость - это дополнительный указатель на элемент.
К сожалению, я не могу добавить комментарий (низкая репутация), но я просто хотел упомянуть, что одним из преимуществ forward_list & list является то, что операции вставки-удаления не делают недействительными итераторы. У меня было приложение, в котором коллекция элементов росла, итерируя и обрабатывая отдельные элементы. Отсутствие аннулирования итератора позволило мне выполнить сканирование сегментов (начало списка как начало сегмента и начало последнего сегмента как конец).