#c #stl #vector #iterator
#c #stl #вектор #итератор
Вопрос:
Я пишу небольшой фрагмент кода, где мне нужно будет вставлять значения в вектор C STL в определенном месте в зависимости от значений в векторных элементах. Для достижения этой цели я использую insert() функцию. Я понимаю, что когда я хочу добавить новый элемент в конец вектора, я мог бы просто использовать push_back() . Но чтобы мой код выглядел красиво, я хотел бы использовать исключительно insert() , который принимает в качестве входных данных итератор, указывающий на элемент после желаемой точки вставки, и значение, которое нужно вставить. Если значение итератора, переданное в качестве аргумента, равно v.end() , где v находится мой вектор, будет ли это работать так же, как push_back() ?
Большое спасибо!
Комментарии:
1. Если вы часто используете insert в векторе, возможно, вы используете неправильную структуру данных. Рассмотрим (например) использование deque. Конечно, если вектор маленький, проблем не будет.
2. @Nick: Да, так и будет. Простой эксперимент мог бы подсказать вам это.
3. @Space Я не понимаю, как эксперимент мог ему это сказать. Если бы это было недопустимо, он получил бы UB, и в этом случае его программа вполне могла бы работать.
4. @unapersson: Удаление помогло бы только в том случае, если большинство вставок находится в начале или в конце последовательности. Если это только в конце последовательности, вектор подойдет так же хорошо.
5. @unapersson Для вставок в начале лучше использовать deque. Это почти наверняка хуже (оба линейные, но у deque будет значительно больший постоянный коэффициент) для вставок в любом месте, кроме начала или конца. И стоимость вставки в середину вектора часто завышалась, по крайней мере, если типы в векторе являются типами POD. (Реальная «стоимость» вставки часто заключается в том, что она делает недействительными итераторы. Только
std::listпозволяет избежать этого, ноstd::listв противном случае это чрезвычайно дорого.)
Ответ №1:
a.push_back(x) определено, чтобы иметь семантику, идентичную (void)a.insert(a.end(),x) для контейнеров последовательностей, которые его поддерживают.
Смотрите таблицу 68 в ISO / IEC 14882:2003 23.1.1/12 [lib.sequence.reqmts].
Что касается времени выполнения vector.push_back(x) vs vector.insert(vector.end(), x) , рассмотрим выделенную часть:
В таблице 68 перечислены операции последовательности, которые предусмотрены для некоторых типов последовательных контейнеров, но не для других. Реализация должна предоставлять эти операции для всех типов контейнеров, показанных в столбце ‘контейнер’, и должна реализовывать их таким образом, чтобы они занимали амортизированное постоянное время.
Комментарии:
1. Быстрый вопрос, с точки зрения производительности, интересно, работает ли pusk_back быстрее? Я тестировал что-то, показывающее, что вставка происходит довольно медленно. Я просто хотел убедиться… Спасибо
2. push_back() не возвращает итератор вновь вставленного элемента. std::list<T>::end() вернет мертвый итератор.
3. Ответ было бы лучше, если бы вы включили раздел стандарта, на который вы ссылаетесь
4. @JonMcClung: Гм, но ответ уже включает эту информацию?
5. Я имел в виду как цитату. Я не знаю, как найти случайный раздел стандарта по маркеру главы или что бы вы ни указали.
Ответ №2:
Есть небольшая разница в том, push_back возвращает void ли insert возврат iterator к только что вставленному элементу.
Кстати, есть другой способ проверить, делают ли они то же самое: скомпилируйте следующие коды
int main()
{
std::vector<int const> v;
v.push_back(0);
return 0;
}
компилятор напечатает много раздражающих сообщений, просто прочитайте, и вы найдете push_back вызовы insert (если нет, попробуйте скомпилировать v.insert(v.end(), 0) , чтобы увидеть, вызывают ли они ту же функцию вставки) в конце.