Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Pure virtual method taking all sorts of iterators?

Tags:

c++

Let a polymorphic Base class have a pure virtual method insert on a stl container member (vector in this case). The function should be able to take iterator of containers like set, vector, list etc, but also take into account the type of reference (move semantics)

The pure virtual nature of the function make using template functions impossible. Afaik iterators of stl containers are separate type, thats why templates are useful. However the polymorphism is necessary. Also I noticed that there is std::move_iterator which is able to encapsulate all types of iterators.

Are there other "iterator wrappers" which I can use to define a pure virtual method in Base which takes all sorts of iterators and also acts like perfectly forwarding function template such that clients can pass iterators and move iterators?

Before introducing polymorphism the function was like this:

vector<Class> v;
template<typename Iter>
void insert(Iter begin, Iter end) {
    v1.insert(begin, end, std::end(v));
}

but now there derived classes which behave slightly different on insert (mutexes, notify observers etc). It would be nice to have something like the following:

vector<Class> v;

virtual void Base::insert(GenericIter begin, GenericIter end) = 0;

[…]

void DerivedMT::insert(GenericIter begin, GenericIter end) override
{
    mutex.lock();
    v1.insert(begin, end, std::end(v));
    mutex.unlock();
}

[…]

void DerivedObserved::insert(GenericIter begin, GenericIter end) override
{
    v1.insert(begin, end, std::end(v));
    notifyObservers();
}
like image 690
ManuelSchneid3r Avatar asked Dec 31 '22 12:12

ManuelSchneid3r


2 Answers

You can't accept all the various iterators and maintain runtime polymorphism because you would then violate Liskov Substitution Principle. That is, a polymorphic bidirectional iterator will not work with wrapped forward iterator, since the latter can only be incremented. Also there are sorted associative containers, whose iterators you can not use for sorting, etc:

  • in case an implementor would want not to skip, but to sort the elements
  • in case an implementor would want to do a particular kind of search

So, the intent of a template iterator for a function is to provide a freedom for an interface implementor to do whatever he desires given he has two iterators. But with runtime polymorphic iterators you are limiting the implementor (you kind of should).

So there are two ways:

  1. Naive. Just declare your interface with insert(std::vector<YourType>). This will handle for your all the generic iterators you want, and an implementor is free to do whatever he desires with the range.
  2. Implement const PolymorphicForwardIterator using traits for a Forward Iterator and type erasure.

Here is an example of how you can erase a type without heap allocations:

class PolymorphicReference final
{
public:
    template <typename RefT>
    explicit PolymorphicReference(RefT &ref)
        : pVTable_(std::addressof(GetVTable(ref))),
          ref_(std::addressof(ref))
    {}

    void Say(const std::string& msg)
    {
        pVTable_->pSay(ref_, msg);
    }

    int Number() const
    {
        return pVTable_->pNumber(ref_);
    }

private:
    struct VTable
    {
        virtual void pSay(void *pRef, const std::string& msg) = 0;
        virtual int pNumber(const void *pRef) = 0;

    protected:
        ~VTable() = default;
    };

    template <typename RefT>
    static VTable &GetVTable(const RefT&)
    {
        struct : VTable
        {
            void pSay(void *pRef, const std::string& msg) override
            {
                static_cast<RefT*>(pRef)->Say(msg);
            }
            int pNumber(const void *pRef) override
            {
                return static_cast<const RefT*>(pRef)->Number();
            }
        } static vTable;

        return vTable;
    }

private:
    VTable *pVTable_;
    void *ref_;
};
like image 102
Sergey Kolesnik Avatar answered Jan 02 '23 01:01

Sergey Kolesnik


Are there other "iterator wrappers" which I can use to define a pure virtual method in Base which takes all sorts of iterators and also acts like perfectly forwarding function template such that clients can pass iterators and move iterators?

No. Either you can have a virtual function, or you can have perfect forwarding, you can't have both.

What you can have is a type-erasing range, such as boost::any_range.

class Base {
public:
    virtual void insert(boost::any_range<Class, std::input_iterator_tag> range) = 0;
};
like image 26
Caleth Avatar answered Jan 02 '23 00:01

Caleth