Контейнер map

Контейнер map<> (таблица, отображение):

  • Содержит упорядоченные пары <ключ,значение>, где ключ и значение могут принадлежать к произвольным типам. Для типа ключа должна быть либо предопределена, либо определена пользователем операция сравнения;

  • Элементы с любым значением ключа должны быть уникальны;

  • Попытка добавить (метод insert()) к таблице новую пару с уже имеющимся значением ключа завершится неудачей;

  • Операция добавления новой пары в таблицу возвращает пару типа <итератор, bool>, у которой второй компонент (логический second) указывает на успешность операции. Если он true, то первый компонент возвращаемого результата (first) даёт итератор добавленного элемента. Если же он false, то возвращается итератор существующего элемента с тем же ключом;

  • Операции индексации таблицы ( [ ] или at() ) требуют в качестве ключа любое значение типа, определённого для ключа;

  • Операция индексации at(), при задании ключа-параметра, отсутствующего в составе элементов таблицы, вызывает исключение;

  • Напротив, операция индексации [ ], при задании ключа-параметра, отсутствующего в составе элементов таблицы, исключение не вызывает. (наоборот, даже если индексация запрошена только по чтению, добавляет к контейнеру новый элемент с требуемым значением ключа, но с нулевым полем значения);

Эти определения могут показаться замысловатыми, но всё разъяснит последующий пример.

Прежде представления примера, мы должны подготовить некоторые файлы тестовых данных для работы с ассоциативными контейнерами. Работа именно с объёмными символьными данными демонстрирует всю мощь использования таблиц STL. В качестве текстовых данных мы подготовим файлы, содержащие англоязычные оригинальные тексты нескольких стихотворений Льюиса Кэрола.

Ничуть не сложнее использовать и русскоязычные тексты, но в этом случае вам придётся работать с классами wstring и локализованными преобразованиями, что только увеличит громоздкость примеров без увеличения их содержательности.

Вам предоставлено несколько текстов разной длины для обстоятельного тестирования кодов этой и последующих частей изложения (файлы показаны с подсчётом числа строк их текстов). Здесь, например, Humpty-Dumpty.txt — это текст из части VI Humpty-Dumpty «Алиса в зазеркалье».

Контейнер map<> (таблица, отображение):

  • Содержит упорядоченные пары <ключ,значение>, где ключ и значение могут принадлежать к произвольным типам. Для типа ключа должна быть либо предопределена, либо определена пользователем операция сравнения;

  • Элементы с любым значением ключа должны быть уникальны;

  • Попытка добавить (метод insert()) к таблице новую пару с уже имеющимся значением ключа завершится неудачей;

  • Операция добавления новой пары в таблицу возвращает пару типа <итератор, bool>, у которой второй компонент (логический second) указывает на успешность операции. Если он true, то первый компонент возвращаемого результата (first) даёт итератор добавленного элемента. Если же он false, то возвращается итератор существующего элемента с тем же ключом;

  • Операции индексации таблицы ( [ ] или at() ) требуют в качестве ключа любое значение типа, определённого для ключа;

  • Операция индексации at(), при задании ключа-параметра, отсутствующего в составе элементов таблицы, вызывает исключение;

  • Напротив, операция индексации [ ], при задании ключа-параметра, отсутствующего в составе элементов таблицы, исключение не вызывает. (наоборот, даже если индексация запрошена только по чтению, добавляет к контейнеру новый элемент с требуемым значением ключа, но с нулевым полем значения);

Эти определения могут показаться замысловатыми, но всё разъяснит последующий пример.

Прежде представления примера, мы должны подготовить некоторые файлы тестовых данных для работы с ассоциативными контейнерами. Работа именно с объёмными символьными данными демонстрирует всю мощь использования таблиц STL. В качестве текстовых данных мы подготовим файлы, содержащие англоязычные оригинальные тексты нескольких стихотворений Льюиса Кэрола.

Ничуть не сложнее использовать и русскоязычные тексты, но в этом случае вам придётся работать с классами wstring и локализованными преобразованиями, что только увеличит громоздкость примеров без увеличения их содержательности.

Вам предоставлено несколько текстов разной длины для обстоятельного тестирования кодов этой и последующих частей изложения (файлы показаны с подсчётом числа строк их текстов). Здесь, например, Humpty-Dumpty.txt — это текст из части VI Humpty-Dumpty «Алиса в зазеркалье».

30 
Brother_And_Sister
11
Humpty-Dumpty
34
Jabberwock

А Jabberwock.txt — это текст из части VI Humpty-Dumpty «Алиса в зазеркалье» — известное в русскоязычном варианте стихотворение (в исполнении В.С.Высоцкого): О бойся Бармаглота, сын! Он так свиреп и дик…

В нашем оригинале (авторском, англоязычном, для отладки — файл Jabberwock.txt) этот текст выглядит так:

Twas brillig, and the slithy toves
Did gyre and gimble in the wabe:
All mimsy were the borogoves,
And the mome raths outgrabe.

 

«Beware the Jabberwock, my son!
The jaws that bite, the claws that catch!
Beware the Jubjub bird, and shun
The frumious Bandersnatch!» …

 

Текст, безусловно, синтаксически сложный, что делает его прекрасным материалом для отладки приложений. Вам предоставляется отменный материал для дальнейших самостоятельных экспериментов!

Итак … наше приложение будет подсчитывать число вхождений каждой из литер алфавита в предлагаемый текст, используя map<>:

#include <iostream>

#include <sstream>

#include <map>

using namespace std;

 

int main(int argc, char **argv) {

map< char, int > alphabet;

 

while (cin) {

string line;

getline(cin, line);

if (line.empty()) continue;

istringstream ist(line); // строка как поток чтения

char let;

while ((let = ist.get()) && let != EOF) { // посимвольно

pair< map< char, int >::iterator, bool > ret;

ret = alphabet.insert(pair< char, int >(let, 1));

// если неудача - буква уже присутствует:

if (!ret.second) ret.first->second++;

}

}

 

cout << "alphabet size = " << alphabet.size() << endl;

// если буква найдена - вывести её:

for (char c = 'a'; c <= 'z'; c++) {

cout << c << "(";

try { cout << alphabet.at(c); }

catch (exception const& e) { cout << '-'; }

cout << ") ";

}

cout << endl;

 

cout << "alphabet size = " << alphabet.size() << endl;

 

for (char c = 'a'; c <= 'z'; c++) {

cout << c << "(" << alphabet[c] << ") ";

}

cout << endl;

 

cout << "alphabet size = " << alphabet.size() << endl;

}

Контейнер map<> — не самый лучший вариант для поставленных целей: при нахождении новой литеры в тексте мы попытаемся добавить её в качестве ключа таблицы, но если эта литера уже присутствует в таблице, то попытка завершится неудачей. В этом случае, после неудачи, мы, по индексу ключа, просто инкрементируем число его вхождений. И вот что мы поучаем:

Brother_And_Sister.txt

Humpty-Dumpty.txt

Jabberwock.txt

Обратите внимание как увеличился размер таблицы после того, как в ней был индексированием [ ] осуществлён поиск (по чтению!) отсутствующих ключей (‘q’, ‘z’, ‘x’).

Возникает вопрос: почему вы видим в качестве size() такие значения как 44, 47, 50, 52, если мы наблюдаем только раскладку по повторяемости 26 символов от ‘a’ до ‘z’? Ответ прост: потому что в текст могут входить символы пробела, знаков препинания, заглавных литер, которых мы не наблюдаем в выдаче теста.

Если воспользоваться такой новой возможностью стандарта C++11, как списки инициализации, создание и инициализация таблицы может выглядеть гораздо проще:

#include <iostream>

#include <map>

using namespace std;

 

int main(int argc, char **argv) {

map< int, char > nums = {

{ 1, 'a' },{ 3, 'b' },{ 5, 'c' },{ 7, 'd' }

};

for (auto i = nums.begin(); i != nums.end(); i++)

cout << i->first << "->" << i->second << " ";

cout << endl;

}

Естественно, всё это станет компилироваться только при указании опций компилятора для использования стандарта C++11:

Из сказанного уже должно быть понятно, что в качестве ключа поиска в таблице может использоваться любой тип, при обязательном условии, что для него либо определена естественная операция сравнения (intfloatstring, …), либо мы сами определим такую пользовательскую функцию, которая будет использоваться для сравнений. Несколько способов сделать это показаны ниже:

#include <iostream>

#include <map>

using namespace std;

 

template< typename Map > void print_map(Map& m) {

cout << "{ ";

for (auto& p : m) // перебор всей таблицы

cout << p.first << ':' << p.second << ' ';

cout << "}" << endl;

}

// функция  сравнения:

bool great(int lhs, int rhs) { return lhs > rhs; }

// функтор сравнения:

struct classcomp {

bool operator()(const int& lhs, const int& rhs) const {

return lhs > rhs;

}

};

 

int main(int argc, char **argv) {

// таблица, сравнение по умолчанию

map< int, int, less< int > > ml = {

{ 1, 2 },{ 2, 3 },{ 3, 4 },{ 4, 5 }

};

print_map(ml);

// таблица с нашей great() функцией сравнения

map< int, int, bool(*)(int, int) > mg1(great);

mg1.insert(ml.begin(), ml.end());

print_map(mg1);

// таблица с классом-функтором

map< int, int, classcomp > mg3(ml.begin(), ml.end());

print_map(mg3);

}

Здесь мы, сменив функцию сравнения ключей, изменили порядок сортировки элементов при размещении их в таблице. (Во 2-м варианте используется функциональный объект, функтор, работе с которыми будет посвящена отдельная часть нашего рассмотрения.)