const, span, and iterator trouble

Question

I try to write an iterator that iterates over a container by index. A It and a const It both allow changing the content of the container. A Const_it and a const Const_it both forbid changing the content of the container.

After that, I try to write a span<T> over a container. For a type T that is not const, both const span<T> and span<T> allows changing the content of the container. Both const span<const T> and span<const T> forbid changing the content of the container.

The code does not compile because:

    // *this is const within a const method
    // But It<self_type> requires a non-const *this here.
    // So the code does not compile
    It<self_type> begin() const { return It<self_type>(*this, 0); }

If I make the constructor of It to accept a const container, it doesn't look right because the iterator can modify the content of the container.

If I get rid of the const of the method, then for a non-const type T, a const span<T> cannot modify the container.

It inherits from Const_it to allow implicit conversion from It to Const_it during template instantiation.

I use a pointer instead of a reference to in the iterators (const C* container_;) for allowing assigning one iterator to another iterator.

I suspect something is very wrong here because I even think about:

Does cast away const of *this cause undefined behavior?

But I don't know how to fix it.

Test:

#include <vector>
#include <numeric>
#include <iostream>

template<typename C>
class Const_it {
    typedef Const_it<C> self_type;
public:
    Const_it(const C& container, const int ix)
            : container_(&container), ix_(ix) {}
    self_type& operator++() {
        ++ix_;
        return *this;
    }

    const int& operator*() const {
        return ref_a()[ix_];
    }

    bool operator!=(const self_type& rhs) const {
        return ix_ != rhs.ix_;
    }

protected:
    const C& ref_a() const { return *container_; }
    const C* container_;
    int ix_;
};

template<typename C>
class It : public Const_it<C> {
    typedef Const_it<C> Base;
    typedef It<C> self_type;
public:
    //It(const C& container.
    It(C& container, const int ix)
            : Base::Const_it(container, ix) {}
    self_type& operator++() {
        ++ix_;
        return *this;
    }

    int& operator*() const {
        return mutable_a()[ix_];
    }

private:
    C& mutable_a() const { return const_cast<C&>(ref_a()); }
    using Base::ref_a;
    using Base::container_;
    using Base::ix_;
};


template <typename V>
class span {
    typedef span<V> self_type;
public:
    explicit span(V& v) : v_(v) {}
    It<self_type> begin() { return It<self_type>(*this, 0); }
    // *this is const within a const method
    // But It<self_type> requires a non-const *this here.
    // So the code does not compile
    It<self_type> begin() const { return It<self_type>(*this, 0); }
    It<self_type> end() { return It<self_type>(*this, v_.size()); }
    It<self_type> end() const { return It<self_type>(*this, v_.size()); }

    int& operator[](const int ix) {return v_[ix];}
    const int& operator[](const int ix) const {return v_[ix];}
private:
    V& v_;
};


int main() {
    typedef std::vector<int> V;
    V v(10);
    std::iota(v.begin(), v.end(), 0);
    std::cout << v.size() << "\n";
    const span<V> s(v);
    for (auto&& x : s) {
        x = 4;
        std::cout << x << "\n";
    }
}

Answer 1

There are two main notes to be said to make this work. First:

If I make the constructor of It to accept a const container, it doesn't look right because the iterator can modify the content of the container.

Not really, because C in your template<typename C> class It is not the actual container, but the span<V>. In other words, take a look at:

It<self_type> begin() const { return It<self_type>(*this, 0); }

Here self_type means const span<V>, therefore you are returning a It<const span<V>>. Thus, your iterator can do whatever can be done with a const span -- but the container is still non-const. The variable name container_ is not fortunate, then.

For a type T that is not const, both const span<T> and span<T> allows changing the content of the container. Both const span<const T> and span<const T> forbid changing the content of the container.

In addition, since you want that const span is allowed to modify the contents, then what you should write inside span itself is (note the const):

int& operator[](const int ix) const {return v_[ix];}
// Removing the other `const` version:
// const int& operator[](const int ix) const {return v_[ix];}

With those two bits clarified, you can then construct a working example. Here is one based from your code and simplified to solve the issue at hand:

#include <vector>
#include <iostream>

template<typename S>
class It {
    typedef It<S> self_type;
    const S& span_;
    int ix_;

public:
    It(const S& span, const int ix)
        : span_(span), ix_(ix) {}

    self_type& operator++() {
        ++ix_;
        return *this;
    }

    int& operator*() const {
        return span_[ix_];
    }

    bool operator!=(const self_type& rhs) const {
        return &span_ != &rhs.span_ or ix_ != rhs.ix_;
    }
};

template <typename V>
class span {
    typedef span<V> self_type;
public:
    explicit span(V& v) : v_(v) {}
    It<self_type> begin() const { return It<self_type>(*this, 0); }
    It<self_type> end() const { return It<self_type>(*this, v_.size()); }

    int& operator[](const int ix) const {return v_[ix];}
private:
    V& v_;
};

int main() {
    typedef std::vector<int> V;
    V v(10);
    const span<V> s(v);
    for (auto&& x : s) {
        x = 4;
        std::cout << x << "\n";
    }
}

Take a look as well at the corrected implementation of operator!= and at the fact that there is no need for the non-const version of begin() and end(). You can also throw there a cbegin() and cend(). Then you have to work on adding back the const iterator cases.

---

By the way, in case it saves some confusion for anybody: in the near future, std::span (proposed for C++20) might be added; and it will be just a (pointer-to-first-element, index) pair -- rather than your (pointer-to-container, index) version.

In other words, as its template parameter, it will take the elements' type, rather than a container:

span<std::vector<int>> s(v);
// vs
std::span<int> s(v);

This allows consumers of std::span to avoid knowing about which container is behind the scenes (or even no container: a contiguous memory area or an array).

Finally, you may want to take a look at GSL's implementation of std::span to get some inspiration on how to fully implement it (including the second template parameter about the extent).