如何讓派生類通過虛方法返回任何類型的迭代器？

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版本。