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

Question

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.

Sounds like an implementation bug to me. Also, why are you trying to increment the iterators *past* the `end`? Using `+ 5` when the `deque` only has 3 elements (or 0 elements) is wrong, no matter what. — Remy Lebeau, Jun 24 '20 at 00:28
The reason is that (at least in my program) the user can enter an invalid index. When they do this, it will check to make sure that the resulting iterator is within range, and display an error message if it's not. It can't do this if the program segfaults. My current workaround is to check if the container is empty before generating the iterator. Although this works fine, I wanted to check to see if it's an actual bug, or just me being dumb. If it's the former, I plan to report it to the proper sources. — yottalogical, Jun 24 '20 at 00:34
What is stopping you from validating the index BEFORE you apply it to the iterator? That is easy to do by checking that the index is `0 <= index < deque::size()`. ALWAYS validate/sanitize user input before you use it. — Remy Lebeau, Jun 24 '20 at 00:40
As an aside, there is *no* mention of standard template library or STL in the actual standard, that term comes from a time long ago. Nowadays it's just "the standard" :-) — paxdiablo, Jun 24 '20 at 00:40
I really wouldn't write my code that way. I would check the index entered against `std::deque::size()`. — Paul Sanders, Jun 24 '20 at 00:41
I was going to need an iterator anyways, so I though it made the most sense to just check bounds using it. But based on what I've learned here, I see that this isn't a good idea. — yottalogical, Jun 24 '20 at 00:51

templatetypedef · Accepted Answer · 2020-06-24T00:55:12.457

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!

Just on that second paragraph start, I wouls say "*before* you increnent an iterator". I see that's made clearer later on but it's ambiguous as to whether this derferencabilty is required before incrementing or after. — paxdiablo, Jun 24 '20 at 00:38

score 0 · Answer 2 · answered Jun 24 '20 at 01:13

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

You are causing undefined behavior.

I have also tried it with GCC version 6.2.0 on Linux, but the problem didn't seem to exist there.

No, the undefined behavior manifests itself differently there; it didn't cause a SEGFAULT the time you tried it. (It could next time you try it, though)

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

2 Answers2