RE: [boost] auto_vector - vector with auto_ptr semantics

From: Brey, Edward D (EdwardDBrey_at_[hidden])
Date: 2002-02-04 09:20:40

I think that an auto_vector class would be a great addition to boost.
Coincidentally, I just made an auto_vector for myself just a week ago.  It
wasn't nearly complete enough (and in some ways possibly had too much) for
Boost, but rather just for my current project's needs.  In any case, the
concept is definitely useful.

I can share a bit of my experience vis a vis George's suggestion regarding
returning references.  Before I made my auto_vector, I had made an earlier
incantation where the iterators performed the dereference for you.  That
worked out fine until I needed to copy the pointers to another container
(the destination container just held pointers, but didn't own any objects).
The problem was that I couldn't go backwards from a reference/pointer to an
iterator.  At this point I decided that there wasn't enough value in hiding
the indirection level to be worth the trouble it causes.

This predicament points out a general lacking in STL that I'd like to hear
other's opinions of.  That is the concept of transforming an iterator to a
pointer.  There have been multiple times when I've had a reference to an
object in a container (usually a map) where I've had to re-look-up the
object using the containers searching mechanism, even though I started with
a pointer that was just essentially the iterator anyway (either exactly the
same or offset by a few bytes).  Of course, one tries to avoid this by
passing around iterators instead of pointers/references, but I've found that
there are two situations where it isn't practical:

1. Module A deals with the elements generically with no knowledge of the
containers, and is fed by module B and C, each which have their own
distinctly-typed containers of the elements.  When B or C get an element
back from A, each knows by contract that it came from its own container and
so the pointer is as good as an iterator, if only it could be converted.
Actually, this scenarios happens with just A and B (no C), too, sometimes
when it is desirable to encapsulate A to the point where it does not know
B's container type.

2. There is a circular reference.  Forward declarations work for pointers,
but not iterators.

Have others encountered this?  Should new containers in boost allow for
creating iterators from pointers?  I'm asking this first at a general level.
Secondly would be consideration for auto_vector, which might prove to be a
special case.

Back to auto_vector: one other item I noticed from experience.  One use I
had for auto_vector in cases where a small number of polymorphic elements
were infrequently added/removed from container, with full traversal, but no
lookup.  In this case, to do the removal, a simple linear search was good,
with a hint from the program indicating whether to start looking from the
beginning or the end, for a constant-time speedup.  A problem with
auto_vector is that mutating algorithms tend not to work with it.  So I
found it better to build my own algorithms into the class, in this case
remove_first and remove_last.  While this seems to go against the original
spirit of STL, it proved to be quite practical.  I will be interesting to
see whether it can be practical in a generic library environment.

 -----Original Message-----
From: 	George A. Heintzelman [mailto:georgeh_at_[hidden]] 
Sent:	Sunday, 03 February 2002 3:23 PM
To:	boost_at_[hidden]
Subject:	Re: [boost] auto_vector - vector with auto_ptr semantics

> From: "Rainer Deyke" <root_at_[hidden]>
> > It sounds like your 'auto_vector' avoids some of the problems of a
> > container of auto_ptrs by conceptually being a container of vanilla
> > pointers.  Unfortunately this has its own set of problems.  Consider:
> > 
> >   auto_vector<Cat> cats;
> >   cats.push_back(new Cat);
> >   cats[0] = new Cat; // Error: memory leak
> 
> With my current version, yes this is unfortunately true.  I know 
> enough not to do that, and so it has never been a problem for me.
> I regard auto_vector as being convenient and not full proof.  
> 
> If more safety is required, I guess we could look at making 
> operator[], front, and back return values rather than references.
> But it would still cause a leak if you did a 
> 
>   *cats.begin() = new Cat;

How about having the interface always dealing with Cats, not pointers 
to Cats? Then the above is a syntax error, as *cats.begin() will be a 
reference to a Cat, not a reference to a pointer to a Cat. You would be 
safe against anything short of:

*cats.begin() = *(new Cat); 

and that I decline to protect programmers from their own stupidity 
for...

My preference is to make the functions which look like vector's act 
like vector's, so all of push_back, etc, pass by value (possibly 
slicing). However, you should supply some other member functions which 
'adopt' a passed-in pointer and place it in an appropriate place, 
avoiding the copy ctor:

cats.adopt_back(new Cat); 

The only issue I see with this interface is that the standard 
push_back, insert, etc, won't behave polymorphically, and this 
container supports polymorphic containment just fine. But since none of 
those functions in STL containers behave that way, this is IMHO not a 
big flaw, as long as functionality is supplied to allow the polymorphic 
behavior when someone desires it. A second potential issue might be that

cats[0] = Calico(...);

would slice, perhaps non-intuitively. Again, I think anyone working 
with polymorphism needs to be aware of slicing possibilities anyway, so 
this is also not a big flaw.

An alternative safe interface would be to have all of the various 
insertion statements (and operator[], which returns a non-const 
reference to an auto_ptr in this scheme) take an auto_ptr instead of a 
straight pointer. This makes the allowed polymorphism a little more 
obvious, and means that accidental adoptions/leaks won't happen. The 
problem as I see it is that begin() now has the semantics of a pointer 
to a pointer to the contained object, which is completely at odds with 
the STL; trying to use algorithms looping over Cats requires 
boost::indirect_iterator when IMHO this should be contained in the 
container's iterators. So while I would probably use this latter 
interface, I prefer the other.

> Or I guess we could go the whole hog and return some sort of 
> proxy that deleted the current pointer on assignment.

> But I don't know if the added safety of either is worth the 
> trouble.  What do others think?  Keep it simple or make it safe?

I think there isn't any proxy necessary in the scheme I would propose. 
The only necessity is to write new iterator types. For that, you can 
use boost::indirect_iterator, though in this case and for orthogonality 
I would rather see it written explicitly. You could I suppose write a 
proxy which prevented (at least simple-minded) slicing possibilities. 
That might be neat, and probably wouldn't be too hard to do, but as I 
say I don't think it is necessary for a useful class, as long as 
functions are provided which do not slice.

George Heintzelman
georgeh_at_[hidden]