Предыдущий пост -
Следующий пост -

std::map

Рубрика: Контейнеры, Дата: 26 May, 2013, Автор:
Tags: ,

std::map это ассоциативный массив. Вроде ключи могут быть только уникальные. Ладно начнем описание. Щас посмотрим как мы можем подключить этот map.

Для подключения нужно прописать:

#include <map>
using std::map;

Рассмотрим инициализацию (constructors)

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

//тест map
#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

//тип для сравнения
struct class_comp
{
	bool operator()(const char& a, const char& b)
	{ return a<b; }
};

//собственная функция для сравнения
bool fncomp(char a, char b){ return a<b;}

int main()
{
	//создание пустого map(ключи тип char, значения тип int)
	map<char, int> m;
	//добавим 4 элемента
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;
	cout <<m['a']<<' '<<m['b']<<' '<<m['c']<<' '<<m['d']<<endl;

	//создаем копию через указатели
	map<char,int> m1(m.begin(),m.end());
	cout <<m1['a']<<' '<<m1['b']<<' '<<m1['c']<<' '<<m1['d']<<endl;

	//вызов конструктора копирования
	map<char,int> m2(m1);
	cout <<m2['a']<<' '<<m2['b']<<' '<<m2['c']<<' '<<m2['d']<<endl;

	//создание map со своей собственной функцией добавления
	map<char,int,class_comp> m3;

	//создание map с передачей для сравнения указателя на функцию
	//создаем указатель на функцию
	bool (*fn_pt)(char, char) = fncomp;//наш указатель на функцию
	//создаем map с использованием указателя на функцию
	map<char,int,bool(*)(char,char)> m4(fn_pt);

	return 0;
}

map::operator=()

Это оператор присваивания служить для присваивания одного map другому. Щас попробуем поэкспериментировать.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создание пустого map
	map<char, int> m;
	map<char, int> m1;
	//заполняем m1
	m1['a']=1;
	m1['b']=2;
	//присваиваем m m1
	m=m1;
	cout <<m1['a']<<' '<<m1['b']<<endl;//1 2

	return 0;
}

Рассмотрим итераторы.

map имеет все типы итераторов, как прямые так и обратные. Рассмотрим пока не константные прямые и обратные итераторы.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создаем пустой map
	map<char,int> m;

	//добавляем значения в map
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;

	//создаем прямой итератор map
	map<char,int>::iterator it;

	//выводим с помощью итератора
	for(it=m.begin();it!=m.end();++it)
	{
		cout <<"m["<<it->first<<"]= "<<it->second<<endl;
	}
	cout <<endl;

	//создаем реверсивный итератор
	map<char,int>::reverse_iterator r_it;
	//вывод с помощью реверсивного итератора
	for(r_it=m.rbegin();r_it!=m.rend();++r_it)
	{
		cout <<"m["<<r_it->first<<"]= "<<r_it->second<<endl;
	}

	return 0;
}

Пример использования константных итераторов map.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//пустой mpa
	map<char,int> m;
	//заполняем значениями
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;

	//создаем константный итератор
	map<char,int>::const_iterator it;

	for(it=m.begin();it!=m.end();++it)
		cout <<"m["<<it->first<<"]= "<<it->second<<endl;
	cout <<endl;

	//создаем константный реверсивный итератор
	map<char,int>::const_reverse_iterator r_it;
	for(r_it=m.rbegin();r_it!=m.rend();++r_it)
		cout <<"m["<<r_it->first<<"]= "<<r_it->second<<endl;

	return 0;
}

Разница между константными и не константными итераторами я думаю понятна. Константные итераторы не могут модифицировать данные, а не константные могу.

Рассмотрим функции емкости (Capacity)

map::empty()

Функция проверяет пустой map или нет. Если map пустой, то возвращается true, если нет то false. Проверим её в работе.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создаем пустой map
	map<char,int> m;

	//проверяем пустой map или нет
	if(m.empty()) cout <<"map empty"<<endl;//map empty

	//добавляем элемент в map
	m['a']=1;

	//проверяем не пустой ли map
	if(!m.empty()) cout <<"map not empty"<<endl;//map not empty

	return 0;
}

map::size()

Функция возвращает количество элементов которые находятся в map.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создаем пустой map
	map<char,int> m;

	cout <<"m.size()= "<<m.size()<<endl;//0
	m['a']=1;
	cout <<"m.size()= "<<m.size()<<endl;//1

	return 0;
}

map::max_size()

Функция возвращает максимально допустимый размер массива который может быть на вашем компьютере.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создаем пустой map
	map<char,int> m;

	cout <<"m.max_size()= "<<m.max_size()<<endl;//громадное число

	return 0;
}

Доступ к элементам (Element access)

map::operator[]()

Доступ к элементам без проверки выхода за допустимые пределы.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создаем пустой map
	map<char,int> m;

	m['a']=1;
	m['b']=2;
	cout <<m['a']<<' '<<m['b']<<endl;

	return 0;
}

map::at()

Произвольный доступ с проверкой выхода за пределы массива с выбросом out_of_range.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;
#include <stdexcept>
using std::out_of_range;

int main()
{
	//создаем пустой map
	map<char,int> m;

	m['a']=1;
	m['b']=2;
	//m.at('c')=3; так нельзя присваивать
	cout <<m.at('a')<<' '<<m.at('b')<<endl;
	try
	{
		m.at('c');//выбрасывается исключение
	}
	catch(out_of_range& e)
	{
		cout <<"out_of_range"<<endl;
	}

	return 0;
}

Модификаторы (Modifiers)

map::insert()

Такая своеобразная функция для map.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;
#include <utility>
using std::pair;

int main()
{
	map<char,int> m;
	map<char,int>::iterator it;

	//добавление одиночного параметра
	m.insert(pair<char,int>('a',100));
	m.insert(pair<char,int>('b',200));

	//вывод результатов
	for(it=m.begin();it!=m.end();++it)
		cout <<it->first<<' '<<it->second<<endl;
	cout <<endl;

	pair<map<char,int>::iterator,bool> ret;
	ret=m.insert(pair<char,int>('b',400));

	if(ret.second==false)
	{
		cout <<"element "<<ret.first->first<<" cozdan"<<endl;//b
		cout <<" i ego znachenie "<<ret.first->second<<endl;//200
	}

	//добавление элемента с указанием позиции перед которой добавлять
	it=m.begin();
	m.insert(it,pair<char,int>('c',800));
	//добавляем второй раз перед тем местом куда указывает указатель
	m.insert(it,pair<char,int>('d',1000));
	//выведем результаты
	for(it=m.begin();it!=m.end();++it)
		cout <<it->first<<' '<<it->second<<endl;
	cout <<endl;
	//после выводов результатов как окозалось элементы добавляются
	//в отсортированом порядке, 
	//поэтому разницы нету куда их добавлять.

	//добавление элемена из одного map в другой и использованием
	//функции find
	map<char,int> m1;
	//добавляет d 1000
	//копирование от и до элемента
	m1.insert(m.begin(),m.find('d')); 

	cout <<endl;
	//вывод результатов
	for(it=m1.begin();it!=m1.end();++it)
		cout <<it->first<<' '<<it->second<<endl;
	cout <<endl;

	return 0;
}

map::erase()

Удаление элементов из map.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;
	map<char,int>::iterator it;

	m['a']=10;
	m['b']=20;
	m['c']=30;
	m['d']=40;
	m['e']=50;
	m['k']=60;
	m['z']=70;

	//удаление значения по итератору
	it=m.find('k');//60
	m.erase(it);

	//удаление по ключу
	m.erase('b');//20

	//удаление списка
	it=m.find('d');
	m.erase(it,m.end());

	//вывод остатка от массива
	for(it=m.begin();it!=m.end();++it)
		cout <<it->first<<' '<<it->second<<endl;

	return 0;
}

map::swap()

Функция обменивает местами два массива.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;
	map<char,int> m1;
	map<char,int>::iterator it;

	m['a']=1;
	m['b']=2;
	cout <<"m.size()= "<<m.size()<<endl;//2
	cout <<"m1.size()= "<<m1.size()<<endl;//0

	//делаем обмен
	m.swap(m1);
	cout <<"m.size()= "<<m.size()<<endl;//0
	cout <<"m1.size()= "<<m1.size()<<endl;//2

	return 0;
}

map::clear()

Удаление всех элементов map.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;

	m['a']=1;
	m['b']=2;
	cout <<"m.size()= "<<m.size()<<endl;//2

	//удаляем все элементы map
	m.clear();
	cout <<"m.size()= "<<m.size()<<endl;//0

	return 0;
}

map::emplace и map::emplace_hint

Эти функции мы пока рассматривать не будем, это новый стандарт 2011 года.

Рассмотрим наблюдателей (Observers)

map::key_comp()

Видимо функция сравнивает ключ с максимальным ключом. Пример то я разобрал, но не понял, что к чему. Щас попробую самостоятельно построить пример возможно тогда более понятно станет, что да как. Да я эту функцию честно не сильно понимаю. Просто она сравнивает ключи с заданным ключом. Практического применения я ей не сильно вижу. Вот в общем примерчик сами смотрите и проверяйте.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	//создание пустого map
	map<char,int> m;
	//создаем тип для сравнения, так сказать
	map<char,int>::key_compare comp = m.key_comp();

	//добавляем элементы
	m['a']=1;
	m['b']=2;
	m['c']=3;

	//значение ключа последнего элемента максимального
	char max=m.rbegin()->first;
	//создание итератора
	map<char,int>::iterator it=m.begin();
	do
	{
		cout <<it->first<<' '<<it->second<<endl;
	}
	while(comp((*it++).first,max));

	return 0;
}

map::value_comp()

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

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;
#include <utility>
using std::pair;

int main()
{
	map<char,int> m;
	m['a']=1;
	m['b']=2;
	m['c']=3;

	//последнее значение
	pair<char,int> max=*m.rbegin();
	map<char,int>::iterator it=m.begin();

	do
	{
		cout <<it->first<<' '<<it->second<<endl;
	}
	while(m.value_comp()(*it++,max));

	return 0;
}

Теперь разберем (Operations)

std::find()

Функция принимает ключ и возвращает итератор на элемент, она осуществляет поиск элемента в массиве по ключу.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;

	map<char,int>::iterator it;
	it=m.find('c');
	cout <<it->first<<' '<<it->second<<endl;//c 3
	it=m.find('a');
	cout <<it->first<<' '<<it->second<<endl;//a 1

	return 0;
}

map::count()

Опять новая функция для меня. Щас попробуем с ней разобраться. Функция принимает ключ, и если возвращает значение больше нуля, то значит имеется элемент в массиве, иначе нету элементов в массиве.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;

	m['a']=1;
	m['c']=2;
	m['e']=3;

	char c;

	for(c='a';c<'h';c++)
	{
		if(m.count(c)>0)
			cout <<c<<" is an element of m"<<endl;
		else
			cout <<c<<" is not an element of m"<<endl;
	}

	return 0;
}

map::lower_bound()

lower bound переводится как нижняя граница. Опять же новая функция и я с ней не сильно разбираюсь. Функция принимает ключ и возвращает указатель на элемент с ключом.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;

int main()
{
	map<char,int> m;
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;
	m['e']=5;

	//создаем итератор
	map<char,int>::iterator it, it1;
	it=m.lower_bound('b');
	cout <<it->first<<' '<<it->second<<endl;

	//указывает как не странно на e, d не включается.
	it1=m.upper_bound('d');
	cout <<it1->first<<' '<<it1->second<<endl;

	//удаляем элементы от и до
	m.erase(it,it1);//удаляет элементы до it1 (it1 не включается)

	//выводим то что у нас осталось в массиве
	cout <<endl<<endl;
	for(it=m.begin();it!=m.end();++it)
		cout <<it->first<<' '<<it->second<<endl;

	return 0;
}

map::upper_bound()

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

map::equal_range()

Эту функцию я честно первый раз вижу, поэтому щас будем вместе разбираться, что за функция такая мудреная. Разбирая пример я вроде кое как догадался, функция возвращает пару указателей на map. Где first элемент это lower_bound() элемента, а second элемент это upper_bound() элемента. То есть другими словами можно сказать, что элемент first это сам элемент, а second это предыдущий элемент. Сейчас я все это испробую на практике, возможно я ошибаюсь.

Да только проверил вроде как не ошибся, просто пара элементов возвращается first это элемент, который возвращается по ключу, а second это элемент следующий за элементом за по ключу. Во примерчик.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;
#include <utility>
using std::pair;

int main()
{
	map<char,int> m;
	m['a']=1;
	m['b']=2;
	m['c']=3;
	m['d']=4;

	//создаем пару итераторов для результата
	pair<map<char,int>::iterator,map<char,int>::iterator> result;
	result=m.equal_range('b');

	cout <<"first= "<<result.first->first<<' '<<result.first->second<<endl;//b 2
	cout <<"second= "<<result.second->first<<' '<<result.second->second<<endl;//c 3

	return 0;
}

Ну и теперь рассмотрим алокатор (Allocator)

map::get_allocator()

Как окозалось это обычный аллокаторо только память он выделяет для указателя на pair пару.

#include <iostream>
using std::cout;
using std::endl;
#include <map>
using std::map;
#include <utility>
using std::pair;

int main()
{
	int size;
	map<char,int> m;//пустой аллокатор
	//создаем указатель на пару
	pair<const char,int>* p;//указатель на пару

	//выделяем память используя аллокатор на 5 элементов
	p=m.get_allocator().allocate(5);

	//подсчет выделенной памяти в байтах
	size=sizeof(map<char,int>::value_type)*5;
	cout <<"size memory= "<<size<<endl;//40
	//получили 40 значит value_type равно 8 байт

	//освобождение памяти
	m.get_allocator().deallocate(p,5);

	return 0;
}

На этом все. Закончим рассматривать контейнер map перейдем к multimap.

 

rss