Does `const_iterator` really need to be a different class than `iterator`?

Question

Let say I define some kind of container A:

struct A
{
    iterator begin(){ return iterator(this,0); }
    const iterator cbegin() const { return iterator(this, last());}
    //...
};

Suppose now I want to declare the iterator (part of A):

struct A::iterator
{
    iterator ( A* ptr, size_t idx){};
    //...
};

Which I would use like:

const A a;
A::iterator it = a.cbegin();

That does not work because the pointer passed to the constructor of iterator is non-const.

The ideal solution would be something like a specific constructor that return a const object:

const A::iterator( const StringUtfInterface *p, size_t s); //Not valid

This is (obviously) not valid in C++. I wonder what is the approach to this problem?

Do I really need to declare/define a new const_iterator class? const keyword is not enough?