Having virtual methods as templates that receive iterators

Question

I know one cannot use templates for virtual methods in C++ (or vice versa), as for example discussed here and here. Unfortunately I am not sure how to deal with that limitation in my case.

We have a class template that includes a method template:

template <class T>
class BeliefSet : public Belief<T>
{
private:
    std::vector<T> m_Facts;

public:
    template <class Iter>
    void SetFacts(Iter IterBegin, Iter IterEnd, bool Append = false)
    {
        if(!Append)
        {
            m_Facts.clear();
        }
        m_Facts.insert(m_Facts.end(), IterBegin, IterEnd);
    }
};

The method SetFacts() should be able to receive two input iterators for an STL container, that's why we are using a method template here.

Now I would like to make this method SetFacts() virtual, which is not possible in C++ the way this code is written at the moment. So what else is the typical approach to deal with this situation?

Answer 1

Something based on the CRTP idiom and a bit of sfinae could probably solve it:

template <class D, class T>
class BeliefSet : public Belief<T>
{
private:
    std::vector<T> m_Facts;

    template <class Iter>
    void SetFactsInternal(char, Iter IterBegin, Iter IterEnd, bool Append = false)
    {
        if(!Append)
        {
            m_Facts.clear();
        }
        m_Facts.insert(m_Facts.end(), IterBegin, IterEnd);
    }

    template <class Iter, typename U = D>
    auto SetFactsInternal(int, Iter IterBegin, Iter IterEnd, bool Append = false)
    -> decltype(static_cast<U*>(this)->OverloadedSetFacts(IterBegin, IterEnd, Append), void())
    {
        static_cast<U*>(this)->OverloadedSetFacts(IterBegin, IterEnd, Append);
    }

public:
    template <typename... Args>
    void SetFacts(Args&&... args)
    {
        SetFactsInternal(0, std::forward<Args>(args)...);
    }
};

Your derived class can implement OverloadedSetFacts member function to overload SetFacts.
Moreover, your derived class must inherit from BeliefSet as it follows:

struct Derived: BeliefSet<Derived, MyTType>
{
    //...
};

That is the key concept behind the CRTP idiom after all.

---

It follows a minimal, working example (in C++14 for simplicity):

#include<iostream>

template <class D>
class Base {
private:
    template <class C>
    auto internal(char, C) {
        std::cout << "internal" << std::endl;
    }

    template <class C, typename U = D>
    auto internal(int, C c)
    -> decltype(static_cast<U*>(this)->overloaded(c), void()) {
        static_cast<U*>(this)->overloaded(c);
    }

public:
    template <typename... Args>
    auto base(Args&&... args) {
        internal(0, std::forward<Args>(args)...);
    }
};

struct Overloaded: Base<Overloaded> {
    template<typename T>
    auto overloaded(T) {
        std::cout << "overloaded" << std::endl;
    }
};

struct Derived: Base<Derived> {};

int main() {
    Overloaded over;
    over.base(0);
    Derived der;
    der.base(0);
}

As you can see, you can provide a default implementation in your base class and override it in the derived class if needed.

See it on wandbox.

Answer 2

If you want to keep a virtual interface, type erasure works if you can find a narrow point of customization.

For example, erasing down to for-each T.

template<class T>
using sink=std::function<void(T)>;
template<class T>
using for_each_of=sink< sink<T> const& >; 

Now in Belief<T> we set up two things:

template<class T>
struct Belief{
    template <class Iter>
    void SetFacts(Iter IterBegin, Iter IterEnd, bool Append = false){
      SetFactsEx(
        [&]( sink<T const&> const& f ){
          for(auto it=IterBegin; it != IterEnd; ++it) {
            f(*it);
        },
        Append
      );
    }
    virtual void SetFactsEx(for_each_of<T const&> elems, bool Append = false)=0;
};

Now we do this in the derived class:

virtual void SetFactsEx(for_each_of<T const&> elems, bool Append = false) override
{
    if(!Append)
        m_Facts.clear();
    elems( [&](T const& e){
      m_Facts.push_back(e);
    } );
}

And we done.

There is loss of efficiency here, but you can keep enriching the type erasure interface to reduce it. All the way down to erasing "insert into end of vector" for near zero efficiency loss.

I gave it a different name because it avoids some overload annoyances.

Answer 3

Another solution would be type erasing the input iterators of the standard library with a user defined TypeErasedIterator. That way, you could wrap any input iterator into a TypeErasedIterator object and your classes' interfaces should deal only with that type.

#include <memory>
#include <iterator>
#include <functional>

// ----- (minimal) input iterator interface ----- //
template<typename T>
struct BaseIterator {
    virtual T& operator*() = 0;
    virtual BaseIterator& operator++() = 0;
    virtual bool operator!=(const BaseIterator& it) const = 0;
};

// ----- templatized derived iterator ----- //
template<typename T, typename It>
class InputIterator : public BaseIterator<T> {
    It it_;
public:    
    InputIterator(It it) : it_{it} {}
    typename It::value_type& operator*() override { return *it_; }
    InputIterator& operator++() override { ++it_; return *this; }
    bool operator!=(const BaseIterator<T>& it) const override 
    { 
        auto ptr = dynamic_cast<const InputIterator<T, It>*>(&it);
        if(!ptr) return true;
        return it_ != ptr->it_;
    }
};

// ----- type erased input iterator ----- //
template<typename T>
class TypeErasedIterator {
    std::unique_ptr<BaseIterator<T>> it_;
    std::function<std::unique_ptr<BaseIterator<T>>()> copy_; // for implementing the copy ctor
public:
    template<typename It>
    TypeErasedIterator(It it) : 
        it_{std::make_unique<InputIterator<T, It>>(it)},
        copy_{[this]{ return std::make_unique<InputIterator<T, It>>(static_cast<const InputIterator<T, It>&>(*this->it_)); }}
    {}
    TypeErasedIterator(const TypeErasedIterator& it) : it_{it.copy_()}, copy_{it.copy_} {}
    T& operator*() { return **it_; }
    TypeErasedIterator& operator++() { ++*it_; return *this; }
    bool operator!=(const TypeErasedIterator& it) const { return *it_ != *it.it_; }
};

// std::iterator_traits partial specialization for TypeErasedIterator's
namespace std {

template<typename T>
struct iterator_traits<TypeErasedIterator<T>> {
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::input_iterator_tag;
};

}

At this point, your Belief hierarchy can be defined as follows:

template<class T>
struct Belief {
    virtual void SetFacts(TypeErasedIterator<T> beg, TypeErasedIterator<T> end, bool Append = false) = 0;
};

template <class T>
class BeliefSet : public Belief<T>
{
private:
    std::vector<T> m_Facts;

public:
    void SetFacts(TypeErasedIterator<T> beg, TypeErasedIterator<T> end, bool Append = false) override
    {
        if(!Append)
        {
            m_Facts.clear();
        }
        m_Facts.insert(m_Facts.end(), beg, end);
        std::cout << "m_Facts.size() = " << m_Facts.size() << '\n';
    }
};

int main()
{
    std::vector<int> v{0, 1, 2};
    std::list<int> l{3, 4};
    BeliefSet<int> bs;
    bs.SetFacts(v.begin(), v.end());
    bs.SetFacts(l.begin(), l.end(), true);
}

As you can see, SetFacts() is accepting iterators both from std::vector and std::list; moreover, inside the implementation of your derived classes you are not forced to handle one element of the sequence at a time, but you can manage the whole sequence (e.g. you could reorder the sequence, or pass the iterators to any standard algorithm supporting them).

_{Note that my implementation of the InputIterator concept is incomplete and minimal to get your example work.}