Вассал моего вассала не мой вассал
Продолжаю пережевывать контейнеры библиотеки STL, на этой неделе очередь Set.
Идея была грандиозная, взять красно-черное дерево из прошлой недели, унаследовать в set, map, multiset и радоваться, горя не зная.
ХА. Радоваться не получилось. При создании контейнера в main все работало, были видны методы и общие поля класса-родителя. Но при написании шаблонных функций для класса было видно 0 целых, хрен десятых, т.е. я не могла напрямую обратиться к полю дерева внутри упорядоченного множества. Путем шаманских танцев с использованием using Имя класса :: функция/поле_класса удалось подключить функции дерева в шаблон и наследование вроде бы заработало. До тех пор, пока я не начала писать итератор для Set.
Этот аллигатор с++ треплет мне нервы уже не один контейнер. Тем не менее чувствую, что иду по спирали усложнения и каждый раз понимаю глубже. Если в списке было достаточно одного узла в итераторе, по которому он будет туда-сюда бегать, то для множества один узел уже не проканал. Точнее он вполне мог бы быть реализован с одним полем, если бы в ноде красно-черного дерева у меня существовало поле родитель./
...Лирическое отступление...
Структура красно-черного дерева подразумевает наличие нескольких нод, связанных друг с другом через указатели лево и право. В самой простой реализации поиска мы спускаемся по дереву в зависимости от значения: уходим влево, если меньше, вправо - если больше. Такая реализация проще в балансировке, но сложнее в поиске конкретного элемента - без указателя на верхний узел физически нельзя вернуться к ноде, от которой произошел спуск.
/ Снова к итератору. Попытка добавить поле родитель в структуру дерева полетела в тартарары, элегантно завершившись сегфолтом примерно раз 100. В итоге родилась рекурсивная функция обхода множества, возвращающая нужный элемент. Тут нужно уточнить, что элементы в множестве идут не друг за другом, и то, что мы привыкли понимать как отсортированное множество - результат скачек от одного узла к другому. И итератор должен выводить элементы по возрастанию/убыванию, а не от узла к узлу в дереве, что моя функция и делала, но принимала она еще один параметр - корень дерева. Тут драма о семейных связях началась снова. Класс итератора существовал вне класса множества, и попытки обратиться к корню дерева ни к чему не привели. Но, оказывается, если класс итератора реализован внутри класса дерева, он также не может обратиться к элементам внешнего класса. Пришлось отойти от канонов STL, создать второе поле внутри итератора множества и при создании итератора передавать не только сам итератор, но и указатель на множество. Чтобы знал, откуда корни растут.
P.S. искренне надеюсь домучить этот проект до конца августа.
#cpp #школа_21