CODEWITHSUNDEEP
c++iteratoroperator-overloadinglanguage-lawyerstd
JeJo
JeJo

Reputation: 32762

Is there any drawbacks in providing operator+ or operator- to bidirectional iterators?

The bidirectional iterators have no luxuries like random access iterators, and hence need to depend upon the std::next and std::prev, when someone needs to do operations like

std::set<int> s{ 1, 2, 3, 4, 5 };

//std::set<int> s2(s.cbegin(), s.cbegin() + 2); // won't work as there is no operator+ for std::set::const_iterator
std::set<int> s2(s.cbegin(), std::next(s.cbegin(), 2));

//std::set<int> s3(s.cbegin(), s.cend() - 2);  // won't work as there is no operator- for std::set::const_iterator
std::set<int> s3(s.cbegin(), std::prev(s.cend(), 2));

However, we can implement those operator+ and operator- using the above std::next and std::prev.

#include <set>
#include <iterator>  // std::iterator_traits, std::next, std::prev

template<typename InputIt>
constexpr InputIt operator+(InputIt it,
    typename std::iterator_traits<InputIt>::difference_type n)
{
    return std::next(it, n);
}

template<typename InputIt>
constexpr InputIt operator-(InputIt it,
    typename std::iterator_traits<InputIt>::difference_type n)
{
    return std::prev(it, n);
}

int main()
{
    std::set<int> s{ 1, 2, 3, 4, 5 };
    std::set<int> s2(s.cbegin(), s.cbegin() + 2); // works now
    std::set<int> s3(s.cbegin(), s.cend() - 2);   // works now
}

Update:

Using InputIt would be a mistake as @Nicol Bolas mentioned in his answer. I thought to demonstrate the idea though. Anyways, let us consider a SFINE ed solution instead, which accepts only the bidirectional iterator. Would be there any other problems, other than what Nicol mentioned?

#include <type_traits>
#include <iterator>  // std::iterator_traits, std::bidirectional_iterator_tag, std::next, std::prev

template<typename BidirIterators>
constexpr auto operator+(BidirIterators it,
   typename std::iterator_traits<BidirIterators>::difference_type n)
   -> std::enable_if_t<
         std::is_same_v<
            std::bidirectional_iterator_tag,
            typename std::iterator_traits<BidirIterators>::iterator_category
         >, BidirIterators
   >
{
   return std::next(it, n);
}

template<typename BidirIterators>
constexpr auto operator-(BidirIterators it,
   typename std::iterator_traits<BidirIterators>::difference_type n)
   -> std::enable_if_t<
         std::is_same_v<
            std::bidirectional_iterator_tag,
            typename std::iterator_traits<BidirIterators>::iterator_category
          >, BidirIterators
   >
{
   return std::prev(it, n);
}

Upvotes: 4

Views: 197

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 473397

If not, isn't nice to have in the C++ standard library?

No.

If an iterator provides numbered increment and decrement operations, then it is advertising that such operations are fast, preferably amortized O(1) operations. That's why you want people to spell out std::next/prev: so that it is completely obvious to someone writing/reading the code that the operation in question may be slow. That is, even if a user passes an iterator that can do it fast, your algorithm recognizes that the user may pass an iterator that may be slow at this.

To provide such operators on bidirectional or lesser iterators is to tell a lie. This is also why you should not impose such operators on arbitrary iterators.

But there are other reasons why your code is wrong.

A pure input iterator (which is presumably what you're expecting, since you called the template parameter InputIt) is not required to have a decrement, so std::prev isn't valid. It would have to be a bidirectional iterator.

But there's more. Forward iterators can be copied around, with the various copies being considered independent positions within a range. This is not the case with a pure input iterator; if you copy them, incrementing one copy is assumed to invalidate all other copies of that iterator. So the user must know this when they try to use it and take care to not assume that separate iterators point to different positions.

But that's not typically how pointers work, is it? So once again, your iterator seems to be lying to the user: it claims to provide functionality which it doesn't.

Upvotes: 6

Related Questions