468,512 Members | 1,426 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

FIFO buffer with fast lookup

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.
Dec 10 '07 #1
2 7394
On Dec 10, 4:16 am, Spoon <root@localhostwrote:
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.
Dec 10 '07 #2
Spoon wrote:
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
Dec 10 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

11 posts views Thread by Ville Vainio | last post: by
2 posts views Thread by Michele Moccia | last post: by
8 posts views Thread by Jack | last post: by
5 posts views Thread by Dinsdale | last post: by
28 posts views Thread by bwaichu | last post: by
5 posts views Thread by akenato | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.