The final word on contiguous iterators Following the paradigms of SCARY iterators, there should only be a single iterator-type for contiguous iterators per value-type.
Here my code for that iterator, working with C++11+:

#include &lt;type_traits&gt;
#include &lt;iterator&gt;

template&lt;class T, class U&gt;
struct is_more_cv_qualified : std::integral_constant&lt;bool, std::is_same&lt;T, const volatile U&gt;{}
    || std::is_same&lt;T, const U&gt;{} || std::is_same&lt;T, volatile U&gt;{}&gt;;

struct contiguous_iterator_tag : std::random_access_iterator_tag {};
struct mutable_contiguous_iterator_tag : contiguous_iterator_tag, std::output_iterator_tag {};

template&lt;class T&gt;
struct contiguous_iterator_base {
    constexpr bool operator==(contiguous_iterator_base other) const noexcept { return _p == other.p; }
    constexpr bool operator!=(contiguous_iterator_base other) const noexcept { return _p != other.p; }
    constexpr bool operator&lt;(contiguous_iterator_base other) const noexcept { return _p &lt; other._p; }
    constexpr bool operator&gt;(contiguous_iterator_base other) const noexcept { return _p &gt; other._p; }
    constexpr bool operator&lt;=(contiguous_iterator_base other) const noexcept { return _p &lt;= other._p; }
    constexpr bool operator&gt;=(contiguous_iterator_base other) const noexcept { return _p &gt;= other._p; }
    constexpr std::ptrdiff_t operator-(contiguous_iterator_base other) const noexcept { return _p - other._p; }
protected:
    constexpr contiguous_iterator_base&amp; operator=(const contiguous_iterator_base&amp;) noexcept = default;
    T* _p = nullptr;
};

template&lt;class T&gt;
struct contiguous_iterator : contiguous_iterator_base&lt;std::remove_cv&lt;T&gt;::type&gt;
, std::iterator&lt;typename std::conditional&lt;std::is_const&lt;T&gt;{}, contiguous_iterator_tag, mutable_contiguous_iterator_tag&gt;::type, T&gt; {
    constexpr contiguous_iterator() noexcept = default;
    template&lt;class U, class = std::enable_if&lt;is_more_cv_qualified&lt;T, U&gt;{}&gt;::type&gt;
    constexpr contiguous_iterator(contiguous_iterator&lt;U&gt; other) noexcept : contiguous_iterator_base&lt;std::remove_cv&lt;T&gt;::type&gt;(other) {}
    constexpr explicit contiguous_iterator(contiguous_iterator_base&lt;std::remove_cv&lt;T&gt;::type&gt; other) noexcept : decltype(other)(other) {}
    constexpr explicit contiguous_iterator(T* p) noexcept { _p = const_cast&lt;decltype(_p)&gt;(p); }
    template&lt;class U&gt;
    constexpr contiguous_iterator&lt;U&gt; rebind() const noexcept { return contiguous_iterator&lt;U&gt;(_p); }
    constexpr T* operator-&gt;() const noexcept { return  _p; }
    constexpr T&amp; operator* () const noexcept { return *_p; }
    constexpr T&amp; operator[](std::ptrdiff_t d) const noexcept { return _p[d]; }
    constexpr contiguous_iterator&amp; operator++() noexcept { ++_p; return *this; }
    constexpr contiguous_iterator operator++(int) noexcept { auto r = *this; ++*this; return r; }
    constexpr contiguous_iterator&amp; operator--() noexcept { --_p; return *this; }
    constexpr contiguous_iterator operator--(int) noexcept { auto r = *this; --*this; return r; }
    constexpr contiguous_iterator&amp; operator+=(std::ptrdiff_t d) noexcept { _p += d; return *this; }
    constexpr contiguous_iterator&amp; operator-=(std::ptrdiff_t d) noexcept { _p -= d; return *this; }
    constexpr contiguous_iterator operator+(std::ptrdiff_t d) const noexcept { return contiguous_iterator(_p) += d; }
    constexpr contiguous_iterator operator-(std::ptrdiff_t d) const noexcept { return contiguous_iterator(_p) -= d; }
protected:
    using contiguous_iterator_base&lt;std::remove_cv&lt;T&gt;::type&gt;::_p;
};

// smoke test

int main() {
    contiguous_iterator_base&lt;int&gt;{};
    contiguous_iterator&lt;int&gt; a;
    contiguous_iterator&lt;const int&gt; b;
    b = a;
    a = b.rebind&lt;int&gt;();
    //a.rebind&lt;char&gt;(); error
}
There really isn't much to say here. This looks really good.

Typos

You have a couple typos in your code on your equality operators. You're comparing against other.p instead of other._p. 

Not restrictive enough

We have this constructor:

constexpr explicit contiguous_iterator(T* p);


But that means if we have contiguous_iterator&lt;Base&gt;, we can construct it with a Derived*. We definitely need to disallow this. 

On a similar vein, rebind&lt;U&gt; should be restricted to those Us which are the same type as T and are at least as cv-qualified. 

Add another alias

Rather than writing this:

constexpr explicit contiguous_iterator(contiguous_iterator_base&lt;std::remove_cv_t&lt;T&gt;&gt; other) noexcept : decltype(other)(other) {}


If you added a using base = contiguous_iterator_base&lt;std::remove_cv_t&lt;T&gt;&gt;;, you could write:

constexpr explicit(base other) noexcept : base(other) {}


which makes way more sense. 

Missing alias

You're using the alias templates for the type traits throughout, except you're using typename std::conditional&lt;X&gt;::type instead of std::conditional_t. 

Line widths

Some of these lines are really long! Add some line breaks.

Why?

I guess lastly... what does contiguous_iterator&lt;T&gt; accomplish that simple T* doesn't?