Skip to content

Latest commit

 

History

History
291 lines (194 loc) · 18.1 KB

README_RUS.md

File metadata and controls

291 lines (194 loc) · 18.1 KB
Raw

Контейнеры

Мною был реализован один из видов самобалансирующихся двоичных деревьев поиска - красно-черное дерево art red black tree

Также были реализованы контейнеры стандартной библиотеки - map set multiset

Стиль кода в проекте - Google code style c++

пространоство имен (namespace) во всем проекте используется jokerooo7 namespace jokerooo7

Красно-черное дерево

Красно-черное дерево реализовано в ввиде класса RBTree, которые может представлено в виде одного шаблонного параметра:

#include "red_black_tree.h"

int main() {
    jokerooo7::RBTree<int> my_class_one;
    jokerooo7::RBTree<std::pair<int, bool>> my_class_two;
}

Моя реализация не использует аллокаторов и компараторов:

template <typename K>
class RBtree {...}

Файлы

Красно-черное дерево представленно в виде файлов red_black_tree.h red_black_tree.tpp

Методы RBTree (public)

Конструкторы и операторы присваивания

Согласно правилу пяти c++, у меня реализовы все базовые конструкции. Дополнительно реализован конструктор с передачей в дерево данных по формату std::initializer_list<value_type>

  RBTree() = default;
  RBTree(std::initializer_list<value_type> const& items);
  RBTree(const RBTree& other);
  RBTree(RBTree&& other) noexcept;
  ~RBTree();

  RBTree& operator=(const RBTree& other);
  RBTree& operator=(RBTree&& other);

Старт и конец

Как и в стандартной библиотеке, у меня реализованы два метода - begin() и end(). begin() - возращает итератор который указывает на первоначальную ветку дерева (наименьшую). end() - возращает итератор который указывает на пустой лист, следующий за самым наибольшим элементом(nullptr), при необбходимости можно вернуться на наибольший элоемент.

  iterator begin() const;
  iterator end() const;

  // возращают неизменные итераторы
  const_iterator cbegin() const;
  const_iterator cend() const;
    typename jokerooo7::multiset<K>::iterator iter_one = my_class_one.begin();
    ++iter_one;  // вернет следующий узел, по значению выше него
    typename jokerooo7::multiset<K>::iterator iter_two = my_class_one.end();
    --iter_two;  // вернет самый наибольший элемент

Размер контейнера и максимальный размер

Реализовал методы size() и max_size() size() - возращает количество элементов в дереве max_size() - использует клвсс std::allocator<value_type> для определения максимального размера контейнера

Вставка множества элементов

insert_many() - метод, который принимает большое количество аргументов и вставляет в контейнер и возращает вектор с парой итераторов и условным(bool) значением, вставился элемент или нет. Использует внутри себя protected метод InsertInTree() для вставки элементов

Перемещение элементов

Для того, чтобы два контейнера поменялись элементами - используется метож swap(RBTree &other), который принимает другой класс в качестве того, чтобы заменить два элемента. merge(RBTree& other) - Используется для того, чтобы с другого контейнера принять все его элементы, без удаления элементов из другого.

Удаление элемента

Для удаления элемента используется метод erase(iterator any), который принимает итератор, который надо удалить с контейнера. Для очистки всего контейнера используется метод clear()

Методы RBTree (protected)

Вставка в дерево

Используется метод InsertInTree*(), в качестве аргументов функции он принимает значение, текущего типа в контейнере, и пару флагов (std::pair<bool, bool> mode). mode.first - Нужно ли переписовать уже существующие элементы, mode second - можно ли добавлять одинаковые элементы в конейнер. Возращает он пару, итератор на вставленный элемент и его условное(bool) значение, был ли вставлен элемент или нет.

Проверка содержимого контейнера

Реализован метод именованный Content() для проверки существет ли текущий элемент в контейнере ил нет. Принимает он значение и ищет его в контейнере. C помощью private методов IsItMore() IsItLess() AreTheyEqual() сравнивает как просто элементы, так может сравнивать тип данных std::pait<AnyType, AnyType>.

Сравнение двух классов

Реализован вспомогательный метод, для проверки соответствуют ли два текущих контейнера друг дургу.

bool EqualityOfClasses(const RBTree& other)

Методы RBTree (private)

Используются для самобалансировки дерева в случаях удаления, вставки и провеки узлов дерева. Использовался алгоритм из wiki

Внутренние классы (Итераторы)

RBTree содержит два внутренних класса, TreeIterator и TreeConstIterator. Чтобы их вызов в производных классах соответствовал стандартной библиотеки, я использую алиасы iterator и const_iterator

Итераторы как и в стандартной библиотеки не защищены от обращения к удаленному узлу. За этим требуется следить самому.

int main() {
    jokerooo7::RBTree<int> my_class_one;

    typename jokerooo7::multiset<K>::iterator iter_one = my_class_one.begin();
}

У класса итераторов реализованы операторы *, =, ++, --, !=, ==

typename jokerooo7::multiset<K>::iterator iter_one = my_class_one.begin()
*iter_one;  // Вернет значение лежащее в этом итераторе
++iter_one;  // Перейдет к следующему элементу и зафиксирует итератор на этом узле и вернет его
iter_one++;  // Вернет копию текущего итератора, перейдет к следующему и зафиксируется на нем
iter_one != any_iterator;  // Вернет булевое значение - несовпадают они или нет
iter_one == any_iterator;  // Обратное !=
iter_one = any_iterator_or_node;  // Присвоит к текущему итератору - другой итератор или узел дерева, также работает с std::move

библиотеки

#include <сstddef>  // Для работы с типом данных sizee_t
#include <utility>  // Для работы с std::pair
#include <vector>   // Для возврата вектоа со множеством вставок
#include <initializer_list>  // Для вставки большого количества аргументов

map, карта, словарь

Файл с реализацией - "map.h"

Мой класс также, как и класс красно-черное дерево находиться в пространстве имен jokerooo7 и принимает два шаблонных аргумента - ключ и значение template <typename KT, typename T>

#include "red_black_tree.h"

namespace jokerooo7 {

    template <typename KT, typename T>
    class map : public RBTree<std::pair<KT, T> {...}

}

Моя реализация STL библиотеки map использует уже написанное красно-черное дерево. Оно наследует все методы и с помощью конструкции using RBTree<std::pair<KT, T>>::RBTree; наследует абсолютно все конструкторы и декструкторы класса красно-черного дерева.

Алиасы совпадают со стандартной библиотекой и их можно видеть в файлах "map.h"

Методы map (public)

Вставка элементов map

  std::pair<iterator, bool> insert(const value_type& value) {
    return this->InsertInTree(value, std::make_pair(false, false));
  };

  std::pair<iterator, bool> insert(const Key& key, const T& obj) {
    value_type value = std::make_pair(key, obj);
    return this->InsertInTree(value, std::make_pair(false, false));
  };

  std::pair<iterator, bool> insert_or_assign(const Key& key, const T& obj) {
    value_type value = std::make_pair(key, obj);
    return this->InsertInTree(value, std::make_pair(true, false));
  };

Эти три конструкции используют InsertInTree из RBTree, для вставки эементов и возращают тоже самое, что и InsertInTree()

  • Первый метод - вставляет только значение, без ключа
  • Второй метод - вставляет по ключу - значения, без переписывания значения
  • Третий метод - вставляет с переписыванием значения по ключу

Проверка существования ключа

Метод contains() - реализует проверку наличия ключа в контейнере и возращает условное(bool) значение о его наличии или отсутсвтие Функция contains() использует Сontent() для проверки содержимого.

Метод at() - реализует возврат неконстантной ссылки/или константного значения по ключу, если ключ не найден - выкидывает исключение. Использует Сontent()

Оператор [] - Возращает элемент по ключу и позволяет вставить элемент по ключу. Использует at()

set, множество, упорядоченное множество

Файл с реализацией - "set.h"

Мой класс также, как и класс красно-черное дерево находиться в пространстве имен jokerooo7 и принимает один шаблонный аргумента - значение template <typename T>

Моя реализация STL библиотеки [set](https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85) использует уже написанное красно-черное дерево. Оно наследует все методы и с помощью конструкции using RBTree<KT>::RBTree; наследует абсолютно все конструкторы и декструкторы класса красно-черного дерева.

Алиасы совпадают со стандартной библиотекой и их можно видеть в файлах "set.h"

Методы set (public)

Вставка set элементов

  std::pair<iterator, bool> insert(const value_type& value) {
    return this->InsertInTree(value, std::make_pair(false, false));
  };

Вставка элемента value использует InsertInTree из RBTree, для вставки эементов и возращают тоже самое, что и InsertInTree()

Проверка существования значения

contains() - такой же, как и у map, принимает значение, котороые в set является ключем

функция find() - возращает итератор на элемент, который использует Сontent() для проверки содержимого.

multiset, мультимножество

То же, что и set, но позволяет хранить повторяющиеся элементы.

Файл с реализацией - "multiset.h"

Методы multiset (public)

Многие методы RBTree - были переписаны, дополнены и изменена реализация, в связи с дополнением одинакового содержимого

Методы те же самые, что и multiset, дополнены некоторыми:

  • iterator lower_bound(const Key& key) - метод находит первый элемент не меньше заданного
  • iterator upper_bound(const Key& key) - метод который находит больше заданного
  • size_type count(const Key& key) const - возращает количество данных ключей в контейнере
  • std::pair<iterator, iterator> equal_range(const Key& key) - возращает пару итераторов, где первый указывает на первый совпадающий ключ, а второй на следующий (больший по значению) за данным ключом;