 |
Ассоциативный контейнер set
|
|
|
|
Контейнерный класс set используется для обеспечения быстрого сохранения и доступа к уникальным ключам. При попытке поместить в контейнер set дубликата ключа это действие игнорируется без идентификации ошибки. Контейнер set поддерживает двунаправленные итераторы. Работа с контейнером set может быть продемонстрирована на предыдущем примере, если в нем строку
typedef std::multiset<int,std::less<int> > intMSET;
заменить на строку
typedef set<int,std::less<int> > intMSET;
что приведет далее к созданию и работе с объектами класса set.
Ассоциативный контейнер 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 – получения ссылки на элемент с наивысшим приоритетом.
|
|
|
