Как проходить через контейнер в другом классе?

Question

Я сталкивался с этой проблемой несколько раз и хотел бы узнать, есть ли простой способ или шаблон, который я могу использовать для его решения.

Представьте себе древовидную структуру, в которой каждый узел содержит контейнер STL (вектор) указателей на детей. Я хочу, чтобы клиентский код мог пересекать это дерево и перебирать дочерние контейнеры для доступа к другим частям.

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

Должен ли я попытаться сделать класс итератора для моего типа узла, иметь метод итераторов вектора вершин узла, или есть более элегантный шаблон, который мне не хватает?

Edit: Я хочу еще раз подчеркнуть, что в то время как я вижу некоторые хорошие идеи, представленные, у меня есть контейнеры указателей к другим узлам. Возврат vector<node *>::const_iterator не будет препятствовать вызовам клиентов неконстантными методами на узле. Он только защищает самих указателей от указания на разные объекты.

Answer 1

Что-то вроде этого, как правило, достаточно:

class node 
{ 
public: 
    typedef std::vector<node> node_list; 
    typedef node_list::const_iterator const_iterator; 

    const_iterator begin() const { return children_.begin(); } 
    const_iterator end() const { return children_.end(); } 

private: 
    node_list children_; 
} 

Это позволяет изменить базовый тип контейнера без изменения кода, который перебирает через node «s детей.

Это имеет тот недостаток, что его утечку детали реализации, потому что код, который использует ваш node::const_iterator знает, что это итератор произвольного доступа (поскольку std::vector:: const_iterator является случайным итератором доступа), так что вы можете иметь трудное время переключение на контейнер которые не поддерживают произвольный доступ.

Если вы хотите иметь возможность управлять классом итератора самостоятельно, вы, вероятно, захотите создать свой собственный класс iterator, который обеспечивает точное поведение, которое вы хотите предоставить.

Answer 2

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

Answer 3

Это не прямой ответ на ваш вопрос, а альтернативный подход. Вместо того, чтобы клиентский код запускал показ, вы можете пойти за control inversion, зарегистрировав функтор обратного вызова. Например:

// Derive from this class to create a visitor 
class AbstractVisitor 
{ 
public: 
    virtual void operator() (const T &) = 0; 
}; 


// Your recursive data-structure class 
class MyClass 
{ 
public: 
    void walk(AbstractVisitor &v) const 
    { 
     // Call the client callback 
     v(payload); 
     for (std::vector<MyClass>::const_iterator it = children.begin(); 
      it != children.end(); ++it) 
     { 
      // Recurse 
      it->walk(v); 
     } 
    } 

private: 
    T payload; // Some sort of payload associated with the class 
    std::vector<MyClass> children; 
}; 


// You could have different visitor classes to do different things 
class MyVisitor : public AbstractVisitor 
{ 
public: 
    virtual void operator() (const T &t) 
    { 
     // Do something with t 
    } 
} 


int main() 
{ 
    MyClass m; 
    MyVisitor v; 
    ... 
    m.walk(v); 
} 

Завершение полного обкатки!