What Data Structure, Exactly, Are Deques in C++

What data structure, exactly, are deques in C++?

(Making this answer a community-wiki. Please get stuck in.)

First things first: A deque requires that any insertion to the front or back shall keep any reference to a member element valid. It's OK for iterators to be invalidated, but the members themselves must stay in the same place in memory. This is easy enough by just copying the members to somewhere on the heap and storing T* in the data structure under the hood. See this other StackOverflow question " About deque<T>'s extra indirection "

(vector doesn't guarantee to preserve either iterators or references, whereas list preserves both).

So let's just take this 'indirection' for granted and look at the rest of the problem. The interesting bit is the time to insert or remove from the beginning or end of the list. At first, it looks like a deque could trivially be implemented with a vector, perhaps by interpreting it as a circular buffer.

BUT A deque must satisfy "Inserting a single element either at the beginning or end of a
deque always takes constant time and causes a single call to a constructor of T."

Thanks to the indirection we've already mentioned, it's easy to ensure there is just one constructor call, but the challenge is to guarantee constant time. It would be easy if we could just use constant amortized time, which would allow the simple vector implementation, but it must be constant (non-amortized) time.

What really is a deque in STL?

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.

There’s a great analysis of the performance characteristics and how it compares to the vector over at CodeProject.

The GCC standard library implementation internally uses a T** to represent the map. Each data block is a T* which is allocated with some fixed size __deque_buf_size (which depends on sizeof(T)).

What is the technical error if we declare a Deque as a general one which allows input and output from both sides?

Under Distinctions and sub-types, the Wikipedia article says, "This general data class has some possible sub-types:" It then goes on to list the input- and output-restricted. Note that they are possible sub-types. Nothing in the article or any other literature I've seen says that you can't have an unrestricted deque, and in fact many runtime libraries provide such.

So there is a deque (unrestricted double-ended queue), and there are input-restricted and output-restricted deques.

It's perhaps a bit of a stretch, but one could make the argument that both FIFO queues and LIFO stacks are also deque sub-types. The FIFO queue is input-restricted at one end and output-restricted at the other. A LIFO stack is input- and output-restricted at the same end.

Difference between enqueue and dequeue

Some of the basic data structures in programming languages such as C and C++ are stacks and queues.

The stack data structure follows the "First In Last Out" policy (FILO) where the first element inserted or "pushed" into a stack is the last element that is removed or "popped" from the stack.

Similarly, a queue data structure follows a "First In First Out" policy (as in the case of a normal queue when we stand in line at the counter), where the first element is pushed into the queue or "Enqueued" and the same element when it has to be removed from the queue is "Dequeued".

This is quite similar to push and pop in a stack, but the terms enqueue and dequeue avoid confusion as to whether the data structure in use is a stack or a queue.

Class coders has a simple program to demonstrate the enqueue and dequeue process. You could check it out for reference.

http://classcoders.blogspot.in/2012/01/enque-and-deque-in-c.html

What data type would have a structure with a maximum size and elements are FIFO?

Is there a built in data structure in C++03

A data structure that would be appropriate for what you describe is circular buffer.

There is no such container in the standard library.

or am I required to make my own?

You can make your own. A circular buffer can be implemented on top of a sequence container. Or - as always - you can use a pre-existing library.

About deque<T>'s extra indirection

For whatever reason, at least as of MSVC 2010, the std::deque implementation appears to make use of an unbelievably small block size (the max of 16 bytes or 1 single element if I'm not mistaken!).

This, in my experience, can result in very significant performance issues, because essentially each "block" in the data structure only ends up storing a single element, which leads to all kinds of additional overhead (time and memory).

I don't know why it's done this way. As far as I understand it setting up a deque with such a small block size is exactly how it's not supposed to be done.

Check out the gcc stdlib implementation. From memory they use a much larger block size.

EDIT: In an attempt to address the other issues:

• std::deque should have an extra layer of indirection. It is often implemented as a "blocked" data structure - i.e. storing an array of "nodes" where each node is itself an array of data elements. It's not ever like a linked-list - the array of nodes is never "traversed" like a list, it's always directly indexed (even in the case of 1 element per block).

• Of course you can roll your own data structure that keeps some extra space at the front. It wont have worst case O(1) push/pop front/back behaviour, and as such it wont satisfy the requirements of the std::deque container. But if you don't care about any of that...

What is the optimal data structure for storing data points acquired during last n seconds

It seems that you can use circular buffer from boost.
There is no equivalent in C++ STL.

If you don't want to depend on boost, implement a non-shrinking circular buffer yourself over std::vector, that's not hard.

Design a data structure that moves referenced element to the beginning. C++

Balanced ropes guarantee amortized O(log N) indexing, deletion and insertion time. The operation in question can be decomposed into a sequence of the three.

Advice about what kind of data structure to use for quick search times C++

Just use any hash table that comes with your standard library or from boost. Most will have the unordered_map (as specified by TR1 and proposed for C++0x) as does boost, but some will have a std::hash_map or stdext::hash_map with various implementation being slightly different, e.g. the original SGI vs. Microsoft.

You don't need to build a list, just put the objects directly in the hash table; it allows sequential iteration, though it will be in some fixed random order.

---

Related Topics