74

For any STL container that I'm using, if I declare an iterator (of this particular container type) using the iterator's default constructor, what will the iterator be initialised to?

For example, I have: 

std::list<void*> address_list;
std::list<void*>::iterator iter;

What will iter be initialised to?

Alexandre C.
  • 53,934
  • 10
  • 121
  • 192
The Void
  • 807
  • 2
  • 7
  • 6
  • `std::list::iterator iter;` is a __definition__. While all definitions are declarations, a declaration that's not a definition would be: `extern std::list::iterator iter;`. – sbi Aug 03 '10 at 09:40
  • In particular, the constructor belongs to the _definition_, not any other declaration. This means you can pass values to the constructor only in the (single) definition. Also, if the ctor is a template (like here), it's instantiated where the definition is. – MSalters Aug 03 '10 at 14:35

4 Answers4

60

By convention a "NULL iterator" for containers, which is used to indicate no result, compares equal to the result of container.end(). 

 std::vector<X>::iterator iter = std::find(my_vec.begin(), my_vec.end(), x);
 if (iter == my_vec.end()) {
     //no result found; iter points to "nothing"
 }

However, since a default-constructed container iterator is not associated with any particular container, there is no good value it could take. Therefore it is just an uninitialized variable and the only legal operation to do with it is to assign a valid iterator to it.

 std::vector<X>::iterator iter;  //no particular value
 iter = some_vector.begin();  //iter is now usable

For other kinds of iterators this might not be true. E.g in case of istream_iterator, a default-constructed iterator represents (compares equal to) an istream_iterator which has reached the EOF of an input stream.

UncleBens
  • 39,805
  • 6
  • 53
  • 90
  • 3
    There is a proposal for a value initialized iterator to exist. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3644.pdf – Ghita Apr 29 '15 at 08:55
  • 4
    Under that proposal writing auto ni = vector::iterator() would create a null vector iterator that would compare equal to any other iterator of the same type – Ghita Apr 29 '15 at 08:56
  • N3644 / null forward iterators exists since C++14. This seems to be this answer but if I understand correctly that's only for forward iterators and better (and only since C++14). – gast128 Jul 20 '20 at 17:42
28

The default constructor initializes an iterator to a singular value:

Iterators can also have singular values that are not associated with any sequence. [ Example: After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer. — end example ]
Results of most expressions are undefined for singular values [24.2.1 §5]

rustyx
  • 73,455
  • 21
  • 176
  • 240
fredoverflow
  • 246,999
  • 92
  • 370
  • 646
  • 19
    My standardese aversion striking again. `` What does that mean in understandable speech? – sbi Aug 03 '10 at 09:41
  • 2
    @sbi: Well, the paragraph goes on and on, I decided to cut it. Basically, you are not allowed to do anything useful with a singular value, for example dereference it or compare it. – fredoverflow Aug 03 '10 at 09:45
  • 11
    @sbi: just replace all instances of "singular" with "weird". You're not allowed to do anything with it because it's in a weird state. – jalf Aug 03 '10 at 10:09
  • 1
    @jalf & Fred: Thanks. Interesting. I've certainly never come across the term "singular value". Would that mean a _certain_, special value_ (as `NULL` is for pointers)? I thought `T*` is a valid type for `std::vector::iterator`? (Old Dinkumware implementations used to do that.) If that was true, `std::vector::iterator it;` certainly wouldn't initialize `it` to a special value, while `std::vector::iterator it = std::vector::iterator();` would. – sbi Aug 03 '10 at 13:37
  • 1
    It might be useful to consider singular iterators "write-only, do not point to a sequence (yet)". As they're write-only, you can't talk about "the value they have". – MSalters Aug 03 '10 at 14:39
  • @sbi: For user-defined types T, the definition `T x;` **always** initializes x with the default constructor (if there is one, of course). – fredoverflow Aug 03 '10 at 14:59
  • @jalf & @Fred: Well, the question still stands. Do you happen to know the answer? – sbi Aug 18 '10 at 21:28
  • @sbi: It is not required to have any special value, it is basically degenerate: you can't really do anything with it, other than assign to it to bring it into a well-defined non-singular state. An uninitialized pointer would be an example of a singular iterator. – jalf Aug 18 '10 at 22:08
  • 2
    @jalf: Thanks for clarifying that. I consider "singular value" a badly coined name for something that could have _any_ possible value. It sure threw me off.... – sbi Aug 19 '10 at 17:40
  • 1
    The only correlation I can think of is in the linear algebra sense, e.g. a singular matrix is one with infinite solutions. – Daniel B. Dec 16 '15 at 21:41
13

The iterator is not initialized, just as int x; declares an integer which isn't initialized. It does not have a properly defined value.

JesperE
  • 61,479
  • 20
  • 135
  • 194
  • 3
    Is there a way to initialise iter to NULL? – The Void Aug 03 '10 at 09:32
  • 3
    @The Void: Your question makes no sense. `NULL` is a value _pointers_ may have, bot iterators. While all pointers are iterators, not all iterators are pointers. – sbi Aug 03 '10 at 09:36
  • So, while there is such a thing as a NULL pointer, there's no such thing as a "NULL iterator"? – The Void Aug 03 '10 at 09:40
  • @The Void: An iterator is an object, and there is no such thing as a "NULL object". (Yes, there is that pattern, but that's a completely different thing.) The closest thing to a "NULL iterator" is the singular value described in my answer. – fredoverflow Aug 03 '10 at 09:46
  • There is no such thing as an "empty" or "null" iterator. It's the same as a lock for instance. You can't talk about an "empty" or a "null" lock, this just makes no sense. – Tomaka17 Aug 03 '10 at 09:48
  • 2
    @JesperE: It most probably is initialized (iterators in many cases are classes, and they will have a default constructor that initializes the contents). – David Rodríguez - dribeas Aug 03 '10 at 11:57
  • 6
    @sbi: is bot a new abbreviation for "but not"? :) – codymanix Aug 04 '10 at 12:27
  • @codymanix: Yeah, something like this. I guess thinking got ahead of typing and my fingers cheated to catch up. `:)` – sbi Aug 04 '10 at 18:44
  • @fredoverflow, ironically, some (all?) standard container iterators have a constructor that take (explicitly?) a `nullptr`/`0` argument, as in `std::vector::iterator vit{nullptr}; std::list::iterator lit{nullptr};`. Not sure what whether it is standard (I am using gcc) and what is the purpose, (maybe to accept generic code in the initialization of a pointer?). – alfC Jun 21 '18 at 21:50
3

An updated answer.

Up to and including C++11: a default- and value-initialized iterator may contain a singular value. Technically it may not be compared, nor dereferenced. See [iterator.requirements.general]/p5.

By convention however, STL implementations used to initialize such an iterator as a past-the-end iterator.

Starting from C++14: a value-initialized forward iterator compares equal to a past-the-end iterator. See [iterators.forward.iterators]/p2:

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

Therefore:

std::list<void*>::iterator iter {}; should work as a past-the-end iterator.

std::list<void*>::iterator iter; is dangerous as iter will be initialized only if one has a non-trivial default constructor. Though for std::list that will probably be the case, and so should also work.

rustyx
  • 73,455
  • 21
  • 176
  • 240
  • Note that I got contradictory answers from : https://stackoverflow.com/questions/68137196/why-does-not-stdsettend-compare-equal-to-stdsettiterator/68137345#68137345 – hl037_ Jun 25 '21 at 21:47
  • 2
    @hl037_ I left a similar comment on the linked answer; this doesn't contradict anything. You're conflating "end" iterator for a specific container with the concept of a "past-the-end iterator". A default-initialized iterator will behave like some arbitrary past-the-end iterator, which means it can be dereferenced or compared to by others **from the same sequence** (e.g. other default-initialized). That doesn't make it a skeleton-key that compares to all `end()` iterators; it's from a different "container", and comparing iterators from different containers is not supported. – Human-Compiler Jun 25 '21 at 22:38
  • This sentence "a value-initialized forward iterator compares equal to a past-the-end iterator." seems wrong and misled me -- it's UB to compare any container's past-the-end iterator with any value-initialized iterator. (If you're trying to say "compares" not as C++ `operator==`, but instead "in general behaves similar to" then don't say "compare"?) – Carl Walsh Apr 05 '22 at 01:11