Вставка в векторах C++ не так проста, как кажется на первый взгляд. Разберем все нюансы std::vector::insert() для эффективного использования в коде.
vector::insert()
Начнем с основного синтаксиса, различают такие разновидности метода insert():
#include <vector>
std::vector<int> numbers = {1, 2, 3, 5};
// Вставляется один элемент
auto it1 = numbers.insert(numbers.begin() + 3, 4);
// «numbers» теперь такой: {1, 2, 3, 4, 5}
// Вставляется несколько копий
auto it2 = numbers.insert(numbers.begin(), 3, 0);
// «numbers» теперь такой: {0, 0, 0, 1, 2, 3, 4, 5}
// Вставляется диапазон из другого контейнера
std::vector<int> other = {-2, -1};
auto it3 = numbers.insert(numbers.begin(), other.begin(), other.end());
// «numbers» теперь такой: {-2, -1, 0, 0, 0, 1, 2, 3, 4, 5}
Возвращаемые значения
В методе insert() возвращается итератор, которым указывается на первый вставленный элемент. Особенно кстати это при объединении операций:
std::vector<int> vec = {1, 3, 4};
auto it = vec.insert(vec.begin() + 1, 2);
// Теперь используется возвращенный итератор
*it = 5; // Только что вставленный «2» заменяется на «5»
Реальный пример: создание планировщика задач
Вот практический пример, где выгодно проявляется векторная вставка, это реализация планировщика приоритетных задач:
#include <string>
#include <algorithm>
struct Task {
std::string name;
int priority;
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
class TaskScheduler {
std::vector<Task> tasks;
public:
void add_task(const Task& task) {
// Находится правильная позиция для вставки, исходя из приоритета
auto pos = std::lower_bound(tasks.begin(), tasks.end(), task);
tasks.insert(pos, task);
}
void display_tasks() const {
for (const auto& task : tasks) {
std::cout << task.priority << ": " << task.name << '\n';
}
}
};
// Пример использования
int main() {
TaskScheduler scheduler;
scheduler.add_task({"Send email", 2});
scheduler.add_task({"Fix bug", 1});
scheduler.add_task({"Deploy app", 3});
scheduler.display_tasks();
}
Последствия для производительности
Вставка в векторе не бесплатна, вот что происходит под капотом:
std::vector<int> vec = {1, 2, 3, 4, 5};
// При этом требуется перемещение всех элементов после позиции «1»
vec.insert(vec.begin() + 1, 10);
// Это эффективнее: вставка в конец
vec.insert(vec.end(), 20);
// Вставка нескольких элементов чревата перераспределением
vec.insert(vec.begin(), 3, 0); // Добавляется три ноля в начало
Чтобы минимизировать влияние на производительность, заранее резервируется место:
std::vector<int> efficient_insert() {
std::vector<int> vec;
vec.reserve(1000); // Перераспределения предотвращаются
for (int i = 0; i < 1000; i++) {
if (i % 2 == 0) {
vec.insert(vec.begin(), i); // Элементы по-прежнему перемещаются, но без перераспределений
}
}
return vec;
}
Insert против Emplace
Иногда emplace() предпочтительнее, чем insert():
struct CustomType {
std::string str;
int num;
CustomType(std::string s, int n) : str(std::move(s)), num(n) {}
};
std::vector<CustomType> vec;
// Используется «insert», и создается временный объект
vec.insert(vec.begin(), CustomType("test", 42));
// Используется «emplace», и объект конструируется на месте
vec.emplace(vec.begin(), "test", 42);
Инвалидация итератора
Типичная ошибка — использование инвалидированных итераторов после вставки:
std::vector<int> vec = {1, 2, 3};
auto it = vec.begin() + 1;
// Не делайте этого:
vec.insert(vec.begin(), 0); // Инвалидируется «it»
*it = 5; // Неопределенное поведение
// Делайте так:
auto it2 = vec.begin() + 1;
it2 = vec.insert(vec.begin(), 0); // Получается новый, валидный итератор
it2++; // Переход к исходной позиции
*it2 = 5; // Безопасно
Практический пример: создание буфера текстового редактора
Вот как векторная вставка используется в буфере простого текстового редактора:
class TextBuffer {
std::vector<char> buffer;
size_t cursor_position = 0;
public:
void insert_text(const std::string& text) {
if (cursor_position > buffer.size()) {
return; // Недопустимая позиция
}
// Во избежание многочисленных перераспределений резервируется место
buffer.reserve(buffer.size() + text.length());
// В позицию курсора вставляется текст
auto it = buffer.begin() + cursor_position;
it = buffer.insert(it, text.begin(), text.end());
// Позиция курсора обновляется
cursor_position += text.length();
}
void delete_range(size_t start, size_t end) {
if (start >= buffer.size() || end > buffer.size() || start > end) {
return;
}
auto start_it = buffer.begin() + start;
auto end_it = buffer.begin() + end;
buffer.erase(start_it, end_it);
// При необходимости курсор обновляется
if (cursor_position > start) {
cursor_position = start;
}
}
std::string get_text() const {
return std::string(buffer.begin(), buffer.end());
}
};
Типичные ошибки и как их избежать
- Не проверяется выделенная память:
std::vector<int> vec = {1, 2, 3};
// Плохо: чревато многочисленными перераспределениями
for (int i = 0; i < 1000; i++) {
vec.insert(vec.begin(), i);
}
// Хорошо: предварительно резервируется место
vec.reserve(1000 + vec.size());
for (int i = 0; i < 1000; i++) {
vec.insert(vec.begin(), i);
}
2. Игнорируются возвращаемые значения:
std::vector<int> vec = {1, 2, 3};
auto it = vec.begin() + 1;
// Плохо: итератор инвалидируется
vec.insert(vec.begin(), 0);
*it = 5;
// Хорошо: используется возвращенный итератор
it = vec.insert(vec.begin(), 0);
++it; // Переход в нужную позицию
*it = 5;
Помните, что при больших наборах данных или частых операциях векторная вставка обходится недешево. Если внутри контейнера выполняется много вставок, воспользуйтесь альтернативными структурами данных вроде std::list или std::deque.
Читайте также:
- C++: подробное руководство по циклам for с векторами
- C++: подробное руководство по размерам векторов
- Как выводятся векторы на C++
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: Vector Insert in C++: A Complete Guide
