多态迭代器？

Question

我正在使用 C++ 模板结构 Node 和存储指向这些 Node 对象的指针的复杂集合类 Collection。 Node结构定义如下：

template <typename T>
struct Node {
    T data;
    // Other methods and members
};

集合类是模板化的并保存

Node

指针：

template <typename T> 
class Collection {
     Node* root;
      
     std::vector<Node*> query(Condition condition); 
     ...
};

我还有一个函数

FoosConsumer

可以处理一系列

Foo

对象：

template <typename FooRange>
void FoosConsumer(FooRange &foos) {
    for(Foo &foo : foos) {
        // Do something with foo
    }
}

当我需要查询我的集合以获取节点本身或仅获取这些节点的数据成员时，就会出现问题。理想情况下，我想直接迭代

collection.query(condition)

返回的节点的数据元素，然后将它们传递给

FoosConsumer

。这就是我想要实现的目标：

int main() {
    DataCollection<Foo> collection;

    // Can iterate over nodes
    for(auto &node : collection.query(condition)) { ... }

    // If I need to access `data` I do this:
    for(auto &node : collection.query(condition)) { 
        Foo &data = node.data;
    }

    // My desire: Iterate over `data` of each node directly
    for(Foo &el : collection.query(condition)) { ... }

    // The intended use case is:
    FoosConsumer(collection.query(condition));
}

目前，我正在使用一种感觉低效且麻烦的解决方法：

std::vector<Foo*> tmp;
for(Node<Foo> &node : collection.query(condition)) {
    tmp.push_back(&node.data);
}
FoosConsumer(tmp);

是否有更优雅的方法来直接迭代我的集合中节点的数据成员？我正在寻找一种解决方案，允许对数据属性进行无缝迭代，而不需要中间容器或额外的循环。

我确实可以实现自定义迭代器或代理：

for(Node &node : collection.queryNode(condition)) {}
for(Data &node : collection.queryFoo(condition)) {}

但是，由于

Node*

和

Data*

共享相同的地址，并且对

Node

大小进行算术运算，我确信有一个技巧。

Answer 1

当我最后实现一个复杂的

tree

结构时，我最终做了类似的事情：

namespace impl {
    enum node_dir {left=0,right=1};
    struct node {
        node* parent;
        node* child[2];

        const node* deep_child_to(node_dir dir) const;
        const node* next_child_to(node_dir dir) const;
        const node* parent_with_other_child_to(node_dir dir) const;
        const node* next_iter_in(node_dir dir) const;
        //etc. Most tree graph methods here, including mutating
    };
}

这阻止了每种模板类型生成相同的树维护代码。容器类本身最终变得微不足道，尽管需要一个尴尬的转换：

template<class T>
class container {
    struct node : impl::node {
         std::aligned_storage_t<sizeof(T), alignof(T)> buffer;
         //details...
    };
    T& data(impl::node* n) {return static_cast<node>(n).buffer;}
    impl::node root = {};

public:
    T& first() {return data(root->deep_child_to(impl::left));}
    void push_back(T& v) {root->push_back(new node(v));}
    //etc.  Almost every method was exactly one line.
    //note the class NEVER exposes `node` or `impl::node` publicly.
}

模板类的方法每个都恰好是一行，这一事实有助于确认实例之间重复的代码最少。

迭代器的工作原理基本相同。他们有一个

node*

并调用

next_iter_in(dir)

，然后将其投射到

container<node>

以提取

data

。有了这些原则，您的

query

方法同样可以在

impl::node

上运行，并且仅在用户边界处转换为

T

。

另请注意，使用

node_dir

和

child[2]

允许我使用相同的 C++ 和二进制代码来镜像每个操作。