Which Stl Container Should I Use for a Fifo

Which STL container should I use for a FIFO?

Since there are a myriad of answers, you might be confused, but to summarize:

Use a std::queue. The reason for this is simple: it is a FIFO structure. You want FIFO, you use a std::queue.

It makes your intent clear to anybody else, and even yourself. A std::list or std::deque does not. A list can insert and remove anywhere, which is not what a FIFO structure is suppose to do, and a deque can add and remove from either end, which is also something a FIFO structure cannot do.

This is why you should use a queue.

Now, you asked about performance. Firstly, always remember this important rule of thumb: Good code first, performance last.

The reason for this is simple: people who strive for performance before cleanliness and elegance almost always finish last. Their code becomes a slop of mush, because they've abandoned all that is good in order to really get nothing out of it.

By writing good, readable code first, most of you performance problems will solve themselves. And if later you find your performance is lacking, it's now easy to add a profiler to your nice, clean code, and find out where the problem is.

That all said, std::queue is only an adapter. It provides the safe interface, but uses a different container on the inside. You can choose this underlying container, and this allows a good deal of flexibility.

So, which underlying container should you use? We know that std::list and std::deque both provide the necessary functions (push_back(), pop_front(), and front()), so how do we decide?

First, understand that allocating (and deallocating) memory is not a quick thing to do, generally, because it involves going out to the OS and asking it to do something. A list has to allocate memory every single time something is added, and deallocate it when it goes away.

A deque, on the other hand, allocates in chunks. It will allocate less often than a list. Think of it as a list, but each memory chunk can hold multiple nodes. (Of course, I'd suggest that you really learn how it works.)

So, with that alone a deque should perform better, because it doesn't deal with memory as often. Mixed with the fact you're handling data of constant size, it probably won't have to allocate after the first pass through the data, whereas a list will be constantly allocating and deallocating.

A second thing to understand is cache performance. Going out to RAM is slow, so when the CPU really needs to, it makes the best out of this time by taking a chunk of memory back with it, into cache. Because a deque allocates in memory chunks, it's likely that accessing an element in this container will cause the CPU to bring back the rest of the container as well. Now any further accesses to the deque will be speedy, because the data is in cache.

This is unlike a list, where the data is allocated one at a time. This means that data could be spread out all over the place in memory, and cache performance will be bad.

So, considering that, a deque should be a better choice. This is why it is the default container when using a queue. That all said, this is still only a (very) educated guess: you'll have to profile this code, using a deque in one test and list in the other to really know for certain.

But remember: get the code working with a clean interface, then worry about performance.

John raises the concern that wrapping a list or deque will cause a performance decrease. Once again, he nor I can say for certain without profiling it ourselves, but chances are that the compiler will inline the calls that the queue makes. That is, when you say queue.push(), it will really just say queue.container.push_back(), skipping the function call completely.

Once again, this is only an educated guess, but using a queue will not degrade performance, when compared to using the underlying container raw. Like I've said before, use the queue, because it's clean, easy to use, and safe, and if it really becomes a problem profile and test.

FIFO type of container - Which STL Container is most suitable and why?

Ever heard of std::deque? :)

It allows amortized constant time random access and constant time push/pop operations on both sides. As such, it can be easily used as a FIFO queue.

That said, since it can be used as such so easily, there is a container adaptor std::queue, though it doesn't offer random access and an iterator interface.

C++ Container for high performance FIFO

A more efficient structure would be to implement a circular queue (ring buffer) using an array.

Since arrays are fixed size, you either have to make the array large enough so there is no data overrun; or only store the last N values, where N is the capacity of the buffer.

Many embedded systems use arrays to reduce any issues of memory fragmentation caused by dynamic memory location.

If your array is small enough, it can fit in the processor's data cache; which speeds up computation.

Using STL vector as a FIFO container for byte data

Erasing a from the front of a vector an element at the time can be quite slow, especially if the buffer is large (unless you can reorder elements, which you cannot with a FIFO queue).

A circular buffer is an excellent, perhaps ideal data structure for a FIFO queue of fixed size. But there is no implementation in the standard library. You'll have to implement it yourself or use a third party implementation such as the Boost one you've discovered.

The standard library provides a high level structure for a growing FIFO queue: std::queue. For a lower level data structure, the double ended queue is a good choice (std::deque, which is the default underlying container of std::queue).

On the flip side, vectors are candidates for CPU cache locality because of the contiguous nature of the data (but this is not guaranteed).

The continuous storage of std::vector is guaranteed. A fixed circular buffer also has continuous storage.

I'm not sure what is guaranteed about cache locality of std::deque but it is typically quite good in practice as the typical implementation is a linked list of arrays.

Which is the fastest STL container for find?

For searching a particular value, with std::set and std::map it takes O(log N) time, while with the other two it takes O(N) time; So, std::set or std::map are probably better. Since you have access to C++0x, you could also use std::unordered_set or std::unordered_map which take constant time on average.

For find_if, there's little difference between them, because it takes an arbitrary predicate and containers cannot optimize arbitrarily, of course.

However if you will be calling find_if frequently with a certain predicate, you can optimize yourself: use a std::map or std::set with a custom comparator or special keys and use find instead.

Quickest Queue Container (C++)

The only way to be sure how the choice effects performance is to measure it, in a situation similar to your expected use cases. That said, here are some observations:

For std::queue:

• std::deque is usually the best choice; it supports all the necessary operations in constant time, and allocates memory in chunks as it grows.
• std::list also supports the necessary operations, but may be slower due to more memory allocations; in special circumstances, you might be able to get good results by allocating from a dedicated object pool, but that's not entirely straightforward.
• std::vector can't be used as it doesn't have a pop_front() operation; such an operation would be slow, as it would have to move all the remaining elements.

A potentially faster, but less flexible, alternative is to implement a circular buffer over a fixed-size array (e.g. std::array, or a std::vector that you don't resize). You'll need to deal with the case of it filling up, either by reporting an error, or allocating a larger buffer and copying all the data.

For std::priority_queue:

• std::vector is usually the best choice; it grows exponentially (reducing the number of memory allocations), and is a simple data structure that's very fast to access - an iterator can be implemented simply as a wrapper around a pointer.
• std::deque may be slower as it typically grows linearly (requiring more memory allocation), and access is more complicated than with a vector.
• std::list can't be used as it doesn't provide random access.

To summarise - the defaults are usually the best choice, but if speed really is important, then measure the alternatives.

---

Related Topics