如何让派生类通过虚方法返回任何类型的迭代器？

Question

我想写一个允许用户实现某些行为的小型库，以便库可以使用他自己的基础数据结构。在这种特殊情况下（虽然我简化了），我试图定义是这样的：

class LibraryClass { 
    virtual std::vector<int>::const_iterator intsBegin() const = 0; 
    virtual std::vector<int>::const_iterator intsEnd() const = 0; 
}; 

换句话说，图书馆将接受任何派生类，允许它遍历一个矢量工作整数。现在棘手的是：我不想强制使用矢量。实际上，只要我能够检测到它的结束时间并将其解引用为整数，任何迭代器都可以用于整数。下面是缺少位：

class LibraryClass { 
    virtual /* ??? */ intsBegin() const = 0; 
    virtual /* ??? */ intsEnd() const = 0; 
}; 

class UserClass { 
    /* This should be allowed, here I'm using vector as an example. */ 
    std::vector<int>::const_iterator intsBegin() const; 
    std::vector<int>::const_iterator intsEnd() const; 
}; 

现在，我知道如何通过方法的参数的模板有that kind of behaviour，但我不能找到一个办法把它用于在虚拟方法的返回值，因为：

• 迭代器是否为const不是很重要。
• 基类中不会有任何默认行为。
• 该机制不能被继承错误：从int迭代器派生的类也应该被接受为返回类型，因为它们满足要求。我不认为这是一个问题，因为传递性，但仍然。
• 理想情况下，应该强制begin和end方法在给定派生类中具有相同的迭代器类型。
• 更理想的是，我想避免使用Boost来处理像enable_if这样的事情。该库是用C++ 11编写的（至少我试过）。

Answer 1

如何提供一个界面，让用户可以随心所欲地处理数据，但不使用迭代器？

class LibraryClass { 
public: 
    virtual void visitInts(std::function<void(int)> f) = 0; 
}; 

class UserClass : public LibraryClass { 
public: 
    void visitInts(std::function<void(int)> f) override { 
     for (int data : m_vec) 
      f(data); 
    } 
private: 
    std::vector<int> m_vec; 
}; 

你失去了，说：std::binary_search的能力，但你大多具有相同的通用性，而不强迫一个特定的存储机制对UserClass。

Answer 2

您也可以使迭代器成为虚拟类，例如， （未测试，并obviosly不完全）：

class LibraryClass { 
protected: 
    struct IteratorBase { // user needs to implement this: 
    virtual const int& deref() const = 0; 
    virtual void increment() = 0; 
    virtual void decrement() = 0; 
    // further methods, e.g., comparison and maybe cloning 
    }; 
    virtual std::unique_ptr<IteratorBase> intsBegin_() const = 0; 
    virtual std::unique_ptr<IteratorBase> intsEnd_() const = 0; 
public: 
    class Iterator { 
    friend class LibraryClass; 
    std::unique_ptr<IteratorBase> iter; 
    Iterator(std::unique_ptr<IteratorBase>&& iter_) : iter(std::move(iter_) {} 
    public: 
    const int& operator*() { return iter->deref(); } 
    const Iterator& operator++() { iter->increment(); return *this; } 
    // further operators ... 
    }; 
    Iterator intsBegin() const { return Iterator(intsBegin_()); } 
    Iterator intsEnd() const { return Iterator(intsEnd_(); } 
}; 

我真的不知道这是值得的，特别是因为你会得到很多的间接即使是非常简单的任务。我想你应该重新考虑你的设计...

Answer 3

任何迭代器都不难写。如果您关心性能，通常是一个糟糕的主意，因为每个操作都需要非零开销来执行类型擦除。

假设您只需要支持for(:)循环和“输入”迭代。

namespace any_iteration_support { 
    template<class VTable, class...Ts> 
    VTable create() { 
    VTable retval; 
    VTable::template populate<Ts...>(retval); 
    return retval; 
    } 
    template<class VTable, class...Ts> 
    VTable const* get_vtable() { 
    static VTable vtable = create<VTable, Ts...>(); 
    return &vtable; 
    } 
    struct input_iterator_vtable { 
    void(*next)(void*) = 0; 
    void(*dtor)(void*) = 0; 
    void(*copy)(void* dest, void const* src) = 0; 
    void*(*clone)(void const* src) = 0; 
    bool(*equals)(void const* lhs, void const* rhs) = 0; 
    template<class It> 
    static void populate(input_iterator_vtable& vtable) { 
     vtable.next = [](void* ptr){ 
     auto& it = *static_cast<It*>(ptr); 
     ++it; 
     }; 
     vtable.dtor= [](void* ptr){ 
     auto* pit = static_cast<It*>(ptr); 
     delete pit; 
     }; 
     vtable.copy= [](void* dest, void const* src){ 
     auto& destit = *static_cast<It*>(dest); 
     auto const& srcit = *static_cast<It const*>(src); 
     destit = srcit; 
     }; 
     vtable.clone= [](void const* src)->void*{ 
     auto const& srcit = *static_cast<It const*>(src); 
     return new It(srcit); 
     }; 
     vtable.equals= [](void const* lhs, void const* rhs)->bool{ 
     auto const& lhsit = *static_cast<It const*>(lhs); 
     auto const& rhsit = *static_cast<It const*>(rhs); 
     return lhsit == rhsit; 
     }; 
    } 
    }; 
    template<class T> 
    struct any_input_iterator_vtable:input_iterator_vtable { 
    T(*get)(void*) = 0; 
    template<class It> 
    static void populate(any_input_iterator_vtable& vtable) { 
     input_iterator_vtable::populate<It>(vtable); 
     vtable.get = [](void* ptr)->T{ 
     auto& it = *static_cast<It*>(ptr); 
     return *it; 
     }; 
    } 
    }; 
} 
template<class T> 
struct any_input_iterator { 
    any_iteration_support::any_input_iterator_vtable<T> const* vtable = 0; 
    void* state = 0; 
    template<class It, 
    std::enable_if_t<!std::is_same<It, any_input_iterator>::value, int> =0 
    > 
    any_input_iterator(It it): 
    vtable(any_iteration_support::get_vtable<any_iteration_support::any_input_iterator_vtable<T>, It>()), 
    state(new It(std::move(it))) 
    {} 
    any_input_iterator(any_input_iterator&& o): 
    vtable(o.vtable), 
    state(o.state) 
    { 
    o.vtable = 0; o.state = 0; 
    } 
    any_input_iterator& operator=(any_input_iterator&& o) { 
    using std::swap; 
    swap(vtable, o.vtable); 
    swap(state, o.state); 
    return *this; 
    } 
    any_input_iterator(any_input_iterator const& o) { 
    if (!o.vtable) return; 
    state = o.vtable->clone(o.state); 
    vtable = o.vtable; 
    } 
    any_input_iterator& operator=(any_input_iterator const& o) { 
    if (!vtable && !o.vtable) return *this; 
    if (vtable == o.vtable) { 
     vtable->copy(state, o.state); 
     return *this; 
    } 
    clear(); 
    if (!o.vtable) { 
     return *this; 
    } 
    state = o.vtable->clone(o.state); 
    vtable = o.vtable; 
    return *this; 
    } 
    explicit operator bool()const { return vtable; } 
    friend bool operator==(any_input_iterator const& lhs, any_input_iterator const& rhs) { 
    if (!lhs && !rhs) return true; 
    if (!lhs) return false; 
    if (lhs.vtable != rhs.vtable) return false; 
    return lhs.vtable->equals(lhs.state, rhs.state); 
    } 
    friend bool operator!=(any_input_iterator const& lhs, any_input_iterator const& rhs) { 
    return !(lhs==rhs); 
    } 
    T operator*() const { 
    return vtable->get(state); 
    } 
    any_input_iterator& operator++() { 
    vtable->next(state); 
    return *this; 
    } 
    any_input_iterator operator++(int) { 
    auto retval = *this; 
    ++*this; 
    return retval; 
    } 
    ~any_input_iterator() { clear(); } 
    void clear() { 
     if (!vtable) return; 
     auto dtor = vtable->dtor; 
     auto s = state; 
     state = 0; 
     vtable = 0; 
     dtor(s); 
    } 
    using reference = T; 
    using value_type = typename std::remove_reference<T>::type; 
    using iterator_category = std::input_iterator_tag; 
}; 

这是你如何键入删除输入迭代的概念在类型T速写。很像std::function，这可以存储几乎任何满足输入迭代要求的东西。

boost提供了类似的类型。

Live example。

您通常最好写一个函数，每次调用一次访问多个节点的函数，或者甚至访问一个节点的函数，以减少类型擦除开销。迭代器很快，因为它们可以内联;随着每一种方法的虚空指针，他们可能会很烦人地慢。

class LibraryClass { 
public: 
    virtual any_input_iterator<const int> intsBegin() const = 0; 
    virtual any_input_iterator<const int> intsEnd() const = 0; 
}; 

当然，手动进行这种类型的擦除是乏味和容易出错的。我会使用类型擦除类型删除与一个薄fascade而不是上述。

的有效方式做到这一点是有一个跨度游客

template<class T> 
struct span { 
    T* b = 0; T* e = 0; 
    T* begin() const { return b; } 
    T* end() const { return e; } 
    bool empty() const { return begin()==end(); } 
    std::size_t size() const { return end()-begin(); } 
    span()=default; 
    span(span const&)=default; 
    span& operator=(span const&)=default; 
    span(T* s, T* f):b(s),e(f) {}; 
    span(T* s, std::size_t length):span(s, s+length) {} 
}; 
template<class T> 
using span_visitor = std::function<void(span<T>)>; 

class LibraryClass { 
public: 
    virtual void visitInts(span_visitor<int const> f) const = 0; 
}; 

class VecImpl : public LibraryClass { 
public: 
    virtual void visitInts(span_visitor<int const> f) const override { 
    f({m_vec.data(), m_vec.size()}); 
    }; 
private: 
    std::vector<int> m_vec; 
}; 
class SimpleListImpl : public LibraryClass { 
public: 
    virtual void visitInts(span_visitor<int const> f) const override { 
    for (int i : m_list) 
     f({&i, 1}); 
    }; 
private: 
    std::list<int> m_list; 
}; 
class FancyListImpl : public LibraryClass { 
public: 
    virtual void visitInts(span_visitor<int const> f) const override { 
    std::size_t count = 0; 
    std::array<int, 10> buffer; 
    for (int i : m_list) { 
     buffer[count] = i; 
     ++count; 
     if (count == buffer.size()) { 
     f({ buffer.data(), buffer.size()}); 
     count = 0; 
     } 
    } 
    if (count) f({ buffer.data(), count}); 
    }; 
private: 
    std::list<int> m_list; 
}; 

你如何使用它？

std::vector<int> get_ints_from(LibraryClass const& library) { 
    std::vector<int> vec; 
    library.visitInits([&](span<int const> ints){ 
    vec.append(ints.begin(), ints.end()); 
    }); 
    return vec; 
} 

此接口将类型擦除移动到每个元素多次为每个多元素一次。

使用这种方法，您可以获得性能接近直接暴露容器的性能，但实际上并未公开它。

我还没有编译span版本。