Steven Schveighoffer wrote:
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?
Well consider an array of File objects, which are reference counted. I'd
want the resizing of an array to not increment the reference count of
the files. That means that resizing leaves the old array without
meaningful content by calling clear() against the remaining files.
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.
For remove that should be the case, but probably not for insert.
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
Iterator invalidation has been a notion thoroughly explored by the STL
and a commonly-mentioned liability of STL iterators. People find it very
jarring that syntactically identical interfaces have distinct effects on
iterators, it's a dependency very difficult to track. I'm glad that that
experience has already been accumulated and that we can build upon it.
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.
I think debug vs. release should not affect complexity.
Andrei
