Returning different iterators with virtual derived methods

Question

Say I have a virtual base class Base, which will in part behave like a container, with two derived classes VectorLike and RangeLike. I want to achieve something like the following:

class VectorLike : public Base {
    std::vector<int> data;
public:
    virtual std::vector<int>::const_iterator cbegin() { return data.cbegin() }
    virtual std::vector<int>::const_iterator cend() { return data.cend() }
}

class RangeLike : public Base {
    int min, max;
    class const_iterator {
        int x;
    public:
        int operator++() { return ++x }
        bool operator==( const_iterator rhs ) { return x == rhs.x }
        const_iterator( int y ) { x = y }
    }
public:
    virtual const_iterator cbegin() { return const_iterator( min ); }
    virtual const_iterator cend() { return const_iterator( max ); }
}

This code will not compile, since std::vector<int>::const_iterator and RangeLike::const_iterator aren't identical or covariant. To achieve the second, I would need an iterator base class from which both std::vector<int>::const_iterator and RangeLike::const_iterator will derive. But then still cbegin() and cend() will have to return pointers to iterators, which will make an even bigger mess.

My question is, is it possible to achieve something like the above code and if so how?

Answer 1

Here is an implementation of a polymorphic const int iterator. You can construct it with any iterator type (including pointers) where std::iterator_traits<Iter>::value_type resolves to int.

This should be the case for both std::vector<int> and your_range_type<int>.

This should get you started.

#include <iostream>
#include <vector>
#include <array>
#include <memory>
#include <algorithm>

struct poly_const_iterator
{
    using value_type = int;

    struct concept {
        virtual void next(int n) = 0;
        virtual const value_type& deref() const = 0;
        virtual bool equal(const void* other) const = 0;
        virtual std::unique_ptr<concept> clone() const = 0;
        virtual const std::type_info& type() const = 0;
        virtual const void* address() const = 0;
        virtual ~concept() = default;
    };

    template<class Iter>
    struct model : concept
    {
        model(Iter iter) : _iter(iter) {}

        void next(int n) override { _iter = std::next(_iter, n); }
        const value_type& deref() const override { return *_iter; }
        bool equal(const void* rp) const override { return _iter == static_cast<const model*>(rp)->_iter; }
        std::unique_ptr<concept> clone() const override { return std::make_unique<model>(*this); }
        const std::type_info& type() const override { return typeid(_iter); }
        const void* address() const override { return this; }


        Iter _iter;
    };

    std::unique_ptr<concept> _impl;

public:
    // interface

    // todo: constrain Iter to be something that iterates value_type
    template<class Iter>
    poly_const_iterator(Iter iter) : _impl(std::make_unique<model<Iter>>(iter)) {};

    poly_const_iterator(const poly_const_iterator& r) : _impl(r._impl->clone()) {};

    const value_type& operator*() const {
        return _impl->deref();
    }

    poly_const_iterator& operator++() {
        _impl->next(1);
        return *this;
    }

    bool operator==(const poly_const_iterator& r) const {
        return _impl->type() == r._impl->type()
        and _impl->equal(r._impl->address());
    }

    bool operator != (const poly_const_iterator& r) const {
        return not(*this == r);
    }
};

void emit(poly_const_iterator from, poly_const_iterator to)
{
    std::copy(from, to, std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;
}

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    std::array<int, 5> a = { 6, 7,8, 9, 0 };

    emit(std::begin(v), std::end(v));
    emit(std::begin(a), std::end(a));


    return 0;
}

expected results:

1, 2, 3, 4, 5,
6, 7, 8, 9, 0,

Answer 2

Here's a C++20 based solution (partial implementation)... just thought I'd put it out there.

It uses a variant with stack storage rather than polymorphism and dynamic allocation, so it might have better performance.

It should work for any given set of iterator types that have a common value_type and whose reference type is value_type&. It should also be fairly easy to adapt for other types of iterator and to include operator->.

Not claiming this is better than the implementation in the original answer. Merely an interesting alternative...

PS. normal in the names below simply indicates a basic pointer based iterator.

  template <typename _Iterator, typename _Value, typename _Reference, typename _Difference>
  concept forward_iterator_for
    = std::forward_iterator<_Iterator>
      && std::same_as<std::iter_value_t<_Iterator>, _Value>
      && std::same_as<std::iter_reference_t<_Iterator>, _Reference>
      && std::same_as<std::iter_difference_t<_Iterator>, _Difference>;

  template <typename _Iterator, typename _Value>
  concept normal_forward_iterator_for //
    = std::same_as<std::remove_cvref_t<_Value>, std::remove_const_t<_Value>>
      && forward_iterator_for<_Iterator, std::remove_const_t<_Value>, _Value&, std::ptrdiff_t>;

  template <typename _Value, normal_forward_iterator_for<_Value> ... _Iterator>
  class normal_forward_iterator_variant {
   public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    using value_type        = std::remove_cv_t<_Value>;
    using reference         = _Value&;
    using iterator_type     = std::variant<_Iterator...>;

   private:
    iterator_type _m_iter;

   public:
    normal_forward_iterator_variant() = default;

    template <normal_forward_iterator_for<_Value> _Iter, typename... _Args>
    normal_forward_iterator_variant(std::in_place_type_t<_Iter>, _Args&&... args)
    noexcept (std::is_nothrow_constructible_v<_Iter, _Args&&...>)
    : _m_iter(std::in_place_type<_Iter>, std::forward<_Args>(args)...) {}

    normal_forward_iterator_variant(iterator_type const& iter)
    noexcept (std::is_nothrow_copy_constructible_v<iterator_type>)
    : _m_iter(iter) {}

    normal_forward_iterator_variant(normal_forward_iterator_variant const&) = default;

    normal_forward_iterator_variant(normal_forward_iterator_variant&&) = default;

    constexpr normal_forward_iterator_variant&
    operator=(normal_forward_iterator_variant const& iter)
    noexcept (std::is_nothrow_copy_assignable_v<iterator_type>) //
    requires std::is_copy_assignable_v<iterator_type> {
      _m_iter = iter._m_iter;
      return *this;
    }

    constexpr normal_forward_iterator_variant&
    operator=(normal_forward_iterator_variant&& iter)
    noexcept (std::is_nothrow_move_assignable_v<iterator_type>) //
    requires std::is_move_assignable_v<iterator_type> {
      _m_iter = std::move(iter._m_iter);
      return *this;
    }

    template <typename _Tp>
    constexpr normal_forward_iterator_variant&
    operator=(_Tp const& x)
    noexcept (std::is_nothrow_assignable_v<iterator_type, _Tp&>) //
    requires std::is_assignable_v<iterator_type, _Tp&> {
      _m_iter = x;
      return *this;
    }

    template <typename _Tp>
    constexpr normal_forward_iterator_variant&
    operator=(_Tp&& x)
    noexcept (std::is_nothrow_assignable_v<iterator_type, _Tp&&>) //
    requires std::is_assignable_v<iterator_type, _Tp&&> {
      _m_iter = std::move(x);
      return *this;
    }

    [[nodiscard]] constexpr reference
    operator*() const noexcept {
      return std::visit([](auto&& iter) -> reference {
        return *iter;
      }, _m_iter);
    }

    constexpr normal_forward_iterator_variant&
    operator++() noexcept {
      std::visit([](auto&& iter) {
        ++iter;
      }, _m_iter);
      return *this;
    }

    constexpr normal_forward_iterator_variant
    operator++(int) noexcept {
      normal_forward_iterator_variant rv(*this);
      ++*this;
      return rv;
    }

    [[nodiscard]] friend constexpr bool
    operator==(normal_forward_iterator_variant const& a, normal_forward_iterator_variant const& b) noexcept {
      return (a._m_iter == b._m_iter);
    }
  };

Example use:

#include <iostream>
#include <iomanip>
#include <vector>
#include <list>

#include <iterator.h>

int
main() {
  using vector   = std::vector<int>;
  using list     = std::list<int>;
  using iterator = normal_forward_iterator_variant<const int, vector::const_iterator, list::const_iterator>;

  iterator iter;

  vector v{ 0, 1, 2 };
  iter = v.cbegin();
  std::cout << *iter++ << std::endl;
  std::cout << *iter << std::endl;
  std::cout << *++iter << std::endl;

  list l{ 3, 4, 5 };
  iter = l.cbegin();
  std::cout << *iter++ << std::endl;
  std::cout << *iter << std::endl;
  std::cout << *++iter << std::endl;
}

Output is 1, 2, ..., 6 as expected.