Відображення та мультивідображення

У відображенні завжди зберігаються пари значень, одне з яких являє собою ключовий об’єкт, інше – об’єкт, що містить значення. Ключовий об’єкт містить ключ, по якому шукається значення. Об’єкт-значення містить деякі дані, які звичайно і цікавлять користувача, що шукає щось за допомогою ключа. Значеннями часто є також рядки, числи чи інші об’єкти включно з контейнерами.

Наприклад, ключем може бути слово, а значенням – кількість його входження в текст (частотна таблиця) або список номерів сторінок книжки, де це слово зустрічається.

Одним з найпопулярніших прикладів використання відображень є асоціативні масиви. В звичайних масивах індекс завжди є цілим числом. З його допомогою здійснюється доступ до конкретних елементів. Так, у виразі anArray[3] число 3 є індексом. З асоціативними масивами справа дещо інша, там тип даних індексу можна задати самостійно. При цьому з’являється унікальна можливість написати, наприклад, такий вираз: anArray[?jane?]

 

Асоціативний масив

Розглянемо невеликий приклад відображення, використовуваного в якості асоціативного масиву. Ключами будуть назви штатів, а значеннями – їх населення.

//демонстрація відображення

#include<iostream>

#include<conio>

#include<string>

#include<map>

using namespace std;

int main()

{string name;

int pop;

string states[]={"Colorado","Newada","Ohio",

            "Montana","Arizona","Texas"};

int pops[]={470,2890,800,707,2710,944};

map<string, int, less<string> >mapStates;//відображення

map<string, int, less<string> >::iterator iter; //ітератор

for (int j=0;j<6;j++)

{name=states[j]; //одержання даних з масивів

pop=pops[j];

mapStates[name]=pop; //занесення їх у відображення

}

cout<<"Vvedit nazvu statu: ";

cin>>name;

pop=mapStates[name];

cout<<"Naselenna: "<<pop<<"000\n";

cout<<endl;

for(iter=mapStates.begin();iter!=mapStates.end();iter++)

cout<<(*iter).first<<" "<<(*iter).second<<"000\n";

getch();

return 0;

}

 

Програма 15.30

При запуску програми у користувача запитується назва штату. Одержане значення використовується в якості ключа для пошуку у відображенні значення населення і виведення його на екран. Після цього виводиться весь вміст відображення. Після цього виводиться весь вміст відображення, всі пари штат-населення.

При використанні множин і відображень не виникає ніяких претензій до швидкості пошуку. В даному випадку програма дуже швидко знаходить значення населення за введеною назвою штату. Зате ітерація в контейнерах даного типу не така швидка, як у послідовних контейнерах. Звернімо увагу, що назви штатів при виведенні розміщені в алфавітному порядку, хоча й були задані в масиві хаотично.

Визначення відображення має три шаблонні аргументи:

map<string, int, less<string> >mapStates;

Перший з них задає тип ключа. В даному випадку це string, оскільки в рядках задається назва штату. Другий аргумент визначає тип значень, що зберігаються в контейнері (int в нашому прикладі – це населення в тисячах чоловік). Третій аргумент задає порядок сортування ключів. Ми тут сортуємо їх по алфавіту, для чого використовуємо less<string>. Ще для цього відображення задається ітератор.

Вхідні дані програми первісно зберігаються в двох різних масивах. Для занесення їх у контейнер ми пишемо:

mapStates[name]=pop;

Цей елегантний вираз дуже нагадує вставку у звичайний масив, однак індексом такого «масиву» є рядок name, а не просто якесь ціле число.

Після того, як користувач введе назву штату, програма шукає відповідне значення населення:

pop=mapStates[name];

Крім того, що можна використовувати синтаксис звертання до елементів по індексах, що нагадує звертання до масивів, можна дістати доступ одночасно до обох частин відображення: ключів та значень. Це робиться за допомогою ітераторів. Ключ одержують по (*iter).first, а значення – по (*iter).second. При інших варіантах звертання ітератор працює так само, як і в інших контейнерах.