RE: [boost] deletable iterators?

From: Michiel Salters (Michiel.Salters_at_[hidden])
Date: 2001-07-23 10:36:02

> -----Original Message-----
> From: Trevor Perrin [mailto:tperrin_at_[hidden]]
> Sent: Sunday, July 15, 2001 4:58 AM
> To: 'boost_at_[hidden]'
> Subject: [boost] deletable iterators?
> 
> 
> a question that's been bugging me:  Since iterators are 
> "like" pointers, it
> seems you should be able to delete them:
> 
> delete somelist.begin(); //remove first element from somelist

Well, deleting pointers is ugly & should be hidden. I'm glad we don't
have that ugliness everywhere where iterators are used.
 
> Then you could have stl algorithms like delete_if() that 
> actually removed items, instead of the (seems to me
> hokey) partitioning behavior of unique() or remove().
> However it's not possible to override operator delete like
> that, unless there's some trick I don't know about, so we could
> add an erase() member function to them instead.  

Good luck adding an erase member to int*. It is an iterator, e.g.
for the int[10] container/array. BTW, how do you delete the 5th
element of an int[10] ?

>Also not all containers' iterators would be naturally eraseable
> but you could provide an  eraseable_iterator class:
[SNIP]
Actually, the only simple container which can easily support
erasure is std::list ( as well as all associate containers ).

> And specialize appropriately so that, for example, a 
> vector<T>::iterator could be converted into a deletable form. 

That's not a good idea IMO, providing a simple interface to an
O(N) algorithm when more appropriate container offers a O(1)
algorithm.

> Anyways, I'm sure this has been ruminated over before. 
> Why don't we have deletable  iterators?  Are they
> just a stupid idea?  Is there any reasonable way of providing 
> them that would be worthwhile in boost or the stl?

The basic idea of the STL is that its algorithms works on
iterator ranges, not containers. Deletable iterators cause
strong ties between them and the underlying containers.

However, if you can come up with a generalized concept of
algorithms that work on containers via a common "
deletable iterators" interface, I'd be interested. That is, can
you find a number of fundamentally different algorithms which
work on a number of fundamentally different containers via
deletable iterators ? Paying the price for abstraction is only
justified by the profit of generalization.

Regards,
Michiel Salters