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

Question

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

Является объявлением функции оператора вставки класса 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 или оба должны быть одинаково дешевыми / дорогостоящими?

Answer 1

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

Другие контейнеры были введены в C ++ 11. Я должен начать искать обновленный график с этими новыми контейнерами и вставить его сюда.

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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