Represent sum of random access iterators as a random access iterator

user_10947572 0
Viewed 131

Random access iterators are constrained to the difference between two iterators, or to adding or subtracting an integer from an iterator. Rules do not allow addition of two iterators.

I stumbled on a situation where adding two iterators could actually be useful:

#include <iostream>
#include <vector>

using std::vector;
using std::cout;            using std::endl;

template<typename RndIterator> 
RndIterator rndIteratorsSum(RndIterator left, RndIterator right)
{
    //return (left + right) / 2;        // forbidden
    return left + (right - left) / 2;   // workaround
}

A sum of pointers has been reduced to a sum of a pointer + (std::ptrdiff_t / int = int) so it is legal now. The test function could be:

int main()
{
// outputs median of input
    vector<int> test = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int>::iterator iter = rndIteratorsSum(test.begin(), test.end());
    
    cout << "median of input vector: " << *iter << endl;

return 0;
}

Is using the above trick allowed or discouraged? If discouraged, why?

pointer-arithmetic iterator templates c++
2 Answers

As per the LegacyRandomAccessIterator spec you can have for iterators a and b:

  • a + b is undefined.
  • a - b yields difference_type, which is numerical (n)
  • a + n yields an iterator

Therefore:

  • a + (a - b) yields an iterator

If difference_type supports division, which it should, then you can also do a + (a - b) / 2.

user_871890

You are asking to allow (left + right) / 2 as a shorter notation for left + (right - left) / 2 because these expressions are equivalent for numbers in mathematics. However, to do that, you would need to define the addition of 2 iterators and division of iterator by a number. Neither of these operations seems to make sense on their own.

user_4595650
Related