Здесь приведена реализация аналога std::set (с некоторыми упрощениями) с использованием структуры 2-3 дерева.
template<class ValueType> class Set;
Релизованные конструкторы и методы:
-
Конструктор по умолчанию.
-
Конструктор, принимающий два итератора, первый из которых указывает на первый элемент последовательности, второй указывает на элемент, следующий за последним элементом. Каждый элемент последовательности имеет тип ValueType.
-
Конструктор, принимающий std::initializer_list описанных выше элементов.
-
Конструктор копирования.
-
Оператор присваивания.
-
Деструктор.
-
Константный метод size, возвращающий количество элементов в множестве.
-
Константный метод empty, возвращающий true, если множество пустое, и false в противном случае.
-
Метод insert, который добавляет элемент во множество. Если элемент уже присутствует, метод не должен ничего делать. Тип возвращаемого значения void.
-
Метод erase, который удаляет переданный элемент из множества. Если искомого элемента во множестве нет, метод не должен ничего делать. Тип возвращаемого значения void.
-
Описан тип iterator, соответствующий итератору, с помощью которого можно просмотреть содержимое контейнера, а также соответствующие методы begin и end (begin указывает на первый элемент, end – на элемент, следующий за последним), итератор умеет адресовать значения типа const ValueType. Конечно же, поскольку множество упорядоченное, итератор перебирает элементы в порядке возрастания. Также Возращаемые итераторы удовлетворяют требованиям bidirecional. Однако итераторы могут стать недействительными после операций вставок и удалений.
-
Константный метод find, который по заданному значению возвращает итератор на соответствующий элемент во множестве, либо end(), если искомого элемента нет во множестве.
-
Константный метод lower_bound, который по заданному значению x возвращает итератор на наименьший элемент множества y, такой что y ≥ x, или end(), если искомого элемента во множестве нет.
Итерирование по всему контейнеру (от begin до end) занимает линейное по числу элементов во множестве время.
Для сравнения элементов используется только оператор <.