43. Контейнерные классы
Контейнерные классы – это классы, предназначенные для хранения данных, организованных определенным образом. Примерами контейнеров могут служить массивы, очереди или стеки. Для каждого типа контейнера определены методы для работы с его элементами, не зависящие от конкретного типа данных, которые хранятся в контейнере. Эта возможность реализована с помощью шаблонов классов, поэтому часть библиотеки С++ называют стандартной библиотекой шаблонов (STL – standart template library).
Использование контейнеров позволяет значительно повысить надежность программ, их переносимость и универсальность, а также уменьшить сроки их разработки.
STL содержит контейнеры, реализующие основные структуры данных, используемые при написании программ – векторы, двусторонние очереди, списки и их разновидности, словари и множества. Контейнеры можно разделить на два типа: последовательные и ассоциативные.
Последовательные контейнеры обеспечивают хранение конечного количества однотипных величин в виде непрерывной последовательности. К ним относятся векторы (vector), двусторонние очереди (deque) и списки (list), а также так называемые адаптеры, то есть варианты, контейнеров – стеки (stack), очереди (queue) и очереди с приоритетами (priority_queue).
Каждый вид контейнера обеспечивает свой набор действий над данными. Выбор вида контейнера зависит от того, что требуется делать с данными в программе. Например, при необходимости часто вставлять и удалять элементы из середины последовательности следует использовать список, а если включение элементов выполняется главным образом в конец или начало – двустороннюю очередь.
Ассоциативные контейнеры обеспечивают быстрый доступ к данным по ключу. Эти контейнеры построены на основе сбалансированных деревьев. Существует пять типов ассоциативных контейнеров: словари (map), словари с дубликатами (multimap), множества (set), множества с дубликатами (multiset) и битовые множества (bitset).
Контейнерные классы обеспечивают стандартизированный интерфейс при их использовании. Смысл одноименных операций для различных контейнеров одинаков, основные операции применимы ко всем типам контейнеров.
Практически в любом контейнерном классе определены поля перечисленных ниже типов:
Поле |
Пояснение |
value_type |
Тип элемента контейнера |
size_type |
Тип индексов, счётчиков элементов и т.д. |
iterator |
Итератор |
reverse_iterator |
Обратный итератор |
reference |
Ссылка на элемент |
const_reference |
Константная ссылка на элемент |
key_type |
Тип ключа (для ассоциативных контейнеров) |
key_compare |
Тип критерия сравнения (для ассоциативных контейнеров) |
Итераторы также включены в библиотеку. Они представляют собой объекты, которые в большей или меньшей степени можно рассматривать как указатели. Они предоставляют возможность организовывать циклы с содержимым контейнера подобно тому, как используются указатели для организации циклов с массивами.
Во всех контейнерах определены методы, позволяющие получить сведения о размере контейнеров.
Метод |
Пояснение |
size() |
Число элементов |
max_size() |
Максимальный размер контейнера |
empty() |
Функция, показывающая, пуст ли контейнер |
Пример
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
cout<< "size = " << v.size() <<endl;
int i;
for(i=0; i<10; i++)
v.push_back(i);
cout<< "size now = " << v.size() << endl;
for(i=0; i<10; i++) cout << v[i] << " ";
cout << endl;
cout << "front = " << v.front() << endl;
cout << "back = " << v.back() <<endl;
vector<int>::iterator p=v.begin();
while(p!=v.end()) {
cout << *p << " ";
p++;
}
return 0;
}
На экран программа выдаст следующие данные
В этой программе вектор первоначально создаётся с нулевой длиной. Функция-член push_back() добавляет значение к концу вектора, увеличивая его размер, если в этом есть необходимость. Функция size() возвращает размер вектора. Вектор может быть индексирован подобно обычному массиву. Доступ к нему может быть обеспечен также с помощью итератора.
Посмотрим, как используется класс list
#include <list>
#include <iostream>
#include <string>
using namespace std;
int main()
{
list<string> groceryList;
list<string>::iterator i = groceryList.begin();
i = groceryList.insert(i, "apple");
i = groceryList.insert(i, "bread");
i = groceryList.insert(i, "juce");
cout << "Number of list elements " << groceryList.size() << endl;
cout << "List's elements:" << endl;
i = groceryList.begin();
while(i !=groceryList.end())
{
cout << *i << endl;
i++;
}
system("pause");
return 0;
}
Здесь использована функция-член insert, её прототип:
iterator insert(iterator i, const T& val=T());
Функция вставляет элемент val в список непосредственно перед элементом, на который установлен итератор. Итератор должен быть проинициализирован, даже если список пуст. Функция возвращает итератор, установленный на вновь созданный элемент.
Программа выдаёт на консоль:
Использование класса map для кодирования
#include <iostream>
#include <map>
#include <string>
#include <strstream>
using namespace std;
int main()
{
map <int, string, greater<int>> a;
map <int, string, greater<int>>::iterator p;
a[1]="00";
a[2]="01";
a[3]="100";
a[4]="101";
a[5]="1100";
a[6]="1101";
a[7]="1110";
a[8]="1111";
int mas[]={0,5,6,4,2,7};
char str[100];
ostrstream message(str,100);
int i;
for(i=0;i<sizeof mas/sizeof(int);i++) {
if(!a[mas[i]].empty()) message<<a[mas[i]];
}
message<<ends;
cout << str << endl;
return 0;
}
Программа выдаст на консоль
Обратите внимание, что ошибочное сообщение (0, для которого нет кода) не было кодировано, поскольку оператор [ ] в этом случае возвращает пустой объект string.