Вставка в вектор спереди

iterator insert ( iterator position, const T& x );

Является объявлением функции оператора insert класса std::Vector.

Этот возвращаемый тип функции является итератором, указывающим на вставленный элемент. Мой вопрос заключается в том, что с учетом этого типа возврата наиболее эффективный способ (это часть более крупной программы, в которой я запускаю, где скорость имеет смысл, поэтому я ищу наиболее эффективный для вычисления способ) вставки в начале. Это следующее?

//Code 1
vector<int> intvector;
vector<int>::iterator it;
it = myvector.begin();
for(int i = 1; i <= 100000; i++){
    it = intvector.insert(it,i);
}

Или

//Code 2
vector<int> intvector;
for(int i = 1; i <= 100000; i++){
    intvector.insert(intvector.begin(),i);
}

По существу, в коде 2 есть параметр,

intvector.begin()

"Достойно" оценить вычислительно по сравнению с использованием возвращенного итератора в коде 1 или оба должны быть одинаково дешевыми/дорогостоящими?

Ответ 1

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

Используйте std:: deque для этого, для чего он предназначен.

Ответ 2

Если одна из критических потребностей вашей программы вставить элементы в начале контейнера: тогда вы должны использовать std::deque, а не std::vector. std::vector хорош только при вставке элементов в конец.

В С++ 11 были введены другие контейнеры. Я должен начать поиск обновленного графика с этими новыми контейнерами и вставить его здесь.

Ответ 3

Старый поток, но он появился на рабочем столе в качестве первого результата поиска для запроса Google.

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

std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
  foo.push_back(T());
std::reverse( foo.begin(), foo.end() );

Вы по-прежнему используете вектор, который значительно более развит, чем deque для производительности. Кроме того, свопы (которые используются в обратном порядке) довольно эффективны. С другой стороны, сложность, хотя и линейная, увеличивается на 50%.

Как всегда, измерьте, прежде чем решать, что делать.

Ответ 4

Если вы ищете эффективный для вычислений способ вставки спереди, то вы, вероятно, захотите использовать deque вместо вектора.

Ответ 5

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

Ответ 6

Когда вы используете вектор, вы обычно знаете фактическое количество элементов, которое оно будет иметь. В этом случае резервирование необходимого количества элементов (100000 в том случае, если вы показываете) и их заполнение с помощью оператора [] является самым быстрым способом. Если вам действительно нужна эффективная вставка спереди, вы можете использовать deque или list, в зависимости от ваших алгоритмов.

Вы также можете рассмотреть возможность инвертирования логики вашего алгоритма и вставки в конце, что обычно быстрее для векторов.

Ответ 7

Я думаю, вы должны изменить тип своего контейнера, если вы действительно хотите вставить данные в начале. Это причина, почему в векторе нет функции-члена push_front().

Ответ 8

Интуитивно я согласен с @Happy Green Kid Naps и провел небольшой тест, показывающий, что для небольших размеров (1 & lt; & lt; 10 элементов простого типа данных) это не имеет значения. Однако для контейнеров большего размера (1 & lt; & lt; 20) std::deque, по-видимому, имеет более высокую производительность, чем реверсирование std::vector. Итак, бенчмарк, прежде чем решить. Другим фактором может быть тип элемента контейнера.

Тест 1: push_front (a) 1 & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; 20 uint64_t в std::deque
Тест 2: push_back (a) 1 & lt; & lt; & lt; & lt; & lt; & lt; & lt; 20 uint64_t в std::vector, за которым следует std::reverse

Результаты:

Тест 1 - deque (a) 19 мкс
Тест 2 - вектор (а) 19 мкс
Тест 1 - deque (b) 6339 мкс
Тест 2 - вектор (б) 10588 мкс