c++ - 如何最有效地迭代私有(private)成员 std::vector？

Question

我正在编写一个实现双向链接树的类，我希望用户能够尽可能高效地遍历节点的所有子节点。

Tree.h(缩写):

我省略了迭代中不涉及的所有内容。

class Tree
{
public:
    static Tree& root(){ return *root_; }
    //index-based iteration
    inline unsigned int numChildren() const{ return childrenSize_; }
    Tree& getChild(unsigned int index) const;                       

    //iterator-based iteration                          
    vector<unique_ptr<Tree>>::iterator children_begin(){
        return children_.begin();
    }
    vector<unique_ptr<Tree>>::iterator children_end(){
        return children_.end();
    }

private:
    vector<unique_ptr<Tree>> children_;
    unsigned int childrenSize_;
    Tree* parent_;

    static unique_ptr<Tree> root_;
};

现在，我在这里看到两种可能性:

1。基于索引的迭代

(假设 static unique_ptr<Tree> root 已经构建)

Tree& myTree = Tree::root();
for(int i = 0; i < myTree.numChildren(); ++i;){
    Tree& child = myTree.getChild(i);
    //do stuff with child
}

这看起来很直接而且很省事，因为用户无法访问底层结构。此外，没有太多开销，因为 children_ 的长度-vector 会在树被修改时保存到一个变量中(请相信我)并且内联获取此长度的函数。

2。基于迭代器的迭代

Tree& myTree = Tree::root();
for(vector<unique_ptr<Tree>>:iterator it = myTree.children_begin(); it < myTree.children_end(); ++it; ){
    Tree& child = (*(*it));
    //do stuff with child
}

这看起来既危险又丑陋，但我可以想象它会更快。我这里的问题是用户可以将 unique_ptr 移动到其他地方，我想尽可能地限制使用以避免结构的错误使用。

什么是更有效的方法，它到底有多大的不同？

---

PS:这是我在写这篇文章时想到的第三种方法，但我现在知道如何实现它了:

3。对于( : ) -循环

for (Tree& child : Tree::root()){
    //do stuff with child
}

语法方面，它看起来非常简单，但我不知道 for ( : ) 是什么-loop 确实在内部执行(可能与迭代器一起工作，如果没有 Tree 上的 ->begin() 和 ->end() 函数将无法工作)。

附加问题:是否可以为我自己的类(class)实现这种模式？

Answer 1

根据@WojitekSurowka 的建议，我查看了 boost indirect iterator ，这似乎是一个不错的选择。但是，它似乎与 VS2013 一起工作得不太好，所以我不得不自己编写一个迭代器，这并不像我最初想象的那么难。

根据 this reference，这使我能够充分利用 for ( : ) 循环正如@JoachimPileborg 发布的那样。但是请注意，我的解决方案使用了一个完全自定义的迭代器，它不是从任何 STL vector 派生的，因此不能保证正确地处理所有 STL 操作。

树.h:

class Tree;

class TreeIterator
{
public:
    TreeIterator(std::vector<unique_ptr<Tree>>::iterator& pos) :
    pos_(pos)
    {};

    bool operator==(const TreeIterator& rhs) { return pos_ == rhs.pos_; }
    bool operator!=(const TreeIterator& rhs) { return pos_ != rhs.pos_; }
    bool operator<=(const TreeIterator& rhs) { return pos_ <= rhs.pos_; }
    bool operator>=(const TreeIterator& rhs) { return pos_ >= rhs.pos_; }
    bool operator<(const TreeIterator& rhs) { return pos_ < rhs.pos_; }
    bool operator>(const TreeIterator& rhs) { return pos_ > rhs.pos_; }

    void operator ++(){ ++pos_; }

    //this is the most important thing!!!
    Tree& operator*(){
        return **pos_; //double-dereferencing
    }

private:
    std::vector<unique_ptr<Tree>>::iterator pos_;
};


class Tree
{
public:
    static Tree& root(){ return *root_; }                   

    //regular begin and end functions for iterators, used by the `for( : )`-loop        
    TreeIterator& begin(){
        return *(beginIter_ = std::move(unique_ptr<TreeIterator>(new TreeIterator(children_.begin()))));
    }
    TreeIterator& begin(){
        return *(endIter_ = std::move(unique_ptr<TreeIterator>(new TreeIterator(children_.end()))));
    }

private:
    vector<unique_ptr<Tree>> children_;
    Tree* parent_;
    unique_ptr<TreeIterator> beginIter_;
    unique_ptr<TreeIterator> endIter_;
    static unique_ptr<Tree> root_;
};

所以现在我可以执行以下操作:

for(Tree& child : Tree::root()){
    //do stuff with child
}

太棒了!