Удаляет ли элемент в середине std::vector еще дорогой с подвижными типами?

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

С С++ 11, std::vector будет вместо этого перемещать все элементы вниз, что должно быть очень быстрым (хотя бы по отношению к копии), по крайней мере, я так думаю. Он по-прежнему будет линейным во времени, конечно, но в целом он должен быть быстрее старой версии.

Будет ли это так? Мне больше не нужно беспокоиться об удалении какого-либо объекта в середине?

Ответ 1

Если принять во внимание то, что стандарт использует для стоимости, он будет таким же дорогостоящим. В стандарте указаны затраты с точки зрения операций, выполняемых по содержащемуся типу, и что количество операций остается одинаковым, просто каждый из них будет быстрее.

В качестве примера рассмотрим в С++ 03 стоимость вставки элемента в середину vector<string>. Стандартные вызовы: O(N), где N - размер вектора, но фактическая стоимость O(N * M), где M - размер строк. Причиной игнорирования M при анализе стоимости операций в контейнерах является то, что он зависит от содержащегося элемента. Эта стоимость в С++ 0x с подвижным типом будет O(N) (строки могут быть перемещены в новые позиции), но объявленная сложность будет O(N) в обоих случаях.

Для простого встречного примера, если вы считаете, что вставка в середине вектора является дорогостоящей операцией в С++ 03, и вы считаете std::vector<int>, тогда вставка в середине вектора в С++ 0x так же дорого, в этом случае ускорения не происходит.

Также обратите внимание, что любое потенциальное улучшение будет зависеть от ваших перемещаемых объектов (которых они не должны быть) и что некоторые из существующих реализаций STL уже оптимизированы аналогичным образом (без поддержки языков), для Например, реализация Dinkumware (я думаю, что это была одна) имеет некоторые оптимизации, с помощью которых при возрастании std::vector<std::vector<T> > создается новое хранилище и инициализируется пустым вектором (у которого нет выделенной памяти, поэтому стоимость минимальна), а затем swap векторы в старой и новой выделенных областях, эффективно реализуя семантику перемещения.

Ответ 2

Это зависит от того, что в векторе. Если это POD или указатель, я не могу представить, чтобы это имело какое-либо значение. Если это экземпляры класса, которые тяжелы для копирования, но могут быть перемещены очень быстро, я бы ожидал ускорения с С++ 0x.

Однако, я думаю, что если удаление элементов из середины std::vectors является узким местом в вашем коде, С++ 0x, вероятно, не является правильным решением. Рассмотрим структуры данных, которые лучше обрабатывают такие случаи, или std::iter_swap plus std::vector::pop_back, если порядок элементов не имеет значения.

Ответ 3

Эффективно, в подавляющем большинстве случаев, он будет значительно быстрее двигаться, чем копировать. Любой тип, который имеет информацию, хранящуюся по ссылке, которую в противном случае нужно было бы скопировать, может предотвратить копирование, например, почти все контейнеры, интеллектуальные указатели и т.д. И любой класс, включающий эти типы.

Конечно, это по-прежнему линейное время, поэтому, если у вас есть миллион ints, это не будет идти быстрее. Однако перемещение таких вещей, как контейнеры и интеллектуальные указатели, может быть на несколько порядков быстрее, чем копирование их.

Ответ 4

Я все еще новичок в С++ 0x, но я не могу понять, как вы получите полезные ускорения здесь, которые присущи vector.

Все должно быть похоже на ваш тип элемента: я не могу себе представить, что вы получите ускорение, если объекты вашего типа элемента быстрее перемещаются, чем копировать.

Ответ 5

Прежде всего, нужно решить, нужен ли вам вектор или список? Если вам не нужен доступ на основе индексов к структуре данных, список будет хорош, так как ваши удаления происходят в середине контейнера. Также вы должны рассмотреть другие варианты, такие как деревья, чтобы выбрать лучшее для вас. Это может не сильно повлиять на вашу производительность, но все же только ради обмена информацией, есть вероятность, что содержимое в списке будет распространено на нескольких файлах страниц, и, следовательно, производительность будет скомпрометирована при использовании большого количества данных.

Rvalue reference and move constructor может улучшить производительность контейнеров. Он может избежать нескольких незавершенных операций копирования и т.д.