Является ли вставка в конце эквивалентно std :: copy ()?
Рассмотрим следующие два способа добавления элементов в вектор
std::vector<int> vi1(10,42), vi2;
vi2.insert(vi2.end(),vi1.begin(),vi1.end());
<OR>
std::copy(vi1.begin(),vi1.end(),std::back_inserter(vi2));
std::copy версия выглядит чище, и мне не нужно печатать vi2 дважды. Но так как это универсальный алгоритм, в то время как вставка является функцией-членом, может insert работать лучше, чем std::copy или это делает то же самое?
Я могу сравнять себя, но я должен сделать это для каждого вектора для каждого типа шаблона. Кто-нибудь уже сделал?
Решение
Есть некоторые тонкие различия. В первом случае (std::vector<>::insert) вы даете диапазон контейнеру, чтобы он мог рассчитать расстояние и выполнить один распределитель для увеличения до конечного требуемого размера. Во втором случае (std::copy) эта информация не присутствует непосредственно в интерфейсе, и она может потенциально вызвать многократное перераспределение буфера.
Обратите внимание, что даже если требуется несколько перераспределений, амортизированная стоимость вставки должна оставаться постоянной, поэтому это не означает асимптотического изменения стоимости, но может иметь значение. Также обратите внимание, что особенно умная реализация библиотеки имеет всю необходимую информацию, чтобы сделать вторую версию более эффективной, специализируя поведение std::copy специально обрабатывать итераторы вставки назад (хотя я не проверял, делает ли это какая-либо реализация).
Другие решения
Вы думаете, что vector::insert может быть в состоянии оптимизировать случай, когда он вставляет несколько элементов одновременно, но это сложнее, чем кажется. Что, если итераторы, например, являются выходными итераторами — невозможно заранее знать, сколько вставок вы сделаете. Вполне вероятно, что код для insert просто делает несколько push_backтак же, как back_inserter,
vector::insert вероятно, будет работать лучше в большинстве случаев на большинстве основных реализаций стандартной библиотеки C ++. Причина в том, что vector Объект обладает внутренними знаниями о выделенном в настоящее время буфере памяти и может предварительно выделить достаточно памяти для выполнения всей вставки, поскольку число элементов может быть заранее вычислено с помощью итераторов с произвольным доступом. Тем не мение, std::copy вместе с std::back_inserter будет продолжать звонить vector::push_back, который может вызвать несколько распределений.
GNU реализация std::vector::insert в libstdc ++, например, заранее выделяет буфер, если категория итератора RandomAccessIterator, С входными итераторами, vector::insert может быть эквивалентно std::copyпотому что вы не можете определить количество элементов заранее.
Это не эквивалентно std::copy, Это эквивалентно push_back (в некотором смысле).
Да, std::back_inserter делает то же самое, что вы используете с std::copy который можно вставить спереди также, если вы используете std:front_inserter (хотя ты не могу использовать его с std::vector). Он может вставить в указанный итератор также, если вы используете std::inserter вместо. Итак, вы видите, std::copy делает вещи на основе того, что вы передаете в качестве третьего аргумента.
Теперь вернемся к сути вопроса. Я думаю, что вы должны использовать insert, так как он может работать лучше, потому что он может обнаружить число элементов, которые он собирается вставить, поэтому он может выделить столько памяти одновременно (при необходимости). В вашем случае это, вероятно, будет работать лучше, потому что v1 является std::vector что означает, что это легко вычислить число элементов в O (1) времени.