473,231 Members | 1,632 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,231 software developers and data experts.

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 7780
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: Ville Vainio | last post by:
I need a dict (well, it would be optimal anyway) class that stores the keys as strings without coercing the case to upper or lower, but still provides fast lookup (i.e. uses hash table). >> d...
2
by: Michele Moccia | last post by:
How can I implement a "time critical" fifo in c++ ? I just have to manage sequences of raw bytes, no user defined types. An std::queue<unsigned char> or std::deque<unsigned char> seems to be slow....
8
by: Jack | last post by:
I want to implement a fixed-size FIFO queue for characters. I only want to use array not linked list. For example, const int N = 10; char c_array; The question is when the queue is full,...
5
by: Dinsdale | last post by:
I have an application that recieves text data via external input (i.e. serial) and displays it on the screen (we use carraige return as a delimiter). At this point I use a regular old text box and...
28
by: bwaichu | last post by:
Is it generally better to set-up a buffer (fixed sized array) and read and write to that buffer even if it is larger than what is being written to it? Or is it better to allocate memory and...
3
by: Polatrite | last post by:
I'm working on a project currently that needs to have a fast FIFO text box that displays output from a serial device. It also needs to have fast refresh rate as the data can stream in at about 50...
5
by: akenato | last post by:
Hi for me this is th first time that I use c++. I have to do this exercise. Somebody can help me? Thanx. Implement a FIFO-queue ( first in, first out ) as a ring buffer. Use a static array as the...
36
by: James Harris | last post by:
Initial issue: read in an arbitrary-length piece of text. Perceived issue: handle variable-length data The code below is a suggestion for implementing a variable length buffer that could be used...
40
by: sazd1 | last post by:
Hi Student2 I am working on similar kind of thing for stock calculation but could not find any solution to my problem even after putting my problem to different forums. I saw your post that you...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.