Is There an Example of an Iterator Which Wouldn't use ptrdiff_t as its difference_type?

Question

I see that iterator_traits always defines a difference_type: https://en.cppreference.com/w/cpp/iterator/iterator_traits#Member_types

I'm just wondering why, wouldn't that be ptrdiff_t for every type? Is there an example of an iterator which doesn't use ptrdiff_t? And if not why isn't difference_type eliminated from iterator_traits and ptrdiff_t used everywhere?

Answer 1

A basic output iterator, with std::ostream_iterator being one example, may not need a difference type at all.

Since it's meant to be a "fire and forget" sort of iterator, it usually doesn't make much sense to obtain a difference between two such iterators. The mere act of writing to one copy may invalidate all other copies. So it will not need to define a difference type, and should not be forced to do so artificially (or have the type forced on it).

Answer 2

Theoretically, any iterator whose difference can't be represented in std::ptrdiff_t. Consider, for example, the following toy iterator, which, given a direction, navigates a 2d matrix:

template<typename T>
struct vec2d {T x; T y;};

template<typename T, typename C>
class cartesian_iterator {
public:
    using value_type = T;
    // because the difference between 2d vectors is an actual 2d vector,
    // we can't use std::ptrdiff_t
    using difference_type = vec2d<int>;

    cartesian_iterator(C* container, vec2d<size_t> position, difference_type increment = difference_type{1,1})
        :    container{container}, position{position}, increment{increment}
    {}

    cartesian_iterator& operator++() {position.x += increment.x; position.y += increment.y; return *this;}
    bool operator==(const cartesian_iterator& rhs) {return position.x == rhs.position.x && position.y == rhs.position.y;}
    bool operator!=(const cartesian_iterator& rhs) {return position.x != rhs.position.x || position.y != rhs.position.y;}
    T& operator*() {
        return (*container)[position.x][position.y];
    }

    // difference could be implemented like this
    difference_type operator-(const cartesian_iterator& rhs) {
        return {
            static_cast<int>(position.x) - static_cast<int>(rhs.position.x),
            static_cast<int>(position.y) - static_cast<int>(rhs.position.y),
        };
    }
private:
    C* container;
    vec2d<size_t> position;
    difference_type increment{1,1};
};

usage:

// outputs 159
int main() {
    using std::array;
    array<array<int, 3>, 3> a {
        1,2,3,
        4,5,6,
        7,8,9
    };
    cartesian_iterator<int, array<array<int, 3>, 3>> it{&a, {0, 0}};
    while (it != decltype(it){&a, {3,3}}) {
        std::cout << *it;
        ++it;
    }
}

Answer 3

I wrote a rope type that can deal with backing store greater than potential memory (that is, it can deal with 64-bit sequences even in 32-bit code). And so I had to use 64-bit size and difference types regardless of whether it was being compiled in 32 or 64 bit mode.