On Sat, 06 Mar 2010 08:19:36 -0500, Steven Schveighoffer
<[email protected]> wrote:
Andrei Alexandrescu Wrote:
In the STL world, writing container-independent code is generally
shunned (see e.g.
http://www.informit.com/content/images/0201749629/items/item2-2.pdf).
One problem is a very small intersection between the functionalities
offered by the various STL containers, and the conceptual organization
that is weaker than that of iterators.
A worse problem is iterator invalidation rules, something that we'll
need to address too. I'm thinking that the best defense is a strong
offense, and I plan to define the following naming convention:
Methods such as insert, remove, pushFront, pushBack, removeFront,
removeBack, are assumed to affect the container's topology and must be
handled in user code as such.
In addition to those, a container may also define functions named after
the above by adding a "soft" prefix (e.g. softInsert, softRemove...)
that are guaranteed to not affect the ranges currently iterating the
container.
Generic code that needs specific iterator (non-)invalidation rules can
use softXxx methods, in confidence that containers not supporting it
will be ruled out during compilations.
Sounds good?
How can softRemove not affect iterating ranges? What if the range is
positioned on the element removed?
It always affects ranges in so far as the range and container are
inconsistent, but that is a problem of softInsert as well. Removing an
element from an array doesn't invalidate the underlying range, since the
memory is still there. And so long as you're not trying to use free lists,
linked-lists, trees, etc. can be written so that the ranges never enter an
invalid state. If they happen to be pointing at the removed node, they
just end up stopping early.
The only two containers that would support softInsert would be linked
list and sorted map/set. Anything else might completely screw up the
iteration. I don't see a lot of "generic" use for it.
There's all the containers based upon linked-lists, etc like hashes,
stacks, queues and dequeues.
Another option is to use a "mutation" field that is checked every chance
by the range. If it changes, then the range is invalidated.
The mutation field would have to be a version number to support multiple
ranges, and given experience with lock-free algorithms which use a 'tag'
in a similar manner, this concept is bug prone and should not be relied
upon. It would be better to 'lock' the node or container to topology
changes, though this does slow things down and has no conflict resolution:
removing a locked node would have to throw an exception.
