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 — потенциально продолжительная операция.

Добавление элементов в контейнеры vector, string или 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!");

Контейнеры vector, deque и string допускают вставку в любую позицию, но это может потребовать больше времени.

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

Следующие аргументы функции 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(), получающие количество или диапазон, возвращают итератор на первый вставленный элемент. (В предыдущих версиях библиотеки эти функции возвращали тип void.) Если диапазон пуст, никакие элементы не вставляются, а функция возвращает свой первый параметр.

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

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

list<string> lst;

auto iter = lst.begin();

while (cin >> word)

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

Важно понимать, почему именно цикл, подобный этому, эквивалентен вызову функции push_front().

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

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

Новый стандарт вводит три новых функции-члена — emplace_front(), emplace() и emplace_back(), которые создают элементы, а не копируют. Они соответствуют функциям push_front(), insert() и push_back(), позволяющим помещать элемент в начало контейнера, перед указанной позицией или в конец контейнера соответственно.

Когда происходит вызов функции-члена 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);

Функция emplace() создает элементы контейнера. Ее аргументы должны соответствовать конструктору типа элемента.

Упражнения раздела 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);