5

I have read the documentation for C++ list iterators, but couldn't figure out one thing: are C++ iterators "safe"? I mean, does it stop incrementing once it reaches the last existing element in a list?

[]'s

Mauren
  • 1,955
  • 2
  • 18
  • 28
  • Have you tried writing a program that does this? What happens? – Karmastan Jan 26 '11 at 21:19
  • 3
    @Karmastan - unfortunately in C++ that kind of experiment is of little value. – Daniel Earwicker Jan 26 '11 at 21:20
  • Why would anyone invent iterators that weren't safe and iterated off the end of the containers? What would you do with one, were it to exist? – David Heffernan Jan 26 '11 at 21:20
  • 10
    @David Heffernan - such iterators are commonplace in C++. The justification is performance. – Daniel Earwicker Jan 26 '11 at 21:21
  • @David Heffernan- As incentive for you to pay extra for the "safe" version :p – bta Jan 26 '11 at 21:22
  • @Karmastan, writing a program to try something doesn't tell you the bigger picture. Sometimes it's the right answer, but not in this case. – Mark Ransom Jan 26 '11 at 21:23
  • 3
    Unsafe iterators should motivate you to quit using them directly, and use algorithms instead, and let the algorithm worry about stopping incrementing when it should. – Jerry Coffin Jan 26 '11 at 21:28
  • @Daniel,Mark - When I implemented a program to do this, it told me that `std::list::iterator` is happy incrementing past the end of the list and being dereferenced without an error or exception. Do I need more information to conclude that iterators aren't safe? – Karmastan Jan 26 '11 at 21:31
  • 1
    @JerryCoffin that's not always enough. If, for instance, you have an iterator `iter` pointing into a `std::list l` and you call `l.erase(iter)` then you must make sure never to use again `iter`. `iter` is invalid after the function call. – wilhelmtell Jan 26 '11 at 21:43
  • If there was no error or exception, you might conclude from your experiment that they were safe - similar to how in Objective C it is a valid operation to call a method on a null pointer (it just does nothing). – Daniel Earwicker Jan 26 '11 at 21:43
  • @Karmastan yes. How do you know your compiler or standard library don't have a bug? – wilhelmtell Jan 26 '11 at 21:44
  • @wilhelmtell: I didn't mean to imply that it was *always* enough, but I'd say it eliminates at least 95% of the situations where iterator validity is a concern. – Jerry Coffin Jan 26 '11 at 21:45
  • I thought you were asking, will they go beyond the end if used properly. Who cares what they do if used incorrectly? – David Heffernan Jan 26 '11 at 21:49
  • 1
    Don't be too harsh with @Karmastan. The fact is that while a single test will not prove a theory, a counter example will prove it wrong. In this case you can know that the iterator will happily increment beyond the end of the container, and @wilhelmtell, you are right in that it could be an issue with the compiler, but if that is the compiler that you are going to use with the code, you better avoid using that construct. If I ship a system that crashes regularly, I don't think that my clients would be happy saying *oh, well, the code is perfectly standards compliant, it's the compiler's fault* – David Rodríguez - dribeas Jan 26 '11 at 21:49
  • @DavidRodriguez this is irrelevant to the question. The question is about a standard guarantee, and if you test your idea with a compiler then you still don't know the answer, no matter what your experiment yields. Whatever your compiler says, you **don't know** if it's buggy and you **don't know** if your idea is right or wrong. You can just conclude "your idea may or may not be right, and the compiler and/or library may or may not be buggy". Not particularly useful a conclusion. – wilhelmtell Jan 26 '11 at 21:58
  • @wilhelmtell: After the test, I know with certainty that iterators are not safe on *my platform* (disproving the theory that iterators are safe on all platforms). Hence, if I want to write code that I can use, I shouldn't rely on iterator safety. The reason that iterators are not safe, whether by committee fiat or compiler fault, is irrelevant. I disagree that the question is only about the standards; from a pragmatic viewpoint, it's about being able to rely on a feature when writing a program. One test with a negative result *can* definitively answer, "This isn't safe." – Karmastan Jan 26 '11 at 22:48
  • @Karmastan, the counter example that proves they're not safe might be enough. If it were me I would want to know the rationale, perhaps leading to the follow-up question "why isn't this documented, or how did I miss it?" – Mark Ransom Jan 27 '11 at 22:09
  • 2
    Possible duplicate of [What happens if you increment an iterator that is equal to the end iterator of an STL container](https://stackoverflow.com/questions/1057724/what-happens-if-you-increment-an-iterator-that-is-equal-to-the-end-iterator-of-a) – Raedwald Nov 29 '17 at 10:55

7 Answers7

13

No, they're not "safe" in that sense. It is possible to increment an iterator past the end. For all the iterators in the standard library doing this will result in undefined behaviour. You could define your own iterators that do behave in a safe way instead if you wanted to.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 1
    That's an oversimplification. Are they always safe: No. Can they be safe yes (debug versions sometimes provide checked iterators). Do we want them to be safe: Usually we don't want to pay a runtime cost for safeness. – Martin York Jan 26 '11 at 21:54
  • @Martin: Really it's up the the writer of the container. You can't go past the end with any of the standard iterators, but MyContainerXXXYYY is perfectly allowed to define STL-style iterators which do not result in undefined behavior if incremented past the end of their controlling container. – Billy ONeal Jan 26 '11 at 22:09
9

What you're asking is does std::list::iterator do bound-checking. The answer is no, it doesn't. This means the iterator is faster than otherwise. If you want bound-checking then you can wrap the iterator with a bound-checking iterator wrapper of your own.

But if you follow conventions when you use iterators then you will always know at compile time when an iterator is invalid, i.e., points at an invalid position. For instance:

  • When you erase an element from a std::list then make sure you store the iterator erase() returns to get a valid iterator pointing at the new valid position, just beyond the element erased.
  • When you call std::remove() make sure you store the returned iterator so you know what are the new bounds of your container.

This approach shifts the bound-checking issue aside while retaining the performance of iterators that don't need to bother with making sure the user doesn't shoot herself in the foot.

wilhelmtell
  • 57,473
  • 20
  • 96
  • 131
  • Actually incrementing past the end can be made safe without any additional overhead. – Yakov Galka Jan 26 '11 at 21:28
  • If you create the container at runtime then you're going to pay for extra checks, there's no way around it. It takes an extra check for incrementing/decrementing and/or for dereferencing. Irrelevant performance concern, you might say, but the standard C++ library is a general-purpose library and therefore efficient for a reason. – wilhelmtell Jan 26 '11 at 21:33
  • @wilhelmtell: not for a list. You may make the last element's 'next' pointer point to itself, so incrementing an iterator to it leaves you in place, without any check. Also an implementation may use cyclic lists so incrementing end returns you to begin, again no checks. – Yakov Galka Jan 26 '11 at 21:40
  • @ybungalobill so what does dereferencing the element past-the-end yield? – wilhelmtell Jan 26 '11 at 21:52
  • 1
    Having the last iterator of a list increment back to itself is not bound-checking. In fact, I prefer that the last iterator increments to an invalid node an crashes, because then I know where the bug is. As opposed to introducing a silent error in my code. A "safe" program that runs without a segfault but has silent errors, is not safe in my opinion. – Mikael Persson Jan 26 '11 at 22:09
  • @Mikael yes. You increment past the last element and into the `end()` iterator and you're still at the last element. You can't tell when you're done, unless you continually test to see if you're at the last element -- which defeats the whole purpose of a "bound-checking" iterator. @ybungalobill take a look at `at()` of `std::vector` to see what bound-checking should mean in a dereference operation. – wilhelmtell Jan 26 '11 at 22:53
  • @wilhelmtell: we were not speaking of dereferencing but of incrementing. When you use a singular node as the end-point, then it is safe to increment continuously, but obviously unsafe to dereference it since no value is stored... it's a fake node. – Matthieu M. Jan 27 '11 at 07:21
  • @wilhelmtell @Mikael: you got me wrong. I'm not advocating safe iterators for lists. I just said that it's possible to implement a safe *increment* operation for lists without efficiency penalty as opposed to what you've written in the first paragraph of your answer. As Matthieu said, we're talking about safe incrementing, not dereferencing. I'm just picky at the factual details, sorry. – Yakov Galka Jan 27 '11 at 07:37
  • 1
    There's more to safety than mere bounds checking. For instance, a safe iterator would check (obviously at runtime) whether it's compared to an iterator from another list. – MSalters Jan 27 '11 at 13:21
3

You must test whether it != list.end(), and leave the loop if end was reached.

Christoph
  • 1,964
  • 2
  • 27
  • 44
2

No. If you dereference a "past-the-end" iterator, you get Undefined Behavior.

aschepler
  • 70,891
  • 9
  • 107
  • 161
2

No. Like many things in C++, the default is speed.

The rationale is that you can trade speed for safety later, but not vice versa.

MSalters
  • 173,980
  • 10
  • 155
  • 350
1

To answer your question, "No" they will not stop as the responsibility is on the owner to check bounds.

However, one can put the checks into a proxy iterator and enforce bounds checks. This is going to cost you though as most likely there will be a price to pay. Most of the std algorithms now have first/last for both input and output iterators( see std::copy( first_in, last_in, first_out, last_out ) and will check the bounds along with ones that do not take the end of the output as that is not always a valid operation(e.g. end of a stream isn't known until it happens)

You can write a iterator proxy that contains a copy of the iterator, the first position and the last position. Then check if it will go out of bounds on operator++, operator--, and when accessing members or dereferencing. It is almost the same work as writing a skeleton contianer and could be used as such. For a small example see Iterator Proxy Example and then in use Iterator Proxy Usage Example

Beached
  • 1,608
  • 15
  • 18
-1

Using properly, iterators are very useful.
Therefore the question "Are C + + iterators safe" will depend on how it is used.
Note that the incorrect use of printf API can cause serious errors. The implementation will it be safe to use or not.

lsalamon
  • 7,998
  • 6
  • 50
  • 63