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

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

Упражнение 3.12. Есть ли ошибки в следующих определениях векторов?
Объясните, что делают допустимые определения. Объясните, почему некорректны недопустимые определения.
(a) vector<vector<int>> ivec;
(b) vector<string> svec = ivec;
(c) vector<string> svec(10, "null");

Упражнение 3.13. Сколько элементов находится в каждом из следующих векторов? Каковы значения этих элементов?
(a) vector<int> v1; (b) vector<int> v2 (10);
(с) vector<int> v3(10, 42); (d) vector<int> v4{10};
(e) vector<int> v5{10, 42}; (f) vector<string> v6{10};
(g) vector<string> v7{10, "hi"};
3.3.2. Добавление элементов в вектор
Прямая инициализация элементов вектора осуществима только при небольшом количестве исходных значений, при копировании другого вектора и при инициализации всех элементов тем же значением. Но обычно при создании вектора неизвестно ни количество его элементов,
ни их значения. Но даже если все значения известны, то определение большого количества разных начальных значений может оказаться очень громоздким, чтобы располагать его в месте создания вектора.
Если необходим вектор со значениями от 0 до 9, то можно легко использовать списочную инициализацию. Но что если необходимы элементы от 0 до 99 или от 0 до 999? Списочная инициализация была бы слишком громоздкой. В таких случаях лучше создать пустой вектор и использовать его функцию-член push_back(), чтобы добавить элементы во время выполнения. Функция push_back() вставляет переданное ей значение в вектор как новый последний элемент. Рассмотрим пример. vector<int> v2; // пустой вектор for (int i = 0; i != 100; ++i) v2.push_back(i); // добавить последовательность целых чисел в v2
// по завершении цикла v2 имеет 100 элементов со значениями от 0 до 99
Page 130/1103

Хотя заранее известно, что будет 100 элементов, вектор v2 определяется как пустой. Каждая итерация добавляет следующее по порядку целое число в вектор v2 как новый элемент.
Тот же подход используется, если необходимо создать вектор, количество элементов которого до времени выполнения неизвестно. Например, в вектор можно читать введенные пользователем значения.
// читать слова со стандартного устройства ввода и сохранять их
// в векторе как элементы string word; vector<string> text; // пустой вектор while (cin >> word) { text.push_back(word); // добавить слово в текст
}
И снова все начинается с пустого вектора. На сей раз, неизвестное количество значений читается и сохраняется в векторе строк text. Ключевая концепция. Рост вектора эффективен
Стандарт требует, чтобы реализация шаблона vector обеспечивала эффективное добавление элементов во время выполнения. Поскольку рост вектора эффективен, определение вектора сразу необходимого размера зачастую является ненужным и может даже привести к потере производительности. Исключением является случай, когда все элементы нуждаются в одинаковом значении. При разных значениях элементов обычно эффективней определить пустой вектор и добавлять элементы во время выполнения, по мере того, как значения становятся известны. Кроме того, как будет продемонстрировано в разделе 9.4, шаблон vector предоставляет возможности для дальнейшего увеличения производительности при добавлении элементов во время выполнения.
Начало с пустого вектора и добавление элементов во время выполнения кардинально отличается от использования встроенных массивов в языке С и других языках. В частности,
если вы знакомы с языком С или Java, то, вероятно, полагаете, что лучше определить вектор в его ожидаемом размере, но фактически имеет место обратное. Последствия возможности добавления элементов в вектор
Тот факт, что добавление элементов в вектор весьма эффективно, существенно упрощает многие задачи программирования. Но эта простота налагает новые обязательства на наши программы: необходимо гарантировать корректность всех циклов, даже если цикл изменяет размер вектора.
Другое последствие динамического характера векторов станет яснее, когда мы узнаем больше об их использовании. Но есть одно последствие, на которое стоит обратить внимание уже сейчас: по причинам, изложенным в разделе 5.4.3, нельзя использовать серийный оператор for, если тело цикла добавляет элементы в вектор.
Тело серийного оператора for не должно изменять размер перебираемой
Page 131/1103

последовательности. Упражнения раздела 3.3.2
Упражнение 3.14. Напишите программу, читающую последовательность целых чисел из потока cin и сохраняющую их в векторе.
Упражнение 3.15. Повторите предыдущую программу, но на сей раз читайте строки.
3.3.3. Другие операции с векторами
Кроме функции push_back(), шаблон vector предоставляет еще несколько операций,
большинство из которых подобно соответствующим операциям класса string. Наиболее важные из них приведены в табл. 3.5.
Таблица 3.5. Операции с векторами v.empty() Возвращает значение true, если вектор v пуст. В
противном случае возвращает значение false v.size() Возвращает количество элементов вектора v v.push_back(t) Добавляет элемент со значением t в конец вектора v v[n] Возвращает ссылку на элемент в позиции n вектора v v1 = v2 Заменяет элементы вектора v1 копией элементов вектора v2 v1 = {a,b,с ... } Заменяет элементы вектора v1 копией элементов из разделяемого запятыми списка v1 == v2 v1 != v2 Векторы v1 и v2 равны, если они содержат одинаковые элементы в тех же позициях <, <=, >, >= Имеют обычное значение и полагаются на алфавитный порядок
Доступ к элементам вектора осуществляется таким же способом, как и к символам строки: по их позиции в векторе. Например, для обработки все элементов вектора можно использовать серийный оператор for (раздел 3.2.3). vector<int> v{1,2,3,4,5,6,7,8,9}; for (auto &i : v) // для каждого элемента вектора v
//
(обратите внимание: i - ссылка) i *= i; // квадрат значения элемента for (auto i : v) // для каждого элемента вектора v cout << i << " "; // вывод элемента cout << endl;
В первом цикле управляющая переменная i определяется как ссылка, чтобы использовать ее для присвоения новых значений элементам вектора v. Используя спецификатор auto,
Page 132/1103

позволим вывести ее тип автоматически. Этот цикл использует новую форму составного оператора присвоения (раздел 1.4.1). Как известно, оператор += добавляет правый операнд к левому и сохраняет результат в левом операнде. Оператор *= ведет себя точно так же, но перемножает левый и правый операнды, сохраняя результат в левом операнде. Второй серийный оператор for отображает каждый элемент.
Функции-члены empty() и size() вектора ведут себя так же, как и соответствующие функции класса string (раздел 3.2.2): функция empty() возвращает логическое значение, указывающее,
содержит ли вектор какие-нибудь элементы, а функция size() возвращает их количество.
Функция-член size() возвращает значение типа size_type, определенное соответствующим типом шаблона vector.
Чтобы использовать тип size_type, необходимо указать тип, для которого он определен. Для типа vector всегда необходимо указывать тип хранимого элемента (раздел 3.3). vector<int>::size_type // ok vector::size_type // ошибка
Операторы равенства и сравнения вектора ведут себя как соответствующие операторы класса string (раздел 3.2.2). Два вектора равны, если у них одинаковое количество элементов и значения соответствующих элементов совпадают. Операторы сравнения полагаются на алфавитный порядок: если у векторов разные размеры, но соответствующие элементы равны, то вектор с меньшим количеством элементов меньше вектора с большим количеством элементов. Если у элементов векторов разные значения, то их отношения определяются по первым отличающимся элементам.
Сравнить два вектора можно только в том случае, если возможно сравнить элементы этих векторов. Некоторые классы, такие как string, определяют смысл операторов равенства и сравнения. Другие, такие как класс Sales_item, этого не делают. Операции, поддерживаемые классом Sales_item, перечислены в разделе 1.5.1. Они не включают ни операторов равенства,
ни сравнения. В результате нельзя сравнить два вектора объектов класса Sales_item.
Вычисление индекса вектора
Используя оператор индексирования (раздел 3.2.3), можно выбрать указанный элемент.
Подобно строкам, индексирование вектора начинаются с 0; индекс имеет тип size_type соответствующего типа; и если вектор не константен, то в возвращенный оператором индексирования элемент можно осуществить запись. Кроме того, как было продемонстрировано в разделе 3.2.3, можно вычислить индекс и непосредственно обратиться к элементу в данной позиции.
Предположим, имеется набор оценок степеней в диапазоне от 0 до 100. Необходимо рассчитать, сколько оценок попадает в кластер по 10. Между нулем и 100 возможна 101
оценка. Эти оценки могут быть представлены 11 кластерами: 10 кластеров по 10 оценок каждый плюс один кластер для наивысшей оценки 100. Первый кластер подсчитывает оценки от 0 до 9, второй — от 10 до 19 и т.д. Заключительный кластер подсчитывает количество оценок 100.
Таким образом, если введены следующие оценки:
Page 133/1103

42 65 95 100 39 67 95 76 88 76 83 92 76 93 результат их кластеризации должен быть таким:
0 0 0 1 1 0 2 3 2 4 1
Он означает, что не было никаких оценок ниже 30, одна оценка в 30-х, одна в 40-х, ни одной в
50-х, две в 60-х, три в 70-х, две в 80-х, четыре в 90-х и одна оценка 100.
Используем для содержания счетчиков каждого кластера вектор с 11 элементами. Индекс кластера для данной оценки можно определить делением этой оценки на 10. При делении двух целых чисел получается целое число, дробная часть которого усекается. Например,
42/10=4, 65/10=6, а 100/10=10.
Как только индекс кластера будет вычислен, его можно использовать для индексирования вектора и доступа к счетчику, значение которого необходимо увеличить.
// подсчет количества оценок в кластере по десять: 0--9,
//
10--19, ... 90--99, 100 vector<unsigned> scores(11, 0); //
11 ячеек, все со значением 0 unsigned grade; while (cin >> grade) { // читать оценки if (grade <= 100) // обрабатывать только допустимые оценки
++scores[grade/10]; // приращение счетчика текущего кластера
Код начинается с определения вектора для хранения счетчиков кластеров. В данном случае все элементы должны иметь одинаковое значение, поэтому резервируем 11 элементов,
каждый из которых инициализируем значением 0. Условие цикла while читает оценки. В цикле проверяется допустимость значения прочитанной оценки (т.е. оно меньше или равно 100).
Если оценка допустима, то увеличиваем соответствующий счетчик.
Оператор, осуществляющий приращение, является хорошим примером краткости кода С++:
++scores[grade/10]; // приращение счетчика текущего кластера
Это выражение эквивалентно следующему: auto ind = grade/10; //
Page 134/1103

получить индекс ячейки scores[ind] = scores[ind] + 1; // приращение счетчика
Индекс ячейки вычисляется делением значения переменной grade на 10. Полученный результат используется для индексирования вектора scores, что обеспечивает доступ к соответствующему счетчику для этой оценки. Увеличение значения этого элемента означает принадлежность текущей оценки данному диапазону.
Как уже упоминалось, при использовании индексирования следует позаботиться о том, чтобы индексы оставались в диапазоне допустимых значений (см. раздел 3.2.3). В этой программе проверка допустимости подразумевает принадлежность оценки к диапазону 0-100. Таким образом, можно использовать индексы от 0 до 10. Они расположены в пределах от 0 до scores.size() - 1. Индексация не добавляет элементов
Новички в С++ иногда полагают, что индексирование вектора позволяет добавлять в него элементы, но это не так. Следующий код намеревается добавить десять элементов в вектор ivec: vector<int> ivec; // пустой вектор for (decltype(ivec.size()) ix = 0; ix != 10; ++ix) ivec[ix] = ix; // катастрофа: ivec не имеет элементов
Причина ошибки — вектор ivec пуст; в нем нет никаких элементов для индексирования! Как уже упоминалось, правильный цикл использовал бы функцию push_back(): for (decltype(ivec.size()) ix = 0; ix != 10; ++ix) ivec.push_back(ix); // ok: добавляет новый элемент со значением ix
Оператор индексирования вектора (и строки) лишь выбирает существующий элемент; он не может добавить новый элемент.Внимание! Индексировать можно лишь существующие элементы!
Очень важно понять, что оператор индексирования ([]) можно использовать для доступа только к фактически существующим элементам. Рассмотрим пример. vector<int> ivec; // пустой вектор cout << ivec[0]; // ошибка: ivec не имеет элементов!
Page 135/1103

vector<int> ivec2(10); // вектор из 10 элементов cout << ivec2[10]; // ошибка: ivec2 имеет элементы 0...9
Попытка обращения к несуществующему элементу является серьезной ошибкой, которую вряд ли обнаружит компилятор. В результате будет получено случайное значение.
Попытка индексирования несуществующих элементов, к сожалению, является весьма распространенной и грубой ошибкой программирования. Так называемая ошибка переполнения буфера (buffer overflow) — результат индексирования несуществующих элементов. Такие ошибки являются наиболее распространенной причиной проблем защиты приложений.
Наилучший способ гарантировать невыход индекса из диапазона — это избежать индексации вообще. Для этого везде, где только возможно, следует использовать серийный оператор for.
Упражнения раздела 3.3.3
Упражнение 3.16. Напишите программу, выводящую размер и содержимое вектора из упражнения 3.13. Проверьте правильность своих ответов на это упражнение. При неправильных ответах повторно изучите раздел 3.3.1.
Упражнение 3.17. Прочитайте последовательность слов из потока cin и сохраните их в векторе. Прочитав все слова, обработайте вектор и переведите символы каждого слова в верхний регистр. Отобразите преобразованные элементы по восемь слов на строку.
Упражнение 3.18. Корректна ли следующая программа? Если нет, то как ее исправить? vector<int> ivec; ivec[0] = 42;
Упражнение 3.19. Укажите три способа определения вектора и заполнения его десятью элементами со значением 42. Укажите, есть ли предпочтительный способ для этого и почему.
Упражнение 3.20. Прочитайте набор целых чисел в вектор. Отобразите сумму каждой пары соседних элементов. Измените программу так, чтобы она отображала сумму первого и последнего элементов, затем сумму второго и предпоследнего и т.д.
3.4. Знакомство с итераторами
Хотя для доступа к символам строки или элементам вектора можно использовать индексирование, для этого существует и более общий механизм — итераторы (iterator). Как будет продемонстрировано в части II, кроме векторов библиотека предоставляет несколько других видов контейнеров. У всех библиотечных контейнеров есть итераторы, но только некоторые из них поддерживают оператор индексирования. С
технической точки зрения тип string не является контейнерным, но он поддерживает большинство контейнерных операций. Как уже упоминалось, и строки, и векторы
Page 136/1103

предоставляют оператор индексирования. У них также есть итераторы.
Как и указатели (см. раздел 2.3.2), итераторы обеспечивают косвенный доступ к объекту. В
случае итератора этим объектом является элемент в контейнере или символ в строке.
Итератор позволяет выбрать элемент, а также поддерживает операции перемещения с одного элемента на другой. Подобно указателям, итератор может быть допустим или недопустим. Допустимый итератор указывает либо на элемент, либо на позицию за последним элементом в контейнере. Все другие значения итератора недопустимы.
3.4.1. Использование итераторов
В отличие от указателей, для получения итератора не нужно использовать оператор обращения к адресу. Для этого обладающие итераторами типы имеют члены, возвращающие эти итераторы. В частности, они обладают функциями-членами begin() и end(). Функция-член begin() возвращает итератор, который обозначает первый элемент (или первый символ), если он есть.
// типы b и е определяют компилятор; см. раздел 2.5.2
// b обозначает первый элемент контейнера v, а е - элемент
// после последнего auto b = v.begin(), е = v.end();
// b и е имеют одинаковый тип
Итератор, возвращенный функцией end(), указывает на следующую позицию за концом контейнера (или строки). Этот итератор обозначает несуществующий элемент за концом контейнера. Он используется как индикатор, означающий, что обработаны все элементы.
Итератор, возвращенный функцией end(), называют итератором после конца (off-the-end iterator), или сокращенно итератором end. Если контейнер пуст, функция begin() возвращает тот же итератор, что и функция end().
Если контейнер пуст, возвращаемые функциями begin() и end() итераторы совпадают и, оба являются итератором после конца.
Обычно точный тип, который имеет итератор, неизвестен (да и не нужен). В этом примере при определении итераторов b и е использовался спецификатор auto (см. раздел 2.5.2). В
результате тип этих переменных будет совпадать с возвращаемыми функциями-членами begin() и end() соответственно. Не будем пока распространяться об этих типах. Операции с итераторами
Page 137/1103

Итераторы поддерживают лишь несколько операций, которые перечислены в табл. 3.6. Два допустимых итератора можно сравнить при помощи операторов == и !=. Итераторы равны,
если они указывают на тот же элемент или если оба они указывают на позицию после конца того же контейнера. В противном случае они не равны.
Таблица 3.6. Стандартные операции с итераторами контейнера *iter Возвращает ссылку на элемент, обозначенный итератором iter iter->mem Обращение к значению итератора iter и выборка члена mem основного элемента. Эквивалент (*iter).mem ++iter Инкремент итератора iter для обращения к следующему элементу контейнера --iter Декремент итератора iter для обращения к предыдущему элементу контейнера iter1 == iter2 iter1 != iter2 Сравнивает два итератора на равенство (неравенство). Два итератора равны, если они указывают на тот же элемент или на следующий элемент после конца того же контейнера
Подобно указателям, к значению итератора можно обратиться, чтобы получить элемент, на который он ссылается. Кроме того, подобно указателям, можно обратиться к значению только допустимого итератора, который обозначает некий элемент (см. раздел 2.3.2). Результат обращения к значению недопустимого итератора или итератора после конца непредсказуем.
Перепишем программу из раздела 3.2.3, преобразующую строчные символы строки в прописные, с использованием итератора вместо индексирования: string s("some string"); if (s.begin() != s.end()) { // удостовериться, что строка s не пуста auto it = s.begin(); // it указывает на первый символ строки s
*it = toupper(*it); // текущий символ в верхний регистр
}
Как и в первоначальной программе, сначала удостоверимся, что строка s не пуста. В данном случае для этого сравниваются итераторы, возвращенные функциями begin() и end(). Эти итераторы равны, если строка пуста. Если они не равны, то в строке s есть по крайней мере один символ.
В теле оператора if функция begin() возвращает итератор на первый символ, который присваивается переменной it. Обращение к значению этого итератора и передача его функции toupper() позволяет перевести данный символ в верхний регистр. Кроме того,
обращение к значению итератора it слева от оператора присвоения позволяет присвоить символ, возвращенный функцией toupper(), первому символу строки s. Как и в первоначальной программе, вывод будет таким:
Some string Перемещение итератора с одного элемента на другой
Итераторы используют оператор инкремента (оператор ++) (см. раздел 1.4.1) для перемещения с одного элемента на следующий. Операция приращения итератора логически подобна приращению целого числа. В случае целых чисел результатом будет целочисленное значение на единицу больше 1. В случае итераторов результатом будет перемещение
Page 138/1103

итератора на одну позицию.
Поскольку итератор, возвращенный функцией end(), не указывает на элемент, он не допускает ни приращения, ни обращения к значению.
Перепишем программу, изменяющую регистр первого слова в строке, с использованием итератора.
// обрабатывать символы, пока они не исчерпаются,
// или не встретится пробел for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
*it = toupper(*it); // преобразовать в верхний регистр
Этот цикл, подобно таковому в разделе 3.2.3, перебирает символы строки s, останавливаясь,
когда встречается пробел. Но данный цикл использует для этого итератор, а не индексирование.
Цикл начинается с инициализации итератора it результатом вызова функции s.begin(), чтобы он указывал на первый символ строки s (если он есть). Условие проверяет, не достиг ли итератор it конца строки (s.end()). Если это не так, то проверяется следующее условие, где обращение к значению итератора it, возвращающее текущий символ, передается функции isspace(), чтобы выяснить, не пробел ли это. В конце каждой итерации выполняется оператор
++it, чтобы переместить итератор на следующий символ строки s.
У этого цикла то же тело, что и у последнего оператора if предыдущей программы.
Обращение к значению итератора it используется и для передачи текущего символа функции toupper(), и для присвоения полученного результата символу, на который указывает итератор it. Ключевая концепция. Обобщенное программирование
Программисты, перешедшие на язык С++ с языка С или Java, могли бы быть удивлены тем,
что в данном цикле for был использован оператор !=, а не <. Программисты С++ используют оператор != исключительно по привычке. По этой же причине они используют итераторы, а не индексирование: этот стиль программирования одинаково хорошо применим к контейнерам различных видов, предоставляемых библиотекой.
Как уже упоминалось, только у некоторых библиотечных типов, vector и string, есть оператор индексирования. Тем не менее у всех библиотечных контейнеров есть итераторы, для которых определены операторы == и !=. Однако большинство их итераторов не имеют оператора <. При обычном использовании итераторов и оператора != можно не заботиться о точном типе обрабатываемого контейнера. Типы итераторов
Подобно тому, как не всегда известен точный тип size_type элемента вектора или строки (см.
раздел 3.2.2), мы обычно не знаем (да и не обязаны знать) точный тип итератора. Как и в случае с типом size_type, библиотечные типы, у которых есть итераторы, определяют типы по имени iterator и const_iterator, которые представляют фактические типы итераторов. vector<int>::iterator it; //
Page 139/1103

it позволяет читать и записывать
// в элементы вектора vector<int> string::iterator it2; // it2 позволяет читать и записывать
// символы в строку vector<int>::const_iterator it3; // it3 позволяет читать, но не
// записывать элементы string::const_iterator it4; // it4 позволяет читать, но не
// записывать символы
Тип const_iterator ведет себя как константный указатель (см. раздел 2.4.2). Как и константный указатель, тип const_iterator позволяет читать, но не писать в элемент, на который он указывает; объект типа iterator позволяет и читать, и записывать. Если вектор или строка являются константой, можно использовать итератор только типа const_iterator. Если вектор или строка на являются константой, можно использовать итератор и типа iterator, и типа const_iterator. Терминология. Итераторы и типы итераторов
Термин итератор (iterator) используется для трех разных сущностей. Речь могла бы идти о концепции итератора, или о типе iterator, определенном классом контейнера, или об объекте итератора.
Следует уяснить, что существует целый набор типов, связанных концептуально. Тип относится к итераторам, если он поддерживает общепринятый набор функций. Эти функции позволяют обращаться к элементу в контейнере и переходить с одного элемента на другой.
Каждый класс контейнера определяет тип по имени iterator, который обеспечивает действия концептуального итератора. Функции begin() и end()
Тип, возвращаемый функциями begin() и end(), зависит от константности объекта, для которого они были вызваны. Если объект является константой, то функции begin() и end()
возвращают итератор типа const_iterator; если объект не константа, они возвращают итератор типа iterator. vector<int> v;
Page 140/1103

const vector<int> cv; auto it1 = v.begin(); // it1 имеет тип vector<int>::iterator auto it2 = cv.begin(); // it2 имеет тип vector<int>::const_iterator
Зачастую это стандартное поведение желательно изменить. По причинам, рассматриваемым в разделе 6.2.3, обычно лучше использовать константный тип (такой как const_iterator), когда необходимо только читать, но не записывать в объект. Чтобы позволить специально задать тип const_iterator, новый стандарт вводит две новые функции, cbegin() и cend(): auto it3 = v.cbegin(); // it3 имеет тип vector<int>::const_iterator
Подобно функциям-членам begin() и end(), эти функции-члены возвращают итераторы на первый и следующий после последнего элементы контейнера. Но независимо от того,
является ли вектор (или строка) константой, они возвращают итератор типа const_iterator.
Объединение обращения к значению и доступа к члену
При обращении к значению итератора получается объект, на который указывает итератор.
Если этот объект имеет тип класса, то может понадобиться доступ к члену полученного объекта. Например, если есть вектор строк, то может понадобиться узнать, не пуст ли некий элемент. С учетом, что it — это итератор данного вектора, можно следующим образом проверить, не пуста ли строка, на которую он указывает:
(*it).empty()
По причинам, рассматриваемым в разделе 4.1.2, круглые скобки в части (*it).empty()
необходимы. Круглые скобки требуют применить оператор обращения к значению к итератору it, а к результату применить точечный оператор (см. раздел 1.5.2). Без круглых скобок точечный оператор относился бы к итератору it, а не к полученному объекту.
(*it).empty() // обращение к значению it и вызов функции-члена empty()
// полученного объекта
*it.empty() // ошибка: попытка вызова функции-члена empty()
// итератора it,
// но итератор it не имеет функции-члена empty()
Второе выражение интерпретируется как запрос на выполнение функции-члена empty()
Page 141/1103

объекта it. Но it — это итератор, и он не имеет такой функции. Следовательно, второе выражение ошибочно.
Чтобы упростить такие выражения, язык предоставляет оператор стрелки (arrow operator) (оператор ->). Оператор стрелки объединяет обращение к значению и доступ к члену. Таким образом, выражение it->mem является синоним выражения (*it).mem.
Предположим, например, что имеется вектор vector<string> по имени text, содержащий данные из текстового файла. Каждый элемент вектора — это либо предложение, либо пустая строка, представляющая конец абзаца. Если необходимо отобразить содержимое первого параграфа из вектора text, то можно было бы написать цикл, который перебирает вектор text,
пока не встретится пустой элемент.
// отобразить каждую строку вектора text до первой пустой строки for (auto it = text.cbegin(); it != text.cend() && !it->empty(); ++it) cout << *it << endl;
Код начинается с инициализации итератора it указанием на первый элемент вектора text.
Цикл продолжается до тех пор, пока не будут обработаны все элементы вектора text или пока не встретится пустой элемент. Пока есть элементы и текущий элемент не пуст, он отображается. Следует заметить, что, поскольку цикл только читает элементы, но не записывает их, здесь для управления итерацией используются функции cbegin() и cend().
Некоторые операции с векторами делают итераторы недопустимыми
В разделе 3.3.2 упоминался тот факт, что векторы способны расти динамически. Обращалось также внимание на то, что нельзя добавлять элементы в вектор в цикле серийного оператора for. Еще одно замечание: любая операция, такая как вызов функции push_back(), изменяет размер вектора и способна сделать недопустимыми все итераторы данного вектора. Более подробная информация по этой теме приведена в разделе 9.3.6.
На настоящий момент достаточно знать, что использующие итераторы цикла не должны добавлять элементы в контейнер, с которым связаны итераторы.
3.4.2. Арифметические действия с итераторами
Инкремент итератора перемещает его на один элемент. Инкремент поддерживают итераторы всех библиотечных контейнеров. Аналогично операторы == и != можно использовать для сравнения двух допустимых итераторов (см. раздел 3.4) любых библиотечных контейнеров.
Итераторы строк и векторов поддерживают дополнительные операции, позволяющие перемещать итераторы на несколько позиций за раз. Они также поддерживают все операторы сравнения. Эти операторы зачастую называют арифметическими действиями с итераторами (iterator arithmetic). Они приведены в табл. 3.7.
Page 142/1103

Таблица 3.7. Операции с итераторами векторов и строк iter + n iter - n Добавление
(вычитание) целочисленного значения n к (из) итератору возвращает итератор, указывающий на элемент n позиций вперед (назад) в пределах контейнера. Полученный итератор должен указывать на элемент или на следующую позицию за концом того же контейнера iter1 += n iter1 -= n Составные операторы присвоения со сложением и вычитанием итератора.
Присваивает итератору iter1 значение на n позиций больше или меньше предыдущего iter1 - iter2 Вычитание двух итераторов возвращает значение, которое, будучи добавлено к правому итератору, вернет левый. Итераторы должны указывать на элементы или на следующую позицию за концом того же контейнера >, >=, <, <= Операторы сравнения итераторов. Один итератор меньше другого, если он указывает на элемент, расположенный в контейнере ближе к началу. Итераторы должны указывать на элементы или на следующую позицию за концом того же контейнера Арифметические операции с итераторами
К итератору можно добавить (или вычесть из него) целочисленное значение. Это вернет итератор, перемещенный на соответствующее количество позиций вперед (или назад). При добавлении или вычитании целочисленного значения из итератора результат должен указывать на элемент в том же векторе (или строке) или на следующую позицию за концом того же вектора (или строки). В качестве примера вычислим итератор на элемент, ближайший к середине вектора:
// вычислить итератор на элемент, ближайший к середине вектора vi auto mid = vi.begin() + vi.size() / 2;
Если у вектора vi 20 элементов, то результатом vi.size()/2 будет 10. В данном случае переменной mid будет присвоено значение, равное vi.begin() + 10. С учетом, что нумерация индексов начинаются с 0, это тот же элемент, что и vi[10], т.е. элемент на десять позиций от начала.
Кроме сравнения двух итераторов на равенство, итераторы векторов и строк можно сравнить при помощи операторов сравнения (<, <=, >, >=). Итераторы должны быть допустимы, т.е. должны обозначать элементы (или следующую позицию за концом) того же вектора или строки. Предположим, например, что it является итератором в том же векторе,
что и mid. Следующим образом можно проверить, указывает ли итератор it на элемент до или после итератора mid: if (it < mid)
// обработать элементы в первой половине вектора vi
Можно также вычесть два итератора, если они указывают на элементы (или следующую позицию за концом) того же вектора или строки. Результат — дистанция между итераторами.
Под дистанцией подразумевается значение, на которое следует изменить один итератор,
чтобы получить другой. Результат имеет целочисленный знаковый тип difference_type. Тип difference_type определен и для вектора, и для строки. Этот тип знаковый, поскольку результатом вычитания может оказаться отрицательное значение. Использование арифметических действий с итераторами
Классическим алгоритмом, использующим арифметические действия с итераторами,
является
Page 143/1103

двоичный поиск (binary search). Двоичный (бинарный) поиск ищет специфическое значение в отсортированной последовательности. Алгоритм работает так: сначала исследуется элемент,
ближайший к середине последовательности. Если это искомый элемент, работа закончена. В
противном случае, если этот элемент меньше искомого, поиск продолжается только среди элементов после исследованного. Если средний элемент больше искомого, поиск продолжается только в первой половине. Вычисляется новый средний элемент оставшегося диапазона, и действия продолжаются, пока искомый элемент не будет найден или пока не исчерпаются элементы.
Используя итераторы, двоичный поиск можно реализовать следующим образом:
// текст должен быть отсортирован
// beg и end ограничивают диапазон, в котором осуществляется поиск auto beg = text.begin(), end = text.end(); auto mid = text.begin() + (end - beg)/2; // исходная середина
// пока еще есть элементы и искомый не найден while (mid != end && *mid != sought) { if (sought < *mid) // находится ли искомый элемент в первой половине? end = mid; // если да, то изменить диапазон, игнорируя вторую
// половину else // искомый элемент во второй половине beg = mid + 1; // начать поиск с элемента сразу после середины mid = beg + (end - beg)/2; // новая середина
}
Код начинается с определения трех итераторов: beg будет первым элементом в диапазоне,
end — элементом после последнего, a mid — ближайшим к середине. Инициализируем эти
Page 144/1103

итераторы значениями, охватывающими весь диапазон вектора vector<string> по имени text.
Сначала цикл проверяет, не пуст ли диапазон. Если значение итератора mid равно текущему значению итератора end, то элементы для поиска исчерпаны. В таком случае условие ложно и цикл while завершается. В противном случае итератор mid указывает на элемент, который проверяется на соответствие искомому. Если это так, то цикл завершается.
Если элементы все еще есть, код в цикле while корректирует диапазон, перемещая итератор end или beg. Если обозначенный итератором mid элемент больше, чем sought, то если искомый элемент и есть в векторе, он находится перед элементом, обозначенным итератором mid. Поэтому можно игнорировать элементы после середины, что мы и делаем,
присваивая значение итератора mid итератору end. Если значение *mid меньше, чем sought,
элемент должен быть в диапазоне элементов после обозначенного итератором mid. В данном случае диапазон корректируется присвоением итератору beg позиции сразу после той, на которую указывает итератор mid. Уже известно, что mid не указывает на искомый элемент,
поэтому его можно исключить из диапазона.
В конце цикла while итератор mid будет равен итератору end либо будет указывать на искомый элемент. Если итератор mid равен end, то искомого элемента нет в векторе text.
Упражнения раздела 3.4.2
Упражнение 3.24. Переделайте последнее упражнение раздела 3.3.3 с использованием итераторов.
Упражнение 3.25. Перепишите программу кластеризации оценок из раздела 3.3.3 с использованием итераторов вместо индексации.