Joel C. Salomon wrote:
> On 3/6/2010 5:18 PM, Andrei Alexandrescu wrote:
>> 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.
> 
> So it’s still a bug to use an invalidated iterator/range, and probably
> still has unusual (if no longer undefined) effects if you do follow it,
> but it (probably) won’t cause memory corruption.  Is that correct?

I'd think so. In SafeD, clearly there's no memory corruption so throwing or iterating over removed elements would be valid choices. In non-safe mode, the user should expect undefined behavior.

Andrei

On Mon, 08 Mar 2010 12:53:40 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Steven Schveighoffer wrote:
>> On Sun, 07 Mar 2010 12:43:09 -0500, Robert Jacques <sandford@jhu.edu> wrote:
>>
>>> On Sun, 07 Mar 2010 08:23:03 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>> What is the advantage?  Why would an algorithm require soft functions?  What is an example of such an algorithm?
>>>
>>> Something that uses toUpperCase or toLowerCase, for example.
>>  I guess I won't get a real example.  I'm not sure it matters.  When Andrei starts implementing the soft methods, either they will be a huge win or obviously useless.  If I were a betting man, I'd bet on the latter, but I'm not really good at betting, and Andrei's ideas are usually good :)
>
> The way people usually take advantage of non-invalidating container primitives is altering the container during an iteration. The canonical way to remove while iterating an erase-non-invalidating container (e.g. map) is this:
>
> typedef ... Container;
> Container c;
> for (Container::iterator i = c.begin(); i != c.end(); )
> {
>      if (should_delete_this_guy)
>          c.remove(i++);
>      else
>          ++i;
> }
>
> The canonical way to remove while iterating an erase-invalidating container (e.g. vector) is:
>
> typedef ... Container;
> Container c;
> for (Container::iterator i = c.begin(); i != c.end(); )
> {
>      if (should_delete_this_guy)
>          i = c.remove(i);
>      else
>          ++i;
> }

Hm... this seems to be a different problem than I originally was thinking about.  So in essence, you want a set of "safe" functions that will not adversely affect a range you are using to iterate with?

BTW, I solved this problem (removing while iterating) in a much better/simpler way in dcollections.

-Steve

Steven Schveighoffer wrote:
> On Mon, 08 Mar 2010 12:53:40 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>> On Sun, 07 Mar 2010 12:43:09 -0500, Robert Jacques <sandford@jhu.edu> wrote:
>>>
>>>> On Sun, 07 Mar 2010 08:23:03 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>>> What is the advantage?  Why would an algorithm require soft functions?  What is an example of such an algorithm?
>>>>
>>>> Something that uses toUpperCase or toLowerCase, for example.
>>>  I guess I won't get a real example.  I'm not sure it matters.  When Andrei starts implementing the soft methods, either they will be a huge win or obviously useless.  If I were a betting man, I'd bet on the latter, but I'm not really good at betting, and Andrei's ideas are usually good :)
>>
>> The way people usually take advantage of non-invalidating container primitives is altering the container during an iteration. The canonical way to remove while iterating an erase-non-invalidating container (e.g. map) is this:
>>
>> typedef ... Container;
>> Container c;
>> for (Container::iterator i = c.begin(); i != c.end(); )
>> {
>>      if (should_delete_this_guy)
>>          c.remove(i++);
>>      else
>>          ++i;
>> }
>>
>> The canonical way to remove while iterating an erase-invalidating container (e.g. vector) is:
>>
>> typedef ... Container;
>> Container c;
>> for (Container::iterator i = c.begin(); i != c.end(); )
>> {
>>      if (should_delete_this_guy)
>>          i = c.remove(i);
>>      else
>>          ++i;
>> }
> 
> Hm... this seems to be a different problem than I originally was thinking about.  So in essence, you want a set of "safe" functions that will not adversely affect a range you are using to iterate with?

That's the idea. Any documentation of STL containers specifies whether iterators are invalidated or not by a primitive. The plan is to simply define a nomenclature (i.e. "softXxx") for primitives that don't invalidate iterators. That moves the documentation into the name of the function.

> BTW, I solved this problem (removing while iterating) in a much better/simpler way in dcollections.

Do tell!


Andrei

On 2010-03-08 13:01:32 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> softXxx functions that remove data should guarantee that existing ranges not including the removed elements will continue to operate on the range without seeing the removed elements. There is no guarantee that soft removal offers for ranges spanning the removed elements. (I'm unclear on this last topic.)

That won't work for a vector as ranges that are further then the removed element need adjustment too.

Just an idea, perhaps remove and other mutator functions for the container could take a list of range to update at the same time they do the operation. This way you don't even need a soft function, if remove can't accept other ranges then it won't take other ranges as an argument. For instance:

	class Container {
		void remove(Range toRemove, Range[] needAdjustment);
	}

	Container x = new Conatiner();
	auto a = x[];
	auto b = x[4..6];
	auto c = x[2..4];
	x.remove(c, [a, b]); // remove elements from c, adjust ranges a and b.

	OtherContainer y = new OtherContainer();
	auto d = y[];
	auto e = y[2..4];
	y.remove(e, [d]); // error, container is unable to adjust other ranges.


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

On Mon, 08 Mar 2010 13:21:14 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Steven Schveighoffer wrote:
>>  Hm... this seems to be a different problem than I originally was thinking about.  So in essence, you want a set of "safe" functions that will not adversely affect a range you are using to iterate with?
>
> That's the idea. Any documentation of STL containers specifies whether iterators are invalidated or not by a primitive. The plan is to simply define a nomenclature (i.e. "softXxx") for primitives that don't invalidate iterators. That moves the documentation into the name of the function.

What I meant was, your example only focuses on the iterator being advanced in the loop.  Another iterator might be invalidated that is not used in the remove function.  Was that the intent?

>> BTW, I solved this problem (removing while iterating) in a much better/simpler way in dcollections.
>
> Do tell!

I created a method purge, which is used as an opApply in a foreach loop like so:

foreach(ref erase, v; &container.purge)
{
   erase = should_delete_this_guy;
}

One nifty thing about this, purging an entire collection is an O(n) up to O(nlgn) operation, whereas purging a vector as you wrote is an O(n*n) operation.

I found that one of the biggest reasons I liked about STL's containers over others that I've used is the ability to remove elements from the container while iterating.  Java allows this also, but no foreach, and it doesn't make optimizations, since the iterator is in charge of removal, not the container itself.

-Steve

Steven Schveighoffer wrote:
> On Mon, 08 Mar 2010 13:21:14 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>>  Hm... this seems to be a different problem than I originally was thinking about.  So in essence, you want a set of "safe" functions that will not adversely affect a range you are using to iterate with?
>>
>> That's the idea. Any documentation of STL containers specifies whether iterators are invalidated or not by a primitive. The plan is to simply define a nomenclature (i.e. "softXxx") for primitives that don't invalidate iterators. That moves the documentation into the name of the function.
> 
> What I meant was, your example only focuses on the iterator being advanced in the loop.  Another iterator might be invalidated that is not used in the remove function.  Was that the intent?

The examples were given just to illustrate common cases when invalidation is relevant. As I mentioned, interesting cases occur when long-distance effects occur. The Observer pattern is a perfect example.

>>> BTW, I solved this problem (removing while iterating) in a much better/simpler way in dcollections.
>>
>> Do tell!
> 
> I created a method purge, which is used as an opApply in a foreach loop like so:
> 
> foreach(ref erase, v; &container.purge)
> {
>    erase = should_delete_this_guy;
> }

Very nifty indeed!

> One nifty thing about this, purging an entire collection is an O(n) up to O(nlgn) operation, whereas purging a vector as you wrote is an O(n*n) operation.

Good point. The loop with erase is good if you have to occasionally erase some element; for bulk conditional erasures the canonical STL approach is to use remove() followed by erase():

http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove

> I found that one of the biggest reasons I liked about STL's containers over others that I've used is the ability to remove elements from the container while iterating.  Java allows this also, but no foreach, and it doesn't make optimizations, since the iterator is in charge of removal, not the container itself.

Yah, the tail that removes the dog. That's one of the reasons I think Java's containers are missing more points than one. In fact the more I think of Java containers, the more reasons I find to dislike them. To me they're more of a point of negative potential in the design space that needs to be carefully navigated away from.


Andrei