►Использование контейнера map...324

Ассоциативный массив map представляет собой ещё один класс-контейнер. Имеется множество ассоциативных массивов, но все они обладают одним общим свойством — обеспечивают быстрое сохранение и выборку в соответствии с некоторым ключом или индексом. Приведённая ниже программа демонстрирует этот принцип на практике.

Например, в институте студенты могут быть зарегистрированы при помощи уникальных идентификационных номеров. Этот идентификационный номер используется во всех случаях студенческой жизни: для получения информации о студенте, при выдаче книг в библиотеке, записи в ведомость об оценках. Очень важно, чтобы любая программа могла получить информацию о студенте по его номеру быстро и эффективно.

Следующая программа демонстрирует использование ассоциативного массива студентов с идентификатором в качестве ключа.

    /* STLMap — использование ассоциативного массива */

    /*        для коллекции студентов, упорядоченной */

    /*              по их идентификаторам */

    #include <cstdio>

    #include <cstdlib>

    #include <iostream>

    #include <sstream>

    #include <string>

    #include <map>

    using namespace std ;

    /* SC — Функция сравнения студентов, */

    /*      определяющая порядок их сортировки */

    struct SC

    {

        bool operator( )( const int id1 , const int id2 ) const

        {

            return id1 < id2 ;

        }

    } ;

    /* Ассоциативный массив в действительности содержит пары, первый элемент которых является ключом, а второй — данными ( в нашем случае — классом Student ) */

    class Student ;

    typedef Student* SP ;

    typedef pair< const int , Student* > Pair ;

    typedef map< int , SP , SC > Map ;

    typedef map< int , SP , SC >::iterator MapIterator ;

    /* Коллекция студентов */

    Map students ;

_________________

324 стр. Часть 5. Полезные особенности

    /* Student — определяет важные свойства студентов, в первую очередь — ключ, используемый для выборки информации о студенте */

    class Student

    {

      public :

        Student( char* pszName , int id )

                : studentIDKey( id ) , name( pszName ) { }

        /* getKey — ключ, используемый в качестве индекса в ассоциативном массиве */

        const int getKey( ) { return studentIDKey ; }

        /* display — вывод информации на экран */

        string display( )

        {

            ostringstream out ;

            out << studentIDKey << " — " << name ;

            return out.str( ) ;

        }

      protected :

        /* Ключевое поле — идентификатор студента */

        const int studentIDKey ;

        /* Имя студента ( а также прочие данные ) */

        string name ;

    } ;

    int main( int argc , char* pArgs[ ] )

    {

        setlocale ( LC_ALL , ".1251" ) ; /* печать кириллицы */

        /* Добавляем несколько студентов в коллекцию */

        Student* pS ;

        pS = new Student( "Алла" , 3456 ) ;

        Pair* ptr = new Pair( pS -> getKey( ) , pS ) ;

        students.insert( *ptr ) ;

        /* Ассоциативный массив перегружает оператор индексирования для создания пары и вставки её в массив */

        students[ 1234 ] = new Student( "Лариса" ,

                                           1234 ) ;

        students[ 5678 ] = new Student( "Марианна" ,

                                           5678 ) ;

        /* Проход по списку студентов. Ассоциативный массив всегда хранит элементы упорядоченными по ключу */

        cout << "Отсортированный список студентов:" << endl ;

        MapIterator iter = students.begin( ) ;

        while ( iter != students.end( ) )

        {

            Pair p = *iter ;

            Student* s = p.second ;

            cout << s -> display( ) << endl ;

            iter++ ;

        } 

_________________

325 стр. Глава 28. Стандартная библиотека шаблонов

        /* Операторы инкремента и декремента могут использоваться для поиска предыдущего и последующего элемента */

        cout << " Ищем студента 3456" << endl ;

        MapIterator p = students.find( 3456 ) ;

        cout << "Найден: " << p -> second -> display( ) << endl ;

        MapIterator p1 = p ;

        MapIterator prior = --p1 ;

        cout << "Предшественник = "

              << prior -> second -> display( ) << endl ;

        MapIterator p2 = p ;

        MapIterator successor = ++p2 ;

        cout << "Следующий = "

              << successor -> second -> display( ) << endl ;

        /* Функция find( ) возвращает итератор end( ), если искомый элемент не найден; operator[ ] возвращает NULL */

        if ( students.find( 0123 ) == students.end( ) )

        {

            cout << "Вызов students.find( 0123 ) возвратил "

                  << "students.end( ), т.к. студента 0123 нет"

                  << endl ;

        }

        /* Вывод с использованием индекса */

            cout << "Проверка индекса: students[ 3456 ] = "

                  << students[ 3456 ] -> display( ) << endl ;

        if ( students[ 0123 ] == NULL )

        {

            cout << "students[ 0123 ] возвращает NULL"

                  << endl ;

        }

        /* Пауза для того, чтобы посмотреть на результат работы программы */

        system( "PAUSE" ) ; return 0 ;

    } 

Ключевым моментом программы являются три оператора typedef. Контейнер map содержит множество объектов Pair, каждый из которых содержит по два элемента. Первый элемент — ключ ( в нашем случае — идентификатор студента ), а второй — сам объект Student. В аргументы шаблона Map добавлен класс SC, который содержит единственный метод, сравнивающий два ключа ( это немного сложнее, чем глобальная функция, использованная в контейнере list, но эффект абсолютно тот же ).

Программа начинает работу с создания трёх объектов Pair и вносит их в список. Затем проход по контейнеру показывает, что он хранит элементы упорядоченными по ключу, так что вызов метода sort( ) нам не нужен.

Во второй части программы выполняется поиск с использованием метода find( ), а также выборка предыдущего и последующего элементов контейнера при помощи операторов инкремента и декремента.

_________________

326 стр. Часть 5. Полезные особенности

Вывод программы выглядит следующим образом:

    Отсортированный список студентов:

    1234 — Лариса

    3456 — Алла

    5678 — Марианна

    Ищем студента 3456

    Найден: 3456 — Алла

    Предшественник = 1234 — Лариса

    Следующий = 5678 — Марианна

    Вызов students.find( 0123 ) возвратил

    students.end( ), т.к. студента 0123 нет

    Проверка индекса: students[ 3456 ] = 3456 — Алла

    students[ 0123 ] возвращает NULL

    Press any key to continue...

_________________

327 стр. Глава 28. Стандартная библиотека шаблонов