Является ли удаление элемента в середине std :: vector все еще дорогостоящим с подвижными типами? - PullRequest
10 голосов
/ 02 июля 2011

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

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

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

Ответы [ 5 ]

15 голосов
/ 02 июля 2011

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

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

11 голосов
/ 02 июля 2011

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

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

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

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

6 голосов
/ 02 июля 2011

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

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

5 голосов
/ 02 июля 2011

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

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

1 голос
/ 02 июля 2011

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

Rvalue ссылка и конструктор перемещения может улучшить производительность контейнеров.Это может избежать нескольких ненужных операций копирования и т. Д.

...