Should it be possible to add to an iterator of an empty deque in C++?

Here's an example of what will cause the problem:

#include <deque>

int main() {
    std::deque<int> has_data = {1, 2, 3};
    std::deque<int>::iterator iter1 = has_data.begin() + 5; // This works fine
    
    std::deque<int> had_data = {4, 5, 6};
    had_data.clear();
    std::deque<int>::iterator iter2 = had_data.begin() + 5; // This also works fine
    
    std::deque<int> is_empty;
    std::deque<int>::iterator iter3 = is_empty.begin() + 5; // This causes a segfault
}

Adding to an iterator of an empty deque only seems to be a problem if the deque has never contained any elements before.

I'm curious as to if this is a bug in the STL, or if I'm just using it in a way that causes undefined behavior. I only get this problem when compiling with Xcode (both the GUI and the command line). I have also tried it with GCC version 6.2.0 on Linux, but the problem didn't seem to exist there.

Solution

The issue you're running into here is that it's undefined behavior to use the + operator to jump an iterator forward beyond the spot one past the end of a container. As a result, each of the iterator operations you're performing leads to undefined behavior, and it just so happens to be the case that the first two cases coincidentally don't crash while the last one does.

(As for why this is undefined behavior: the C++17 standard requires that (§27.2.3/2), to increment an iterator, the iterator must be dereferencable, in the sense that it must safe and legal to dereference the iterator before you increment it. It then says (§27.2.7/1) that if you use + or += on an iterator, it should have the same effect as if you iteratively did ++ the appropriate number of times. As a result, if you jump an iterator more that one step past the end of a container, at some point you'll reach the end of the container where the iterator isn't dereferencable and will trigger undefined behavior.)

Hope this helps!