Container insertion and removal

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> On Mon, 08 Mar 2010 12:53:40 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>> On Sun, 07 Mar 2010 12:43:09 -0500, Robert Jacques <sandford at jhu.edu> 
>>> wrote:
>>>
>>>> On Sun, 07 Mar 2010 08:23:03 -0500, Steven Schveighoffer 
>>>> <schveiguy at 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