Boost logo

Boost :

From: Jason House (jhouse_at_[hidden])
Date: 2003-04-28 09:58:54


I wrote the e-mail below thinking the circular buffers discussion was on
the developers list... (This e-mail is going both to users and
developers)

Jason House wrote:
>
> I had need of an interesting data structure in the past...
> Just to give it a name, a circular multi-map...
> (I believe my implementation called it a timed_map)
>
> The circular nature was not a fixed count, but actually based off an
> associated timestamp with each item stored in the container. When the
> newest item coming in was sufficiently in advance of the oldest, the
> oldest item(s) would be removed...
>
> Just to put this into perspective, the application was calculating
> packet completion rate... Key/Value pair for each packet is a
> relatively straight-forward implementation... The problem was that the
> completion rate was very low (70%?), and on 6 gigabytes of data, a
> problem quickly arises... I needed fast lookup by packet key, and a
> reverse iterator by timestamp...
>
> A multi-map with 2 independent key fields would be perfect for this
> application... My implementation was sub-optimal in that I placed the
> timestamp in the value field (part of a pair) and would iterate over all
> data items when I wanted to clean up...
>
> Just trying to add fuel for thought on circular buffer
> implementation... I guess the 2 points in here are: 1. some kind of
> more arbitrary expiration mechanism than just count 2. circular
> structures other than just queues
>
> Joe Mariadassou wrote:
> >
> > Thank You. I'll use that as a starting point to make my own.
> > Joe
> >
> > -----Original Message-----
> > From: Tom Matelich [mailto:tmatelich_at_[hidden]]
> > Sent: Friday, April 25, 2003 1:01 AM
> > To: 'Boost-Users_at_[hidden]'
> > Subject: RE: [Boost-Users] Circular Buffer
> >
> > I've seen several implementations of things like this come up on the
> > boost
> > mailing list in the past. My impression is a lot of people gave up when
> > confronted with all the different options that would have to be
> > considered
> > to make it through a Boost review. I did see cyclic_buffer.zip in the
> > Files
> > section at the old yahoo group site (
> > http://groups.yahoo.com/group/boost/files/ ).
> >
> >
> > Info: <http://www.boost.org>
> > Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
> > Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
> >
> >
> > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
> ------------------------ Yahoo! Groups Sponsor ---------------------~-->
> Get 128 Bit SSL Encryption!
> http://us.click.yahoo.com/xaxhjB/hdqFAA/bW3JAA/EbFolB/TM
> ---------------------------------------------------------------------~->
>
> Info: <http://www.boost.org>
> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
> Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk