Ассоциативный контейнер multimap
Ассоциативный контейнер multimap эффективен для быстрого сохранения и нахождения ключей и ассоциированных с ними значений. Многие методы, используемые в контейнерах set и multiset, применимы к контейнерам map и multimap.
Элементами multimap и map являются объекты pair - пары ключей и соответствующих им значений. Порядок сортировки ключей в контейнере определяется компараторным объектом-функцией less<тип>. В контейнере multimap допускается дублирование ключей. Это означает, что несколько значений могут быть ассоциированы с одним ключом (отношение ”один ко многим”). Например, ученик изучает много предметов, один человек может иметь несколько банковских счетов и т.д.
Контейнер multimap поддерживает двунаправленные итераторы. Для работы с контейнерным классом multimap необходимо подключить заголовочный файл <map>. Рассмотрим пример использования контейнера multimap.
#include <iostream>
using std::cout;
using std::endl;
#include <map>
#include <algorithm>
typedef float T1; // тип ключа
typedef float T2; // тип элемента
typedef std::multimap<T1,T2,std::less<T1> > MUL_MAP;
T1 key;
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));
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();
return 0;
}
Результат работы программы:
пар с ключом 3.1 в multimap 0 раз
пар с ключом 3.1 в multimap 0 раз
размер multimap = 4
1 20.12
3.1 1.1
3.1 2.2
12 20.12
нижняя граница 3.1 3.1
верхняя граница 3.1 12
найдено значение 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), создающая объект pair, в котором first – это ключ (5) типа T1, а second – значение (12) типа T2.
В цикле for выводится содержимое контейнерного класса multimap (ключи и значения). Для доступа к компонентам pair элементов контейнера используется const_iterator itr. При этом ключи выводятся в порядке возрастания.
for(itr=mmap.begin();itr!=mmap.end();itr++)
cout<<itr->first<<'\t'<<itr->second<<'\n';
Для вывода нижней и верхней границ ключа key в контейнере используются
cout<<"нижняя граница "<<key<<'\t'<<(mmap.lower_bound(key)->first);
cout<<"верхняя граница "<<key<<'\t'<<(mmap.upper_bound(key)->first);
функции lower_bound() и upper_bound(), возвращающие итератор соответствующего элемента pair.
Ассоциативный контейнер map
Контейнерный класс map используется для обеспечения быстрого сохранения и доступа к уникальным ключам и соответствующих значений. При этом между ними устанавливается взаимно однозначное соответствие. Попытка поместить в контейнер map дубликат ключа игнорируется без идентификации ошибки. Контейнер map поддерживает двунаправленные итераторы. Работа с контейнером map может быть продемонстрирована на предыдущем примере, если в нем строку
typedef std::multimap<T1,T2,std::less<T1> > MUL_MAP;
заменить на строку
typedef std:map<T1,T2,std::less<T1> > MUL_MAP;
что приведет далее к созданию и работе с объектами класса map.
Адаптеры контейнеров
В состав STL входят три адаптера контейнеров – stack, queue и priority_queue. Адаптеры не предоставляют реализации фундаментальной структуры данных и не поддерживают работу с итераторами. Это отличает их от контейнеров первого класса. Преимущество класса адаптеров состоит в возможности выбирать требуемую базовую структуру данных. Все три класса адаптеров содержат компоненты-функции push и pop, реализуемые посредством вызова соответствующих функций базового класса.
Адаптеры stack
Класс stack обеспечивает возможность вставки и удаления данных в базовой структуре с одной стороны. Адаптер stack может быть реализован с любым из контейнеров последовательностей: vector, list и deque(по умолчанию реализуется с контейнером deque). Для класса stack определены следующие операции (реализуемые через соответствующие функции базового контейнера): push – помещение элемента на вершину стека, pop – удаление элемента с вершины стека, top – получение ссылки на вершину стека, empty – проверки на пустоту стека и size – получение числа элементов стека.
#include <iostream>
using std::cout;
using std::endl;
#include <stack>
#include <vector>
#include <list>
typedef char T;
template<class E>
void popElement(E &e)
{ while(!e.empty()) // пока стек не пустой
{ cout<<e.top()<<' '; // получение значения элемента на вершине стека
e.pop(); // удаление элемента с вершины стека
}
}
main()
{ std::stack <T> deque_st; // стек на основе deque
std::stack <T, std::vector<T> > vect_st; // стек на основе vector
std::stack <T, std::list<T> > list_st; // стек на основе list
char c='a';
for(int i=0;i<5;i++) // занесение в стеки
{ deque_st.push(c++);
vect_st.push(c++);
list_st.push(c++);
}
cout << "\nСтек deque :";
popElement(deque_st);
cout << "\nСтек vector :";
popElement(vect_st);
cout << "\nСтек list :";
popElement(list_st);
cout<<endl;
return 0;
}
Результат работы программы:
Стек deque : m j g d a
Стек vector : n k h e b
Стек list : o l i f c
В первых трех строках функции main создаются три стека для хранения символов, использующие в качестве базовых структур контейнеры deque (по умолчанию), vector и list соответственно. Далее в программе использована функция push для помещения элементов на вершину соответствующего стека.
Реализованная в программе template функция выводит на экран удаляемый с вершины стека элемент. Для этого использованы функции top – нахождения (но не удаления) элемента на вершине стека и pop – удаления его с вершины стека.
Адаптеры queue
Класс queue предназначен для вставки элементов в конец базовой структуры данных и удаления элементов из ее начала. Адаптер queue реализуется с контейнерами list и deque (по умолчанию).
Наряду с общими для всех классов адаптеров операциями push, pop, empty и size в классе queue имеются операции front – получения ссылки на первый элемент очереди, back – ссылки на последний элемент очереди.
#include <iostream>
using std::cout;
using std::endl;
#include <queue>
// #include <list> для базового контейнера list
typedef int T;
main()
{ std::queue <T> och;
// std::queue <T, std::list<T> > lst; очередь на основе контейнера list
och.push(1); // занесение в очередь
och.push(2);
och.push(3);
int k=och.size(); // количество элементов в очереди
cout << "Очередь : ";
if(och.empty()) cout<<" пустая"; // проверка на пустоту очереди
else
{ for(int i=0;i<k;i++)
{ cout<<och.front()<<' '; // вывод значения первого элемента очереди
och.pop(); // удаление из очереди первого элемента
}
}
cout<<endl;
return 0;
}
Результат работы программы:
Очередь : 1 2 3
Инструкция
std::queue <T> och;
создает очередь для хранения в ней значений типа T. Очередь создается на основе контейнера deque по умолчанию. Функция front считывает значение первого элемента очереди, не удаляя его из нее. Для этого используется функция pop.
Адаптеры priority_queue
Класс priority_queue используется для вставки элементов в отсортированном порядке в базовую структуру данных и удаления элементов из ее начала. Адаптер priority_queue реализуется с контейнерами vector (по умолчанию) и deque.
Элементы в очередь с приоритетом заносятся в соответствии со своим значением. Это означает, что элемент с максимальным значением помещается в начало очереди и будет первым из нее удален, а с минимальным - в конец очереди. Это достигается с помощью метода, называемого сортировкой кучи. Сравнение элементов выполняется функцией-объектом less<Тип> или другой компораторной функцией.
Как и предыдущие адаптеры, priority_queue использует операции push, pop, empty, size, а также операцию top – получения ссылки на элемент с наивысшим приоритетом.