Re: Circular Buffers + Multi-Maps = circular maps?

From: Jason House (yg-boost-users_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/
> 
> 
> 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/