Язык программирования C Пятое издание

• Название: Язык программирования C Пятое издание
• Дата: 15.07.2019
• Размер: 1.85 Mb.
• Имя файла: 620354-www.libfox.ru.pdf
• Тип: Документы; #84130
• страница: 24 из 54

Упражнение 9.3. Каким условиям должны удовлетворять итераторы, обозначающие диапазон?
Упражнение 9.4. Напишите функцию, которая получает два итератора вектора vector<int>
и значение типа int. Организуйте поиск этого значения в диапазоне и возвратите логическое значение (тип bool), указывающее, что значение найдено.
Упражнение 9.5. Перепишите предыдущую программу так, чтобы она возвращала итератор на найденный элемент. Функция должна учитывать случай, когда элемент не найден.
Упражнение 9.6. Что не так со следующей программой? Как ее можно исправить? list<int> lst1;
Page 422/1103

list<int>::iterator iter1 = lst1.begin(), iter2 = lst1.end(); while (iter1 < iter2) /* ... */
9.2.2. Типы-члены классов контейнеров
Класс каждого контейнера определяет несколько типов, представленных в табл. 9.2. Три из них уже использовались: size_type (см. раздел 3.2.2), iterator и const_iterator (см. раздел 3.4.1).
Кроме итераторов уже использовавшихся типов, большинство контейнеров предоставляет реверсивные итераторы (reverse_iterator). Другими словами, реверсивный итератор — это итератор, перебирающий контейнер назад и инвертирующий значение его операторов.
Например, оператор ++ возвращает реверсивный итератор к предыдущему элементу. Более подробная информация о реверсивных итераторах приведена в разделе 10.4.3.
Остальные псевдонимы типов позволяют использовать тип хранящихся в контейнере элементов, даже не зная его конкретно. Если необходим тип элемента, используется тип value_type контейнера. Если необходима ссылка на этот тип, используется член reference или const_reference. Эти связанные с элементами псевдонимы типов весьма полезны в обобщенном программировании, которое рассматривается в главе 16.
Чтобы использовать один из этих типов, следует указать класс, членами которого они являются
// iter имеет тип iterator, определенный классом list<string> list<string>::iterator iter;
// count имеет тип difference_type, определенный классом vector<int> vector<int>::difference_type count;
В этих объявлениях оператор области видимости (см. раздел 1.2) позволяет указать, что используется тип-член iterator класса list<string> и тип-член difference_type, определенный классом vector<int>, соответственно. Упражнения раздела 9.2.2

Упражнение 9.7. Какой тип следует использовать в качестве индекса для вектора целых чисел?
Упражнение 9.8. Какой тип следует использовать для чтения элементов в списке строк?
9.2.3. Функции-члены begin() и end()
Page 423/1103

Функции-члены begin() и end() (см. раздел 3.4.1) возвращают итераторы на первый и следующий после последнего элементы контейнера соответственно. Эти итераторы, как правило, используют при создании диапазона итераторов, охватывающего все элементы контейнера.
Как показано в табл. 9.2, есть несколько версий этих функций: имена которых начинаются с буквы r возвращают реверсивные итераторы (рассматриваются в разделе 10.4.3), а с буквы c
— возвращают константную версию соответствующего итератора: list<string> a = {"Milton", "Shakespeare", "Austen"}; auto it1 = a.begin(); // list<string>::iterator auto it2 = a.rbegin(); // list<string>::reverse_iterato r auto it3 = a.cbegin(); // list<string>::const_iterator auto it4 = a.crbegin();// list<string>::const_reverse_iterator
Функции, имена которых не начинаются с буквы c, перегружены. Таким образом, фактически есть две функции-члена begin(). Одна является константной (см. раздел 7.1.2) и возвращает тип const_iterator контейнера. Вторая не константна и возвращает тип iterator контейнера.
Аналогично для функций rbegin(), end() и rend(). При вызове такой функции-члена для неконстантного объекта используется версия, возвращающая тип iterator. Константная версия итераторов будет получена только при вызове этих функций для константного объекта. Подобно указателям и ссылкам на константу, итератор типа iterator можно преобразовать в соответствующий итератор типа const_iterator, но не наоборот.
Версии этих функций, имена которых не начинаются с буквы с, были введены согласно новому стандарту для обеспечения использования ключевого слова auto с функциями begin()
и end() (см. раздел 2.5.2). Прежде не было никакого иного выхода, кроме как явно указать необходимый тип итератора:
// тип указан явно list<string>::iterator it5 = a.begin(); list<string>::const_iterator it6 = a.begin();
// iterator или const_iterator в зависимости от типа а auto it7 = a.begin(); // const_iterator только если a константа
Page 424/1103

auto it8 = a.cbegin(); // it8 - const_iterator
Когда с функциями begin() или end() используется ключевое слово auto, тип возвращаемого итератора зависит от типа контейнера. То, как предполагается использовать итератор,
несущественно. Версии c позволяют получать итератор типа const_iterator независимо от типа контейнера.
Когда доступ на запись не нужен, используйте версии cbegin() и cend(). Упражнения раздела
9.2.3

Упражнение 9.9. В чем разница между функциями begin() и cbegin()?
Упражнение 9.10. Каковы типы следующих четырех объектов? vector<int> v1; const vector<int> v2; auto it1 = v1.begin(), it2 = v2.begin(); auto it3 = v1.cbegin(), it4 = v2.cbegin();
9.2.4. Определение и инициализация контейнера
Каждый контейнерный тип определяет стандартный конструктор (см. раздел 7.1.4). За исключением контейнера array стандартный конструктор создает пустой контейнер определенного типа. Также за исключением контейнера array другие конструкторы получают аргументы, которые определяют размер контейнера и исходные значения его элементов.
Инициализация контейнера как копии другого контейнера
Существуют два способа создать новый контейнер как копию другого: можно непосредственно скопировать контейнер или (за исключением контейнера array) скопировать только диапазон его элементов, обозначенный парой итераторов.
Таблица 9.3. Определение и инициализация контейнера С c; Стандартный конструктор. Если
C — массив, то элементы контейнера с инициализируются значением по умолчанию; в противном случае контейнер с пуст С c1(c2) С c1 = c2 Контейнер c1 — копия c2. Контейнеры c1 и c2 должны быть одинакового типа (т.е. должны иметь тот же тип контейнера и содержать элементы того же типа; у массивов должен также совпадать размер) С с{a, b, с...} С с = {a, b,
с...} Контейнер c содержит копию элементов из списка инициализации. Тип элементов в списке должен быть совместимым с типом элементов C. В случае массива количество элементов списка не должно превышать размер массива, а все недостающие элементы инициализируются значением по умолчанию (см. раздел 3.3.1) С с(b, е) Контейнер c содержит копию элементов из диапазона, обозначенного итераторами b и е. Тип элементов должен быть совместимым с типом элементов С. (Недопустимо для массива.) Получающие размер конструкторы допустимы только для последовательных контейнеров (исключая массив) С
seq(n) Контейнер seq содержит n элементов, инициализированных значением по умолчанию;
этот конструктор является явным (см. раздел 7.5.4). (Недопустимо для строки.) С seq(n,t)
Контейнер seq содержит n элементов со значением t
Page 425/1103

Чтобы создать контейнер как копию другого, их типы контейнеров и элементов должны совпадать. При передаче итераторов идентичность типов контейнеров необязательна. Кроме того, могут отличаться типы элементов нового и исходного контейнеров, если возможно преобразование между ними (см. раздел 4.11):
// каждый контейнер имеет три элемента, инициализированных
// предоставленными инициализаторами list<string> authors = {"Milton", "Shakespeare", "Austen"}; vector<const char*> articles = {"a", "an", "the"}; list<string> list2(authors); // ok: типы совпадают deque<string> authList(authors); // ошибка: типы контейнеров
// не совпадают vector<string> words(articles); // ошибка: типы элементов не совпадают
// ok: преобразует элементы const char* в string forward_list<string> words(articles.begin(), articles.end());
При копировании содержимого одного контейнера в другой типы контейнеров и их элементов должны точно совпадать.
Конструктор, получающий два итератора, использует их для обозначения диапазона копируемых элементов. Как обычно, итераторы отмечают первый и следующий элемент после последнего копируемого. Размер нового контейнера будет совпадать с количеством элементов в диапазоне. Каждый элемент в новом контейнере инициализируется значением соответствующего элемента в диапазоне.
Поскольку итераторы обозначают диапазон, этот конструктор можно использовать для копирования части последовательности. С учетом того что it является итератором,
обозначающим элемент в контейнере authors, можно написать следующее:
// копирует до, но не включая элемент, обозначенный итератором it deque<string> authList(authors.begin(), it); Списочная инициализация
По новому стандарту контейнер допускает списочную инициализацию (см. раздел 3.3.1):
Page 426/1103

// каждый контейнер имеет три элемента, инициализированных
// предоставленными инициализаторами list<string> authors = {"Milton", "Shakespeare", "Austen"}; vector<const char*> articles = {"a", "an", "the"};
Это определяет значение каждого элемента в контейнере явно. Кроме контейнеров таких типов, как array, список инициализации неявно определяет также размер контейнера: у контейнера будет столько элементов, сколько инициализаторов в списке. Конструкторы последовательных контейнеров, связанные с размером
Кроме конструкторов, общих для последовательных и ассоциативных контейнеров,
последовательные контейнеры (кроме массива) можно также инициализировать, указав их размера и (необязательного) инициализирующий элемент. Если его не предоставить,
библиотека создает инициализирующее значение сама (см. раздел 3.3.1): vector<int> ivec(10, -1); // десять элементов типа int; значение -1 list<string> svec(10, "hi!"); // десять строк; значение "hi!" forward_list<int> ivec(10); // десять элементов; значение 0 deque<string> svec(10); // десять элементов; все пустые строки
Конструктор, получающий аргумент размера, можно также использовать, если элемент имеет встроенный тип или тип класса, у которого есть стандартный конструктор (см. раздел 9.2).
Если у типа элемента нет стандартного конструктора, то наряду с размером следует определить явный инициализатор элемента.
Конструкторы, получающие размер, допустимы только для последовательных контейнеров; ассоциативные контейнеры их не поддерживают.Библиотечные массивы имеют фиксированный размер
Подобно тому, как размер встроенного массива является частью его типа, размер библиотечного контейнера array тоже входит в состав его типа. Когда определяется массив,
кроме типа элемента задается также размер контейнера: array<int, 42> // тип: массив, содержащий 42 целых числа array<string, 10> //
Page 427/1103

тип: массив, содержащий 10 строк
Чтобы использовать контейнер array, следует указать тип элемента и его размер: array<int, 10>::size_type i; // тип массива включает тип элемента
// и размер array<int>::size_type j; // ошибка: array<int> - это не тип
Поскольку размер является частью типа массива, контейнер array не поддерживает обычные конструкторы контейнерных классов. Эти конструкторы, явно или неявно, определяют размер контейнера. В случае массива разрешение пользователям передавать аргумент размера было бы избыточно (в лучшем случае) и приводило бы к ошибкам.
Фиксированный характер размера массивов влияет также на поведение остальных конструкторов, действительно определяющих массив. В отличие от других контейнеров,
созданный по умолчанию массив не пуст: количество его элементов соответствует размеру, а инициализированы они значением по умолчанию (см. раздел 2.2.1), как и элементы встроенного массива (см. раздел 3.5.1). При списочной инициализации массива количество инициализаторов не должно превышать размер массива. Если инициализаторов меньше, чем элементов массива, они используются для первых элементов, а все остальные инициализируются значением по умолчанию (см. раздел 3.3.1). В любом случае, если типом элемента является класс, то у него должен быть стандартный конструктор, обеспечивающий инициализацию значением по умолчанию: array<int, 10> ia1; // десять целых чисел, инициализированных
// значением по умолчанию array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // списочная инициализация array<int, 10> ia3 = {42}; // ia3[0] содержит значение 42, остальные
// элементы - значение 0
Следует заметить, что хоть и нельзя копировать или присваивать объекты массивов встроенных типов (см. раздел 3.5.1), для контейнеров array такого ограничения нет: int digs[10] = {0,1,2,3,4,5,6,7,8,9}; int cpy[10] = digs; //
Page 428/1103

ошибка: встроенные массивы не допускают
// копирования и присвоения array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9}; array<int, 10> copy = digits; // ok: если типы массивов совпадают
Как обычно, инициализирующий контейнер должен иметь тот же тип, что и создаваемый. Для контейнера array совпадать должны тип элемента и размер, поскольку размер массива —
часть его типа. Упражнения раздела 9.2.4
Упражнение 9.11. Приведите пример каждого из шести способов создания и инициализации контейнеров vector. Объясните, какие значения будет содержать каждый вектор.
Упражнение 9.12. Объясните различие между конструктором, получающим контейнер для копирования, и конструктором получающим два итератора.
Упражнение 9.13. Как инициализировать контейнер vector<double> из контейнера list<int> и контейнера vector<int>? Напишите код для проверки ответов.
9.2.5. Присвоение и функция swap()
Связанные с присвоением операторы, перечисленные в табл. 9.4, воздействуют на весь контейнер. Оператор присвоения заменяет весь диапазон элементов в левом контейнере копиями элементов из правого: c1 = c2; // заменяет содержимое контейнера c1 копией
// элементов контейнера c2 c1 = {a,b,c}; // после присвоения контейнер c1 имеет размер 3
После первого присвоения контейнеры слева и справа равны. Если контейнеры имели неравный размер, после присвоения у обоих будет размер контейнера из правого операнда.
После второго присвоения размер контейнера c1 составит 3, что соответствует количеству значений, представленных в списке.
Таблица 9.4. Операторы присвоения контейнеров c1 = c2 Заменяет элементы контейнера c1
копиями элементов контейнера c2. Контейнеры c1 и c2 должны иметь тот же тип с = {a, b, с...}
Заменяет элементы контейнера c1 копиями элементов списка инициализации. (Недопустимо для массива.) swap(c1, c2) c1.swap(c2) Обменивает элементы контейнеров c1 и c2.
Page 429/1103

Контейнеры c1 и c2 должны иметь тот же тип. Обычно функция swap() выполняется намного быстрее, чем процесс копирования элементов из контейнера c2 в c1 Операторы присвоения недопустимы для ассоциативных контейнеров и массива seq.assign(b,е) Заменяет элементы в контейнере seq таковыми из диапазона, обозначенного итераторами b и е. Итераторы b и е не должны ссылаться на элементы в контейнере seq seq.assign(il) Заменяет элементы в контейнере seq таковыми из списка инициализации il seq.assign(n,t) Заменяет элементы в контейнере seq набором из n элементов со значением t
В отличие от встроенных массивов, библиотечный тип array поддерживает присвоение. У
левых и правых операндов должен быть одинаковый тип: array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9}; array<int, 10> а2 = {0}; // все элементы со значением 0 a1 = а2; // замена элементов в a1 а2 = {0}; // ошибка: нельзя присвоить массиву значения из списка
Поскольку размер правого операнда может отличаться от размера левого операнда, тип array не поддерживает функцию assign() и это не позволяет присваивать значения из списка.
Связанные с присвоением операторы делают недопустимыми итераторы, ссылки и указатели на контейнер слева. Применение функции assign() (только последовательные контейнеры)
Оператор присвоения требует совпадения типов левых и правых операндов. Он копирует все элементы правого операнда в левый. Последовательные контейнеры (кроме array)
определяют также функцию-член assign(), обеспечивающую присвоение разных, но совместимых типов, или присвоение контейнерам последовательностей. Функция assign()
заменяет все элементы в левом контейнере копиями элементов, указанных в ее аргументе.
Например, функцию assign() можно использовать для присвоения диапазона значений char*
из вектора в список строк: list<string> names; vector<const char*> oldstyle; names = oldstyle; // ошибка: типы контейнеров не совпадают
// ok: преобразование из const char* в string возможно names.assign(oldstyle.cbegin(), oldstyle.cend());
Вызов функции assign() заменяет элементы в контейнере names копиями элементов из диапазона, обозначенного итераторами. Аргументы функции assign() определяют количество элементов контейнера и их значения.
Поскольку существующие элементы заменяются, итераторы, переданные функции assign(),
Page 430/1103

не должны относиться к контейнеру, для которого вызвана функция assign().
Вторая версия функции assign() получает целочисленное значение и значение элемента. Она заменяет указанное количество элементов контейнера заданным значением:
// эквивалент slist1.clear();
// сопровождается slist1.insert(slist1.begin(), 10, "Hiya!"); list<string> slist1(1); // один элемент; пустая строка slist1.assign(10, "Hiya!"); // десять элементов; со значением "Hiya!" Применение функции swap()
Функция swap() меняет местами значения двух контейнеров того же типа. Типы контейнеров и их элементов должны совпадать. После обращения к функции swap() элементы правого операнда оказываются в левом, и наоборот: vector<string> svec1(10); // вектор из 10 элементов vector<string> svec2(24); // вектор из 24 элементов svec1.swap(svec2);
После выполнения функции swap() вектор svec1 содержит 24 строки, а вектор svec2 — 10. За исключением массивов смена двух контейнеров осуществляется очень быстро — сами элементы не меняются; меняются лишь внутренние структуры данных.
За исключением массивов функция swap() не копирует, не удаляет и не вставляет элементы,
поэтому она гарантированно выполняется за постоянное время.
Благодаря тому факту, что элементы не перемещаются, итераторы, ссылки и указатели в контейнере, за исключением контейнера string, остаются допустимыми. Они продолжают указывать на те же элементы, что и перед перестановкой. Однако после вызова функции swap() эти элементы находятся в другом контейнере. Предположим, например, что итератор iter обозначал в векторе строк позицию svec1[3]. После вызова функции swap() он обозначит элемент в позиции svec2[3]. В отличие от других контейнеров, вызов функции swap() для строки делает некорректными итераторы, ссылки и указатели.
В отличие от поведения функции swap() с другими контейнерами, когда дело доходит до массивов, элементы действительно обмениваются. Обмен двух массивов потребует времени,
пропорционального количеству их элементов.
После выполнения функции swap(), указатели, ссылки и итераторы остаются связанными с тем же элементом, который они обозначили ранее. Конечно, значение самого элемента заменено значением соответствующего элемента другого массива.
Page 431/1103

Новая библиотека предоставляет функцию swap() в версии члена класса контейнера и в версии, не являющейся членом какого-либо класса. Прежние версии библиотеки определили только версию функции-члена swap(). Функция swap() не являющаяся членом класса контейнера, имеет большое значение в обобщенных программах. Как правило, лучше использовать именно эту версию. Упражнения раздела 9.2.5
Упражнение 9.14. Напишите программу, присваивающую значения элементов списка указателей на символьные строки в стиле С (тип char*) элементам вектора строк.
9.2.6. Операции с размером контейнера
За одним исключением у классов контейнеров есть три функции, связанные с размером.
Функция-член size() (см. раздел 3.2.2) возвращает количество элементов в контейнере;
функция-член empty() возвращает логическое значение true, если контейнер пуст, и значение false в противном случае; функция-член max_size() возвращает число, большее или равное количеству элементов, которые может содержать контейнер данного типа. По причинам,
рассматриваемым в следующем разделе, контейнер forward_list предоставляет функции max_size() и empty(), но не функцию size().
9.2.7. Операторы сравнения
Для сравнения используется тот же реляционный оператор, который определен для типа элементов: при сравнении двух контейнеров на неравенство (!=) используется оператор !=
типа их элементов. Если тип элемента не поддерживает определенный оператор, то для сравнения контейнеров такого типа данный оператор использовать нельзя.
Сравнение двух контейнеров осуществляется на основании сравнения пар их элементов. Эти операторы работают так же, как и таковые у класса string (см. раздел 3.2.2):
• Если оба контейнера имеют одинаковый размер и все их элементы совпадают, контейнеры равны, в противном случае — не равны.
• Если контейнеры имеют различный размер, но каждый элемент короткого совпадает с соответствующим элементом длинного, считается, что короткий контейнер меньше длинного.
• Если значения элементов контейнеров не совпадают, результат их сравнения зависит от значений первых неравных элементов.
Проще всего понять работу операторов, рассмотрев их на примерах. vector<int> v1 = { 1, 3, 5, 7, 9, 12 }; vector<int> v2 = { 1, 3, 9 }; vector<int> v3 = { 1, 3, 5, 7 }; vector<int> v4 = { 1, 3, 5, 7, 9, 12 }; v1 < v2 //
Page 432/1103

true; v1 и v2 отличаются элементом [2]: v1[2] меньше,
// чем v2[2] v1 < v3 // false; все элементы равны, но у v3 их меньше; v1 == v4 // true; все элементы равны и размер v1 и v4 одинаков v1 == v2 // false; v2 имеет меньше элементов, чем v1
При сравнении контейнеров используются операторы сравнения их элементов
Сравнить два контейнера можно только тогда, когда используемый оператор сравнения определен для типа элемента контейнера.
Операторы равенства контейнеров используют оператор == элемента, а операторы сравнения — оператор < элемента. Если тип элемента не предоставляет необходимый оператор, то не получится использовать соответствующие операторы и с содержащими их контейнерами. Например, определенный в главе 7 тип Sales_data не предоставлял операторов == и <. Поэтому нельзя сравнить два контейнера, содержащих элементы типа
Sales_data: vector<Sales_data> storeA, storeB; if (storeA < storeB) // ошибка: Sales_data не имеет оператора < Упражнения раздела 9.2.7
Упражнение 9.15. Напишите программу, выясняющую, равны ли два вектора vector<int>.
Упражнение 9.16. Перепишите предыдущую программу, но сравните элементы списка list<int> и вектора vector<int>.
Упражнение 9.17. Допустим, c1 и c2 являются контейнерами. Какие условия налагают типы их элементов в следующем выражении? if (c1 < c2)
9.3. Операции с последовательными контейнерами
Последовательные и ассоциативные контейнеры отличаются организацией своих элементов.
Это различие влияет на способ хранения, доступа, добавления и удаления элементов. В
предыдущем разделе рассматривались операции, общие для всех контейнеров (см. табл.
9.2). В остальной части этой главы рассматриваются операции, специфические для последовательных контейнеров.
Page 433/1103

9.3.1. Добавление элементов в последовательный контейнер
За исключением массива все библиотечные контейнеры обеспечивают гибкое управление памятью. Они позволяют добавлять и удалять элементы, динамически изменяя размер контейнера во время выполнения. В табл. 9.5 перечислены функции, позволяющие добавлять элементы в последовательный контейнер (но не в массив).
Используя эти функции, следует помнить, что контейнеры применяют различные стратегии резервирования памяти для элементов и что эти стратегии влияют на производительность.
Например, добавление элементов в любое место вектора или строки (но не в конец) либо в любое место двухсторонней очереди (но не в начало или в конец) требует перемещения элементов.
Кроме того, добавление элементов в вектор или строку может привести к повторному резервированию памяти всего объекта. Это, в свою очередь, потребует резервирования новой памяти для элементов и их перемещения из старых областей в новые.
Таблица 9.5. Функции, добавляющие элементы в последовательный контейнер
Эти функции изменяют размер контейнера; они не поддерживаются массивами. Контейнер forward_list обладает специальными версиями функций insert() и emplace(); см. раздел 9.3.4, а функций push_back() и emplace_back() у него нет. Функции push_front() и emplace_front()
недопустимы для контейнеров vector и string. c.push_back(t) c.emplace_back( args ) Создает в конце контейнера с элемент со значением t или переданным аргументом args . Возвращает тип void c.push_front(t) c.emplace_front( args ) Создает в начале контейнера с элемент со значением t или переданным аргументом args . Возвращает тип void c.insert(p,t) c.emplace(p, args ) Создает элемент со значением t или переданным аргументом args перед элементом, обозначенным итератором p. Возвращает итератор на добавленный элемент c.insert(p,n,t) Вставляет n элементов со значением t перед элементом, обозначенным итератором p. Возвращает итератор на первый вставленный элемент; если n — нуль,
возвращается итератор p c.insert(p,b,e) Вставляет элементы из диапазона, обозначенного итераторами b и е перед элементом, обозначенным итератором p. Итераторы b и е не могут относиться к элементам в контейнере с. Возвращает итератор на первый вставленный элемент; если диапазон пуст, возвращается итератор p c.insert(p,il) il — это список значений элементов. Вставляет переданные значения перед элементом, обозначенным итератором p.
Возвращает итератор на первый вставленный элемент; если список пуст, возвращается итератор p Применение функции push_back()
В разделе 3.3.2 упоминалось, что функция push_back() добавляет элемент в конец вектора.
Кроме контейнеров array и forward_list, каждый последовательный контейнер (включая string)
поддерживает функцию push_back().
Цикл следующего примера читает по одной строке за раз в переменную word:
Page 434/1103

// читать слова со стандартного устройства ввода и помещать
// их в конец контейнера 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 гарантирует постоянное время вставки и удаления
Page 435/1103

элементов в начало и в конец контейнера. Как и у контейнера 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() возможна
// внимание: вставка возможна везде, но вставка в конец вектора может
// потребовать больше времени
Page 436/1103

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;
Page 437/1103

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));
Page 438/1103

Вызов функции 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;
Page 439/1103

while (iter != mid) if (*iter == some_val) iv.insert(iter, 2 * some_val);
9.3.2. Доступ к элементам
В табл. 9.6 приведен список функций, которые можно использовать для доступа к элементам последовательного контейнера. Если в контейнере нет элементов, функции доступа неприменимы.
У каждого последовательного контейнера, включая array, есть функция-член front(), и у всех,
кроме forward_list, есть также функция-член back(). Эти функции возвращают ссылку на первый и последний элементы соответственно:
// перед обращением к значению итератора удостовериться, что
// элемент существует, либо вызвать функции front() и back() if (!с.empty()) {
// val и val2 - копии значений первого элемента в контейнере с auto val = *с.begin(), val2 = c.front();
// val3 и val4 - копии значений последнего элемента в контейнере с auto last = c.end(); auto val3 = *(--last); // невозможен декремент итератора forward_list auto val4 = c.back(); // не поддерживается forward_list
}
Таблица 9.6. Функции доступа к элементам последовательного контейнера Функция at() и оператор индексирования допустимы только для контейнеров string, vector, deque и array.
Функция back() недопустима для контейнера forward_list. c.back() Возвращает ссылку на последний элемент контейнера с, если он не пуст c.front() Возвращает ссылку на первый элемент контейнера с, если он не пуст c[n] Возвращает ссылку на элемент, индексированный
Page 440/1103

целочисленным беззнаковым значением n. Если n >= c.size(), результат непредсказуем c.at(n) Возвращает ссылку на элемент по индексу n. Если индекс находится вне диапазона,
передает исключение out_of_range
Эта программа получает ссылки на первый и последний элементы контейнера с двумя разными способами. Прямой подход — обращение к функциям front() и back(). Косвенный подход получения ссылки на тот же элемент подразумевает обращение к значению итератора, возвращенного функцией begin(), или декремент с последующим обращением к значению итератора, возвращенного функцией end().
В этой программе примечательны два момента: поскольку возвращенный функцией end()
итератор указывает на элемент, следующий после последнего, для доступа к последнему элементу контейнера применяется декремент полученного итератора. Вторым очень важным моментом является необходимость удостовериться в том, что контейнер c не пуст, перед вызовом функций front() и back() или обращением к значению итераторов, возвращенных функциями begin() и end(). Если контейнер окажется пустым, все выражения в блоке операторов if будут некорректны.
Вызов функций front() или back() для пустого контейнера, равно как и использование индекса,
выходящего за диапазон существующих элементов, является серьезной ошибкой.
Функции-члены, обращающиеся к элементам в контейнере (т.е. функции front(), back(), at() и индексирование), возвращают ссылки. Если контейнер является константным объектом,
возвращается ссылка на константу. Если контейнер не константа, возвращается обычная ссылка, которую можно использовать для изменения значения выбранного элемента: if (!с.empty()) { с.front() = 42; // присвоить 42 первому элементу в контейнере с auto &v = c.back(); // получить ссылку на последний элемент v = 1024; // изменить элемент в контейнере с auto v2 = c.back(); // v2 не ссылка; это копия c.back() v2 = 0; // это не изменит элемент в контейнере с
}
Как обычно, если ключевое слово auto применяется для определения переменной,
сохраняющей значения, возвращаемые одной из этих функций, и эту переменную предстоит использовать для изменения элемента, то определять эту переменную следует как ссылочный тип. Индексация и безопасный произвольный доступ
Контейнеры, предоставляющие быстрый произвольный доступ (string, vector, deque и array),
предоставляют также оператор индексирования (см. раздел 3.3.3). Как уже упоминалось,
Page 441/1103

оператор индексирования получает индекс и возвращает ссылку на элемент в этой позиции контейнера. Индекс не должен выходить за диапазон элементов (т.е. больше или равен 0 и меньше размера контейнера). Допустимость индекса должен обеспечить разработчик;
оператор индексирования не проверяет принадлежность индекса диапазону. Использование для индекса значения вне диапазона является серьезной ошибкой, но компилятор ее не обнаружит.
Если необходимо гарантировать допустимость индекса, вместо него можно использовать функцию-член at(). Она действует как оператор индексирования, но если индекс недопустим,
то она передает исключение out_of_range (см. раздел 5.6): vector<string> svec; // пустой вектор cout << svec[0]; // ошибка времени выполнения: вектор svec
// еще не имеет элементов! cout << svec.at(0); // передает исключение out_of_range Упражнения раздела 9.3.2
Упражнение 9.23. Какими были бы значения переменных val2, val3 и val4, в первой программе данного раздела, если бы функция c.size() возвращала значение 1?
Упражнение 9.24. Напишите программу, которая обращается к первому элементу вектора,
используя функции at(), front() и begin(), а также оператор индексирования. Проверьте программу на пустом векторе.
9.3.3. Удаление элементов
Подобно тому, как существует несколько способов добавления элементов в контейнер
(исключая array), существует несколько способов их удаления. Функции удаления перечислены в табл. 9.7.
Таблица 9.7. Функции удаления последовательных контейнеров Эти функции изменяют размер контейнера; они не поддерживаются массивами. Контейнер forward_list обладает специальной версией функции erase(); см. раздел 9.3.4, а функции pop_back() у него нет.
Функция pop_front() недопустима для контейнеров vector и string. c.pop_back() Удаляет последний элемент контейнера c. Результат непредсказуем, если контейнер c пуст.
Возвращает void c.pop_front() Удаляет первый элемент контейнера с. Результат непредсказуем, если контейнер с пуст. Возвращает void c.erase(p) Удаляет элемент,
обозначенный итератором p. Возвращает итератор на элемент после удаленного или итератор после конца (off-the-end iterator), если итератор p обозначает последний элемент.
Результат непредсказуем, если итератор p указывает на следующий элемент после
Page 442/1103

последнего c.erase(b,е) Удаляет диапазон элементов, обозначенных итераторами b и е.
Возвращает итератор на элемент после последнего удаленного или после последнего элемента контейнера, если итератор е указывал на последний элемент c.clear() Удаляет все элементы контейнера с. Возвращает void
Функции-члены удаления элементов не проверяют свои аргументы. Разработчик должен сам позаботиться о проверке наличия элементов перед их удалением. Применение функций pop_front() и pop_back()
Функции pop_front() и pop_back() удаляют, соответственно, первый и последний элементы контейнера. Векторы и строки функциями push_front() и pop_front() не обладают. У контейнера forward_list также нет функции pop_back(). Подобно функциям-членам доступа к элементам,
эти функции не применимы к пустому контейнеру.
Удалив соответствующий элемент, эти функции возвращают тип void. Если необходимо извлечь элемент, то следует сохранить его значение перед удалением: while (!ilist.empty()) { process(ilist.front()); // действия с текущей вершиной списка ilist ilist.pop_front(); // готово; удалить первый элемент
}
Удаление элементов в любой позиции, кроме начала или конца двухсторонней очереди,
объявляет недействительными все итераторы, ссылки и указатели. В векторе и строке недействительными объявляются итераторы, ссылки и указатели на элементы,
расположенные после удаленного элемента. Удаление элемента в середине контейнера
Функции-члены удаления удаляют элемент (элементы) в указанной позиции контейнера.
Можно удалить как отдельный элемент, обозначенный итератором, так и диапазон элементов, отмеченных парой итераторов. Обе формы функции erase() возвращают итератор на область после последнего удаленного элемента.
В качестве примера рассмотрим следующий цикл, удаляющий нечетные элементы списка: list<int> lst = {0,1,2,3,4,5,6,7,8,9}; auto it = lst.begin(); while (it != lst.end()) if (*it % 2) // если элемент является нечетным it = lst.erase(it); // удалить его else
Page 443/1103

++it;
На каждой итерации проверяется нечетность текущего элемента. Если это так, то данный элемент удаляется, а итератор it устанавливается на следующий элемент после удаленного.
Если элемент *it четный, осуществляется приращение итератора it, чтобы при следующей итерации он указывал на следующей элемент. Удаление нескольких элементов
Версия функции erase() с парой итераторов позволяет удалить диапазон элементов:
// удалить диапазон элементов между двумя итераторами
// возвращает итератор на элемент сразу после последнего удаленного elem1 = slist.erase(elem1, elem2); // после вызова elem1 == elem2
Итератор elem1 указывает на первый удаляемый элемент, а итератор elem2 — на следующий после последнего удаляемого.
Чтобы удалить все элементы в контейнере, можно либо вызвать функцию clear(), либо перебирать итераторы от возвращаемого функцией begin() до end() и передавать их функции erase(): slist.clear(); // удалить все элементы в контейнере slist.erase(slist.begin(), slist.end()); // эквивалент Упражнения раздела 9.3.3
Упражнение 9.25. Что будет, если в программе, где удалялся диапазон элементов, итераторы elem1 и elem2 равны? Что если итератор elem2 или оба итератора (elem1 и elem2) являются итератором после конца?
Упражнение 9.26. Используя приведенное ниже определение массива ia, скопируйте его содержимое в вектор и в список. Используя версию функции erase() для одного итератора,
удалите из списка элементы с нечетными значениями, а из вектора — с четными. int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
9.3.4. Специализированные функции контейнера forward_list
Чтобы лучше понять, почему у контейнера forward_list есть специальные версии функций добавления и удаления элементов, рассмотрим, что происходит при удалении элемента из односвязного списка. Как показано на рис. 9.1, удаление элемента изменяет связи в последовательности. В данном случае удаление элемента elem3 изменяет связь элемента elem2; элемент elem2 указывал на элемент elem3, но после удаления элемента elem3
элемент elem2 указывает на элемент elem4.
Page 444/1103

Рис. 9.1. Специализированные функции контейнера forward_list
При добавлении или удалении элемента у элемента перед ним будет другой последователь.
Чтобы добавить или удалить элемент, необходимо обратиться к его предшественнику и изменить его ссылку. Однако контейнер forward_list — это односвязный список. В
односвязном списке нет простого способа доступа к предыдущему элементу. Поэтому функции добавления и удаления элементов в контейнере forward_list работают, изменяя элемент после указанного. Таким образом, у нас всегда есть доступ к элементам, на которые влияет изменение.
Поскольку эти функции ведут себя отлично от функций других контейнеров, класс forward_list не определяет функции-члены insert(), emplace() и erase(). Вместо них используются функции-члены insert_after(), emplace_after() и erase_after() (перечислены в табл. 9.8). На рисунке выше, например, для удаления элемента elem3 использовалась бы функция erase_after() для итератора, обозначающего элемент elem2. Для реализации этих операций класс forward_list определяет также функцию before_begin(), которая возвращает итератор после начала (off-the-beginning iterator). Этот итератор позволяет добавлять или удалять элементы после несуществующего элемента перед первым в списке.
Таблица 9.8. Функции вставки и удаления элементов контейнера forward_list lst.before_begin()
lst.cbefore_begin() Возвращает итератор, обозначающий несуществующий элемент непосредственно перед началом списка. К значению этого итератора обратиться нельзя.
Функция cbefore_begin() возвращает итератор const_iterator lst.insert_after(p,t)
lst.insert_after(p,n,t) lst.insert_after(p,b,e) lst.insert_after(p,il) Вставляет элемент (элементы)
после обозначенного итератором p. t — это объект, n — количество, b и е — обозначающие диапазон итераторы (они не должны принадлежать контейнеру lst), il — список, заключенный в скобки. Возвращает итератор на последний вставленный элемент. Если диапазон пуст, возвращается итератор p. Если p —
итератор после конца, результат будет непредсказуемым emplace_after(p, args ) Параметр args используется для создания элементов после обозначенного итератором p. Возвращает итератор на новый элемент. Если p — итератор после конца, результат будет непредсказуемым lst.erase_after(p) lst.erase_after(b,e) Удаляет элемент после обозначенного итератором p или диапазоном элементов после обозначенного итератором b и до, но не включая обозначенного итератором е. Возвращает итератор на элемент после удаленного или на элемент после конца контейнера. Если p — итератор после конца или последний элемент контейнера, результат будет непредсказуемым
При добавлении или удалении элементов в контейнер forward_list следует обратить внимание на два итератора: на проверяемый элемент и на элемент, предшествующий ему. В качестве примера перепишем приведенный выше цикл, удалявший из списка нечетные элементы, так,
чтобы использовался контейнер forward_list: forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9}; auto prev = flst.before_begin(); //
Page 445/1103

обозначает элемент "перед началом"
// контейнера flst auto curr = flst.begin(); // обозначает первый элемент контейнера flst while (curr != flst.end()) { // пока есть элементы для обработки if (*curr % 2) // если элемент нечетный curr = flst.erase_after(prev); // удалить его и переместить curr else { prev = curr; // переместить итератор на следующий элемент
++curr; // и один перед следующим элементом
}
}
Здесь итератор curr обозначает проверяемый элемент, а итератор prev — элемент перед curr. Итератор curr инициализирует вызов функции begin(), чтобы первая итерация проверила на четность первый элемент. Итератор prev инициализирует вызов функции before_begin(),
который возвращает итератор на несуществующий элемент непосредственно перед curr.
Когда находится нечетный элемент, итератор prev передается функции erase_after(). Этот вызов удаляет элемент после обозначенного итератором prev; т.е. элемент, обозначенный итератором curr. Итератору curr присваивается значение, возвращенное функцией erase_after(). В результате он обозначит следующий элемент последовательности, а итератор prev останется неизменным; он все еще обозначает элемент перед (новым) значением итератора curr. Если обозначенный итератором curr элемент не является нечетным, то в части else оба итератора перемещаются на следующий элемент. Упражнения раздела 9.3.4
Упражнение 9.27. Напишите программу для поиска и удаления нечетных элементов в контейнере forward_list<int>.
Упражнение 9.28. Напишите функцию, получающую контейнер forward_list<string> и два дополнительных аргумента типа string. Функция должна находить первую строку и вставлять вторую непосредственно после первой. Если первая строка не найдена, то вставьте вторую строку в конец списка.
Page 446/1103

9.3.5. Изменение размеров контейнера
Для изменения размера контейнера, за исключением массива, можно использовать функцию resize(), представленную в табл. 9.9. Если текущий размер больше затребованного, элементы удаляются с конца контейнера; если текущий размер меньше нового, элементы добавляются в конец контейнера: list<int> ilist(10, 42); //
10 целых чисел со значением 42 ilist.resize(15); // добавляет 5 элементов со значением 0
// в конец списка ilist ilist.resize(25, -1); // добавляет 10 элементов со значением -1
// в конец списка ilist ilist.resize(5); // удаляет 20 элементов от конца списка ilist
Функция resize() получает необязательный аргумент — значение элемента, используемое для инициализации всех добавляемых элементов. Если этот аргумент отсутствует, добавленные элементы инициализируются значением по умолчанию (см. раздел 3.3.1). Если контейнер хранит элементы типа класса и функция resize() добавляет элементы, то либо следует предоставить инициализатор, либо тип элемента должен иметь стандартный конструктор.
Таблица 9.9. Функции размера последовательного контейнера За исключением массива c.resize(n) Измените размеры контейнера с так, чтобы у него было n элементов. Если n <
c.size(), то лишние элементы отбрасываются. Если следует добавить новые элементы, они инициализируются значением по умолчанию с.resize(n,t) Измените размеры контейнера с так,
чтобы у него было n элементов. Все добавляемые элементы получат значение t
Если функция resize() сокращает контейнер, то итераторы, ссылки и указатели на удаленные элементы окажутся некорректными; выполнение функции resize() для контейнеров vector,
string и deque может сделать некорректными все итераторы, указатели и ссылки. Упражнения раздела 9.3.5
Упражнение 9.29. Если контейнер vec содержит 25 элементов, то что делает выражение vec.resize(100)? Что если затем последует вызов vec.resize(10)?
Упражнение 9.30. Какие ограничения (если они есть) налагает использование функции resize() с одиночным аргументом, имеющим тип элемента?
Page 447/1103

9.3.6. Некоторые операции с контейнерами делают итераторы недопустимыми
Функции, добавляющие и удаляющие элементы из контейнера, могут сделать некорректными указатели, ссылки или итераторы на его элементы. Некорректными считаются те указатели,
ссылки и итераторы, которые больше не указывают на элемент. Использование некорректного указателя, ссылки или итератора является серьезной ошибкой, последствия которой, вероятно, будут схожи с использованием неинициализированного указателя (см.
раздел 2.3.2, стр. 89).
После операции добавления элементов в контейнер возможно следующее.
• Итераторы, указатели и ссылки на элементы вектора или строки становятся недопустимыми после повторного резервирования пространства контейнера. Если повторного резервирования не было, ссылки на элементы перед позицией вставки остаются допустимыми, а на элементы после позиции вставки — нет.
• Итераторы, указатели и ссылки на элементы двухсторонней очереди становятся недопустимыми после добавления элементов в любую позицию кроме начала или конца. При добавлении в начало или в конец недопустимыми становятся только итераторы, а ссылки и указатели на существующие элементы — нет.
Нет ничего удивительного в том, что после удаления элементов из контейнера итераторы,
указатели и ссылки на удаленные элементы становятся недопустимыми. В конце концов, этих элементов больше нет.
• У контейнеров list и forward_list все остальные итераторы, ссылки и указатели (включая итераторы после конца и перед началом) остаются допустимыми.
• У контейнера deque все остальные итераторы, ссылки и указатели становятся недопустимыми, если удалены элементы в любой позиции, кроме начала или конца. Если удаляются элементы в конце, итератор после конца становится недопустимым, но другие итераторы, ссылки и указатели остаются вполне допустимыми. То же относится к удалению из начала.
• У контейнеров vector и string все остальные итераторы, ссылки и указатели на элементы перед позицией удаления остаются допустимыми. При удалении элементов итератор после конца всегда оказывается недопустимым.
Использование недопустимого итератора, указателя или ссылки является серьезной ошибкой, которая проявится во время выполнения программы. Совет. Контроль итераторов
При использовании итератора (или ссылки, или указателя на элемент контейнера) имеет смысл минимизировать ту часть программы, где итератор обязан оставаться допустимым.
Поскольку код, добавляющий или удаляющий элементы из контейнера, может сделать итераторы недопустимыми, необходимо позаботиться о переустановке итераторов соответствующим образом после каждой операции, которая изменяет контейнер. Это особенно важно для контейнеров vector, string и deque. Создание циклов, которые изменяют контейнер
Циклы, добавляющие или удаляющие элементы из контейнеров vector, string или deque,
должны учитывать тот факт, что итераторы, ссылки и указатели могут стать недопустимыми.
Программа должна гарантировать, что итератор, ссылка или указатель обновляется на
Page 448/1103

каждом цикле. Если цикл использует функцию insert() или erase(), обновить итератор довольно просто. Они возвращают итераторы, которые можно использовать для переустановки итератора:
// бесполезный цикл, удаляющий четные элементы и вставляющий дубликаты
// нечетных vector<int> vi = {0,1,2,3,4,5,6,7,8,9}; auto iter = vi.begin(); // поскольку vi изменяется, используется
// функция begin(), а не cbegin() while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); // дублирует текущий элемент iter +=2; // переместить через элемент
} else iter = vi.erase(iter); // удалить четные элементы
// не перемещать итератор; iter обозначает элемент после
// удаленного
}
Эта программа удаляет четные элементы и дублирует соответствующие нечетные. После вызова функций insert() и erase() итератор обновляется, поскольку любая из них способна сделать итератор недопустимой.
После вызова функции erase() никакой необходимости в приращении итератора нет,
поскольку возвращенный ею итератор обозначает следующий элемент в последовательности. После вызова функции insert() итератор увеличивается на два.
Помните, функция insert() осуществляет вставку перед указанной позицией и возвращает итератор на вставленный элемент. Таким образом, после вызова функции insert() итератор
Page 449/1103

iter обозначает элемент (недавно добавленный) перед обрабатываемым. Приращение на два осуществляется для того, чтобы перескочить через добавленный и только что обработанный элементы. Это перемещает итератор на следующий необработанный элемент. Не храните итератор, возвращенный функцией end()
При добавлении или удалении элементов в контейнер vector или string либо при добавлении или удалении элементов в любую, кроме первой, позицию контейнера deque возвращенный функцией end() итератор всегда будет недопустимым. Потому циклы, которые добавляют или удаляют элементы, всегда должны вызывать функцию end(), а не использовать хранимую копию. Частично поэтому стандартные библиотеки С++ реализуют обычно функцию end() так,
чтобы она выполнялась очень быстро.
Рассмотрим, например, цикл, который обрабатывает каждый элемент и добавляет новый элемент после исходного. Цикл должен игнорировать добавленные элементы и обрабатывать только исходные. После каждой вставки итератор позиционируется так, чтобы обозначить следующий исходный элемент. Если попытаться "оптимизировать" цикл, сохраняя итератор,
возвращенный функцией end(), то будет беда:
// ошибка: поведение этого цикла непредсказуемо auto begin = v.begin(), end = v.end(); // плохая идея хранить значение итератора end while (begin != end) {
// некоторые действия
// вставить новое значение и переприсвоить итератор begin, который
// в противном случае окажется недопустимым
++begin; // переместить begin, поскольку вставка необходима после
// этого элемента begin = v.insert(begin, 42); // вставить новое значение
++begin; // переместить begin за только что добавленный элемент
Page 450/1103

}
Поведение этого кода непредсказуемо. На многих реализациях получится бесконечный цикл.
Проблема в том, что возвращенное функцией end() значение хранится в локальной переменной end. В теле цикла добавляется элемент. Добавление элемента делает итератор,
хранимый в переменной end, недопустимым. Этот итератор не указывает ни на какой элемент в контейнере v, ни на следующий после его конца.
Не кешируйте возвращаемый функцией end() итератор в циклах, которые вставляют или удаляют элементы в контейнере deque, string или vector.
Вместо того чтобы хранить итератор end, его следует повторно вычислять после каждой вставки:
// существенно безопасный: повторно вычислять end после каждого
// добавления/удаления элементов while (begin != v.end()) {
// некоторые действия
++begin; // переместить begin, поскольку вставка необходима после
// этого элемента begin = v.insert(begin, 42); // вставить новое значение
++begin; // переместить begin за только что добавленный элемент
} Упражнения раздела 9.3.6
Упражнение 9.31. Программа из пункта «Создание циклов, которые изменяют контейнер»,
удаляющая четные и дублирующая нечетные элементы, не будет работать с контейнером list или forward_list. Почему? Переделайте программу так, чтобы она работала и с этими типами тоже.
Упражнение 9.32. Будет ли допустим в указанной выше программе следующий вызов функции insert()? Если нет, то почему? iter = vi.insert(iter, *iter++);
Упражнение 9.33. Что будет, если в последнем примере этого раздела не присваивать переменной begin результат вызова функции insert()? Напишите программу без этого
Page 451/1103

присвоения, чтобы убедиться в правильности своего предположения.
Упражнение 9.34. Учитывая, что vi является контейнером целых чисел, содержащим четные и нечетные значения, предскажите поведение следующего цикла. Проанализировав этот цикл,
напишите программу, чтобы проверить правильность своих ожиданий. iter = vi.begin(); while (iter != vi.end()) if (*iter % 2) iter = vi.insert(iter, *iter);
++iter;
9.4. Как увеличивается размер вектора
Для обеспечения быстрого произвольного доступа элементы вектора хранятся последовательно — каждый элемент рядом с предыдущим. Как правило, нас не должно заботить то, как реализован библиотечный тип; достаточно знать, как его использовать. Но в случае векторов и строк реализация частично просачивается в интерфейс.
С учетом того, что элементы последовательны и размер контейнера гибок, рассмотрим происходящее при добавлении элемента в вектор или строку: если для нового элемента нет места, контейнер не сможет просто добавить элемент в некую другую область памяти —
элементы должны располагаться последовательно. Поэтому контейнер должен зарезервировать новую область памяти, достаточную для содержания уже существующих элементов, плюс новый элемент, а затем переместить элементы из старой области в новую,
добавить новый элемент и освободить старую область памяти. Если бы вектор осуществлял резервирование и освобождение памяти при каждом добавлении элемента, его работа была бы неприемлемо медленной.
Во избежание дополнительных затрат конструкторы библиотечных контейнеров используют стратегию, сокращающую количество повторных резервирований. При необходимости выделения новой области памяти реализации классов vector и string обычно резервируют больший объем, чем необходимо в данный момент. Контейнер хранит его в резерве и использует для размещения новых элементов при их добавлении. Поэтому нет никакой необходимости в повторном резервировании места для контейнера при каждом добавлении нового элемента.
Эта стратегия резервирования существенно эффективней таковой при каждой необходимости добавления нового элемента. Фактически ее производительность настолько высока, что на практике вектор обычно растет эффективней, чем список или двухсторонняя очередь, хотя вектор должен еще перемещать свои элементы при каждом повторном резервировании памяти. Функции-члены управления емкостью
Типы vector и string предоставляют описанные в табл. 9.10 функции-члены, позволяющие взаимодействовать с частью реализации, относящейся к резервированию памяти. Функция capacity() сообщает количество элементов, которое контейнер может создать прежде, чем ему понадобится занять больший объем памяти. Функция reserve() позволяет задать количество резервируемых элементов.
Page 452/1103

Таблица 9.10. Управление размером контейнера Функция shrink_to_fit() допустима только для контейнеров vector, string и deque. Функции capacity() и reserve() допустимы только для контейнеров vector и string. c.shrink_to_fit() Запрос на уменьшение емкости в соответствии с размером c.capacity() Количество элементов, которое может иметь контейнер с прежде, чем понадобится повторное резервирование c.reserve(n) Резервирование места по крайней мере для n элементов
Функция reserve() не изменяет количество элементов в контейнере; она влияет только на объем памяти, предварительно резервируемой вектором.
Вызов функции reserve() изменяет емкость вектора, только если требуемое пространство превышает текущую емкость. Если требуемый размер больше текущей емкости, функция reserve() резервирует по крайней мере столько места, сколько затребовано (или несколько больше).
Если требуемый размер меньше или равен существующей емкости, функция reserve() ничего не делает. В частности, вызов функции reserve(), при размере меньшем, чем емкость, не приведет к резервированию контейнером памяти. Таким образом, после вызова функции reserve() емкость будет больше или равна переданному ей аргументу.
В результате вызов функции reserve() никогда не сократит объем контейнера. Точно так же функция-член resize() (см. раздел 9.3.5) изменяет только количество элементов контейнера, а не его емкость. Функцию resize() нельзя использовать для сокращения объема память,
которую контейнер держит в резерве.
В новой библиотеке есть функция shrink_to_fit(), позволяющая запросить контейнеры deque,
vector или string освободить неиспользуемую память. Вызов этой функции означает, что никакой резервной емкости больше не нужно. Однако реализация имеет право проигнорировать этот запрос. Нет никакой гарантии, что вызов функции shrink_to_fit()
освободит память. Функции-члены capacity() и size()
Очень важно понимать различие между емкостью (capacity) и размером (size). Размер — это количество элементов, хранящихся в контейнере в настоящий момент, а емкость — это количество элементов, которое контейнер может содержать, не прибегая к следующей операции резервирования памяти. Следующий код иллюстрирует взаимосвязь размера и емкости: vector<int> ivec;
// размер нулевой; емкость зависит от реализации cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
// присвоить вектору ivec 24 элемента for (vector<int>::size_type ix = 0; ix != 24; ++ix)
Page 453/1103

ivec.push_back(ix);
// размер 24; емкость равна или больше 24, согласно реализации cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
При запуске на компьютере автора эта программа отобразила следующий результат: ivec: size: 0 capacity: 0 ivec: size: 24 capacity: 32
Как известно, пустой вектор имеет нулевой размер, вполне очевидно, что библиотека для пустого вектора также устанавливает нулевую емкость. При добавлении элементов в вектор его размер составляет количество добавленных элементов. Емкость будет, по крайней мере совпадать с размером, но может быть и больше. Конкретный объем резервной емкости зависит от реализации библиотеки. В данной конкретной реализации добавление 24
элементов по одному приводит к созданию емкости 32.
Визуально текущее состояние вектора ivec можно представить так:
Теперь при помощи функции reserve() можно зарезервировать дополнительное пространство.
ivec.reserve(50); // задать емкость 50 элементов (можно и больше)
// размер будет 24, а емкость - 50 или больше, если так определено
// в реализации cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Вывод свидетельствует о том, что вызов функции reserve() зарезервировал именно столько места, сколько было запрошено: ivec: size: 24 capacity: 50
Эту резервную емкость можно впоследствии израсходовать следующим образом:
// добавить элементы, чтобы исчерпать резервную емкость
Page 454/1103

while (ivec.size() != ivec.capacity()) ivec.push_back(0);
// емкость не изменилась, размер и емкость теперь равны cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Результат свидетельствует, что в настоящий момент резервная емкость исчерпана, а размер и емкость равны. ivec: size: 50 capacity: 50
Поскольку использовалась только резервная емкость, в повторном резервировании нет никакой потребности. Фактически, пока не превышена существующая емкость вектора,
никакой необходимости в перераспределении его элементов нет.
Если теперь добавить в вектор новый элемент, то последует повторное резервирование памяти. ivec.push_back(42); // добавить еще один элемент
// размер будет 51, а емкость 51 или больше, если так определено
// в реализации cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Результат выполнения этой части программы имеет следующий вид: ivec: size: 51 capacity: 100
Он свидетельствует о том, что в данной реализации класса vector использована стратегия удвоения текущей емкости при каждом резервировании новой области памяти.
По мере необходимости можно вызвать функцию shrink_to_fit(), запрашивающую освобождение и возвращение операционной системе памяти, ненужной для текущего размера контейнера: ivec.shrink_to_fit(); // запрос на возвращение памяти
// размер остался неизменным; емкость определена реализацией
Page 455/1103

cout << "ivec: size: " << ivec.size()
<< " capacity: " << ivec.capacity() << endl;
Вызов функции shrink_to_fit() является только запросом; нет никакой гарантии того, что память будет действительно возвращена.
Каждая реализация контейнера vector может использовать собственную стратегию резервирования. Однако резервирование новой памяти не должно происходить, пока его емкость не исчерпана.
Вектор может начать повторное резервирование только после выполнения пользователем операции вставки, когда размер равен емкости, вызова функции resize() или reserve() со значением, превышающим текущую емкость. Количество памяти, резервируемое свыше указанного объема, зависит от реализации.
Каждая реализация обязана следовать стратегии, гарантирующей эффективное использование функции push_back() при добавлении элементов в вектор. С технической точки зрения время создания n элементов вектора составляет время выполнения функции push_back() для первоначально пустого вектора, умноженное на n .Упражнения раздела 9.4
Упражнение 9.35. Объясните различие между емкостью вектора и его размером.