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?


Andrei

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?

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.

Another option is to use a "mutation" field that is checked every chance by the range.  If it changes, then the range is invalidated.

-Steve

On 2010-03-06 07:49:18 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> 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.

I think it'd be better to say "they are assumed to invalidate linked ranges". I know it's the same thing, but I think it's preferable to state the effect on the container's interface than the effects on the container's internals.

Side note: me thinks it'd be better to rename pushFront and pushBack to insertFront and insertBack. One reason for this is that "push" is often seen as the opposite of "pop" in container parlance while in our case it's not. Also, "insert" is a more natural opposite for "remove". And you're already using the "insert" term standalone anyway when it's not accompanied by "Front" or "Back".


> 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.

I think that's a good idea. The problem is that you don't necessarily know when writing an algorithm whether you are authorized or not to invalidate iterators. Wouldn't it be more useful if it worked with a wrapper instead?

	auto range = container[];
	playWithContainer(container.softwrap); // playWithContainer can't invalidate range
	playWithRange(range); // range is still valid here

The soft wrapper could be build automatically from compile time reflection by looking at which soft methods are available.


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Sat, 06 Mar 2010 08:19:36 -0500, Steven Schveighoffer <schveiguy@yahoo.com> 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.

>> Sounds good?
> 
> How can softRemove not affect iterating ranges?  What if the range is positioned on the element removed?
> 
> 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.
> 
> Another option is to use a "mutation" field that is checked every chance by the range.  If it changes, then the range is invalidated.
> 
> -Steve

Steve,

Wouldn't the soft things throw (or maybe just nudge) an exception if the container was in a state where the soft option was not appropriate.

That would be the other way round to what you said, The container would note when some range operation had a conflicting currency.

Steve

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.

> 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.


Andrei

On 2010-03-06 14:55:49 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> Steven Schveighoffer wrote:
>> 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.

What exactly is an "invalidated" iterator? Is an iterator that no longer points to the container still "valid"? Or is "valid" just another word for "memory safe"?

Wouldn't the notion of "detached" iterators/ranges be more useful?

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

Michel Fortin wrote:
> On 2010-03-06 14:55:49 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:
> 
>> Steven Schveighoffer wrote:
>>> 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.
> 
> What exactly is an "invalidated" iterator? Is an iterator that no longer points to the container still "valid"? Or is "valid" just another word for "memory safe"?
> 
> Wouldn't the notion of "detached" iterators/ranges be more useful?

Good question. In STL, invalidation roughly means undefined behavior if you use it. With GC in tow, the concept could be significantly milder. For example, reallocating an array would leave the old contents of the array sort of around, just obsoleted and also depleted of meaningful content if the data type has a destructor.

Andrei

On 06/03/2010 20:55, Andrei Alexandrescu wrote:
> Singly linked lists, doubly linked lists, various trees - three's a
> crowd. Most node-based containers support softInsert.

slightly OT
I am pretty sure that you have to implement IsRangeOfRange! and SubRange! for non linear collections. (if not already done)

Guess what I want to say is that I doubt that std.algo will fit in every case; and creating  a collection lib reduced to what is possible under the std.algo umbrella is (IMHO) a bad idea.

..and frankly said I wonder .. no offense.. why you are the (only) one who is creating and designing the collection library ?
finally :
from a pragmatic view > why create from scratch instead of reusing Stevens data-structures..
Bjoern

Steve Teale Wrote:

> >> Sounds good?
> > 
> > How can softRemove not affect iterating ranges?  What if the range is positioned on the element removed?
> > 
> > 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.
> > 
> > Another option is to use a "mutation" field that is checked every chance by the range.  If it changes, then the range is invalidated.
> > 
> > -Steve
> 
> Steve,
> 
> Wouldn't the soft things throw (or maybe just nudge) an exception if the container was in a state where the soft option was not appropriate.
> 
> That would be the other way round to what you said, The container would note when some range operation had a conflicting currency.

I think the point of soft functions is to not compile if they are not supported by the container.  Can you think of a way a container can have a soft option that is appropriate sometimes, but not others (thereby enabling a runtime option)?  I can't really see it, but maybe I'm missing it.

-Steve