c++ - 如何从高性能的输入迭代器返回变体？

Question

我有一些文件格式解码器，它返回自定义 input iterator 。此迭代器的值类型(当使用 *iter 取消引用它时)可以是多种标记类型之一。

这是一个简化的使用示例:

File file {"/path/to/file"};

for (const auto& token : file) {
    // do something with token
}

这个 token 怎么可能有多种可能的类型？根据 token 的类型，其有效负载的类型也会发生变化。

在遍历过程中，性能非常重要。例如，我不想进行任何不必要的分配。这就是为什么迭代器的类型是输入迭代器:一旦您推进迭代器，根据 InputIterator 标记的要求，前一个标记就会失效。

到目前为止我有两个想法:

1. 使用单个Token类，该类具有所有可能的有效负载(及其公共(public)getter)的私有(private) union 和公共(public)类型ID(枚举) setter/getter 。 用户需要打开此类型 ID 才能知道要调用哪个有效负载 getter:

   for (const auto& token : file) {
       switch (token.type()) {
       case Token::Type::APPLE:
           const auto& apple = token.apple();
           // ...
           break;
   
       case Token::Type::BANANA:
           const auto& banana = token.banana();
           // ...
           break;
   
       // ...
       }
   }
   

   虽然这可能是我在 C 中选择的，但我不喜欢 C++ 中的这种解决方案，因为用户仍然可以调用错误的 getter，并且没有什么可以强制执行此操作(除了我想避免的运行时检查)出于性能考虑)。

2. 创建一个抽象 Token 基类，该基类具有用于接受访问者的 accept() 方法，以及继承的多个具体类(每种有效负载类型一个)这个基类。在迭代器对象中，在创建时实例化每个具体类之一。还有一个 Token *token 成员。迭代时，填充适当的预分配负载对象，并设置this->token = this->specificToken。使 operator*() 返回 this->token (引用)。要求用户在迭代期间使用访问者(或更糟糕的是，使用dynamic_cast):

   class MyVisitor : public TokenVisitor {
   public:
       void visit(const AppleToken& token) override {
           // ...
       }
   
       void visit(const BananaToken& token) override {
           // ...
       }
   };
   
   TokenVisitor visitor;
   
   for (const auto& token : file) {
       token.accept(visitor);
   }
   

   这为每个 token 引入了额外的函数调用，至少其中一个是虚拟的，但这可能不是世界末日；我对这个解决方案保持开放态度。

还有其他有趣的解决方案吗？我认为返回 boost::variant或std::variant与想法 #2 相同。

Answer 1

Although this is probably what I would choose in C, I'm not a fan of this solution in C++ because the user can still call the wrong getter and nothing can enforce this (except run-time checks which I want to avoid for performance concerns).

您可以反转该方法并接受可调用对象，而不是向用户返回迭代器。然后您可以在内部迭代容器并分派(dispatch)正确的类型。这样，用户就不会再因忽略您标记的 union 所携带的信息而犯错误，因为您负责考虑它。

这是一个最小的、有效的示例来展示我的意思:

#include <vector>
#include <utility>
#include <iostream>

struct A {};
struct B {};

class C {
    struct S {
        enum { A_TAG, B_TAG } tag;
        union { A a; B b; };
    };

public:
    void add(A a) {
        S s;
        s.a = a;
        s.tag = S::A_TAG;
        vec.push_back(s);
    }

    void add(B b) {
        S s;
        s.b = b;
        s.tag = S::B_TAG;
        vec.push_back(s);
    }

    template<typename F>
    void iterate(F &&f) {
        for(auto &&s: vec) {
            if(s.tag == S::A_TAG) {
                std::forward<F>(f)(s.a);
            } else {
                std::forward<F>(f)(s.b);
            }
        }
    }

private:
    std::vector<S> vec;
};

void f(const A &) {
    std::cout << "A" << std::endl;
}

void f(const B &) {
    std::cout << "B" << std::endl;
}

int main() {
    C c;
    c.add(A{});
    c.add(B{});
    c.add(A{});
    c.iterate([](auto item) { f(item); });

}

在 Coliru 上查看它并运行.