С ++ vector's insert и push_back разница

79

Я хочу знать , что есть разница (s) между vector«s push_backи insertфункциями.

Есть ли структурные различия?

Есть ли действительно большая разница в производительности?

тоттен
источник
4
insertможет делать это где угодно и включает в себя другие вещи, например поддержку диапазонов. push_backудобнее добавлять в конец.
Крис

Ответы:

93

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

Адам Снайдер
источник
9
С другой стороны, вставка в конце должна быть такой же эффективной, как push_back.
Matthieu M.
18
Что ж, почти так же эффективно - код должен определять, что на insertсамом деле находится в end(), поэтому будет больше ветвей, insertчем в push_back, если компилятор не сможет понять, что они на самом деле не нужны.
Yakk - Adam Nevraumont
5
@TomerW Люди выбирают C или C ++, чтобы иметь возможность выполнять sqeeze каждый отдельный машинный цикл, который они могут, для повышения производительности, вплоть до того, что иногда пишут прямо в ASM ... каждое «если» имеет значение, это не java ..
Cesar
1
@Cesar Это не то, почему вы выбираете свой язык ... cpp может быть быстрее, чем c, и наоборот ... черт возьми, в некоторых случаях даже java может быть быстрее, чем c для его оптимизаций во время выполнения.
Tomer W
@TomerW хо, так почему? просветите меня пожалуйста.
Cesar
32

Функции имеют разные цели. vector::insertпозволяет вставить объект в указанную позицию в vector, а vector::push_backпросто приклеить объект к концу. См. Следующий пример:

using namespace std;
vector<int> v = {1, 3, 4};
v.insert(next(begin(v)), 2);
v.push_back(5);
// v now contains {1, 2, 3, 4, 5}

Вы можете использовать insertдля выполнения той же работы, что и push_backс v.insert(v.end(), value).

Джозеф Мэнсфилд
источник
9

Помимо того, что это push_back(x)делает то же самое insert(x, end())(возможно, с немного большей производительностью), есть несколько важных вещей, которые нужно знать об этих функциях:

  1. push_backсуществует только в BackInsertionSequenceконтейнерах - поэтому, например, он не существует в set. Это невозможно, потому push_back()что это дает вам возможность всегда добавлять в конце.
  2. Некоторые контейнеры также могут удовлетворить, FrontInsertionSequenceи они есть push_front. Это удовлетворяет deque, но не удовлетворяет vector.
  3. Это insert(x, ITERATOR)от InsertionSequence, которое является общим для setи vector. Таким образом, вы можете использовать либо, setлибо vectorкак цель для нескольких вставок. Однако setимеет дополнительно insert(x), что делает практически то же самое (эта первая вставка setозначает только ускорение поиска подходящего места за счет запуска с другого итератора - функция в данном случае не используется).

Обратите внимание на последний случай: если вы собираетесь добавлять элементы в цикл, то по сути дела container.push_back(x)и container.insert(x, container.end())будут делать то же самое. Однако это не будет правдой, если вы container.end()сначала получите это, а затем используете его во всем цикле.

Например, вы можете рискнуть следующим кодом:

auto pe = v.end();
for (auto& s: a)
    v.insert(pe, v);

Это эффективно скопирует все aв vвектор в обратном порядке , и только если вам повезет, и вы не перераспределите вектор для расширения (вы можете предотвратить это, позвонив reserve()сначала); если вам не повезет, вы получите так называемое UndefinedBehavior (tm). Теоретически это недопустимо, поскольку итераторы вектора считаются недействительными каждый раз, когда добавляется новый элемент.

Если вы сделаете это так:

copy(a.begin(), a.end(), back_inserter(v);

он будет копироваться aв конце vв исходном порядке, и это не несет риска аннулирования итератора.

[РЕДАКТИРОВАТЬ] Раньше я заставлял этот код выглядеть так, и это было ошибкой, потому что inserterфактически поддерживает действительность и продвижение итератора:

copy(a.begin(), a.end(), inserter(v, v.end());

Таким образом, этот код также добавит все элементы в исходном порядке без какого-либо риска.

Ethouris
источник
Ваши замечания о том, что std :: insertter "опасен" для векторных контейнеров, неверны. Фактически, он призван устранить эти риски. Ни обратного порядка, ни неопределенного поведения. См., Например, fluentcpp.com/2017/10/06/stl-inserter-iterators-work для разбивки.
downhillFromHere
Вы правы. Я просто хотел сделать код коротким, а не расширять его до обширного ручного цикла, так что на самом деле это неверно, потому что inserterподдерживает продвижение и достоверность итератора. Придется отредактировать пост :)
Ethouris