Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Based on what's considered idiomatic in C++11:

  • should an iterator into a custom container survive the container itself being destroyed?
  • should it be possible to detect when an iterator becomes invalidated?
  • are the above conditional on "debug builds" in practice?

Details: I've recently been brushing up on my C++ and learning my way around C++11. As part of that, I've been writing an idiomatic wrapper around the uriparser library. Part of this is wrapping the linked list representation of parsed path components. I'm looking for advice on what's idiomatic for containers.

One thing that worries me, coming most recently from garbage-collected languages, is ensuring that random objects don't just go disappearing on users if they make a mistake regarding lifetimes. To account for this, both the PathList container and its iterators keep a shared_ptr to the actual internal state object. This ensures that as long as anything pointing into that data exists, so does the data.

However, looking at the STL (and lots of searching), it doesn't look like C++ containers guarantee this. I have this horrible suspicion that the expectation is to just let containers be destroyed, invalidating any iterators along with it. std::vector certainly seems to let iterators get invalidated and still (incorrectly) function.

What I want to know is: what is expected from "good"/idiomatic C++11 code? Given the shiny new smart pointers, it seems kind of strange that STL allows you to easily blow your legs off by accidentally leaking an iterator. Is using shared_ptr to the backing data an unnecessary inefficiency, a good idea for debugging or something expected that STL just doesn't do?

(I'm hoping that grounding this to "idiomatic C++11" avoids charges of subjectivity...)

share|improve this question
add comment

4 Answers 4

up vote 6 down vote accepted

Is using shared_ptr to the backing data an unnecessary inefficiency

Yes - it forces an extra indirection and an extra allocation per element, and in multithreaded programs each increment/decrement of the reference count is extra expensive even if a given container is used only inside a single thread.

All of these might be fine, and even desirable, in some situations, but the general rule is not to impose unnecessary overheads which the user cannot avoid, even when they're useless.

Since none of these overheads are necessary, but are rather debugging niceties (and remember, incorrect iterator lifetime is a static logic bug, not some weird runtime behaviour), no-one would thank you for slowing down their correct code to catch your bugs.


So, to the original question:

should an iterator into a custom container survive the container itself being destroyed?

the real question is, should the cost of tracking all live iterators into a container, and invalidating them when the container is destroyed, be foisted on people whose code is correct?

I think probably not, although if there is some case where it's genuinely hard to manage iterator lifetimes correctly and you're willing to take the hit, a dedicated container (or container adapter) that provides this service could be added as an option.

Alternatively, switching to a debug implementation based on a compiler flag might be reasonable, but it's a much bigger and more expensive change than most that are controlled by DEBUG/NDEBUG. It's certainly a bigger change than either removing assert statements or using a debugging allocator.


I forgot to mention, but your solution of using shared_ptr everywhere doesn't necessarily fix your bug anyway: it may merely exchange it for a different bug, namely a memory leak.

share|improve this answer
add comment

In C++, if you let the container get destroyed, then the iterators become invalid. At the very least this means that the iterator is useless, and if you try to dereference it, then lots of bad things can happen (exactly how bad depends on implementation, but it's usually pretty bad).

In a language like C++, it is the responsibility of the programmer to keep such things straight. That's one of the strengths of the language, because you can pretty much depend on when things happen (you deleted an object? That means that at the moment of deletion, the destructor will be called and the memory will be freed, and you can depend on that), but it also means that you can't go keeping iterators into containers all over the place, and then delete that container.

Now, could you write a container that keeps the data around until the iterators are all gone? Of course, you've clearly got that going. That's NOT the usual C++ way, but there's nothing wrong with it, as long as it's properly documented (and of course, debugged). It's just not how the STL containers work.

share|improve this answer
    
note that bad can go from returning a sentinal to undefined behavior –  ratchet freak Jun 27 '12 at 12:10
    
@ratchetfreak - yes, that's true. In the case in question (iterators into a container) there's usually no good way to define the sentinal value, so the usual C++ way (and the behavior of the STL) tends toward 'undefined behavior'. –  Michael Kohne Jun 27 '12 at 17:39
add comment

One of the (often not said) difference between C++ and other GC languages is that the mainstream C++ idiom assumes that all classes are value classes.

There are pointer and references, but they are mostly relegated in allowing polymorphic dispatch (via virtual function indirection) or managing object whose lifetime must survive the one of the block who created them.

In this last case, it is the programmer responsibility to define the policy and politics about who create and who and when must destroy. Smart pointers (like shared_ptr or unique_ptr) are just tools to help in this task in the very particular (and frequent) cases an object is "shared" by different owners (and you want the last one to destroy it) or needs to be moved across contexts having always a single context owning it.

Interators, by design, makes sense only during ... an iteration, and hence they should not be "stored for later use" since what they refer to, is not granted to remain the same or to stay there (a container may relocate it's content when growing or shrinking ... invalidating everything). Link-based containers (like list-s) are an exception to this general rule, not the rule themselves.

In the idiomatic C++ if A "needs" B, B must be owned in a place that lives longer than the place that owns A, hence no "life tracking" of B from A is required.

shared_ptr and weak_ptr helps where this idiom is too restrictive, by allowing respectively the "don't go away until all of us allow you" or the "if you go away just leave a message for us" policies. Bit they have a cost, since -to do that- they have to allocate some auxiliary data to handle those stuffs.

The next step are gc_ptr-s (that the standard library doesn't offer, but that you can implement if you want, using -for example- mark & sweep algorithms) where the tracking structures will be even more complex and more processor intensive is their maintenance.

share|improve this answer
add comment

In C++ it's idiomatic to make anything that

  • can be prevented by careful coding and
  • would incur runtime cost to protect against

an Undefined Behaviour.

In particular case of iterators, the documentation of each containers says which operations invalidate iterators (destruction of the container is always among them) and access to invalid iterator is Undefined Behaviour. In practice it means that runtime will blindly access the no longer valid pointer. Usually it crashes, but it might corrupt memory and cause completely unpredictable outcome.

Providing optional checks that can be turned on in debug mode (with #define that defaults to on if _DEBUG is defined and disabled if NDEBUG is) is good practice.

However remember that C++ is designed to handle cases where one needs every bit of performance and the checks can be quite costly sometimes, since iterators are often used in tight loops, so don't enable them by default.

In our work project I had to disable iterator check in Microsoft standard library even in debug mode, because some containers use other containers and iterators internally and just destroying one huge one was taking half an hour because of the checks!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.