Re: [boost] auto_vector - vector with auto_ptr semantics

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-02-04 09:43:21

----- Original Message -----
From: "Brey, Edward D" <EdwardDBrey_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, February 04, 2002 9:20 AM
Subject: RE: [boost] auto_vector - vector with auto_ptr semantics

> 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.

I agree with this in principle. An adaptive layer that hides the indirection
can be useful, though... or you can just use make_indirect_iterator() where
needed.

> 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.

You mean vice-versa?

> 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?

Yep and yep.

> Should new containers in boost allow for
> creating iterators from pointers?  I'm asking this first at a general
level.

It's a very interesting idea. You can't do it in all cases (for example, in
the adapted container which hides the indirection, or in most std::deque
implementations), but I think it would be useful.

> 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.

In theory, "fixing swap" should handle lots of that issue (you just use the
indirect interface). Of course "fixing swap" is a big topic ;-)

-Dave