9.3.1. Добавление элементов в последовательный контейнер

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

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

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

Таблица 9.5. Функции, добавляющие элементы в последовательный контейнер

Применение функции push_back()

В разделе 3.3.2 упоминалось, что функция push_back() добавляет элемент в конец вектора. Кроме контейнеров array и forward_list, каждый последовательный контейнер (включая string) поддерживает функцию push_back().

Цикл следующего примера читает по одной строке за раз в переменную word:

// читать слова со стандартного устройства ввода и помещать

// их в конец контейнера

string word;

while (cin >> word)

 container.push_back(word);

Вызов функции push_back() создает новый элемент в конце контейнера container, увеличивая его размер на 1. Значением этого элемента будет копия значения переменной word. Контейнер может иметь любой тип: list, vector или deque.

Поскольку класс string — это только контейнер символов, функцию push_back() можно использовать для добавления символов в ее конец:

void pluralize(size_t cnt, string &word) {

 if (cnt > 1)

  word.push_back('s'); // то же, что и word += 's'

}

Ключевая концепция. Элементы контейнера содержат копии значений

Когда объект используется для инициализации контейнера или вставки в него, в контейнер помещается копия значения объекта, а не сам объект. Подобно передаче объекта в не ссылочном параметре (см. раздел 6.2.1), между элементом в контейнере и объектом, значение которого было использовано для его инициализации, нет никакой связи. Последующие изменения элемента в контейнере никак не влияют на исходный объект, и наоборот.

Применение функции push_front()

Кроме функции push_back(), контейнеры list, forward_list и deque предоставляют аналогичную функцию push_front(). Она вставляет новый элемент в начало контейнера:

list<int> ilist;

// добавить элементы в начало ilist

for (size_t ix = 0; ix != 4; ++ix)

 ilist.push_front(ix);

Этот цикл добавляет элементы 0, 1, 2, 3 в начало списка ilist. Каждый элемент вставляется в новое начало списка, т.е. когда добавляется 1, она оказывается перед 0, 2 — перед 1 и так далее. Таким образом, добавленные в цикле элементы расположены в обратном порядке. После этого цикла список ilist содержит такую последовательность: 3, 2, 1, 0.

Обратите внимание: контейнер deque, предоставляющий подобно контейнеру vector быстрый произвольный доступ к своим элементам, обладает функцией-членом push_front(), а контейнер vector — нет. Контейнер deque гарантирует постоянное время вставки и удаления элементов в начало и в конец контейнера. Как и у контейнера vector, вставка элементов иначе как в начало или в конец контейнера deque — потенциально продолжительная операция.

Добавление элементов в указанную точку контейнера

Функции push_back() и push_front() предоставляют весьма удобный способ добавления одиночных элементов в конец или в начало последовательного контейнера. Функция insert() обладает более общим характером и позволяет вставлять любое количество элементов в любую указанную позицию контейнера. Ее поддерживают контейнеры vector, deque, list и string, а контейнер forward_list предоставляет собственные специализированные версии этих функций-членов, которые рассматриваются в разделе 9.3.4.

Каждая из функций вставки получает в качестве первого аргумента итератор, указывающий позицию помещения элемента (элементов) в контейнере. Он может указывать на любую позицию, включая следующий элемент после конца контейнера. Поскольку итератор может указывать на несуществующий элемент после конца контейнера, а также потому, что полезно иметь способ вставки элементов в начало контейнера, элемент (элементы) вставляются перед позицией, обозначенной итератором. Рассмотрим следующий оператор:

slist.insert(iter, "Hello!"); // вставить "Hello!" прямо перед iter

Он вставляет строку со значением "Hello" непосредственно перед элементом, обозначенным итератором iter.

Даже при том, что у некоторых контейнеров нет функции push_front(), к функции insert() это не относится. Функция insert() позволяет вставлять элементы в начало контейнера, не заботясь о наличии у контейнера функции push_front():

vector<string> svec;

list<string> slist;

// эквивалент вызова slist.push_front("Hello!");

slist.insert(slist.begin(), "Hello!");

// вектор не имеет функции push_front(),

// но вставка перед begin() возможна

// внимание: вставка возможна везде, но вставка в конец вектора может

// потребовать больше времени

svec.insert(svec.begin(), "Hello!");

Вставка диапазона элементов

Следующие аргументы функции insert(), расположенные после начального итератора, похожи на аргументы конструкторов контейнеров. Версия, получающая количество элементов и значение, добавляет определенное количество одинаковых элементов перед указанной позицией:

svec.insert(svec.end(), 10, "Anna");

Этот код вставляет 10 элементов в конец вектора svec и инициализирует каждый из них строкой "Anna".

Данная версия функции insert() получает пару итераторов или список инициализации для вставки элементов из данного диапазона перед указанной позицией:

vector<string> v = {"quasi", "simba", "frollo", "scar"};

// вставить два последних элемента вектора v в начало slist

slist.insert(slist.begin(), v.end() - 2, v.end());

slist.insert(slist.end(), {"these", "words", "will",

                           "go", "at", "the", "end"});

// ошибка времени выполнения:

// обозначающие копируемый диапазон итераторы

// не должны принадлежать тому же контейнеру, который изменяется

slist.insert(slist.begin(), slist.begin(), slist.end());

При передаче пары итераторов они не могут относиться к тому же контейнеру, к которому добавляются элементы.

Применение возвращаемого значения функции insert()

Значение, возвращенное функцией insert(), можно использовать для многократной вставки элементов в определенной позиции контейнера:

list<string> lst;

auto iter = lst.begin();

while (cin >> word)

 iter = lst.insert(iter, word); // то же, что и вызов push_front()

Перед циклом итератор iter инициализируется возвращаемым значением функции lst.begin(). Первый вызов функции insert() получает только что прочитанную строку и помещает ее перед элементом, обозначенным итератором iter. Значение, возвращенное функцией insert(), является итератором на этот новый элемент. Присвоим этот итератор итератору iter и повторим цикл, читая другое слово. Пока есть слова для вставки, каждая итерация цикла while вставляет новый элемент перед позицией iter и снова присваивает ему позицию недавно вставленного элемента. Этот (новый) элемент является первым. Таким образом, каждая итерация вставляет элемент перед первым элементом в списке.

Применение функций emplace()

Когда происходит вызов функции-члена insert() или push(), им передается объект типа элемента для копирования в контейнер. Когда происходит вызов функции emplace(), ее аргументы передаются конструктору типа элемента, который создает элемент непосредственно в области, контролируемой контейнером. Предположим, например, что контейнер с содержит элементы типа Sales_data (см. раздел 7.1.4):

// создает объект класса Sales_data в конце контейнера с

// использует конструктор класса Sales_data с тремя аргументами

с.emplace_back("978-05903534 03", 25, 15.99);

// ошибка: нет версии функции push_back(), получающей три аргумента

с.push_back("978-0590353403", 25, 15.99);

// ok: создается временный объект класса Sales_data для передачи

// функции push_back()

c.push_back(Sales_data("978-0590353403", 25, 15.99));

Вызов функции emplace_back() и второй вызов функции push_back() создают новые объекты класса Sales_data. При вызове функции emplace_back() этот объект создается непосредственно в области, контролируемой контейнером. Вызов функции push_back() создает локальный временный объект, который помещается в контейнер.

Аргументы функции emplace() зависят от типа элемента, они должны соответствовать конструктору типа элемента:

// iter указывает на элемент класса Sales_data контейнера с

с.emplace_back(); // использует стандартный конструктор

                  // класса Sales_data

с.emplace(iter, "999-999999999"); // используется Sales_data(string)

// использует конструктор класса Sales_data, получающий ISBN,

// количество и цену

с.emplace_front("978-0590353403", 25, 15.99);

Упражнения раздела 9.3.1

Упражнение 9.18. Напишите программу чтения последовательности строк со стандартного устройства ввода в контейнер deque. Для записи элементов в контейнер deque используйте итераторы и цикл.

Упражнение 9.19. Перепишите программу из предыдущего упражнения, чтобы использовался контейнер list. Перечислите необходимые изменения.

Упражнение 9.20. Напишите программу, копирующую элементы списка list<int> в две двухсторонние очереди, причем нечетные элементы должны копироваться в один контейнер deque, а четные в другой.

Упражнение 9.21. Объясните, как цикл из пункта «Применение возвращаемого значения функции insert()», использующий возвращаемое значение функции insert() и добавляющий элементы в список, работал бы с вектором вместо списка.

Упражнение 9.22. С учетом того, что iv является вектором целых чисел, что не так со следующей программой? Как ее можно исправить?

vector<int>::iterator iter = iv.begin(),

mid = iv.begin() + iv.size()/2;

while (iter != mid)

 if (*iter == some_val)

  iv.insert(iter, 2 * some_val);