Изучаем map (ассоциативный массив) C++

На данный момент существует отличный контейнер map, который позволяет вам ассоциировать элементы с чем угодно. Например, у вас есть список продуктов для покупки (список книг в библиотеке). Вам необходимо хранить сколько и чего нужно купить (название и количество книг в библиотеке). Контейнер <map> позволяет нам хранить эти данные в виде ключ-значение (книга-количество, продукт-вес\объем...). Контейнер <map> является отсортированным массивом. Сортировка произведена по ключу.

Для использования <map> вам необходимо сначала его подключить:
#include <map>

Для создание контейнера достаточно написать:

map <key type, data type> map_name;

Например map<string, int> books; Содержит связку название книги / количество
или
map<string, CObject*> objects; Содержит связку название объекта / указатель на объект

Для доступа (или записи) в массив нужно писать:

map_name[key];

Контейнер map также имеет возможность работы с итераторами. Поэтому вы можете использовать с ним множество различных алгоритмов.

Элементы класса map имеют только уникальные значения ключей.
Элементы автоматически сортируются.
Класс multimap может иметь несколько элементов с одинаковым значением ключа.

begin() - итератор на первый элемент;
end() - итератор на элемент идущий после последнего;
rbegin() - итератор на последний элемент (для обратных алгоритмов);
rend() - итератор на позицию перед первым элементом (для обратных алгоритмов).
размер отображения
empty() - возвращает истину, если размер отображения 0;
size() - возвращает число элементов;
max_size() - максимально возможный размер отображения.
count(key) - число элементов соответствующих указанному ключу. Для класса map значения 1 или 0;
find(key) - итератор на первый элемент с указанным ключом;
lower_bound(key) - итератор на первый элемент, чей ключ больше или равен указанному ключу;
upper_bound(key) - итератор на первый элемент, чей ключ больше указанного ключа;
equal_range(key) - диапазон элементов, чей ключ равен указанному ключу;
[] - операция индексации по ключу.
swap(map& m) - обмен значениями с другим отображением;
insert(el) - вставка элемента, возвращается его позиция;
insert(beg,end) - вставка элементов из указанного диапазона;
erase(key) - удалить указанный элемент;
erase(it), erase(start,end) - удаляет элемент с заданным итератором или между заданными
clear() - удалить все элементы.
прочие методы

Для классов перегружены операции =,[],==,!=,<,>,<=,>=.

Про работы с итераторами:

Для обращения к элементу в строках и векторах достаточно было перед именем контейнера поставить *, но в map так не получится, т.к. в каждом элементе хранится 2 значения (ключ и данные). Поэтому надо писать так:

(*iter).first - для обращения к ключу и

(*iter).second -для обращения к данным,

где iter - итератор элемента

Кроме контейнера map существует контейнер multimap. Его отличие в том, что мы можем одному ключу задать несколько соответствий. Например, автору сопоставить несколько написанных им книг.

Примеры:

Программы для подсчета количества слов в тексте и вывод частоты их встречи в процентном соотношении (подсчет частоты встречи слов в тексте в процентах)

#include <iostream>
#include <string>
#include <map>
#include <fstream>

using namespace std;

int main()
	{
	map <string,int> words;
	
	ifstream in;
	in.open("in.txt");
	
	string word;
	
	while (in>>word)
	{
		words[word]++;
	}
	
	ofstream out;
	out.open("out.txt");
	
	int count = 0;
	
	map <string,int>::iterator cur;
	
	out<<"Words count:"<<endl;
	
	for (cur=words.begin();cur!=words.end();cur++)
	{
		out<<(*cur).first<<": "<<(*cur).second<<endl;count+=(*cur).second;
	}
	
	out<<"Words percenc:"<<endl;
	
	for (cur=words.begin();cur!=words.end();cur++)
	{
		out<<(*cur).first<<": "<<(float)((float)(*cur).second/(float)count)*100<<"%"<<endl;
	}
	
	return 0;
}

Программа для создания словаря для брута (и не только).

#include <iostream>
#include <string>
#include <map>
#include <fstream>

using namespace std;

int main()
	{
	map  words;
	ifstream in;
	in.open("in.txt");
	
	string word;
	
	while (in>>word)
	{
		words[word]++;
	}
	
	ofstream out;
	out.open("out.txt");
	
	for (map ::iterator  it=words.begin();it!=words.end();it++)
	{
		out<<(*it).first<<";"<<endl;
	}
	
	cout<<"Done"<<endl;
	return 0;
}

Программа подсчета частоты встречи слов в тексте может быть полезна для расшифровки текста. (Некоторые алгоритмы для шифровки используют замену букв каким-то образом)

Вторая программа, создающая словарь для брута, работает очень просто. Она берет текст и вытаскивает из него все слова.

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

#include<iostream>
#include<map>
#include<string>
#include<functional>
#include<math.h>
#define PI 3.1415926
using namespace std;

typedef  pointer_to_unary_function<double,double>fdu;
map<string,fdu> funcs; 
void testFuncs();

// инициализируем словарь функций
void initFuncs(){
	funcs.insert(make_pair("sin",ptr_fun(sin)));
	funcs.insert(make_pair("abs",ptr_fun(fabs)));
	//...
}

//---------------------------------------------
int main(){
	
	initFuncs();
	
		// используем наш словарь  для вычислений
		cout<<funcs["abs"](-23)<<endl;
		cout<<funcs["sin"](PI/2)<<endl;
		cout<<funcs["sin"](PI/6)<<endl;
		
		// тест  с ручным вводом
		// testFuncs();
		
		return 0;
	}
	
	//---------------------------------------------
	void testFuncs(){
		string key=""; double arg=0;
		
		// выполняем пока  не будет набран
		//  не существующий ключ
		// можно также сделать потомка  от map
		//  с возбуждением исключения  в []  при не существующем ключе
		while(1){
		cout<<"input function name and argument:"<<endl;
		cin>>key;
		
		// проверка есть ли элемент
		//  с указанным ключом
		if(!funcs.count(key)){
		  cout<<"no function "<<key<<endl<<"exit"<<endl;
		  break;
		}
	
		cin>>arg;
		cout<<"result: "<<funcs[key](arg)<<endl;
	}
}

хеш отображения

В дополнение к стандарту stl многие компиляторы реализовали дополнительные классы hash_map и hash_multimap. В нем элементы не сортируются. А для быстрого доступа к элементу по ключу используется специальная хеш-функция.

Включаемый файл зависит от компилятора. Так в MinGw это
#include <ext/hash_map>

В других компиляторах это может быть
#include <hash_map>

Для использования этого класса в MinGw необходимо использовать пространство имен __gnu_cxx.

Во-вторых, часто типом для ключа является строка. А в MinGw (возможно старых версий как у меня) определена хеш-функция только для С строк, но не для класса string. Решается эта проблема специализацией шаблона хеш-функции для класса string. Этот код можно вынести во включаемый файл или вставлять его перед объявлением первой переменной такого типа.

В остальном классы аналогичны map и multimap. Так что переделка предыдущего примера с использованием hash_map для MinGw не составляет труда.

...
#include <ext/hash_map>
...
using namespace __gnu_cxx;

// специализация шаблона хеш-функции  для класса string
namespace __gnu_cxx{
	template<> struct hash<std::string> {
	  size_t operator()(const std::string& s) const {
	    return __stl_hash_string(s.c_str());
	  }
	};
}
...
hash_map<string,fdu> funcs;
...

Эти классы включены в последние стандарты C++ под именами unordered_map и unordered_multimap.