Хочу написать итератор для самописного дерева (авл), но не могу понять как должен вести себя итератор во время инкременирования? Тоесть, в зависимости от положения элеманта, на который указывает итератор (нахождение в правой или левой ветке) он должен поступать по разному. К тому же он должен иметь возможность подниматься вверх по дереву, но узлы указывают только на потомков, а не на родителей. Нужно дописывать в каждый узел указатель на потомка? Как подобная задача решена в stl
?
2 ответа
Если вы хотите реализовать "лековесный" итератор по дереву, то да, в такой ситуации вам придется тем или иным образом в узлах дерева также хранить указатели на их предка. Детали такого хранения могут отличаться, но общая идея остается неизменной: надо уметь по данному узлу дерева определить его предка на основе информации, хранящейся именно в самом дереве.
Если такое хранение реализовано в самом дереве, то обход дерева итератором становиться относительно тривиальной задачей (в зависимости от того, какой порядок обхода вам нужен).
Если вы не имеете возможности хранения связи потомок-предок в самом дереве, то "лековесного" итератора не получится: каждый итератор должен будет хранить внутри себя "тяжеловесное" состояние. А именно: путь от корня дерева до текущего узла дерева. Этот путь и даст итератору возможность возвращаться из потомка в передка, когда такая необходимость возникает в процессе обхода.
Разумеется, если у вас есть выбор, наиболее разумным является именно первый вариант с "лековесным" итератором. Именно так это и реализуется в STL.
Не знаю как написаны итераторы для стандартных контейнеров, но чтобы выразить свое мнение, написал незаконченный и недоработанный класс дерева со своим итератором:
template <class T>
class Tree {
struct Node {
T data;
Node *parent;
Node *left;
Node *right;
Node(const T& t) :
data(t), left(0), right(0), parent(0) {}
};
Node *current;
std::less<int> cmp;
public:
Tree(const T& t = T()) : current(new Node(t)) {}
~Tree();
Tree(const Tree &);
Tree& operator =(const Tree&);
using Itcat = std::bidirectional_iterator_tag;
void insert(const T&);
// ищем в ветке, с конкретным корнем, предыдущий элемент по компаратору
Node* next_element(Node*);
// указатель на следующий элемент по компаратору
Node* prev_element(Node*);
struct iterator : public std::iterator<Itcat,Tree<T>::Node>
{
using It = std::iterator<Itcat,Tree<T>::Node>;
using reference = typename std::iterator_traits<It>::reference;
Node* cur;
iterator(Node* p = nullptr) : cur(p) {}
reference operator *() { return *cur; }
// если, допустим вы хотите, чтобы после ++ итератор указывал на
// следующий элемент по возрастанию, что вполне естественно
// для копаратора less<T>
iterator& operator ++() {
// current должен указывать на предыдущий элемент по компаратору
//для нашего копаратора
if(cur->right)
cur = next_element(cur->right);
else {
cur = next_element(cur->parent);
}
return *this;
}
iterator& operator --() {
if(cur->left)
cur = prev_element(cur->left);
return *this;
}
};
};
Демонстрация того, что пока вы не напишете свой класс, не выразите пожелания, какой элемент вы хотите получать с помощью итератора и при дальнейших операций с ним, то невозможно написать для него итератор, ведущий себя корректно. Т.е. итераторный класс в своей реализации зависит от класса, чьим итератором он является. Ведь деревья бывают разные и написаны разным стилем... Вы в вопросе не показали нужную информацию о вашем классе, и мне кажется, поэтому вы до сих пор не получили конкретного ответа
-
1ну вообще ответ на мой вопрос я уже получил: в комментариях, где предложили использовать стэк - этого мне вполне достаточно. К тому же я указывал, что элементы дерева не указывают на родителя - в этом и была вся проблематика! Если у ноды родитель есть, то никакого вопроса нет, так, как итератор может беспрепятственно обойти все дерево. Но не в случае, когда у ноды нет родителя - тогда итератор никак не сможет обратится к родителю - в этом и был вопрос! Тобишь есть (о тех что я знаю) два решения: дописать родителя или сделать стэк внутри итератора (что я сейчас и делаю). – Andrej Levkovitch 13 июл '18 в 8:34
auto alfa = stack.begin();
а дальше его инкреминируете:++alfa
- и как итератор должен инкреминироваться, если у вас операция инкремента определена в классе Stack? – Andrej Levkovitch 12 июл '18 в 14:33