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

9.6. Ассоциативные контейнеры

Ассоциативные контейнеры предназначены для обеспечения прямого доступа посредством использования ключей. В STL имеется четыре ассоциа- тивных контейнерных класса: multiset, set, multimap и map. Во всех контейне- рах ключи отсортированы. Классы multiset и set манипулируют множествами значений, одновременно являющихся ключами. При этом multiset допускает одинаковые ключи, а set нет. Классы multimap и map манипулируют множест-

вами значений, ассоциируемых с ключами. При этом multimap допускает хра-
нение одинаковых ключей с ассоциированными значениями, а map нет.
9.6.1. Ассоциативный контейнер multiset		Р
Ассоциативный контейнер multiset обеспечивает Ибыстрое сохранение и
	У

выборку ключей. Упорядочение элементов контейнера определяется компара-

	торным объектом-функцией less<тип>, при этом отсортированные ключи долж-
	ны поддерживать сравнение с помощью operator<,Гиначе (для пользовательских
	типов) необходимо перегружать опер цию сравнения.
		Класс multiset поддерживает двун прБвленные итераторы (но не итерато-
	ры произвольного доступа).				е		а
		#include <iostream>
		using namespace std;				к
		#include <set>		т
		#include <algorithm>
			о
		typedef std::multiset<int,std::less<int> > intMSET;
		#define size 10
		int main()
		л
		{ int mas[]={2,4,1,6,19,17,1,7,17,14};
		б
		intMSETиmset;
		std::ostream_iterator<int> out(cout," ");
	и
		intMSET::const_iterator res;
	Б	cout<<"элемент 8 содержится в multiset " << mset.count(8)<<" раз\n";
		mset.insert(8);		mset.insert(8); // длбавление двух 8 в контейнер
		cout<<"содержимое multiset :";
		std::copy(mset.begin(),mset.end(),out);
		res=mset.find(6);
		cout<<'\n' ;
		if(res!=mset.end())
		cout<<"найдено значение 6\n";
		else cout<<"не найдено значение 6\n";
		mset.insert(mas,mas+sizeof(mas)/sizeof(int));						//
								211

cout<<"содержимое multiset :" ;
std::copy(mset.begin(),mset.end(),out);
cout<<"\nнижняя граница числа 17					" << *(mset.lower_bound(17));
cout<<"\nверхняя граница числа 17					" << *(mset.upper_bound(17));
std::pair<intMSET::const_iterator, intMSET::const_iterator> pr;
pr=mset.equal_range(17);
cout<<"\nнижняя граница числа 17					" << *(pr.first);
cout<<"\nверхняя граница числа 17					" << *(pr.second);
return 0;											Р
}
										И
Результат работы программы:
элемент 8 содержится в multiset 0 раз									У
содержимое multiset : 8 8
не найдено значение 6								Г
содержимое multiset : 1 1 2 4 6 7 8 8 14 17 17 19
нижняя граница числа 17			17				Б
верхняя граница числа 17			19
нижняя граница числа 17			17			асс
верхняя граница числа 17			19
В приведенной программе использованы следующие компоненты контей-
нерного класса multiset:				е				оциативных контейнерах,
mset.count(8) – функция, доступная во всех
возвращает число вхождений значения 8 кв multiset. Затем в программе исполь-
			т
зованы две из трех версий функции insert:
mset.insert(8);		о
mset.insert(mas,mas+sizeof(mas)/sizeof(int));
	и
первая из двух функций insert вс авляет значение 8 во множество, а вторая −
числа из интервала.
л
Далее используются функции lower_bound(17) и upper_bound(17) (доступ-
б

ные во всех ассоциативных контейнерах) для определения позиции первого вхождения числа 17 во множество и позиции элемента после последнего вхож- дения. Обеифункц и возвращают iterator, или const_iterator соответствующих по- зиций, или тератор, возвращаемый функцией end.

БВ строке

std::pair<intMSET::const_iterator, intMSET::const_iterator> pr;

создается объект класса pair. Объекты класса pair используются для связывания пар значений. Объект pr используется для сохранения в нем значения pair, воз- вращаемого функцией equal_range и содержащего результаты lower_bound() и upper_bound(). Тип pair содержит две открытые компоненты с именами first и second. Для доступа к lower_bound() и upper_bound используются pr.first и pr.second.

212

9.6.2. Ассоциативный контейнер set

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

typedef std::multiset<int,std::less<int> > intMSET;

заменить на строку

typedef set<int,std::less<int> > intMSET;

что приведет далее к созданию и работе с объектами класса set.
9.6.3. Ассоциативный контейнер multimap
Ассоциативный контейнер multimap эффективен для быстрогоР	сохране-
У
ния и нахождения ключей и ассоциированных с ними значений. Многие мето-
Г

ды, используемые в контейнерах set и multiset, применимыИк контейнерам map и multimap.

Элементами multimap и map являются объекты pair – пары ключей и со- ответствующих им значений. Порядок сортировки ключей в контейнере опреде-

			а
ляется компараторным объектом-функцией less<тип>. В контейнере multimap
допускается дублирование ключей. Это ознБчает, что несколько значений могут
		к
быть ассоциированы с одним лючом (отношение «один ко многим»). Напри-
	ме
мер, ученик изучает много пр д тов, один человек может иметь несколько
банковских счетов и т.д.
т
Контейнер multimap подд рживает двунаправленные итераторы. Для ра-

боты с контейнерным классом multimap необходимо подключить заголовочный файл <map>. Рассм рим пример использования контейнера multimap.

		#include <iostream>
		using namespace std;
				о
		#include <map>
		#include <algorithm>
			и		//	тип ключа
		typedef float T1;
		л			//	тип элемента
		typedef float T2;
		typedef std::multimap<T1,T2,std::less<T1> > MUL_MAP;
		б
		T1 key;
	иint main()
	Б	{ MUL_MAP mmap,mm;
		MUL_MAP::const_iterator itr;
		MUL_MAP::value_type pr;				// элемент типа pair
		key=3.1;

cout<<"пар с ключом "<<key<<" в multimap " << mmap.count(key)<< " раз"<<endl;

mmap.insert(MUL_MAP::value_type(key,1.1));

213

mmap.insert(MUL_MAP::value_type(key,2.2));

cout<<"пар с ключом "<<key<<" в multimap " << mmap.count(key)<< " раз"<<endl;

mmap.insert(MUL_MAP::value_type(5,12)); mmap.insert(MUL_MAP::value_type(1,20.12)); mmap.insert(MUL_MAP::value_type(12,20.12)); mmap.erase(5);

cout<<" размер multimap = "<<mmap.size()<<endl; for(itr=mmap.begin();itr!=mmap.end();itr++)

cout<<itr->first<<'\t'<<itr->second<<'\n';

cout<<"нижняя граница "<<key<<'\t'<<(mmap.lower_bound(key)->first);
cout<<"верхняя граница "<<key<<'\t'<<(mmap.upper_bound(key)->first);
itr=mmap.find(key);									У		Р
cout<<'\n' ;								Г		И
if(itr!=mmap.end())
}	cout<<"найдено значение "<<itr->second<<”\tпо ключу ”
	<<itr->first<<endl;							Б
else cout<<"не найден ключ "<<key<<'\n';
mmap.clear();							а
Результат работы программы:					е
пар с ключом		3.1	в multimap		0	раз
пар с ключом		3.1	в multimap		0	разк
размер multimap =			4	т
1	20.12

3.11.1

				о
3.1	2.2		и
12	20.12
		л		3.1
нижняя граница 3.1
	б			12
верхняя граница 3.1
найдено значение 1.1 по ключу 3.1
и
В приведенном выше тексте программы в строках:
typedef float T1;
Б
typedef float T2;

typedef std::multimap<T1,T2,std::less<T1> > MUL_MAP;

используя typedef, типам float и double назначаются псевдонимы T1 и T2 и эк- земпляру шаблонного класса multimap псевдоним MUL_MAP.

Компонента-функция mmap.count(key) возвращает число пар ключа key, содержащихся в multimap. Далее следуют функции insert для ввода пар ключей и соответствующих значений в контейнер.

mmap.insert(MUL_MAP::value_type(5,12));

В этой инструкции используется функция value_type(5,12), создающая объект

214