C++ value initialized vector iterator comparison

Question

Is the following code legal in c++17?

std::vector<int> x{1,2,3};
std::vector<int>::iterator it{};
bool result = x.begin() != it;

The following is quoted from https://en.cppreference.com/w/cpp/named_req/ForwardIterator :

Equality and inequality comparison is defined over all iterators for the same underlying sequence and the value initialized-iterators

If I understand this correctly, the comparison should be ok. And it seems to work on clang and gcc, but when I run this with MSVC 2019 in debug mode, I get an assert saying "vector iterators incompatible".

I'm not asking about the outcome of the comparison, I'm only interested if MSVC is conforming to the standard here.

Live example on godbolt

Just ignore it. It's MSVC trying to help you from making mistakes in debug mode. It should not come up if you compile in release mode. — NathanOliver, Jun 08 '20 at 16:05
Related: https://stackoverflow.com/questions/4657513/comparing-iterators-from-different-containers — ioums, Jun 08 '20 at 16:08
@NathanOliver I don't believe that's true. You and the OP are, I think, misinterpreting the (admittedly poorly-worded) cppreference text. And, if it were, an assertion in debug would be worrying as that suggests the library impl would consider it "UB" in release. — Asteroids With Wings, Jun 08 '20 at 16:19
@AsteroidsWithWings Personally I enjoy that it's there. What sense does it make to compare an iterator to a vector, to an iterator not to a vector? Even if the standard says it is okay since the empty vector and the empty iterator will "point" to the same thing (nothing) it doesn't make sense to do. — NathanOliver, Jun 08 '20 at 16:23
@NathanOliver Exactly, which is why the standard _doesn't_ say it's okay ;) VS doesn't (shouldn't) assert on valid code just to warn you about style; it asserts to warn you that you're violating some standard rule for which no actual diagnostic is provided — Asteroids With Wings, Jun 08 '20 at 16:24
@AsteroidsWithWings Don't the answer below say the standard says it's okay? — NathanOliver, Jun 08 '20 at 16:26
@NathanOliver There was a (now deleted) answer saying it's ok. But it's not. — cigien, Jun 08 '20 at 16:26
@NathanOliver No, neither answer says it's okay. Song's answer was worded in a confusing way until my edit (it started with just "yes"), but it also quoted the standard that says, effectively, "yes, MSVS is conformant in asserting on your code because your code has UB" — Asteroids With Wings, Jun 08 '20 at 16:27
@AsteroidsWithWings Aah, I see the confusion. When that answer said "yes", I assumed it was answering the "is this code legal" question OP asked :) — cigien, Jun 08 '20 at 16:30
Dup of [Is it well-defined to compare with a value-initialized iterator?](https://stackoverflow.com/questions/26241878/is-it-well-defined-to-compare-with-a-value-initialized-iterator) — Language Lawyer, Jun 09 '20 at 04:19
@LanguageLawyer Not sure if it's a duplicate. That question explicitly asks about input iterators, and this one about random access iterators. The answer to that question *does* cover how it works for forward iterators, which also applies to this case, but I still feel they are sufficiently different. — cigien, Jun 09 '20 at 13:18

eerorika · Answer 1 · 2020-06-08T16:48:50.923

3

MSVC is conforming.

Only iterators to the same sequence may generally be compared with one another. Value initialised iterators are considered to be iterators to the same empty sequence. That "virtual" empty sequence is distinct from any other sequence, and comparisons across separate sequences are not (required to be) defined, and thus the example is potentially undefined.

Standard quote (latest draft)

[forward.iterators] The domain of == for forward iterators is that of iterators over the same underlying sequence. However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type. [ Note: Value-initialized iterators behave as if they refer past the end of the same empty sequence. — end note

Vector iterators are not guaranteed to implement the comparison for a wider domain than this. If it doesn't, then the behaviour is undefined. Your comparison is outside of this domain.

edited Jun 08 '20 at 16:48

answered Jun 08 '20 at 16:18

eerorika

232,697
12
197
326

This is correct, but could you add a standard reference? – cigien Jun 08 '20 at 16:19
I don't think anything here says "potentially ill-formed"; I think it says the code has UB. No such ordering is defined by the standard, period – Asteroids With Wings Jun 08 '20 at 16:26
@AsteroidsWithWings I think that using types in a way that their concept doesn't guarantee is allowed to fail compilation. Thus ill-formed. – eerorika Jun 08 '20 at 16:28
@AsteroidsWithWings is correct. Potentially ill-formed is not a thing. If it's ill-formed, it must be diagnosed. I believe this is just ub. ub *could* be diagnosed though. – cigien Jun 08 '20 at 16:28
@cigien Whether it is ill-formed depends on how the type is defined. If it is ill-formed, then it must be diagnosed. If it is not ill-formed, then it does not need to be diagnosed. The standard doesn't provide definition for iterators, it specifies expressions and operations that must behave in certain way. – eerorika Jun 08 '20 at 16:29
2

@eerorika I've never heard of that. The passage you quote clearly defines the domain of `==`, and the OP's case is not in that domain. Hence, UB. This is borne out by the compiler accepting the code, except for an assert in debug (much like MSVS's debug-mode range checks on `vector::op[]`) – Asteroids With Wings Jun 08 '20 at 16:30
@AsteroidsWithWings Pointers are also iterators. `nullptr == not_null_ptr` has well defined behaviour. Forward iterators are simply not required to have any specific behaviour, defined or otherwise for those outside the domain. Whether they have UB or not depends on that type. As an example of ill-formed case, input iterators are not required to support `it + X`. But some input iterators do support it. For all other itreators, such expression is ill-formed. – eerorika Jun 08 '20 at 16:35
@eerorika _"Forward iterators are simply not required to have any specific behaviour, defined or otherwise for those outside the domain"_ That's literally what undefined behaviour is. It has nothing to do with "depending on the type". The standard defines no behaviour for comparing iterators (or pointers!) to different sequences. Period, full stop. It's right there in the text of your own answer! :) – Asteroids With Wings Jun 08 '20 at 16:36
@AsteroidsWithWings It has everything to do with the type. The fact that `nullptr == not_null_ptr` is outside the domain of == operator for forward iterators does not mean that it is UB. It is not UB – eerorika Jun 08 '20 at 16:37
@eerorika Okay, we'll have to agree to disagree. – Asteroids With Wings Jun 08 '20 at 16:37
By the way, your pointer example is defined by http://eel.is/c++draft/expr.eq#3. That's a separate, parallel rule, that does not apply to iterators in general, and certainly not to a `vector::iterator`. – Asteroids With Wings Jun 08 '20 at 16:48
@AsteroidsWithWings **That** rule doesn't apply to all iterators. But it is entirely possible for such rules to exist for other iterators. The existence of such hypothetical rules is not excluded by the rule quoted in my answer just like the rule that you linked isn't excluded. Exactly what rules apply to the iterator depends exactly on how that iterator type and its operations are defined. And that is not specified by the standard. The requirements of iterator concepts are a minimal set that must be implemented. – eerorika Jun 08 '20 at 16:51
I removed "ill-formed" from the answer by the way. While it is possible in general as far as iterator requirements are concerned, I don't think that's a way to define an iterator in a way that comparing value initialised iterator to non-value initialised would be ill-formed in practice. – eerorika Jun 08 '20 at 16:56
@eerorika It's possible in some alternative universe that a rule exists for other iterators. But it is not the case in _this_ universe. Unless you can find one then feel free to quote. Regardless, the OP used a `vector::iterator`. – Asteroids With Wings Jun 08 '20 at 17:03

score 1 · Accepted Answer · answered Jun 08 '20 at 16:38

Visual Studio is correct. You are getting an assertion (in debug only!) because your code has undefined behaviour, and the implementation is warning you about that.

Value-initialised iterators can only be compared to other value-initialised iterators. This is a generalisation of the rule that comparing pointers or iterators only works within a sequence or array (with one notable exception being std::less, which handily provides a total ordering over the whole memory space; this is the only way a set, using the default comparator, of unrelated pointers can work).

[forward.iterators] The domain of == for forward iterators is that of iterators over the same underlying sequence. However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type. [ Note: Value-initialized iterators behave as if they refer past the end of the same empty sequence. — end note ]

No semantics are defined for an ordering between a value-initialised iterator, and an iterator to a position in a sequence.

The cppreference text is a little badly-worded in this regard, though the same page does do a little better on the semantics for a successful equality between two singular iterators:

A value-initialized LegacyForwardIterator behaves like the past-the-end iterator of some unspecified empty container: it compares equal to all value-initialized LegacyForwardIterators of the same type.

And, again, you cannot compare iterators to different containers, so there we have our rule.

C++ value initialized vector iterator comparison

2 Answers2

Linked