4

I do not want to use std::distance because it will calculate whole distance from my iterator to the end. But I need to be sure that I have N or more elements from my iterator to the end. So I'm using next code: 

if (std::next(it, n) != c.end()) // c is a std::multimap
{
    /// my logic
}

Everything is great and working with my compiler (g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-9)) but I have doubts. In documentation (cpprefenece.com && cplusplus.com) I can not find any information about case when n > std::distance(it , c.end()) or about any other exceptional cases. So. Is my code safe? Or I should write my own nextIfPossible?

denys
  • 2,437
  • 6
  • 31
  • 55
  • I would say not to depend on `std::next` though the implementation for `*map` on libstd++ currently works as per your needs. But the same would not work in case of `std::vector`. Since the behaviour is _not_ same across containers, you should not depend on it. – Arunmu Jul 11 '16 at 11:40
  • It looks okay to me as long as you guarantee there are at least `n` elements in the container. – NathanOliver Jul 11 '16 at 11:42

3 Answers3

5

next(it, n) is undefined behavior if distance(it, c.end()) is less than n.

[C++14: 5.7/5] 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.

See here for more info: Are non dereferenced iterators past the "one past-the-end" iterator of an array undefined behavior?

You must write a nextIfPossible or your code is undefined. That said, since I'm guessing this is a Random Access Iterator, you'll find working with indexes to benchmark faster than working with iterators in the case where bounds checking must be performed: https://stackoverflow.com/a/37299761/2642059

So I'd recommend not even bothering with iterators or nextIfPossible but just using an index and checking it against the size.

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • 3
    Do note that you accepted answer on that post its actually talking about pointers and not iterators. I'm still not sure I have seen something that proves `end() + 1` is undefined. – NathanOliver Jul 11 '16 at 11:48
  • @NathanOliver Iterators are also illegal, you can find that in [Ben Voigt's excellent answer](http://stackoverflow.com/a/37219916/2642059) to my first linked question. But it's just a little too much material to reproduce here. – Jonathan Mee Jul 11 '16 at 11:49
  • 1
    I still do not think it proves anything. For one thing he says *For iterators, incrementing past the "end" (one-past-the-last-element) is not prohibited generally, but it IS prohibited for most of the various kinds of iterators* and for another thing there is AFAIK nothing that actual says the end iterator is not dereferencable. There is a quote that the standard never assumes it is but IMHO that is not enough. – NathanOliver Jul 11 '16 at 11:53
  • @NathanOliver He demonstrates it for Input Iterators. All other types of iterators are required to adhere to the requirements of Input Iterators: http://en.cppreference.com/w/cpp/iterator#Iterator_categories So his specification is proof enough. The only reason that he bothers to expound on Random Access Iterators is they may be advanced by something other than the Increment Operator. – Jonathan Mee Jul 11 '16 at 12:05
  • He proves it by saying the end iterator has to be dereferencable but nowhere does he prove the end iterator is not dereferencable. – NathanOliver Jul 11 '16 at 12:08
  • @NathanOliver It would be impossible to prove that the One Past the End Iterator cannot be dereferenced, because that is explicitly allowed for `strings`: http://en.cppreference.com/w/cpp/string/basic_string/operator_at But he doesn't need to prove or disprove that fact. He's saying that iterating past the One Past the End Iterator is undefined. – Jonathan Mee Jul 11 '16 at 12:12
  • 1
    @NathanOliver: It's never safe to increment past the end. For some iterators (e.g. infinite generators), it's not even possible to reach the end by incrementing, which is why there is no general prohibition. For others where it is possible to reach the end, the precondition on the increment operator is that the iterator is currently before the end. – Ben Voigt Jul 11 '16 at 17:43
  • @BenVoigt Where is that defined? All I ever see in the standard is the iterator must be dereferenecable. I cannot find anywhere that says the end iterator is not dereferenecable. – NathanOliver Jul 11 '16 at 17:48
  • @NathanOliver: You're looking for the wrong thing. There is no statement that "it is not dereferenceable", rather that is the default case unless you find a statement that it is dereferenceable. "Undefined behavior" still has its meaning of "behavior that has never been defined" in addition to " explicitly called out as undefined". – Ben Voigt Jul 11 '16 at 17:51
  • @BenVoigt To me that translate to it is implementation defined and not actually UB. – NathanOliver Jul 11 '16 at 17:55
  • @NathanOliver I think you may be correct that they are implementation defined rather than undefined: "Iterators are not dereferenceable if they are past-the-end iterators (including pointers past the end of an array) or before-begin iterators. Such iterators may be dereferenceable in a particular implementation, but the library never assumes that they are." [[Source](http://en.cppreference.com/w/cpp/concept/Iterator)] I've asked a maligned question about that here: https://stackoverflow.com/questions/32760445/assignment-of-a-singular-iterator – Jonathan Mee Jul 11 '16 at 18:03
  • 1
    @Nathan UB means an implementation can assign valid behavior but does not have to, implementation-defined means that every implementation must accept it, but the Standard leaves the implementation a choice of behavior. This is in the first category - an implementation is not required to provide any guarantees about dereferencing iterators past the end. – Ben Voigt Jul 11 '16 at 18:39
4

According to the standard §24.4.4/p3 & p6 Iterator operations [iterator.operations] (Emphasis Mine):

template <class InputIterator, class Distance>
constexpr void advance(InputIterator& i, Distance n);

2 Requires: n shall be negative only for bidirectional and random access iterators.

3 Effects: Increments (or decrements for negative n) iterator reference i by n.

template <class InputIterator>
constexpr InputIterator next(InputIterator x,
typename std::iterator_traits<InputIterator>::difference_type n = 1);

6 Effects: Equivalent to: advance(x, n); return x;

Consequently, there's no bound checking and therefore you may result in undefined behaviour if input n is greater than std::distance(it , c.end()).

101010
  • 41,839
  • 11
  • 94
  • 168
0

The implementation of RB_Tree::iterator increment operator in libstd++ makes sure it would not return an iterator to an undefined memory location:

static _Rb_tree_node_base*
  local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_right != 0)
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right)
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }

But the same is not true for std::vector:

#include <iostream>
#include <vector>
#include <iterator>

int main() {
  std::vector<int> vec = {1,2};
  auto it = vec.begin();
  it = std::next(it, 5);
  if (it != vec.end()) {
    std::cout << "Not end..go on" << std::endl;
  }
  return 0;
}

This will go on printing the message..

So, since the behaviour is not same across containers, you should not depend on std::next for its current correct behaviour for map based containers.

Arunmu
  • 6,837
  • 1
  • 24
  • 46