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 или оба должны быть одинаково дешевыми/дорогостоящими?
Эффективность получения точки вставки не будет иметь никакого значения - это будет затмевать неэффективность постоянного перетасовки существующих данных каждый раз, когда вы вставляете.
Используйте std:: deque для этого, для чего он предназначен.
Если одна из критических потребностей вашей программы вставить элементы в начале контейнера: тогда вы должны использовать std::deque, а не std::vector. std::vector хорош только при вставке элементов в конец.
В С++ 11 были введены другие контейнеры. Я должен начать поиск обновленного графика с этими новыми контейнерами и вставить его здесь.
Старый поток, но он появился на рабочем столе в качестве первого результата поиска для запроса Google.
Существует одна альтернатива использованию детекса, который стоит рассмотреть:
std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
foo.push_back(T());
std::reverse( foo.begin(), foo.end() );
Вы по-прежнему используете вектор, который значительно более развит, чем deque для производительности. Кроме того, свопы (которые используются в обратном порядке) довольно эффективны. С другой стороны, сложность, хотя и линейная, увеличивается на 50%.
Как всегда, измерьте, прежде чем решать, что делать.
Если вы ищете эффективный для вычислений способ вставки спереди, то вы, вероятно, захотите использовать deque вместо вектора.
Скорее всего, deque является подходящим решением, предложенным другими. Но только для полноты, предположим, что вам нужно сделать эту переднюю вставку только один раз, что в другом месте программы вам не нужно делать другие операции спереди, а в противном случае vector предоставляет необходимый вам интерфейс. Если все они верны, вы можете добавить элементы с очень эффективным push_back, а затем reverse вектором, чтобы все было в порядке. Это будет иметь линейную сложность, а не полиномиальную, как при вставлении спереди.
Когда вы используете вектор, вы обычно знаете фактическое количество элементов, которое оно будет иметь. В этом случае резервирование необходимого количества элементов (100000 в том случае, если вы показываете) и их заполнение с помощью оператора [] является самым быстрым способом. Если вам действительно нужна эффективная вставка спереди, вы можете использовать deque или list, в зависимости от ваших алгоритмов.
Вы также можете рассмотреть возможность инвертирования логики вашего алгоритма и вставки в конце, что обычно быстрее для векторов.
Я думаю, вы должны изменить тип своего контейнера, если вы действительно хотите вставить данные в начале. Это причина, почему в векторе нет функции-члена push_front().
Интуитивно я согласен с @Happy Green Kid Naps и провел небольшой тест, показывающий, что для небольших размеров (1 & lt; & lt; 10 элементов простого типа данных) это не имеет значения. Однако для контейнеров большего размера (1 & lt; & lt; 20) std::deque, по-видимому, имеет более высокую производительность, чем реверсирование std::vector. Итак, бенчмарк, прежде чем решить. Другим фактором может быть тип элемента контейнера.
Результаты: