Re: template<typename C> C::reverse_iterator erase(C&, C::reverse_iterator)

From: Paul Hollingsworth (boost_at_[hidden])
Date: 2001-07-16 22:45:31

Just a quick follow up to anyone who is interested - I just realised 
a much simpler way to do erase for reverse_iterators:

For std::map, std::set etc. (where the erase method does not return a 
value but also for which iterators that weren't deleted stay valid), 
the correct code is:

// Use for std::set, std::map, containers whose erase method doesn't
// return a new iterator. Cannot be used for containers whose
// erase method invalidates other iterators (e.g. std::vector)
template<typename C>
C::reverse_iterator erase(C& c, const C::reverse_iterator& rpos)
{
    c.erase(--(rpos.base()));
    return rpos;
}

For containers where the erase method returns the new value, the 
correct code is:

template<typename C>
C::reverse_iterator erase(C& c, const C::reverse_iterator& rpos)
{
    return C::reverse_iterator(c.erase(--(rpos.base())));
}

Now all that is needed is a way to select the correct one at compile 
time based on the container type. Ideally, it would always pick the 
latter version if the return type of erase is the new iterator, as 
that is guaranteed to be correct. Otherwise it could pick the former 
one, assuming that by default that unrelated iterators stay valid 
after the erase operation.

Any comments are appreciated (or if you see a mistake - please point 
it out thanks! :-) ),

Paul Hollingsworth
http://PaulHollingsworth.com

--- In boost_at_y..., "Paul Hollingsworth" <boost_at_P...> wrote:
> Hi All,
> IMO, the current state of affairs for erasing elements from a 
> container is somewhat unsatisfactory for average programmers.
> 
> For some of the containers (std::set, std::map), erase is a "void" 
> method - in which case the correct action is to keep a copy of the 
> increment iterator beforehand, like this:
> 
> c.erase(it++)
> 
> But for other containers (e.g. std::vector), the correct action is 
to 
> take the return value of erase:
> 
> it = c.erase(it);
> 
> It is a mistake, for example, to use the post-increment form with a 
> std::vector.
> 
> Also, there is no equivalent erase option for reverse iterators - 
> something that I needed while working on some code to clean up 
> entries from an in-memory cache (implemented as a std::map).
> 
> Anyway, it seems that a uniform interface for erasing elements from 
> containers would be nice. Ideally, it would work so that you could 
> _always_ write:
> 
> it = boost::erase(c, it);
> 
> in any sort of loop and have everything work properly, irrespective 
> of which type of container or what type of iterator it is.
> 
> I started writing an erase method for reverse iterators - it looks 
> like this right now:
> 
> // This operation is only valid for containers whose
> // erase method does not return a value (e.g. std::set, std::map - 
NOT
> // std::vector).
> // Returns: iterator pointing to next valid element, or c.rend()
> template<typename C>
> C::reverse_iterator erase(C& c, const C::reverse_iterator& rpos)
> {
>  	C::iterator pos = rpos.base(); --pos; // pos = rpos.base() - 
> 1;
> 	c.erase(pos++);
> 	return C::reverse_iterator(pos);
> }
> 
> The above solution immediately suffers from the flaw that there is 
> nothing to stop you using it with a std::vector, for example, which 
> would be the wrong course. However, I imagine that some template 
> tricks could be used to make sure that it used the correct form to 
> erase the element based on the return signature of erase (or by 
> partial specialisation based on common container types perhaps?).
> 
> Anyway, it would have solved me a considerable amount of time if I 
> had been able to pluck this from boost instead.
> 
> I thought I'd post this to see if anyone had any ideas about how to 
> achieve this... or felt like adding to it ;-)
> 
> Paul Hollingsworth
> http://PaulHollingsworth.com