Что делает инкремент константного итератора?
const_iterator не позволяет менять элемент коллекции на который он указывает, но перемещается по коллекции он точно так же, как неконстантный итератор. Аналоги -- const T* и просто T*. Отличайте const T * от T * const.
А в чем проблема посмотреть как это реализовано в std, например для вектора? Сразу же станет понятно,  что итератор не изменяет элемент, но сам может бегать по коллекции.