Г. Шилтд - Самоучитель C++ (DJVU) (1114955), страница 68
Текст из файла (страница 68)
С этой целью используются два класса: )кого (слово) и орроя1е (антоним). Поскольку для ассоциативных списков поддерживается отсортированный список ключей, в программе для объектов типа )кот(1 определяется оператор <. Как правило, оператор < необходимо перегружать для всех классов, объекты которых предполагается использовать в качестве ключей. (Помимо оператора < в некоторых компиляторах может потребоваться определить дополнительные операторы сравнения.) // Ассоциативный список слов и антонимов () тпс1ис)е <ъоа~теат> ()тпс1ис(е спер> Ф(пс1цс)е <сзтг(пя> цв)пд патеврасе зМ; 45г Самоучитель с1азз иогй ( сваг звг (20]; рыЫ1с: иогй() ( я'спору(я'сг, ""): ыогй ( спал *я) ( я~гору (з~г, з ); сваг *де~() ( гесыгп звг; для объектов типа иогй следует определить оператор < (меньше) Ьоо1 орегагог< (иог<( а, иогй Ы ( гесцгп зггсшр(а.дев(), Ь дев() ) < 0; с1азз орроя1бе сваг звг (20); рвЫ1с: орроз1ге () ( зггсшр (згг, ""); ) орроз1Ге (сЬаг+з) ( зггсру(згг, я) ) с)таг +дев () ( гевыгп ясг; 1п' ша1п () шар<иогй, орроя1бе> гп !! размещение в ассоциативном списке слов и антонимов ш.
1пзегс (ра1г<иог«(, орроя1'се> (иогй("да"),орроз1ге("нет"))) х ш, 1пзегг (ра1г<иогй, орроя1 е> (иого("хорошо" ),орроз1ге["плохо"))); т 1пзегГ(ра1г<иогй, орроя1~е> (иого("влево" ),орроз1ге("вправо'")) ); ш, 1пзегГ (ра1г<иогй, орроя(бе> (иогй("вверх"),орроз1Ге("вниз")) ); поиск антонима по заданному слову сваг згг(80); сопя « "Введите слово: с1п » ясг; шар<иогс, орроз1Ге>:: 1гегатог р; р =ш. Нпс~(иогй(згг) ); 1Г (р ! = т. еп<) () ) сопя « "Антоним: " «р->зесопс(,дед (): е1яе сорб « "Такого слова в ассоциативном списке нетМ"; Глава т4.
Библиотека стандартных шаблонов гетогп О; В данном примере любой объект, который вводится в ассоциативный спи- сок, представляет собой символьный массив для хранения заканчивающейся нулем строки. Далее в этой главе будет показано, как упростить эту про- грамму, используя стандартный тип данных в1пвя. 1.
Поэкспериментируйте с представленными примерами. Попытайтесь делать небольшие изменения в программах и исследуйте результаты. '2. Создайте ассоциативный список для хранения имен абонентов и их телефонных номеров. Имена и номера телефонов должны вводиться пользователем, а поиск нужного номера должен выполняться по введенному имени абонента. (Подсказка: в качестве модели воспользуйтесь примером 3.) 3. Нужно ли определять для объектов оператор <, если эти объекты используются в качестве ключей ассоциативного списка? 14.6.
Алгоритмы Таблица 14.5. Алгоритмы библиотеки стандартных шаблонов Алгоритм Назначение Выполняет поиск смежных парных элементов в последовательности. Возвращает итератор первой, пары ае1асеМ т1пб Выполняет бинарный поиск в упорядоченной после- довательности Ыаагу ааагаа Как уже объяснялось, алгоритмы предназначены для разнообразной обработки контейнеров. Хотя в каждом контейнере поддерживается собственный базовый набор операций„стандартные алгоритмы обеспечивают более широкие и комплексные действия. Кроме этого, они позволяют одновременно работать с двумя контейнерами разных типов.
Для доступа к алгоритмам библиотеки стандартных шаблонов в программу необходимо включить заголовок <а1~огИш>. В библиотеке стандартных шаблонов определяется большое число алгоритмов, которые систематизированы в табл. 14.5. Все алгоритмы представляют собой функции-шаблоны. Это означает, что их можно использовать с контейнерами любых типов. Наиболее показательные варианты такого использования приведены в примерах данного раздела.
454 Назначение Алгоритм Г1пЫ„ап6 гсг еасЬ 1пр!асс магде Нег вчгар 1ех1содгарп1са! сотраге 1сягег„ЬсипЫ глаИе Ьеар сору серу ЬасИчгагЫ сооп! СООП! 1Г емца! ег!Па! гапде г!!! уи! и Ипб г!пЫ г1гвг От ПпЫ И делегате депегайе и !по!одев Самоучитель С++ Таблица !4.5(продолжение) Копирует последовательность Аналогична функции ссруЦ, за исключением того, что перемещает в начало последовательности эле- менты из ее конца Возвращает число элементов в последовательности Возвращает число элементов в последовательности, удовлетворяющих некоторому предикату Определяет идентичность двух диапазонов Возвращает диапазон, в который можно вставить элемент, не нарушив при этом порядок следования элементов в последовательности Заполняет диапазон заданным значением Выполняет поиск диапазона для значения и возвра- щает первый найденный элемент Выполняет поиск диапазона для подпоследователь- ности.
Функция возвращает итератор конца подпос- ледовательности внутри диапазона Находит первый элемент внутри последовательно- сти, парный элементу внутри диапазона Выполняет поиск диапазона для элемента, для кото- рого определенный пользователем унарный преди- кат возвращает истину Назначает функцию диапазону элементов Присваивает элементам в диапазоне значения, воз- вращаемые порождающей функцией Определяет, включает ли одна последовательность все элементы другой последовательности Выполняет слияние одного диапазона с другим.
Оба диапазона должны быть отсортированы в порядке возрастания элементов. Результирующая последо- вательностьсортируется Меняет местами значения, на которые указывают два итератора, являющиеся аргументами функции Сравнивает две последовательности в алфавитном порядке Обнаруживает первое значение в последовательно- сти, которое не меньше заданного значения Выполняет пирамидальную сортировку последовательности (пирамида, на английском языке Пеар,— полное двоичное дерево, обладающее тем свойством, что значение каждого узла не меньше значения любого из его дочерних узлов.
— Примеч. пер.) Глава 14. Библиотека стандартныхшаблонов 455 Алгоритм Назначение Возвращает максимальное из двух значений так тах е!етеп1 Возвращает итератор максимального элемента внутри диапазона Выполняет слияние двух упорядоченных последова- тельностей, а результат размещает в третьей после- довательности тегде т!и Возвращает минимальное из двух значений т!п е!етеп1 Возвращает итератор минимального элемента внут- ри диапазона Обнаруживает первое несовпадение между элемен- тами в двух последовательностях. Возвращает ите- раторы обоих несовпадающих элементов т!вта1сп Образует следующую перестановку (регто1а1!оп! последовательности пех1 реппи1аИоп Упорядочивает последовательность таким образом, чтобы все элементы, меньшие заданного элемента Е, располагались перед ним, а все элементы, боль- шие заданного элемента Е, — после него п1п е!етеп1 Сортирует диапазон Сортирует диапазон, а затем копирует столько эле- ментов, сколько войдет в результирующую последо- вательность Упорядочивает последовательность таким образом, чтобы все элементы, для которых предикат возвра- щает истину, располагались перед элементами, для которых предикат возвращает ложь рагИИоп Меняет местами первый и предыдущий перед по- следним элементы, а затем восстанавливает пира- миду рор Ьеар Образует предыдущую перестановку последова- тельности ргеч регти1аИсп Размещает элемент на конце пирамиды Беспорядочно перемешивает последовательность Удаляет элементы из заданного диапазона Заменяет элементы внутри диапазона Меняет порядок сортировки элементов диапазона на обратный гечегве гечегве сору ра гИ а! в о г1 рагИа! вог1 сору рив!! 'оеар гапбот вний!е геточе геточе И гегпоче сору геточе сору И гер!асе гер!асе И гор!асс сору гер!асе сору И Таблица 14.
5(продолжение) Самоучитель С++ 456 Таблица 14. о(продолжение) Назначение Алгоритм Выполняет циклический сдвиг влево элементов в диапазоне го1а1е го1а1е сору Выполняет поиск подпоследовательности внутри последовательности веагсп Выполняет поиск последовательности заданного числа одинаковых элементов Создает последовательность, которая содержит раз- личающиеся участки двух упорядоченных наборов Создает последовательность, которая содержит одинаковые участки двух упорядоченных наборов Создает последовательность, которая содержит симметричные различающиеся участки двух упоря- доченных наборов Создает последовательность, которая содержит объединение (ип~юп! двух упорядоченных наборов Сортируетдиапазон веагсп и ве1 г!!11егепсе ве1 !п1егвес11оп веФ„еупппеФг1с„гй11егепсе ве1 ып!оп вогт Сортирует пирамиду внутри диапазона вог1 'оеар в1аЫе рагИИоп Упорядочивает последовательность таким образом, чтобы все элементы, для которых предикат возвращает истину, располагались перед элементами, для которых предикат возвращает ложь.
Разбиение на разделы остается постоянным; относительный порядок расположения элементов последовательности не меняется Сортирует диапазон. Одинаковые элементы не пе- реставляются Меняет местами два значения в1аЫе аог1 виар виар гапяев 1гапв1оггп Меняет местами элементы в диапазоне Назначает функцию диапазону элементов и сохраня- ет результат в новой последовательности Удаляет повторяющиеся элементы из диапазона ип!цие ип!оце сору оррег ооопб Обнаруживает последнее значение в последовательности, которое не больше некоторого значения сенр1асе<с1ааа ХпХкеа, с1авв т> вазе с оспой.
(ХпХтеа начало, хп1еег оаонаание, ооввс т ьанаианае! т !. Одними из самых простых алгоритмов являются алгоритмы соппХО и савв$ Щ). Ниже представлены их основные формы: 14. Библиотека етандартнык шаблоноа 457 Глава севр1асв<о1ааа 1п1сек, с1авв Т> яуе 1 осипа (1п1сек начало, (П)1ЕГ окончание, т)пРкес( й$ предмнаж); Алгоритм сопв10 возвращает число элементов в последовательности, начиная с элемента, обозначенного итератором начало, и заканчивая элементом, обозначенным итератором окончание, значение которых равно параметру значение.
Алгоритм еапи1 Ы() возвращает число элементов в последовательности,, начиная с элемента начало и заканчивая элементом окончание, для которых унарный предикат ф нреоикаж возвращает истину. В следующей программе демонстрируются алгоритмы соцп1() и со(ш1 Ио. // Демонстрация алгоритмов соцп1 и саппв 1й ()1пс1и«(е «1оастеап> 11(пс! пс(е <чес1ог> ()1пс1пс)е <а1сог1тла> цз1пя пагпезрасе аМ; /* это унарный предикат, который определяет, является ли значение четным Ф/ Ьоо1 ечеп(1ис х) ( теснин ! (х%2); 1и"' ватп ( ) ( чес ои«1ии>;т; 1тт1 1; ~от('=Ор 1<20; 1++) ( 1~(1$2) ч.рпвЛ Ьасх(1); е(ве ч.риаи Ьас)«(2); соис « "Последовательность: йое(1=01 1<ч.а1ае(); 1++) соис « к[11 « соис « епс(1; 1ии и; и = соипе (ч. Ьеотп (), ч.епс((), 1); сони « и с< " элементов равно 1~п"; и = соипЕ 1Е(ч.Ьесьп (), е.еп«)(), ечеи); сопи с< и « " четных элементов~и"; те"ити О; 458 Самоучитель После выгюлнения программы на экране появится следующее: Последовательность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
