Братцы, хотелось бы услышать мнение, как можно имплентировать следующую вещь.
Есть некая иерархическая структура, элементы которой представлены объектами типа
class TreeNode
{
// ...public:
TreeNode* pParent; // ссылка на элемент - родитель
list<TreeNode*> Children; // элементы, являющиеся потомками данного
}
Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии. Т.е. для структуры
Здравствуйте, Kislookhin, Вы писали:
K>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?
Можно пойти еще наоборот, использовать вектор, тогда доступ по индексу уже есть, и делать эмуляцию дерева.
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, Kislookhin, Вы писали:
K>>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?
__>Можно пойти еще наоборот, использовать вектор, тогда доступ по индексу уже есть, и делать эмуляцию дерева.
imho это сложнее будет. В силу специфики задачи очень много операций придется эмулировать. А описанный итератор с произвольным доступом нужен только в одном месте...
Re: Итератор, иерархическая структура, как сделать?
Здравствуйте, Kislookhin, Вы писали:
K>Братцы, хотелось бы услышать мнение, как можно имплентировать следующую вещь. K>Есть некая иерархическая структура, элементы которой представлены объектами типа
K>
K>class TreeNode
K>{
K>// ...
K>public:
K> TreeNode* pParent; // ссылка на элемент - родитель
K> list<TreeNode*> Children; // элементы, являющиеся потомками данного
K>}
K>
K>Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии. Т.е. для структуры
K>
K>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?
Надо еще параллельно держать вектор ссылок на элементы дерева, чтобы обращатсья по индексу.
Re[2]: Итератор, иерархическая структура, как сделать?
Здравствуйте, mefrill, Вы писали:
K>>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?
M>Надо еще параллельно держать вектор ссылок на элементы дерева, чтобы обращатсья по индексу.
Вариант неплохой, но так как с деревом происходят операции вставки и удаления веток, вектор приходится часто перестраивать, что не хочется...
Re[3]: Итератор, иерархическая структура, как сделать?
Здравствуйте, Kislookhin, Вы писали:
K>А описанный итератор с произвольным доступом нужен только в одном месте...
1) Если это нужно нечасто и между "пачкой" последовательных запросов на произвольный доступ дерево не меняется: перед "пачкой" обходим дерево и формируем соответствующий временный вектор со ссылками на его элементы, далее работаем с ним. Можно отслеживать изменения в дереве и делать перестройку вектора "по запросу".
2) Если изменение дерева происходит редко: постоянно поддерживаем вектор со ссылками на элементы, обновляем его одновременно с деревом.
3) Дерево часто модифицируется, доступ по индексу нужен редко и случайно разбросан по времени: обход дерева при соответствующем запросе.
Все, что здесь сказано, может и будет использоваться против меня...
Re: Итератор, иерархическая структура, как сделать?
хъ > Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой > итератор, позволяющий перемещаться по нодам именно таким оьразом? Или > это лишнее?
Можно посмотреть на реализацию итераторов в A STL-like C++ tree <br />
class от Kasper Peeters или взять этот контенейр уже готовым, если условия лицензирования позволяют.
--
foobar2000 v0.8.3: 04. Amon Tobin — Sordid [Permutation]
Re[3]: Итератор, иерархическая структура, как сделать?
Здравствуйте, Kislookhin, Вы писали:
K>Вариант неплохой, но так как с деревом происходят операции вставки и удаления веток, вектор приходится часто перестраивать, что не хочется...
Ну и не перестраивай на каждый запрос. Тут есть варианты
1)Создать метод который надо дергать для того чтобы перестроить индекс. Это проще всего но можно наступить на грабли забыв вызвать этот метод перед доступом.
2)Создать флаг актуальности индекса те в случае вставки/удаления сбрасываем этод флаг, а при попытке доступа по индексу проверяем и в случае если индекс валиден то обращаемся по индексу, а если нет то перестраиваем индекс...
... << RSDN@Home 1.1.4 rev. 185 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Итератор, иерархическая структура, как сделать?
Здравствуйте, Kislookhin, Вы писали:
K>Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии.
Вариант решения:
Каждый узел знает "вес" — т.е. количество узлов его поддерева (вес листа равен 1).
Любая операция над деревом должна сохранять целостность этой информации.
Поиск узла по номеру требует O(K * log N) времени, где K — количество детей одного узла.
class node
{
size_t weight_;
list<node*> children_;
public:
size_t weight() const { return weight_; }
node* find(size_t i) const
{
if(i==0) return this;
if(i >= weight()) return NULL;
--i; // себя мы уже проверили, поедем по детям
list<node*>::const_iterator it;
for(it = children_.begin(); it != children_.end(); ++it)
{
node* child = *it;
size_t w = child->weight();
if(i < w) return child->find(i);
i -= w; // проехали поддерево очередного ребёнка
}
}
};
Другой вариант решения (если поиск по номеру — крайне редкая операция, и можно себе позволить линейный поиск).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Kislookhin, Вы писали:
K>>Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии.
К>Вариант решения:
Спасибо за подробный ответ. Пошел делать.
Re: Итератор, иерархическая структура, как сделать?