Why does libstdc++ implement both <L,R> and <LR> overloads for binary operators on iterators?

user_616460 0
Viewed 96

In libstdc++3, in the header bits/stl_iterator.h (GCC 10 source here), every binary operator for __normal_iterator has two overloads defined (here is == for example):

  template<typename _IteratorL, typename _IteratorR, typename _Container>
    _GLIBCXX20_CONSTEXPR
    inline bool
    operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
           const __normal_iterator<_IteratorR, _Container>& __rhs)
    _GLIBCXX_NOEXCEPT
    { return __lhs.base() == __rhs.base(); }

  template<typename _Iterator, typename _Container>
    _GLIBCXX20_CONSTEXPR
    inline bool
    operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
           const __normal_iterator<_Iterator, _Container>& __rhs)
    _GLIBCXX_NOEXCEPT
    { return __lhs.base() == __rhs.base(); }

Where .base() returns a pointer to an array element in this case. This is done throughout the library for other iterator types as well. According to comments and changelogs scattered throughout, it's done to support interoperability between iterators and const_iterators.

My question is, why are both the the <_IteratorL, _IteratorR, _Container> and <_Iterator, _Container> overloads defined for all of them? That is, why is <_Iterator, _Container> necessary? Wouldn't the former cover every case? What would break if the latter was removed?

GCC's libstdc++ implementation has a lot of street cred, so I'm sure there's a good, possibly subtle reason, but I can't figure out what it could be.

I ask because I'm currently working out some kinks in my own custom iterator implementations and looking at the STL as a model.

libstdc++ iterator templates stl c++
1 Answers

The comment above that complains about std::rel_ops, which provide a template<class T> bool operator!=(const T& lhs, const T& rhs).

Reducing __normal_iterator to it's bare essentials to show the problem, we get this:

#include <utility>

template<typename T>
struct normal_iterator {
    T m_base;

    const T& base() const { return m_base; }
};

// (1)
template<typename IteratorL, typename IteratorR>
bool operator!=(const normal_iterator<IteratorL>& lhs, const normal_iterator<IteratorR>& rhs) {
    return lhs.base() != rhs.base();
}

// (2)
template<typename Iterator>
bool operator!=(const normal_iterator<Iterator>& lhs, const normal_iterator<Iterator>& rhs) {
    return lhs.base() != rhs.base();
}

int main() {
    using namespace std::rel_ops;
    // Your container's `const_iterator` is `const int*`, and `iterator` is `int*`
    normal_iterator<const int*> a{nullptr};
    normal_iterator<int*> b{nullptr};
    a != b;  // Uses (1) to compare const_iterator and iterator

    a != a;  // Uses (2) to compare two iterators
}

Without the second overload, this would not compile since there are two viable functions to call:

std::rel_ops::operator!=<normal_iterator<int*>>(const normal_iterator<int*>&, const normal_iterator<int*>&)

operator!=<int*, int*>(const normal_iterator<int*>&, const normal_iterator<int*>&)

And neither is more specialiased than the other (it is ambiguous)

For std::rel_ops specifically, there is no reason for the extra == overload, but nothing is stopping a user from writing a similar template<typename T> bool operator==(const T&, const T&) in some other namespace.

user_57546560
Related