Compiler can't "convert" between Vector_const_iterator and Vector_iterator, even though methods for both are available

Question

I'm trying to create a small wrapper class around a std::vector to represent the coefficients of a polynomial. The caller needs to be able to iterate through the coefficients, but I don't want to expose the underlying implementation.

Using the pattern described here, here, and elsewhere, I've tried to pass along the iterators as below:

typedef std::vector<unsigned char> charVec;

class gf255_poly
{
    public:

        // Constructors and Polynomial-y Functions

        // ...

        // Iterators to go from high to low degree

        charVec::const_reverse_iterator h2l_begin() const { return p.rbegin(); };
        charVec::const_reverse_iterator h2l_end()   const { return p.rend(); };
        charVec::reverse_iterator       h2l_begin() { return p.rbegin(); };
        charVec::reverse_iterator       h2l_end()   { return p.rend(); };

        // Iterators to go from low to high degree

        charVec::const_iterator l2h_begin() const { return p.begin(); };
        charVec::const_iterator l2h_end()   const { return p.end(); };
        charVec::iterator       l2h_begin() { return p.begin(); };
        charVec::iterator       l2h_end()   { return p.end(); };

    protected:
        std::vector<unsigned char> p;
};

These gf255_poly objects then get used in methods such as this one:

// Performs polynomial evaluation in GF(2^8)
unsigned char gf255_poly_eval(const gf255_poly &poly, unsigned char x) const
{
    unsigned char fx = poly.coefHigh(); // Initialize with coef of highest degree term

    // Use Horner's method with consecutively factored terms:
    // x^3 + 2x^2 + 3x + 4 -> (((1x + 2)x + 3)x + 4)

    charVec::reverse_iterator next_coef;

    for (next_coef = poly.h2l_begin(); next_coef != poly.h2l_end(); next_coef++)
        fx = gf255_mul(fx, x) ^ *next_coef; // Recall ^ is addition in GF 2^8

    return fx;
}

Simple though that seems, there's something going wrong with the types. Visual Studio gives me this error on the line with the for loop, which I can't seem to puzzle out:

error C2664: 'std::_Revranit<_RanIt,_Base>::_Revranit(_RanIt)' : cannot convert parameter 1 from 'std::_Vector_const_iterator<_Ty,_Alloc>' to 'std::_Vector_iterator<_Ty,_Alloc>'

I don't understand this message - I've provided methods that return both iterators and const_iterators. Why can't the compiler choose between them?

---

Implicit in this question is whether this is a good strategy for hiding the details from the caller at all (since they still have to deal with these std::vector types), and I would appreciate answers that also address this.

Answer 1

charVec::reverse_iterator next_coef = poly.h2l_begin();

next_coef is a reverse_iterator. What does h2l_begin() return?

Well, poly is a:

const gf255_poly &poly

a const gf255_poly. So let us look at the overrides of h2l_begin():

charVec::const_reverse_iterator h2l_begin() const { return p.rbegin(); };
charVec::reverse_iterator       h2l_begin() { return p.rbegin(); };

There are two overloads. Only one is valid, because poly is const, and that is this one:

charVec::const_reverse_iterator h2l_begin() const { return p.rbegin(); };

so poly.h2l_begin() returns a charVec::const_reverse_iterator.

charVec::const_reverse_iterator cannot be converted to charVec::reverse_iterator, because charVec::const_reverse_iterator allows you to modify the thing being iterated over, while charVec::reverse_iterator does not.

In short, because poly is const, you have promised not to modify it. And then you iterated it over it using types that could modify it. So you get a type error.

Second, and as an aside, note that the compiler never chooses between functions based on return type (except arguably the conversion operator T()). If you had a non-const poly stored it in a const_reverse_iterator, you'd still call the reverse_iterator h2l_begin(). The reverse_iterator would just convert to a const_reverse_iterator.

---

First thing to do is to upgrade to C++11. This is 2016.

Second, I'd write a range_t<Iterator> which stores a range of iterators and exposes begin and end and conditionally (based on random-access-ness of Iterator operator[], size, etc. Also remove_front(size_t) and front() and empty and ...

Then I'd write array_view<T>:range_it<T*> which represents a range of contiguous Ts, with implicit ctors from containers with a T* C::data() method, raw C-arrays, and T*, size_t.

Finally, I'd write backwards_t and backwards function, which takes a range_t<Iterator> and returns a range_t< reverse_iterator< Iterator > >.

Now my gf255_poly has these:

backwards_t< array_view< unsigned char > > h2l();
backwards_t< array_view< unsigned char const > > h2l() const;
array_view< unsigned char > l2h();
array_view< unsigned char const > l2h() const;

We can expose typedefs for the iterators if we choose (and in C++03 we have little choice).

In C++11 it looks like:

for (auto&& next_coef = poly.h2l())
  fx = gf255_mul(fx, x) ^ next_coef; // Recall ^ is addition in GF 2^8

which is nice.

Answer 2

poly is a const object, so h2l_begin() will return a const_reverse_iterator. You've declared next_coef as a reverse_iterator, and you can't assign a const iterator to an iterator. Either change next_coef to be a const_reverse_iterator, or declare it in the for loop with auto.

for (auto next_coef = poly.h2l_begin(); next_coef != poly.h2l_end(); ++next_coef)

Answer 3

Change this:

charVec::reverse_iterator next_coef;

to this:

charVec::const_reverse_iterator next_coef;

You see: poly is a const reference to a gf255_poly object, meaning the request for poly.h2l_begin(); will prefer the const qualified version of that function during overload resolution.

Better still, use auto

for (auto next_coef = poly.h2l_begin(); next_coef != poly.h2l_end(); next_coef++)
    fx = gf255_mul(fx, x) ^ *next_coef; // Recall ^ is addition in GF 2^8

If you must still keep the iterator outside the for loop initializer, you can move the intitialization outside:

auto next_coef = poly.h2l_begin()
for (; next_coef != poly.h2l_end(); next_coef++)
    fx = gf255_mul(fx, x) ^ *next_coef; // Recall ^ is addition in GF 2^8