FIFO buffer with fast lookup

[Spoon]

Hello,

I'm wondering whether the STL defines a data structure with
the following features:

o provides push_front() and pop_back() (like std::list) to
implement a FIFO buffer.

o allows fast lookup (like std::map) so I can easily search
for a specific item in the buffer.

I suppose I could always use std::list and write my own search
function, but I'm asking in case I've overlooked something.

(The keys would be int, and the values would be character arrays.)

Regards.

 

[Vladislav.Lazarenko]

Hello,

I'm wondering whether the STL defines a data structure with
the following features:

o provides push_front() and pop_back() (like std::list) to
implement a FIFO buffer.

Look at std::queue (http://www.sgi.com/tech/stl/queue.html),
std::deque (http://www.sgi.com/tech/stl/Deque.html).

o allows fast lookup (like std::map) so I can easily search
for a specific item in the buffer.

I suppose I could always use std::list and write my own search
function, but I'm asking in case I've overlooked something.

(The keys would be int, and the values would be character arrays.)

Regards.

Mixing FIFO and searching is rather strange. Standard STL containers
supports generic search algorithms, you can use on of them or write
your own. However, you may also use multiple containers. For example,
store your data in std::queue and provide some std::set or
std::hash_set for fast lookup.

Vlady.

 

[Kai-Uwe Bux]

I'm wondering whether the STL defines a data structure with
the following features:

o provides push_front() and pop_back() (like std::list) to
implement a FIFO buffer.

o allows fast lookup (like std::map) so I can easily search
for a specific item in the buffer.

I suppose I could always use std::list and write my own search
function, but I'm asking in case I've overlooked something.

You could use a pair of containers, something like:

class fifo_map {

typedef std::list< item_type > item_fifo;
typedef std::map< key_type, item_fifo::iterator > lookup_table;

item_fifo the_fifo;
lookup_table the_table;

public:

void push_front ( key_type const & key, item_type const & item ) {
the_table[ key ] = the_fifo.insert( the_fifo.end(), item );
}

};

Note that iterators into a list are not invalidated by adding and removing
other elements.

If the map from keys to items is not unique, you would have to use a
multimap. Of course, hash-maps would also work.


Best

Kai-Uwe Bux