Язык программирования C Пятое издание
 Скачать 1.85 Mb.
|
|
Упражнение 10.39. Итератором какой категории обладает список? А вектор? Упражнение 10.40. Итераторы какой категории нужны алгоритму copy()? А алгоритмам reverse() и unique()? 10.5.2. Параметрическая схема алгоритмов Эта классификация алгоритмов основана на соглашениях об именах параметров. Понимание этих соглашений поможет в изучении новых алгоритмов: зная, что означает имя данного параметра, можно догадаться, какие операции выполняет соответствующий алгоритм. Большинство алгоритмов получают параметры в одной из четырех форм: алг (beg, end, другие параметры ); алг (beg, end, dest, другие параметры ); алг (beg, end, beg2, другие параметры ); Page 519/1103 алг (beg, end, beg2, end2, другие параметры ); где алг — это имя алгоритма, а параметры beg и end обозначают исходный диапазон элементов, с которыми работает алгоритм. Хотя почти все алгоритмы получают исходный диапазон, присутствие других параметров зависит от выполняемых действий. Как правило, остальные параметры, dest, beg2 и end2, также являются итераторами. Кроме них, некоторые алгоритмы получают дополнительные параметры, не являющиеся итераторами.Алгоритмы с одним итератором назначения Параметр dest (destination — назначение) — это итератор, обозначающий получателя, используемого для хранения результата. Алгоритмы подразумевают, что способны безопасно записать в последовательность назначения столько элементов, сколько необходимо. Алгоритмы, осуществляющие запись по итератору вывода, подразумевают, что получатель достаточно велик для содержания вывода. Если dest является итератором контейнера, алгоритм записывает свой результат в уже существующие элементы контейнера. Как правило, итератор dest связан с итератором вставки (см. раздел 10.4.1) или итератором ostream_iterator (см. раздел 10.4.2). Итератор вставки добавляет новые элементы в контейнер, гарантируя, таким образом, достаточную емкость. Итератор ostream_iterator осуществляет запись в поток вывода, а следовательно, тоже не создает никаких проблем независимо от количества записываемых элементов. Алгоритмы с двумя итераторами, указывающими исходную последовательность Алгоритмы, получающие один параметр (beg2) или два параметра (beg2 и end2), используют эти итераторы для обозначения второго исходного диапазона. Как правило, для выполнения необходимых действий эти алгоритмы используют элементы второго диапазона вместе с элементами исходного. Когда алгоритм получает параметры beg2 и end2, эти итераторы обозначают весь второй диапазон. Такой алгоритм получает два полностью определенных диапазона: исходный диапазон, обозначенный итераторами [beg, end), а также второй, исходный диапазон, обозначенный итераторами [beg2, end2). Алгоритмы, получающие только итератор beg2 (но не end2), рассматривают итератор beg2 как указывающий на первый элемент во втором исходном диапазоне. Конец этого диапазона не определен. В этом случае алгоритмы подразумевают, что диапазон, начинающийся с элемента, указанного итератором beg2, имеет, по крайней мере, такой же размер, что и диапазон, обозначенный итераторами beg и end. Алгоритмы, получающие один параметр beg2, подразумевают , что последовательность, начинающаяся с элемента, указанного итератором beg2, имеет такой же размер, как и диапазон, обозначенный итераторами beg и end. 10.5.3. Соглашения об именовании алгоритмов Кроме соглашений об именовании параметров, алгоритмы также имеют набор однозначных соглашений об именовании перегруженных версий. Эти соглашения учитывают то, как Page 520/1103 предоставляется оператор, используемый вместо принятого по умолчанию оператора < или ==, а также то, используется ли алгоритм для исходной последовательности или отдельного получателя. Некоторые алгоритмы используют перегруженные версии для передачи предиката Как правило, перегружаются алгоритмы, которые получают предикат для использования вместо оператора < или == и не получающие других аргументов. Одна версия функции использует для сравнения элементов оператор типа элемента, а вторая получает дополнительный параметр, являющийся предикатом, используемым вместо оператора < или ==: unique(beg, end); // использует для сравнения элементов оператор == unique(beg, end, comp); // использует для сравнения элементов // предикат comp Оба вызова переупорядочивают переданную последовательность, удаляя смежные повторяющиеся элементы. Первая версия для проверки на совпадение использует оператор == типа элемента, а вторая вызывает для этого предикат comp. Поскольку эти версии функции отличаются количеством аргументов, нет никакой неоднозначности (см. раздел 6.4) относительно версии вызываемой функции. Алгоритмы с версиями _if У алгоритмов, получающих значение элемента, обычно есть вторая (не перегруженная) версия, получающая предикат (см. раздел 10.3.1) вместо значения. Получающие предикат алгоритмы имеют суффикс _if: find(beg, end, val); // найти первый экземпляр val в исходном диапазоне find_if(beg, end, pred); // найти первый экземпляр, для // которого pred возвращает true Оба алгоритма находят в исходном диапазоне первый экземпляр заданного элемента. Алгоритм find() ищет указанное значение, а алгоритм find_if() — значение, для которого предикат pred возвратит значение, отличное от нуля. Эти алгоритмы предоставляют вторую именованную версию, а не перегруженную, поскольку обе версии алгоритма получают то же количество аргументов. Перегрузка была бы неоднозначна и возможна лишь в некоторых случаях. Чтобы избежать любых неоднозначностей, библиотека предоставляет отдельные именованные версии этих алгоритмов. Различия между копирующими и не копирующими версиями По умолчанию переупорядочивающие элементы алгоритмы записывают результирующую последовательность в исходный диапазон. Эти алгоритмы предоставляют вторую версию, Page 521/1103 способную записывать результат по указанному назначению. Как уже упоминалось, пригодные для записи по назначению алгоритмы имеют в имени суффикс _copy (см. раздел 10.2.2): reverse(beg, end); // обратить порядок элементов в исходном диапазоне reverse_copy(beg, end, dest); // скопировать элементы по назначению в // обратном порядке Некоторые алгоритмы предоставляют и версии _copy, и _if. Эти версии получают и итератор назначения, и предикат: // удаляет нечетные элементы из v1 remove_if(v1.begin(), v1.end(), [](int i) { return i % 2; }); // копирует только четные элементы из v1 в v2; v1 неизменен remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i) { return i % 2; }); Для определения нечетности элемента оба вызова используют лямбда-выражение (см. раздел 10.3.2). В первом случае нечетные элементы удаляются из самой исходной последовательности. Во втором не нечетные (четные) элементы копируются из исходного диапазона в вектор v2. Упражнения раздела 10.5.3 Упражнение 10.41. Исходя только из имен алгоритмов и их аргументов, опишите действия, выполняемые каждым из следующих библиотечных алгоритмов: replace(beg, end, old_val, new_val); replace_if(beg, end, pred, new_val); replace_copy(beg, end, dest, old_val, new_val); replace_copy_if(beg, end, dest, pred, new_val); 10.6. Алгоритмы, специфические для контейнеров В отличие от других контейнеров, контейнеры list и forward_list определяют несколько алгоритмов в качестве членов. В частности, тип list определяют собственные версии Page 522/1103 алгоритмов sort(), merge(), remove(), reverse() и unique(). Обобщенная версия алгоритма sort() требует итераторов произвольного доступа. В результате она не может использоваться с контейнерами list и forward_list, поскольку эти типы предоставляют двунаправленные и прямые итераторы соответственно. Обобщенные версии других алгоритмов, определяемых типом list, вполне применимы со списками, но ценой производительности. Эти алгоритмы меняют элементы в исходной последовательности. Список может "поменять" свои элементы, поменяв ссылки на элементы, а не перемещая значения этих элементов. В результате специфические для списка версии этих алгоритмов могут обеспечить намного лучшую производительность, чем соответствующие обобщенные версии. Эти специфические для списка функции приведены в табл. 10.6. В ней нет обобщенных алгоритмов, которые получают соответствующие итераторы и выполняются одинаково эффективно как для других контейнеров, так и для контейнеров list и forward_list. Предпочтительней использовать алгоритмы-члены классов list и forward_list, а не их обобщенные версии. Таблица 10.6. Алгоритмы-члены классов list и forward_list Эти функции возвращают void. lst.merge(lst2) lst.merge(lst2, comp) Объединяет элементы списков lst2 и lst. Оба списка должны быть отсортированы. Элементы из списка lst2 удаляются, и после объединения список lst2 оказывается пустым. Возвращает тип void. В первой версии используется оператор <, а во второй — указанная функция сравнения lst.remove(val) lst.remove_if(pred) При помощи функции lst.erase() удаляет каждый элемент, значение которого равно переданному значению, или для которого указанный унарный предикат возвращает значение, отличное от нуля lst.reverse() Меняет порядок элементов списка lst на обратный lst.sort() lst.sort(comp) Сортирует элементы списка lst, используя оператор < или другой заданный оператор сравнения lst.unique() lst.unique(pred) При помощи функции lst.erase() удаляет расположенные рядом элементы с одинаковыми значениями. Вторая версия использует заданный бинарный предикат Алгоритм-член splice() Типы списков определяют также алгоритм splice(), описанный в табл. 10.7. Этот алгоритм специфичен для списочных структур данных. Следовательно, обобщенная версия этого алгоритма не нужна. Таблица 10.7. Аргументы алгоритма-члена splice() классов list и forward_list lst.splice( аргументы ) или flst.splice_after( аргументы ) (p, lst2) p — итератор на элемент списка lst или итератор перед элементом списка flst. Перемещает все элементы из списка lst2 в список lst непосредственно перед позицией p или непосредственно после в списке flst. Удаляет элементы из списка lst2. Список lst2 должен иметь тот же тип, что и lst (или flst), и не может быть тем же списком (p, lst2, p2) p2 — допустимый итератор в списке lst2. Перемещает элемент, обозначенный итератором p2, в список lst или элемент после обозначенного итератором p2 в списке flst. Список lst2 может быть тем же списком, что и lst или flst (p, lst2, b, е) b и е обозначают допустимый диапазон в списке lst2. Перемещает элементы в заданный диапазон из списка lst2. Списки lst2 и lst (или flst) могут быть тем же списком, но итератор p не должен указывать на элемент в заданном диапазоне Специфические для списка функции, изменяющие контейнер Большинство специфических для списков алгоритмов подобны (но не идентичны) их Page 523/1103 обобщенным аналогам. Но кардинально важное различие между специфическими и обобщенными версиями в том, что специфические версии изменяют базовый контейнер. Например, специфическая версия алгоритма remove() удаляет указанные элементы. Специфическая версия алгоритма unique() удаляет второй и последующий дубликаты элемента. Аналогично алгоритмы merge() и splice() деструктивны к своим аргументам. Например, обобщенная версия функции merge() запишет объединенную последовательность по заданному итератору назначения; две исходных последовательности останутся неизменны. Специфическая для списка функция merge() разрушит заданный список — элементы будут удаляться из списка аргумента по мере их объединения в объект, для которого был вызван аргумент merge(). После объединения элементы из обоих списков продолжают существовать, но принадлежат уже одному списку. Упражнения раздела 10.6 Упражнение 10.42. Переделайте программу, устранявшую повторяющиеся слова, написанную в разделе 10.2.3, так, чтобы использовался список, а не вектор. Резюме Стандартная библиотека определяет порядка ста независимых от типа алгоритмов, работающих с последовательностями. Последовательности могут быть элементами контейнера библиотечного типа, встроенного массива или созданного (например, при чтении или записи в поток). Алгоритмы достигают независимости от типа, работая только с итераторами. Большинство алгоритмов получает их как первые два аргумента, обозначающие диапазон элементов. К дополнительным аргументам может относиться итератор вывода, обозначающий получателя, или другой итератор, или пара итераторов, обозначающая вторую исходную последовательность. Итераторы подразделяются на пять категорий в зависимости от поддерживаемых ими функциональных возможностей. Категории итераторов: ввода, вывода, прямой, двунаправленный и произвольного доступа. Итератор относится к определенной категории, если он поддерживает функциональные возможности, обязательные для итератора данной категории. Подобно категоризации итераторов по их функциональным возможностям, параметры итераторов для алгоритмов классифицируются по функциональным возможностям требуемых для них итераторов. Алгоритмам, которые только читают из последовательности, достаточно итератора ввода. Алгоритмам, которые пишут по итератору назначения, требуются итераторы вывода и т.д. Алгоритмы никогда непосредственно не изменяют размер последовательности, с которой они работают. Они могут скопировать элементы из одной позиции в другую, но не могут самостоятельно добавить или удалить элемент. Хотя алгоритмы не могут добавлять элементы в последовательность, итератор вставки может создавать их. Итератор вставки связан с контейнером. При присвоении значения типа элемента контейнера итератору вставки он добавляет данный элемент в контейнер. Контейнеры forward_list и list определяют собственные версии некоторых из обобщенных алгоритмов. В отличие от обобщенных алгоритмов, эти специфические версии изменяют Page 524/1103 переданные им списки. Термины Адаптер back_inserter. Адаптер итератора, который, получив ссылку на контейнер, создает итератор вставки, использующий функцию push_back() для добавления элементов в указанный контейнер. Адаптер front_inserter. Адаптер итератора, который, получив ссылку на контейнер, создает итератор вставки, использующий функцию push_front() для добавления элементов в начало указанного контейнера. Адаптер inserter. Адаптер итератора, который, получив итератор и ссылку на контейнер, создает итератор вставки, используемый функцией insert() для добавления элементов непосредственно перед элементом, указанным данным итератором. Бинарный предикат (binary predicate). Предикат с двумя параметрами. Вызываемый объект (callable object). Объект, способный быть левым операндом оператора вызова. К вызываемым объектам относятся указатели на функции, лямбда-выражения и объекты классов, определяющих перегруженные версии оператора вызова. Двунаправленный итератор (bidirectional iterator). Поддерживает те же операции, что и прямые итераторы, плюс способность использовать оператор -- для перемещения по последовательности назад. Итератор istream_iterator. Потоковый итератор, обеспечивающий чтение из потока ввода. Итератор ostream_iterator. Потоковый итератор, обеспечивающий запись в поток вывода. Итератор ввода (input iterator). Итератор, позволяющий читать, но не записывать элементы. Итератор вставки (insert iterator). Итератор, использующий функции контейнера для добавления элементов в данный контейнер. Итератор вывода (output iterator). Итератор, позволяющий записывать, но не обязательно читать элементы. Итератор перемещения (move iterator). Итератор, позволяющий перемещать элементы, а не копировать их. Итераторы перемещения рассматриваются в главе 13. Итератор прямого доступа (random-access iterator). Поддерживает те же операции, что и двунаправленный итератор, плюс способность использовать операторы сравнения для выяснения позиций двух итераторов относительно друг друга, а также способность осуществлять с итераторами арифметические действия, обеспечивая таким образом произвольный доступ к элементам. Категории итераторов (iterator categories). Концептуальная организация итераторов на основании поддерживаемых ими операций. Категории итераторов составляют иерархию, в которой более мощные итераторы предоставляют те же операции, что и менее мощные. Пока итератор обеспечивает, по крайней мере, достаточный уровень операций, он вполне применим. Например, некоторым алгоритмам требуются только итераторы ввода. Такие алгоритмы могут быть применены к любому другому итератору, который обладает Page 525/1103 возможностями, не ниже, чем у итератора вывода. Алгоритмы, которым необходимы итераторы прямого доступа, применимы только для тех итераторов, которые поддерживают операции прямого доступа. Лямбда-выражение (lambda expression). Вызываемый блок кода. Лямбды немного похожи на безымянные встраиваемые функции. Они начинается со списка захвата, позволяющего лямбда-выражению получать доступ к переменным в содержащей функции. Подобно функции, имеет список параметров (возможно пустой), тип возвращаемого значения и тело функции. У лямбда-выражения может отсутствовать тип возвращаемого значения. Если тело функции представляет собой одиночный оператор return, тип возвращаемого значения выводится из типа возвращаемого объекта. В противном случае типом пропущенного возвращаемого значения по умолчанию принимается void. Обобщенный алгоритм (generic algorithm). Алгоритм, не зависящий от типа контейнера. Потоковый итератор (stream iterator). Итератор, который может быть связан с потоком. Предикат (predicate). Функция, которая возвращает значение типа bool (логическое) или допускающее преобразование в него. Зачастую используется обобщенными алгоритмами для проверки элементов. Используемые библиотекой предикаты являются либо унарными (получающими один аргумент), либо бинарными (получающими два аргумента). Прямой итератор (forward iterator). Итератор, позволяющий читать и записывать элементы, но не поддерживающий оператор --. Реверсивный итератор (reverse iterator). Итератор, позволяющий перемещаться по последовательности назад. У этих итераторов операторы ++ и -- имеют противоположный смысл. Список захвата (capture list). Часть лямбда-выражения, определяющая переменные из окружающего контекста, к которым может обращаться лямбда-выражение. Унарный предикат (unary predicate). Предикат с одним параметром. Функция bind(). Библиотечная функция, связывающая один или несколько аргументов с вызываемым выражением. Функция bind() определена в заголовке functional. Функция cref(). Библиотечная функция, возвращающая копируемый объект, содержащий ссылку на константный объект типа, не допускающего копирования. Функция ref(). Библиотечная функция, создающая копируемый объект из ссылки на объект типа, не допускающего копирования. Глава 11 Ассоциативные контейнеры Ассоциативные контейнеры кардинально отличаются от последовательных: элементы в ассоциативном контейнере хранятся и предоставляются по ключу. Элементы последовательного контейнера, напротив, хранятся и предоставляются последовательно, по их позиции в контейнере. Хотя поведение ассоциативных контейнеров по большей части одинаково, у Page 526/1103 последовательных контейнеров оно отличается и зависит от способа использования ключей. Ассоциативные контейнеры (associative container) обеспечивают быстрый поиск и предоставление элементов по ключу. Двумя первичными типами ассоциативных контейнеров являются map (карта) и set (набор). Элементами контейнера map являются пары ключ-значение (key-value pair): ключ выступает в роли индекса, а значение представляет собой хранимые в контейнере данные. Контейнер set содержит только ключи и предоставляет эффективные способы запроса на проверку наличия определенного ключа. Набор можно было бы использовать для хранения слов, которые следует проигнорировать при некой обработке текста. Карту можно использовать для словаря: слово было бы ключом, а его определение — значением. Библиотека предоставляет восемь ассоциативных контейнеров (табл. 11.1), которые различаются по трем факторам: (1) они являются набором (set) или картой map; (2) они требуют уникальных ключей или допускает их совпадение; (3) они хранят элементы упорядочено или нет. В именах контейнеров, допускающих совпадение ключей, присутствует слово multi; имена контейнеров, не упорядочивающих хранимые ключи начинаются со слова unordered. Следовательно, unordered_multi_set — это набор, не требующий уникальных ключей и хранящий элементы неупорядоченными, в то время как set — это набор с уникальными ключами, которые хранятся упорядочено. Для организации своих элементов неупорядоченные контейнеры используют хеш-функцию. Подробно хеш-функции рассматриваются в разделе 11.4. Таблица 11.1. Типы ассоциативных контейнеров Элементы упорядочиваются по ключу map Ассоциативный массив, хранящий пары ключ-значение set Контейнер, в котором ключ является значением multimap Карта, допускающая совпадение ключей multiset Набор, допускающий совпадение ключей Неупорядоченные коллекции unordered_map Карта, организованная по хеш-функции unordered_set Набор, организованный по хеш-функции unordered_multimap Хешированная карта; ключи могут повторяться unordered multiset Хешированный набор; ключи могут повторяться Типы map и multimap определены в заголовке map; классы set и multiset — в заголовке set; неупорядоченные версии контейнеров определены в заголовках unordered_map и unordered_set соответственно. 11.1. Использование ассоциативных контейнеров Хотя большинство программистов знакомы с такими структурами данных, как векторы и списки, многие из них никогда не используют ассоциативные структуры данных. Прежде чем перейти к подробностям того, как библиотека поддерживает эти типы, имеет смысл начать с примеров использования этих контейнеров. Карта (тип map) — это коллекция пар ключ-значение. Например, каждая пара может содержать имя человека как ключ и номер его телефона как значение. О такой структуре данных говорят, что она "сопоставляет имена с номерами телефонов". Тип map зачастую называют ассоциативным массивом (associative array). Ассоциативный массив похож на обычный массив, но его индексы не обязаны быть целыми числами. Значения в карте находят по Page 527/1103 ключу, а не по их позиции. В карте имен и номеров телефонов имя человека использовалось бы как индекс для поиска номера телефона этого человека. В отличие от карты, набор — это просто коллекция ключей. Набор полезен тогда, когда необходимо знать, имеется ли в нем значение. Например, банк мог бы определить набор bad_checks для хранения имен личностей, которые выписывали фальшивые чеки. Прежде чем принять чек, этот банк запросил бы набор bad_checks и убедился, есть ли в нем имя клиента. Использование контейнера map Классическим примером применения ассоциативного массива является программа подсчета слов: // подсчитать, сколько раз каждое слово встречается во вводе map<string, size_t> word_count; // пустая карта строк и чисел string word; while (cin >> word) ++word_count[word]; // получить и прирастить счетчик слов for (const auto &w : word_count) // для каждого элемента карты // отобразить результаты cout << w.first << " occurs " << w.second << ((w.second >1) ? " times" : " time") << endl; Эта программа читает ввод и сообщает, сколько раз встречается каждое слово. Подобно последовательным контейнерам, ассоциативные контейнеры являются шаблонами (см. раздел 3.3). Чтобы определить карту, следует указать типы ключа и значения. В этой программе карта хранит элементы, ключи которых имеют тип string, а значения — тип size_t (см. раздел 3.5.2). При индексации карты word_count строка используется как индекс, а возвращаемый счетчик типа size_t связан с этой строкой. Цикл while читает слова со стандартного устройства ввода по одному за раз. Он использует каждое слово для индексирования карты word_count. Если слова еще нет в карте, оператор индексирования создает новый элемент, ключом которого будет слово, а значением 0. Независимо от того, должен ли быть создан элемент, его значение увеличивается. Как только весь ввод прочитан, серийный оператор for (см. раздел 3.2.3) перебирает карту выводя каждое слово и соответствующий счетчик. При получении элемента из карты возвращается объект типа pair (пара), рассматриваемого в разделе 11.2.3 (стр. 545). Если не вдаваться в подробности, то pair — это шаблон типа, Page 528/1103 который содержит две открытые переменные-члена по имени first (первый) и second (второй). У используемых картой пар член first является ключом, a second — соответствующим значением. Таким образом, оператор вывода должен отобразить каждое слово и связанный с ним счетчик. Если бы эта программа была запущена для текста первого параграфа данного раздела, то вывод был бы таким: Although occurs 1 time Before occurs 1 time an occurs 1 time and occurs 1 time ... Использование контейнера set Логичным усовершенствованием создаваемой программы будет игнорирование таких распространенных слов, как "the", "and", "or" и т.д. Для хранения игнорируемых слов будет использован набор, а подсчитываться будут только те слова, которые отсутствуют в этом наборе: // подсчитать, сколько раз каждое слово встречается во вводе map<string, size_t> word_count; // пустая карта строк и чисел set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"}; string word; while (cin >> word) // подсчитать только не исключенные слова if (exclude.find(word) == exclude.end()) ++word_count[word]; // получить и прирастить счетчик слов Подобно другим контейнерам, set является шаблоном. Чтобы определить набор, следует указать тип его элементов, которым в данном случае будет string. Подобно последовательным контейнерам, для элементов ассоциативного контейнера применима списочная инициализация (см. раздел 3.3.6). Набор exclude будет содержать 12 слов, которые следует игнорировать. Важнейшее различие между этой программой и предыдущей в том, что перед подсчетом каждого слова оно проверяется на принадлежность к набору исключенных. Для этого используется оператор if: // Page 529/1103 подсчитать только не исключенные слова if (exclude.find(word) == exclude.end()) Вызов функции find() возвращает итератор. Если заданный ключ находится в наборе, итератор указывает на него. Если элемент не найден, функция find() возвращает итератор на элемент после конца. В этой версии счетчик слов изменяется, только если слово не находится в наборе exclude. Если запустить эту версию для того же ввода, что и прежде, вывод будет таким: Although occurs 1 time Before occurs 1 time are occurs 1 time as occurs 1 time ... Упражнения раздела 11.1 Упражнение 11.1. Опишите различия между картой и вектором. Упражнение 11.2. Приведите пример того, когда наиболее полезен контейнер list, vector, deque, map и set. Упражнение 11.3. Напишите собственную версию программы подсчета слов. Упражнение 11.4. Усовершенствуйте свою программу так, чтобы игнорировать регистр и пунктуацию. Т.е. слова "example" и "Example", например, должны увеличить тот же счетчик. 11.2. Обзор ассоциативных контейнеров Ассоциативные контейнеры (и упорядоченные, и неупорядоченные) поддерживают общие функции контейнеров, описанные в разделе 9.2 и перечисленные в табл. 9.2. Ассоциативные контейнеры не поддерживают функции, специфические для последовательных контейнеров, такие как push_front() или back(). Поскольку элементы хранятся на основании их ключа, эти операции были бы бессмысленны для ассоциативных контейнеров. Кроме того, ассоциативные контейнеры не поддерживают конструкторы и функции вставки, получающие значение элемента и его позицию. Кроме функций, общих для всех контейнеров, ассоциативные контейнеры предоставляют некоторые функции (табл. 11.7) и псевдонимы типов (табл. 11.3), которых нет у последовательных контейнеров. Помимо этого, неупорядоченные контейнеры предоставляют функции настройки производительности их хеша, которые рассматриваются в разделе 11.4. Итераторы ассоциативных контейнеров двунаправлены (см. раздел 10.5.1). 11.2.1. Определение ассоциативного контейнера Page 530/1103 Как только что упоминалось, при определении карты следует указать типы ключа и значения; при определении набора задают только тип ключа, поскольку значения у него нет. Каждый из ассоциативных контейнеров имеет стандартный конструктор, который создает пустой контейнер заданного типа. Ассоциативный контейнер можно также инициализировать копией другого контейнера того же типа или диапазоном значений, тип которых может быть приведен к типу контейнера. По новому стандарту возможна также списочная инициализация элементов: map<string, size_t> word_count; // пустая карта // списочная инициализация set<string> exclude = {"the", "but", "and", "or", "an", "a", "The", "But", "And", "Or", "An", "A"}; // три элемента; authors сопоставляет фамилию с именем map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"} }; Как обычно, тип инициализаторов должен быть преобразуемым в тип контейнера. Типом элемента набора является тип ключа. При инициализации карты следует предоставить и ключ, и значение. Каждая пара ключ-значение заключается в фигурные скобки, { ключ , значение }, означая, что вместе элементы формируют единый элемент карты. Первый элемент каждой пары — это ключ, второй — значение. Таким образом, карта authors сопоставляет фамилии с именами и инициализируется тремя элементами.Инициализация контейнеров multimap и multiset Ключи в контейнерах map и set должны быть уникальными; с каждым ключом может быть сопоставлен только один элемент. У контейнеров multimap и multiset такого ограничения нет; вполне допустимо несколько элементов с тем же ключом. Например, у использованной для подсчета слов карты должен быть только один элемент, содержащий некое слово. С другой стороны, у словаря может быть несколько определений того же слова. Следующий пример иллюстрирует различия между контейнерами с уникальными ключами и таковыми с не уникальными ключами. Сначала необходимо создать вектор целых чисел ivec на 20 элементов: две копии каждого из целых чисел от 0 до 9 включительно. Этот вектор будет использован для инициализации контейнеров set и multiset: // определить вектор из 20 элементов, содержащий две копии каждого // Page 531/1103 числа от 0 до 9 vector<int> ivec; for (vector<int>::size_type i = 0; i != 10; ++i) { ivec.push_back(i); ivec.push_back(i); // сдублировать каждое число } // iset содержит уникальные элементы ivec; // miset содержит все 20 элементов set<int> iset(ivec.cbegin(), ivec.cend()); multiset<int> miset(ivec.cbegin(), ivec.cend()); cout << ivec.size() << endl; // выводит 20 cout << iset.size() << endl; // выводит 10 cout << miset.size() << endl; // выводит 20 Хотя набор iset был инициализирован значениями всего контейнера ivec, он содержит только десять элементов: по одному для каждого уникального элемента вектора ivec. С другой стороны, контейнер miset содержит 20 элементов, сколько и вектор ivec. Упражнения раздела 11.2.1 |