Re: [boost] Re: Container Adaptors

From: David White (dave_at_[hidden])
Date: 2002-10-29 04:49:04

hi there,

I just thought I'd interject here with a real world example that I've
come across:

I was writing a program that works with stock market data, and needed to
store a list of all buy requests and sell requests - known as 'bids' and
'asks'. The bids and asks are stored in vectors, with the most
attractive bid/ask being known as the 'first' bid/ask, and so is
naturally stored at index 0 of the vector. Bids and asks can be
inserted, deleted, or modified dynamically, and this happens very
frequently for high-volume equities.

It was found that this component of the program was running rather
slowly, and profiling it I found it was related to vector operations. I
did a study and found that 90+% of activity on the bids and asks happens
around the top order. So, I needed to store the first bid or ask at the
back of their vectors.

Rather than change lots of code in lots of places, I wrote a simple
container 'adaptor', which I called reverse_container. It would operate
on sequential containers, and make the back the front, and the front the
back.

This solved the problem immediately, and with minimal effort. I don't
think a solution using reverse_iterator or any other kind of immutable
views would have worked, since clearly the container must be mutated.

Just something to consider.

Cheers,

-David.

On Tue, 2002-10-29 at 08:00, David A. Greene wrote:
> Roland Richter wrote:
> >
> > + Yes, it might be valueable to have a container adaptor or "views"
> >   library (I like the later term better) which follows closely the
> >   paths of the iterator adaptor library.
> 
> That's the general idea, yes.
> 
> > + If given some further thought, such an container adaptor library
> >   appears as a straight-forward extension to the iterator adaptor
> >   library. As much as the iterator adaptor lib is designed to
> >   make "smart iterators" out of dumb one's, a container adaptor
> >   library would wrap STL containers and add functionality to them.
> 
> Precisely.  It's not really an extension of iterator adaptor, but
> rather it follows the same model.
> 
> > + Another way to think of views is that these mimic STL containers
> >   (i.e., provide a common subset of methods, such as begin(), end(),
> >    size(), etc.), but do return adapted iterators instead of ordinary ones.
> >   Simply put: filter_view::iterator = filter_iterator_type etc.
> 
> "View" sounds a little too static to me.  The idea I have is not to
> take existing data and provide different perspective on it.  Rather
> it is to take a entity that organizes data and provide a different
> interface to it, which may result in a different organization of the
> data.  Views may be a subset of this goal.
> 
> > + I do not know your exact requirements; however, I doubt that views
> >   are what you really need to design a "fixed-sized vector", since,
> >   as Martin Weiser already pointed out, such container adaptors provide
> >   "immutable 'views' onto existing data".
> 
> Right, that was exactly my comment.
> 
> >  > We raised this topic some time ago, but got only a limited response. Not
> >  > much discussion evolved.
> > 
> > I guess the reason for this is that STL supports a style of programming
> > where iterators are used in preference over containers. Thus, to adapt
> > iterators seems to be more important than to adapt containers.
> 
> Unless the container is modeling some real-world item.  As I've
> mentioned before, I've found it useful in simulation.
> 
> > As a final point, let me add that I hacked an own version of a views
> > library (completely relying on Boost.IteratorAdapor, which makes things
> > much easier compared to VTL) some time ago (not guaranteed to even
> > compile with any compiler different than gcc).
> > 
> > If there actually is some interest in it [is there?], I'd be happy
> > to contribute it to the Boost community.
> 
> How does it differ from the VTL?
> 
>                       -Dave
> 
> -- 
> 
> "Some little people have music in them, but Fats, he was all music,
>   and you know how big he was."  --  James P. Johnson
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost