Is clamping on iterators valid

Question

I found the following in actual production code. My suspicion is that it actually has undefined behavior into it, however, I couldn't find the related info on cppreference. Can you confirm this is UB or valid code and why this is UB/valid (preferably with a quote of the standard)?

#include <vector>

int main(int, char **)
{
    auto v = std::vector<int>({1,2,3,4,5});
    auto begin = v.begin();
    auto outOfRange = begin + 10;
    auto end = v.end();
    auto clamped = std::min(outOfRange, end);
    return (clamped == end) ? 0 : 42;
}

Code on Compiler Explorer

As you can see begin + 10 will create an iterator that's out of range of the std::vector. However, that iterator ain't being used, as it is clamped using std::min.

I think as soon as you form an iterator beyond the end, you have UB, whether or not it gets dereferenced. That would be the same as pointers, which is usual for iterators. — underscore_d, Jul 03 '20 at 08:02
Does this answer your question? [c++ what's the result of iterator + integer when past-end-iterator?](https://stackoverflow.com/questions/5947437/c-whats-the-result-of-iterator-integer-when-past-end-iterator) — underscore_d, Jul 03 '20 at 08:02
@underscore_d All those answers state it's UB without explaining why — JVApen, Jul 03 '20 at 08:08
So then someone should post a better answer at the question we already have, I'd expect! — underscore_d, Jul 03 '20 at 08:09
So to use std::min the iterator needs to implement LessThanComparable. Which a LegacyRandomAccessIterator has acording to cpp refence or atleast implies implies. Which means it has at least weak ordering. so Becuase of the the defintion of weak ordering this should not be UB unless between outOfRange and end the vectors size changes. — Mellester, Jul 03 '20 at 08:19
I've now voted to close the other one as a duplicate of this, since Evg's answer finally cites the Standard. That should be the accepted answer. — underscore_d, Jul 03 '20 at 08:31

Evg · Answer 1 · 2020-07-03T09:04:28.983

The operational semantics of operator+(n), for a random access iterator is this [random.access.iterators], Table 99 *:

difference_type m = n;
if (m >= 0)
    while (m--)
        ++r;
else
    while (m++)
        --r;
return r;

And for ++r the precondition is [input.iterators], Table 95 *:

Preconditions: r is dereferenceable.

With begin() + n this precondition will not be satisfied starting from some value of m if n is greater than the size of the container. After begin + 10; you already have UB, and the rest of the code is irrelevant.

GCC standard library sanitizer (compile with -D_GLIBCXX_DEBUG) will give you the following error:

/usr/include/c++/10/debug/safe_iterator.h:885:
In function:
    __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*, 
    std::__cxx1998::vector<int, std::allocator<int> > >, 
    std::__debug::vector<int>, std::random_access_iterator_tag>::_Self 
    __gnu_debug::operator+(const _Self&, 
    __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*, 
    std::__cxx1998::vector<int, std::allocator<int> > >, 
    std::__debug::vector<int>, 
    std::random_access_iterator_tag>::difference_type)

Error: attempt to advance a dereferenceable (start-of-sequence) iterator 10 
steps, which falls outside its valid range.

Objects involved in the operation:
    iterator @ 0x0x7fffffffb900 {
      type = __gnu_cxx::__normal_iterator<int*, std::__cxx1998::vector<int, std::allocator<int> > > (mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::__debug::vector<int, std::allocator<int> >' @ 0x0x7fffffffb8c0
    }

N4659 (March 2017 post-Kona working draft/C++17 DIS)

score 2 · Accepted Answer · answered Jul 03 '20 at 08:25

Well, defining an iterator that is out-of-range is UB according to the Standard §5/5.7:

When an expression that has integral type is added to or subtracted from a pointer, the result has the typeof the pointer operand. If the pointer operand points to an element of an array object, and the array islarge enough, the result points to an element offset from the original element such that the difference ofthe subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the valuen) point to, respectively, the i+n-th and i−n-th elements of the arrayobject, provided they exist. Moreover, if the expression P points to the last element of an array object,the expression (P)+1 points one past the last element of the array object, and if the expressionQpointsone past the last element of an array object, the expression (Q)-1 points to the last element of the arrayobject. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined

You can verify this if you turn on iterator debugging for gcc

# g++ main.cpp -D_GLIBCXX_DEBUG -o main
# ./main
C:/mingw-w64/i686-8.1.0-win32-dwarf-rt_v6-rev0/mingw32/lib/gcc/i686-w64-mingw32/8.1.0/include/c++/debug/safe_iterator.h:374:
Error: attempt to advance a dereferenceable (start-of-sequence) iterator 10
steps, which falls outside its valid range.

Objects involved in the operation:
    iterator @ 0x0061FE3C {
      type = __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*, std::__cxx1998::vector<int, std::allocator<int> > >, std::__debug::vector<int, std::allocator<int> > > (mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::__debug::vector<int, std::allocator<int> >' @ 0x0061FE50
    }

It should be noted that iterators are not pointers in general. Even `std::vector` iterators can be implemented using a user-defined type (`class`). — Evg, Jul 03 '20 at 08:29
The other answer is better because it explicitly (un)defines the behaviour for iterators, whereas yours just mentions pointers and assumes (granted, rather fairly) that they are representative of iterators. However, this is not necessarily true, nor I think enough to conclusively answer the specific question about iterators. — underscore_d, Jul 03 '20 at 08:29
Both of you are right. I was assuming that this would be enough to declare it UB because the value an iterator points to is stored inside a pointer according to: https://en.cppreference.com/w/cpp/iterator/iterator. — A.K., Jul 03 '20 at 08:43

Is clamping on iterators valid

2 Answers2

Linked