StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Since there are a myriad of answers, you might be confused, but to summarize:</p> <p>Use a <a href="http://en.cppreference.com/w/cpp/container/queue" rel="noreferrer"><code>std::queue</code></a>. The reason for this is simple: it is a FIFO structure. You want FIFO, you use a <code>std::queue</code>.</p> <p>It makes your intent clear to anybody else, and even yourself. A <a href="http://en.cppreference.com/w/cpp/container/list" rel="noreferrer"><code>std::list</code></a> or <a href="http://en.cppreference.com/w/cpp/container/deque" rel="noreferrer"><code>std::deque</code></a> does not. A list can insert and remove anywhere, which is not what a FIFO structure is suppose to do, and a <code>deque</code> can add and remove from either end, which is also something a FIFO structure cannot do.</p> <p>This is why you should use a <code>queue</code>.</p> <p>Now, you asked about performance. Firstly, always remember this important rule of thumb: <strong>Good code first, performance last.</strong></p> <p>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.</p> <p>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.</p> <p>That all said, <code>std::queue</code> 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.</p> <p>So, which underlying container should you use? We know that <code>std::list</code> and <code>std::deque</code> both provide the necessary functions (<code>push_back()</code>, <code>pop_front()</code>, and <code>front()</code>), so how do we decide?</p> <p>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 <code>list</code> has to allocate memory every single time something is added, and deallocate it when it goes away.</p> <p>A <code>deque</code>, on the other hand, allocates in chunks. It will allocate less often than a <code>list</code>. Think of it as a list, but each memory chunk can hold multiple nodes. (Of course, I'd suggest that you <a href="http://en.wikipedia.org/wiki/Double-ended_queue" rel="noreferrer">really learn how it works</a>.)</p> <p>So, with that alone a <code>deque</code> 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.</p> <p>A second thing to understand is <a href="https://homes.cs.washington.edu/~lamarca/pubs/ladner-fix-lamarca-soda99.pdf" rel="noreferrer">cache performance</a>. 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 <code>deque</code> 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 <code>deque</code> will be speedy, because the data is in cache.</p> <p>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.</p> <p>So, considering that, a <code>deque</code> should be a better choice. This is why it is the default container when using a <code>queue</code>. That all said, this is still only a (very) educated guess: you'll have to profile this code, using a <code>deque</code> in one test and <code>list</code> in the other to really know for certain.</p> <p>But remember: get the code working with a clean interface, then worry about performance.</p> <p>John raises the concern that wrapping a <code>list</code> or <code>deque</code> 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 <code>queue</code> makes. That is, when you say <code>queue.push()</code>, it will really just say <code>queue.container.push_back()</code>, skipping the function call completely.</p> <p>Once again, this is only an educated guess, but using a <code>queue</code> will not degrade performance, when compared to using the underlying container raw. Like I've said before, use the <code>queue</code>, because it's clean, easy to use, and safe, and if it really becomes a problem profile and test.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload