Container insertion and removal

[Andrei Alexandrescu]

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;
}

I know, subtle :o/. Of course, things can get quickly more interesting 
when calling functions from within loops that may affect the container 
(think the Observer pattern).


Andrei