On Sat, 06 Mar 2010 14:55:49 -0500, Andrei Alexandrescu
<[email protected]> wrote:
Steven Schveighoffer 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?
With GC, you can softRemove things without invalidating iterators.
If you define invalidation by "not pointing to unallocated memory,"
wouldn't normal remove (not soft remove) also result in valid memory being
pointed to? Why do we need a special soft version?
Even if this is what you mean, with allocators (which significantly speed
up container insert/removal), you may be pointing to a newly valid piece
of memory that may not be where you want.
I thought you meant by not invalidating that the range would iterate over
the elements it was originally scheduled to iterate over, sans the removed
element.
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.
Singly linked lists, doubly linked lists, various trees - three's a
crowd. Most node-based containers support softInsert.
Hashes may rehash on insert, invalidating any ranges (it's one of the
notes of dcollections' HashMap and HashSet). I guess it depends on if an
insert alters the ordering of the nodes. This is why I said sorted
containers which should be unaffected.
You have a point that this covers a lot of containers however, but I think
the usefulness of just having a softInsert (I think softRemove is not a
useful concept) is pretty limited. It limits you to
BTW, I think its a good idea to think about how to make this work, if we
can come up with something that covers a lot of ground, I think that's a
good thing. I thought of making ranges slower but more robust to
container changes in debug mode, does this sound useful? I.e. if you
compile in non-release mode, removing/adding an element may trigger the
range to do a O(n) check to validate itself.
-Steve
