Г. Шилтд - Самоучитель C++ (PDF) (1114887), страница 67
Текст из файла (страница 67)
Возвращает итератор этого элементаtemplate<class lnlter> voidEnsert(lnlter начало,Inlter конец);Вставляетпоследовательностьэлементов,заданную итераторами начало и конецpaiKiterator, bool>insert(const value_type &значение);Вставляет значение в вызывающий ассоциативный список.
Возвращает итератор вставленного элемента. Элемент вставляется только в случае, если такого в ассоциативном списке еще нет. При удачной вставке элементафункция возвращает значение pair<iterator,true>, в противном случае — paiKiterator,false>key_compare key_comp() const;Возвращает объект-функцию сравнения ключейiterator lower_boundВозвращает итератор первого элемента ассоциативного списка, ключ которого равен илибольше заданного ключа ksize_type max_size() const;Возвращает максимальное число элементов,которое можно хранить в ассоциативномспискеreference operator[](const key_type &i);Возвращает ссылку на элемент, соответствующий ключу I.
Если такого элемента не существует, он вставляется в ассоциативныйсписокreverse_iterator rbegin();const_reverse_iteratorВозвращает обратный итератор конца ассоциативного спискаreversejterator rendf);const_reverse_lteratorВозвращает обратный итератор начала ассоциативного спискаsize_type size() const;Возвращает хранящееся на данный момент вассоциативном списке число элементовvoid swap(map<Key, T, Comp,Allocator> & объект);Обменивает элементы из вызывающего ассоциативного списка с элементами из объектаобъектiterator upper_bound(const key_type &.k);constjterator upper_boundВозвращает итератор первого элемента ассоциативного списка, ключ которого большезаданного ключа kvalue_comparevalue_comp() const;Возвращает объект-функцию сравнения значений(const key_type &fc);constjterator lower_bound(const key_type &k) const;rbegin() const;rend() const;(const key_type &k) const;Глава 14.
Библиотека стандартных шаблонов449В ассоциативном списке хранятся пары ключ/значение в виде объектов типаpair. Шаблон объекта типа pair имеет следующую спецификацию:template<class Ktype, class Vtype> struct pair {typedef Ktype первый_тяп; // тип ключаtypedef Vtype второй тип; // тип значенияKtype первый; // содержит ключвторой; // содержит значение/ / конструкторыpair () ;pair (const Ktype &k, const Vtype fiv) ;template< class A, class B> pair (const<A, B> &объект)Ранее уже говорилось, что значение переменной первый содержит ключ изначение, а значение переменной второй — значение, соответствующее этому ключу.Создавать пары ключ/значение можнокласса pair, но и с помощью функциитипа pair, используя типы данныхmake_pair() — это родовая функция соне только с помощью конструкторовmake_pair(), которая создает объектыв качестве параметров.
Функцияследующим прототипом:template<class Ktype, class Vtype>pair<Ktype, Vtype>make_pair (const Ktype fit, const Vtype fiv) ;Как видите, функция возвращает объект типа pair, содержащий заданные вкачестве параметров функции значения типов Ktype и Vtype. Преимуществоиспользования функции make_pair() состоит в том, что она дает возможность компилятору автоматически распознавать типы предназначенных дляхранения объектов, и вам не нужно указывать их явно.В следующей программе на примере ассоциативного списка, предназначенного для хранения десяти пар ключ/значение, иллюстрируются основы использования ассоциативных списков. Ключом здесь является символ, а значением — целое. Пары ключ/значение хранятся следующим образом:АвО1С2.
. .J9Поскольку пары хранятся именно таким образом, то, когда пользователь набирает на клавиатуре ключ (т. е. одну из букв от А до J), программа выводитна экран соответствующее этому ключу значение.450__СамоучительС++II Иллюстрация возможностей ассоциативного списка^include <iostream>^include <map>using namespace std;int main{}{map<char, int> m;int i ;// размещение пар в ассоциативном спискеfor(i=0; i<10; i++) {m. insert !pair<char, int>('A' + i, i) ) ;1char ch;cout « "Введите ключ: ";cin » ch;map<char, int>: : iterator p;// поиск значения по заданному ключуР = m. find(ch) ;if (p != m.endO }cout « p->second;elsecout « "Такого ключа в ассоциативном списке нет\п";return 0;Обратите внимание на использование класса-шаблона pair для образованияпар ключ/значение.
Типы данных, указанные в классе -шаблоне pair, должнысоответствовать типам данных, хранящимся в ассоциативном списке.После того как ассоциативный список инициализирован парами ключ/значение, найти нужное значение по заданному ключу можно с помощью функции findQ. Функция find() возвращает итератор соответствующего ключу элемента или итератор конца ассоциативного списка, если указанный ключ ненайден. Когда соответствующее ключу значение найдено, оно сохраняется вкачестве второго члена класса-шаблона pair.2. В предыдущем примере типы пар ключ/значение были указаны явно в конструкции pair<char, int>. Хотя такой подход совершенно правилен, частопроще использовать функцию make_pair(), которая создает пары объектов наоснове типов данных своих параметров.^include <iostream>^include <map>using namespace std;Глава14.Библиотекастандартныхшаблонов_451int main { ){map<char, int> m;int i;// размещение пар в ассоциативном спискеfor(i=0; i<10; i++) {m.
insert {make__pair (char) ( ' A ' H- i, i) ) ;char ch;cout « "Введите ключ: ";с in » ch;map<char, int>: : iterator p;// поиск значения по заданному ключур = m. find(ch) ;if (р !- т. end () )cout « p->second;elsecout « "Такого ключа в ассоциативном списке нет\п";return 0;Данный пример отличается от предыдущего только строкойm. insert (make_pair (char) ( ' A ' + i, i) ) ;В данном случае, чтобы в операции сложения 'А* + i не допустить автоматического преобразования в тип int, используется приведение к типу char. Вовсем остальном процесс определения типов объектов выполняется автоматически.Так же как и в других контейнерах, в ассоциативных списках можно хранитьсоздаваемые вами типы данных.
Например, в представленной ниже программе создается ассоциативный список для хранения слов с соответствующимисловам антонимами. С этой целью используются два класса: word (слово) иopposite (антоним). Поскольку для ассоциативных списков поддерживаетсяотсортированный список ключей, в программе для объектов типа word определяется оператор <. Как правило, оператор < необходимо перегружать длявсех классов, объекты которых предполагается использовать в качестве ключей. (Помимо оператора < в некоторых компиляторах может потребоватьсяопределить дополнительные операторы сравнения.)// Ассоциативный список слов и антонимовtinclude <iostream># include <map>#include <cstring>using namespace std;452_____________Самоучительclass word {char str [20];public:wordO { strcpy(str, ""); }word(char *s) { strcpyfstr, s); }char *get() { return str; }// для объектов типа word следует определить оператор < (меньше)bool operator< (word a, word b){return strcmp(a.get {) , b.getO) < 0;}class opposite {char str [20] ;public:opposite!) { strcmp(str, ""); }opposite (char *s) ( strcpyfstr, s) ; }char *get() { return str; })!int main(){map<word, opposite> m;// размещение в ассоциативном списке слов и антонимовm.
insert (pair<word, opposite>(word ("да") , opposite ("нет") } ) ;m. insert (pair<word, opposite>(word ("хорошо") , opposite ("плохо") } ) ;m. insert {pair<word, opposite>(word ("влево") , opposite ("вправо") ) ) ;m. insert (pair<word, opposite>(word ("вверх") , opposite ("вниз") } ) ;// поиск антонима по заданному словуchar str [80] ;cout « "Введите слово: ";cin » str;map<word, opposite>: : iterator p;p = m. find{word(str) ) ;if (p != m.endO )cout « "Антоним: " « p->second.get () ;elsecout « "Такого слова в ассоциативном списке нет\п";C++Глава14. Библиотека стандартных шаблонов453return 0;iВ данном примере любой объект, который вводится в ассоциативный список, представляет собой символьный массив для хранения заканчивающейсянулем строки. Далее в этой главе будет показано, как упростить эту программу, используя стандартный тип данных string.1.
Поэкспериментируйте с представленными примерами. Попытайтесь делатьнебольшие изменения в программах и исследуйте результаты.2. Создайте ассоциативный список для хранения имен абонентов и их телефонных номеров. Имена и номера телефонов должны вводиться пользователем, а поиск нужного номера должен выполняться по введенному имениабонента. (Подсказка: в качестве модели воспользуйтесь примером 3.)3. Нужно ли определять для объектов оператор <, если эти объекты используются в качестве ключей ассоциативного списка?14.6. АлгоритмыКак уже объяснялось, алгоритмы предназначены для разнообразной обработки контейнеров. Хотя в каждом контейнере поддерживается собственныйбазовый набор операций, стандартные алгоритмы обеспечивают более широкие и комплексные действия.