Circular Buffers + Multi-Maps = circular maps?

From: Jason House (yg-boost-users_at_[hidden])
Date: 2003-04-28 09:14:33

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/