RE: [boost] deletable iterators?

From: Trevor Perrin (tperrin_at_[hidden])
Date: 2001-07-24 14:25:36

(I tried to send this earlier; apologies if it repeats!)

>-----Original Message-----
>From: Michiel Salters
>To: 'boost_at_[hidden]'
>Sent: 7-23-01 8:36 AM
>Subject: RE: [boost] deletable iterators?
>
[SNIP]
>
>
>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.

I'm not sure the profit would justify the price here either.  To clarify
what the profit might be though: if you added an erase() member to the
iterators for lists and associative containers you could implement the
algorithms
  remove_erase()/remove_erase_if()
  unique_erase()
  set_intersection_erase()
  set_difference_erase() 

And then do things like
  //remove all occurences of 7 from list:
  remove_erase(l.begin(), l.end(), 7); 

  //remove all occurences of items in s2 from s1:
  set_difference_erase(s1.begin(), s1.end(), s2.begin(), s2.end());

Instead of
  erase(remove(l.begin, l.end(), 7), l.end());
  set_difference_erase(s1.begin(), s1.end(), s2.begin(), s2.end(),
back_inserter(s3));

Aside from being easier to read, the _erase() versions would be more
efficient: in the remove() case you wouldn't have to copy the removed
elements before erasing them, and in the set_difference() case you wouldn't
have to copy the result elements.

As for vector, deque, and string, I think their iterators are usually
implemented without enough state for us to provide erase() functions on
them, and erasing elements from them one at a time would be inefficient
anyways.  So you could provide an erasable_iterator class like below, that
one constructs with a container and a nonerasable iterator to produce an
erasable one.  This erasable_iterator might have a one-arg erase() function
for erasing a sequence, since you'd want to erase things a bunch at a time
instead of incurring a re-allocation/copying cost each time.  Then the
algorithms above could be specialized to either erase elements one at a time
for lists and associate containers, or first swap them all and then erase in
one fell swoop for the other containers.

Anyways, the gain is some efficiency and a simpler syntax for certain
operations, the cost is complexity and more concepts to keep track of.  I'm
not sure if it's worth it, I'm curious what people with more STL experience
think.  I'll write the above algorithms to work with the erasable_iterator
class if anyone wants to try them out.  Thanks for the feedback,

Trevor

template<class T>
class erasable_iterator : public T::iterator
{
public:
  erasable_iterator(T& t, T::iterator i):
    T::iterator(i), m_t(t){}
  erasable_iterator<T> erase() {
    return erasable_iterator<T>(m_t, m_t.erase(*this));}
  erasable_iterator<T> erase(T::iterator i) {
    return erasable_iterator<T>(m_t, m_t.erase(*this, i);}
private:
  T& m_t;
};