Объединенный список: 0 0 2 4 5 6 8 10 10 12 14 15 16 18 20 25 30 35 40 45

Отображения

Отображение — это ассоциативный контейнер.

Класс map поддерживает ассоциативный контейнер, в котором уникальным ключам соответствуют определенные значения. По сути, ключ — это просто имя, которое присвоено некоторому значению. После того как значение сохранено в контейнере, к нему можно получить доступ, используя его ключ. Таким образом, в самом широком смысле отображение — это список пар " ключ-значение". Если нам известен ключ, мы можем легко найти значение. Например, мы могли бы определить отображение, в котором в качестве ключа используется имя человека, а в качестве значения — его телефонный номер. Ассоциативные контейнеры становятся все более популярными в программировании.

Как упоминалось выше, отображение может хранить только уникальные ключи. Ключи-дубликаты не разрешены. Чтобы создать отображение, которое бы позволяло хранить неуникапьные ключи, используйте класс multimap.

Контейнер map имеет следующую шаблонную спецификацию.

template < class Key, class T, class Comp = less< Key>, class Allocator =allocator< pair< const Key, T> > > class map

Здесь Key— тип данных ключей, T— тип сохраняемых (отображаемых) значений, а Comp — функция, которая сравнивает два ключа. По умолчанию в качестве функции сравнения используется стандартная функция-объект less. Элемент Allocator означает распределитель памяти, который по умолчанию использует стандартный распределитель allocator.

Класс map имеет следующие конструкторы.

explicit map(const Comp & cmpfn = Comp(), const Allocator & a = Allocator());

map(const map< Key, T, Comp, Allocator> & ob);

template < class InIter> map(InIter start, InIter end, const Comp & cmpfn = Comp(), const Allocator & a = Allocator());

Первая форма конструктора создает пустое отображение. Вторая предназначена для создания отображения, которое содержит те же элементы, что и отображение ob. Третья создает отображение, которое содержит элементы в диапазоне, заданном итераторами start и end. Функция, заданная параметром cmpfn (если она задана), определяет характер упорядочения отображения.

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

Для класса map определены следующие операторы сравнения:

==, <, < =, ! =, > и > =

Функции-члены, определенные для класса map, представлены в табл. 21.4. В их описании под элементом key_type понимается тип ключа, а под элементом value_type — значение выражения pair< Key, Т> .

Пары " ключ-значение" хранятся в отображении как объекты класса pair, который имеет следующую шаблонную спецификацию.

template < class Ktype, class Vtype>

struct pair {

　 typedef Ktype first_type; // тип ключа

　 typedef Vtype second_type; // тип значения

　 Ktype first; // содержит ключ

　 Vtype second; // содержит значение

　 // Конструкторы

　 pair();

　 pair (const Ktype & k, const Vtype & v);

　 template< class A, class B> pair(const< A, B> & ob);

}

Как отмечено в комментариях, член first содержит ключ, а член second — значение, соответствующее этому ключу.

Создать пару " ключ-значение" можно либо с помощью конструкторов класса pair, либо путем вызова функции make_pair(), которая создает парный объект на основе типов данных, используемых в качестве параметров. Функция make_pair() — это обобщенная функция, прототип которой имеет следующий вид.

template < class Ktype, class Vtype>

pair< Ktype, Vtype> make_pair(const Ktype & k, const Vtype & v);

Как видите, функция make_pair() возвращает парный объект, состоящий из значений, типы которых заданы параметрами Ktype и Vtype. Преимущество использования функции make_pair() состоит в том, что типы объектов, объединяемых в пару, определяются автоматически компилятором, а не явно задаются программистом.

Возможности использования отображения демонстрируется в следующей программе. В данном случае в отображении сохраняется 10 пар " ключ-значение". Ключом служит символ, а значением — целое число. Пары " ключ-значение" хранятся следующим образом:

А 0

В 1

С 2

и т.д. После сохранения пар в отображении пользователю предлагается ввести ключ (т.е. букву из диапазона А-J), после чего выводится значение, связанное с этим ключом.

// Демонстрация использования простого отображения.

#include < iostream>

#include < map>

using namespace std;

Int main()

{

　 map< char, int> m;

　 int i;

　 // Помещаем пары в отображение.

　 fоr(i = 0; i < 10; i++) {

　　 m.insert(pair< char, int> ('A'+i, i));

　 }

　 char ch;

　 cout < < " Введите ключ: ";

　 cin > > ch;

　 map< char, int>:: iterator p;

　 // Находим значение по заданному ключу.

　 р = m.find(ch);

　 if(р! = m.end())

　　 cout < < p-> second;

　 else cout < < " Такого ключа в отображении нет.";

　 return 0;

}

Обратите внимание на использование шаблонного класса pair для построения пар " ключ-значение". Типы данных, задаваемые pair-выражением, должны соответствовать типам отображения, в которое вставляются эти пары.

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

В предыдущем примере пары " ключ-значение" создавались явным образом с помощью шаблона pair< char, int> . И хотя в этом нет ничего неправильного, зачастую проще использовать с этой целью функцию make_pair(), которая создает pair-объект на основе типов данных, используемых в качестве параметров. Например, эта строка кода также позволит вставить в отображение m пары " ключ-значение" (при использовании предыдущей программы):

m.insert(make_pair((char) ('А'+i), i));

Здесь, как видите, выполняется операция приведения к типу char, которая необходима для переопределения автоматического преобразования в тип int результата сложения значения i с символом 'А'.

Хранение в отображении объектов класса

Подобно всем другим контейнерам, отображение можно использовать для хранения объектов создаваемых вами типов. Например, следующая программа создает простой словарь на основе отображения слов с их значениями. Но сначала она создает два класса word и meaning. Поскольку отображение поддерживает отсортированный список ключей, программа также определяет для объектов типа word оператор " < " . В общем случае оператор " < " следует определять для любых классов, которые вы собираетесь использовать в качестве ключей. (Некоторые компиляторы могут потребовать определения и других операторов сравнения.)

// Использование отображения для создания словаря.

#include < iostream>

#include < map>

#include < cstring>

using namespace std;

class word {

　　 char str[20];

　 public:

　　 word() { strcpy(str, " " ); }

　　 word(char *s) { strcpy(str, s); }

　　 char *get() { return str; }

};

bool operator< (word a, word b)

{

　 return strcmp(a.get(), b.get()) < 0;

}

class meaning {

　　 char str[80];

　 public:

　　 meaning() { strcmp(str, " " ); }

　　 meaning(char *s) { strcpy(str, s); }

　　 char *get() { return str; }

};

Int main()

{

　 map< word, meaning> dictionary;

　 /* Помещаем в отображение объекты классов word и meaning. */

　 dictionary.insert( pair< word, meaning> (word(" дом" ), meaning(" Место проживания." )));

　 dictionary.insert( pair< word, meaning> (word(" клавиатура" ), meaning(" Устройство ввода данных." )));

　 dictionary.insert( pair< word, meaning> (word(" программирование" ), meaning(" Процесс создания программы." )));

　 dictionary.insert( pair< word, meaning> (word(" STL" ), meaning(" Standard Template Library" )));

　 // По заданному слову находим его значение.

　 char str[80];

　 cout < < " Введите слово: ";

　　 cin > > str;

　 map< word, meaning>:: iterator р;

　 р = dictionary.find(word(str));

　 if(p! = dictionary.end())

　　 cout < < " Определение: " < < p-> second.get();

　 else cout < < " Такого слова в словаре нет.";

　 return 0;

}

Вот один из возможных вариантов выполнения этой программы.

Введите слово: дом

⇐ Предыдущая 60 61 62 63 646566 67 68 69 Следующая ⇒