Is clamping on iterators valid

user_2466431 0
Viewed 296

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.

language-lawyer iterator stl c++
2 Answers

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)
user_16251870

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
    }
user_96342890
Related