c++ - What does enabling STL iterator debugging really do? -

i've enabled iterator debugging in application defining

_has_iterator_debugging = 1 

i expecting check vector bounds, have feeling it's doing lot more that. checks, etc being performed?

dinkumware stl, way.

there number of operations iterators lead undefined behavior, goal of trigger activate runtime checks prevent occuring (using asserts).

the issue

the obvious operation use invalid iterator, invalidity may arise various reasons:

• unitialized iterator
• iterator element has been erased
• iterator element physical location has changed (reallocation vector)
• iterator outside of [begin, end)

the standard precise in excruciating details each container operation invalidates iterator.

there somehow less obvious reason people tend forget: mixing iterators different containers:

std::vector<animal> cats, dogs;  for_each(cats.begin(), dogs.end(), /**/); // obvious bug 

this pertain more general issue: validity of ranges passed algorithms.

• [cats.begin(), dogs.end()) invalid (unless 1 alias other)
• [cats.end(), cats.begin()) invalid (unless cats empty ??)

the solution

the solution consists in adding information iterators validity , validity of ranges defined can asserted during execution preventing undefined behavior occur.

the _has_iterator_debugging symbol serves trigger capability, because unfortunately slows down program. it's quite simple in theory: each iterator made observer of container it's issued , notified of modification.

in dinkumware achieved 2 additions:

• each iterator carries pointer related container
• each container holds linked list of iterators created

and neatly solves our problems:

• an unitialized iterator not have parent container, operations (apart assignment , destruction) trigger assertion
• an iterator erased or moved element has been notified (thanks list) , know of invalidity
• on incrementing , decrementing iterator can checks stays within bounds
• checking 2 iterators belong same container simple comparing parent pointers
• checking validity of range simple checking reach end of range before reach end of container (linear operation containers not randomly accessible, of them)

the cost

the cost heavy, correctness has price ? can break down cost though:

• extra memory allocation (the list of iterators maintained): o(nbiterators)
• notification process on mutating operations: o(nbiterators) (note push_back or insert not invalidates iterators, erase does)
• range validity check: o( min(last-first, container.end()-first) )

most of library algorithms have of course been implemented maximum efficiency, typically check done once , @ beginning of algorithm, unchecked version run. yet speed might severely slow down, hand-written loops:

for (iterator_t = vec.begin();      != vec.end();              // oups      ++it) // body 

we know oups line bad taste, here it's worse: @ each run of loop, create new iterator destroy means allocating , deallocating node vec's list of iterators... have underline cost of allocating/deallocating memory in tight loop ?

of course, for_each not encounter such issue, yet compelling case toward use of stl algorithms instead of hand-coded versions.