Братцы, хотелось бы услышать мнение, как можно имплентировать следующую вещь.
Есть некая иерархическая структура, элементы которой представлены объектами типа

class TreeNode
{

// ...

public:
    TreeNode* pParent;        // ссылка на элемент - родитель
    list<TreeNode*> Children; // элементы, являющиеся потомками данного
}

Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии. Т.е. для структуры

node0            -- индекс элемента 0
    node00       -- 1
    node01       -- 2
        node010  -- 3
        node011  -- 4
    node02       -- 5
        node020  -- 6
    node03       -- 7
node1            -- 8

Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?

Здравствуйте, Kislookhin, Вы писали:

K>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?

Можно пойти еще наоборот, использовать вектор, тогда доступ по индексу уже есть, и делать эмуляцию дерева.

Здравствуйте, _nn_, Вы писали:

__>Здравствуйте, Kislookhin, Вы писали:

K>>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?

__>Можно пойти еще наоборот, использовать вектор, тогда доступ по индексу уже есть, и делать эмуляцию дерева.

imho это сложнее будет. В силу специфики задачи очень много операций придется эмулировать. А описанный итератор с произвольным доступом нужен только в одном месте...

Здравствуйте, Kislookhin, Вы писали:

K>Братцы, хотелось бы услышать мнение, как можно имплентировать следующую вещь.
K>Есть некая иерархическая структура, элементы которой представлены объектами типа

K>

K>class TreeNode
K>{

K>// ...

K>public:
K>    TreeNode* pParent;        // ссылка на элемент - родитель
K>    list<TreeNode*> Children; // элементы, являющиеся потомками данного
K>}
K>

K>Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии. Т.е. для структуры

K>

K>node0            -- индекс элемента 0
K>    node00       -- 1
K>    node01       -- 2
K>        node010  -- 3
K>        node011  -- 4
K>    node02       -- 5
K>        node020  -- 6
K>    node03       -- 7
K>node1            -- 8
K>

K>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?


Надо еще параллельно держать вектор ссылок на элементы дерева, чтобы обращатсья по индексу.

Здравствуйте, mefrill, Вы писали:

K>>Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой итератор, позволяющий перемещаться по нодам именно таким оьразом? Или это лишнее?

M>Надо еще параллельно держать вектор ссылок на элементы дерева, чтобы обращатсья по индексу.

Вариант неплохой, но так как с деревом происходят операции вставки и удаления веток, вектор приходится часто перестраивать, что не хочется...

Здравствуйте, Kislookhin, Вы писали:

K>А описанный итератор с произвольным доступом нужен только в одном месте...

1) Если это нужно нечасто и между "пачкой" последовательных запросов на произвольный доступ дерево не меняется: перед "пачкой" обходим дерево и формируем соответствующий временный вектор со ссылками на его элементы, далее работаем с ним. Можно отслеживать изменения в дереве и делать перестройку вектора "по запросу".
2) Если изменение дерева происходит редко: постоянно поддерживаем вектор со ссылками на элементы, обновляем его одновременно с деревом.
3) Дерево часто модифицируется, доступ по индексу нужен редко и случайно разбросан по времени: обход дерева при соответствующем запросе.

Здраствуйте, Kislookhin, Вы писали:

хъ
> Вопрос: как это сделать правильнее? Изобрести свой контейнер и свой
> итератор, позволяющий перемещаться по нодам именно таким оьразом? Или
> это лишнее?
Можно посмотреть на реализацию итераторов в A STL-like C++ tree <br />
class от Kasper Peeters или взять этот контенейр уже готовым, если условия лицензирования позволяют.
--
foobar2000 v0.8.3: 04. Amon Tobin — Sordid [Permutation]

Здравствуйте, Kislookhin, Вы писали:

K>Вариант неплохой, но так как с деревом происходят операции вставки и удаления веток, вектор приходится часто перестраивать, что не хочется...
Ну и не перестраивай на каждый запрос. Тут есть варианты
1)Создать метод который надо дергать для того чтобы перестроить индекс. Это проще всего но можно наступить на грабли забыв вызвать этот метод перед доступом.
2)Создать флаг актуальности индекса те в случае вставки/удаления сбрасываем этод флаг, а при попытке доступа по индексу проверяем и в случае если индекс валиден то обращаемся по индексу, а если нет то перестраиваем индекс...

Здравствуйте, 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; // проехали поддерево очередного ребёнка
    }
  }
};

Другой вариант решения (если поиск по номеру — крайне редкая операция, и можно себе позволить линейный поиск).

class node
{
public:
  // базовые функции
  node* parent() const;
  node* first_child() const;
  node* next_sibling() const // может быть определён через функцию next_child
    { return parent() ? parent()->next_child(this) : NULL; }
  node* next_child(node* child) const;

  // линейный поиск
  node* next_linear() const
  {
    node* p;
    p = first_child(); if(p) return p;
    node* q = this;
    while(true)
    {
      p = q->next_sibling(); if(p) return p;
      q = q->parent(); if(!q) return NULL;
    }
  }

  node* next_nth(size_t n) const
  {
    node* p = this;
    while(p && n) { p = p->next_linear(); --n; }
    return p;
  }
};

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Kislookhin, Вы писали:

K>>Все вроде понятно и прозрачно. Но с этим деревом нужно работать специфичным образом: требуется получать элемент дерева по номеру, без учета иерархии.

К>Вариант решения:

Спасибо за подробный ответ. Пошел делать.

Здравствуйте, Kislookhin, Вы писали:

Есть еще решение на фиберах. В дотнете уже есть такой итератор (правда в 2 ке).