Стандартная библиотека шаблонов (STL) поддерживает большинство типовых операций со структурами данных.
Мы уже использовали последовательные контейнеры vector, list и deque и их производные (адаптеры) stack и queue. В STL имеются ассоциативные контейнеры: set — для множеств, map — для отображений, multiset, multimap — для множеств и отображений с повторениями, основанные на деревьях двоичного поиска, и их аналоги unordered_set, unordered_map, unordered_multiset и unordered_multimap на базе хеш-таблиц. Для обработки данных используются возможности библиотеки алгоритмов (algorithm).
Каждому контейнеру соответствует заголовочный файл, который нужно подключать директивой #include.
Контейнеры set и map хранят множества в виде дерева двоичного поиска с автобалансировкой (красно-черное дерево). Контейнер set хранит множество ключей, а map — пары <ключ, значение>, причем все ключи в них уникальны. Для множеств с повторениями используются контейнеры multimap и multiset. При просмотре всех этих контейнеров их содержимое выдается в виде упорядоченной последовательности (внутренний обход дерева двоичного поиска).
При просмотре unordered контейнеров будет выдана неупорядоченная последовательность ключей.
Возможно много вариантов приспособления контейнеров для работы с последовательностями: использование map (или multimap) вместо set, чтобы хранить вместе с ключами их порядковые номера, комбинирование контейнера для множеств с контейнером последовательностей (vector или forward_list), хранящим итераторы, и т. п.
Конструкторы контейнеров позволяют уже при их объявлении сформировать множество заданной мощности. Для этого достаточно в качестве инициализатора содержимого контейнера использовать датчик случайных чисел.
Все необходимое для операций с контейнерами можно найти в библиотеке алгоритмов (algorithm). В частности, в ней имеются функции set_union, set_intersection, set_difference, set_symmetric_difference, вычисляющие объединение, пересечение, вычитание и симметрическую разность множеств. Функции принимают в качестве аргументов отрезки из двух контейнеров и формируют новый контейнер с результатом. В них реализуется схема слияния, поэтому входные отрезки должны быть упорядочены. Это справедливо по умолчанию для контейнеров set, map и аналогичных. Для unordered_set аналогичные результаты дает одновременный просмотр двух контейнеров с применением функций проверки наличия и вставки элемента множества в результат. В библиотеке STL имеются функции для выполнения любых операций с последовательностями.
Подробнее — в [3, с. 295–368], [11, с. 835–962]. Полезно также посмотреть библиотечные файлы в каталоге include компилятора C++: только там содержится исчерпывающая информация о том, какие на самом деле объявляются классы и какие функции-члены они содержат. Информация в литературных источниках, как правило, запаздывает и содержит неточности. Важно и то, что в сообщениях компилятора об ошибках обычно присутствует информация из текстов каталога include, поскольку эти тексты компилируются вместе с программой пользователя.
3.5. Превращение в контейнер
пользовательской структуры данных
Пользовательскую структуру данных для хранения множества/последовательности можно превратить в подобие библиотечного контейнера и тем самым обеспечить возможность применения к нему стандартных алгоритмов библиотеки algorithm. Для этого достаточно соблюдать соглашения о кодировании, принятые для контейнеров: объявить классы итераторов для просмотра и вставки и функции для их инициализации и контроля.
Можно ограничиться только теми средствами, которые действительно понадобятся для работы с пользовательским контейнером.
Для просмотра контейнера в цикле необходимы и достаточны функции begin( ) и end( ), возвращающие прямой итератор чтения, который указывает на первый элемент контейнера и элемент «сразу за последним» соответственно. Итератор должен поддерживать операцию разыменования для доступа к элементам контейнера, операцию инкремента для перемещения по контейнеру и операцию сравнения с результатом end( ). Для вставки нового значения необходим итератор вставки и средство для его инициализации (инсертер). Итератор вставки должен обеспечивать вставку нового элемента одновременно и в множество, и в последовательность.
Наличие этих средств позволит, например, стандартным образом получить копию не только стандартного, но и пользовательского контейнера A в произвольном контейнере B:
std∷copy(A.begin( ), A.end( ), back_inserter(B));
Пример объявления итераторов для пользовательского контейнера (хеш-таблица из массива bct, содержащего указатели на цепочки переполнения):
#include
using namespace std;
//ИТЕРАТОР ЧТЕНИЯ — нужны сравнения, разыменования, инкремент
struct myiter : public std::iterator
{ //В качестве базы использован стандартный прямой итератор
myiter(Node *p) : bct(nullptr), pos(0), Ptr(p) {}
bool operator == (const myiter & Other) const { return Ptr == Other.Ptr; }
bool operator != (const myiter & Other) const { return Ptr != Other.Ptr; }
myiter operator++(); //Ключевая операция — инкремент по контейнеру
myiter operator++(int) { myiter temp(*this); ++*this; return temp; }
pointer operator->() { return & Ptr->key; } //Разыменование косвенное
reference operator*() { return Ptr->key; } //Разыменование прямое
//protected:
// Container& c;
Node **bct; //Указатель на хеш-таблицу (массив экстентов)
size_t pos; //Номер текущего экстента
Node * Ptr; //Реальный указатель на элемент контейнера
};
//ИТЕРАТОР ВСТАВКИ — нужно только присваивание!
template
class outiter : public std::iterator
{
protected:
Container& container; // Контейнер для вставки элементов
Iter iter; // Текущее значение итератора чтения
public:
// Конструктор
explicit outiter(Container& c, Iter it) : container(c), iter(it) { }
// Присваивание = вставка ключа в контейнер
const outiter&
operator = (const typename Container::value_type& value) {
iter = container.insert(value, iter).first;
return *this;
}
const outiter& //Присваивание копии — фиктивное
operator = (const outiter&) { return *this; }
// Разыменование — пустая операция
outiter& operator* ( ) { return *this; }
// Инкремент — пустая операция
outiter& operator++ ( ) { return *this; } //префиксный
outiter& operator++ (int) { return *this; } //постфиксный
};
// ИНСЕРТЕР — функция для создания итератора вставки — аргумент для алгоритма, создающего новый контейнер (универсальная)
template
inline outiter outinserter(Container& c, Iter it)
{ return outiter(c, it); }
//Функции, превращающие хеш-таблицу в контейнер
myiter HT::begin( )const { //Получение итератора на начало
myiter p(nullptr); //Инициализация итератора значением «на конец»
p.bct = bucket; //Установка на массив экстентов хеш-таблицы
for (; p.pos < Buckets; ++p.pos) { //Поиск первого элемента в ХТ
p.Ptr = bucket[p.pos];
if (p.Ptr) break; //Нашли!
}
return p;
}
myiter HT::end( )const { return myiter(nullptr); } //Итератор на конец
myiter myiter::operator++( ) //Инкремент итератора: пример для ХТ
{
if (!Ptr) { //Инициализация сделана?
return *this; //Не работает без предварительной установки на ХТ
}
else
{ //Текущий уже выдан
if(Ptr->down) { //Есть следующий, вниз
Ptr = Ptr->down;
return (*this);
}
while(++pos < HT::Buckets) //Поиск очередного элемента
if(Ptr = bct[pos]) return *this; //Нашли — выход
}
Ptr = nullptr; //Не нашли — выход с пустым итератором
return *this;
}
}
Детальная информация о пользовательских итераторах уровня стандарта C++17 — в [2], [3] и [10]. Справку о текущем состоянии вопроса можно получить в Интернете на сайте ru.cppreference.com.
|
Скачать 0.78 Mb.