What Really Is a Deque in Stl

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.

schematic of the memory layout of a deque

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)).

How is deque implemented in c++ stl

I just wanted to know how deque is implemented

It's always a good to have an excuse for doing ASCII art:

+-------------------------------------------------------------+                       
| std::deque<int> |
| |
| subarrays: |
| +---------------------------------------------------------+ |
| | | | | | | |
| | int(*)[8] | int(*)[8] | int(*)[8] |int(*)[8]|int(*)[8] | |
| | | | | | | |
| +---------------------------------------------------------+ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| - - |
| +------------------------------+ |
| | ?, ?, 42, 43, 50, ?, ?, ?, ? | |
| +------------------------------+ |
| |
| additional state: |
| |
| - pointer to begin of the subarrays |
| - current capacity and size |
| - pointer to current begin and end |
+-------------------------------------------------------------+

how are the basic operations like push_front and random access operator are provided in that implementation?

First, std::deque::push_front, from libcxx:

template <class _Tp, class _Allocator>
void
deque<_Tp, _Allocator>::push_front(const value_type& __v)
{
allocator_type& __a = __base::__alloc();
if (__front_spare() == 0)
__add_front_capacity();
__alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
--__base::__start_;
++__base::size();
}

This obviously checks whether the memory already allocated at the front can hold an additional element. If not, it allocates. Then, the main work is shifted to the iterator: _VSTD::addressof(*--__base::begin()) goes one location before the current front element of the container, and this address is passed to the allocator to construct a new element in place by copying v (the default allocator will definitely do a placement-new).

Now random access. Again from libcxx, std::deque::operator[] (the non-const version) is

template <class _Tp, class _Allocator>
inline
typename deque<_Tp, _Allocator>::reference
deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
{
size_type __p = __base::__start_ + __i;
return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
}

This pretty much computes an index relative to some start index, and then determines the subarray and the index relative to the start of the subarray. __base::__block_size should be the size of one subarray here.

Why is an STL deque not implemented as just a circular vector?

As cppreference writes

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

This means that the large internal reallocations std::vector occasionally does, are not performed by std::deque. When space runs out, only a small fixed-size array is added. (The same but reverse happens when space becomes too large because of erasing.)

Here is a small test:

#include <vector>
#include <deque>
#include <string>
#include <iostream>
#include <chrono>


using namespace std;


int main()
{
{
const auto start = chrono::high_resolution_clock::now();

vector<string> v;
for(size_t i = 0; i < 9999999; ++i)
v.push_back(string("hello"));

cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
}

{
const auto start = chrono::high_resolution_clock::now();

deque<string> v;
for(size_t i = 0; i < 9999999; ++i)
v.push_back(string("hello"));

cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
}

return 0;
}

On my machine, it shows deque is twice as fast as vector for this case:

$ ./a.out 
301
164

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's the difference between deque and list STL containers?

From the (dated but still very useful) SGI STL summary of deque:

A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

Here's the summary on list from the same site:

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

In summary the containers may have shared routines but the time guarantees for those routines differ from container to container. This is very important when considering which of these containers to use for a task: taking into account how the container will be most frequently used (e.g., more for searching than for insertion/deletion) goes a long way in directing you to the right container.

STL internals: deque implementation

deque is implemented as a vector of vectors (a list of vectors would impede the constant time random access). The size of the secondary vectors is implementation dependent, a common algorithm is to use a constant size in bytes.

What is underlying data structure of std::deque and how does it's iterator work?

The key point is that a deque is made of several chunks of contiguous memory.

When you add an element in the first position then there are two situations:

Either the first chunk has still place to add an element:

 |   |   | first element | second element | .... | ...
^
inserted element can be placed here

Or there is no place in the first chunk, then the inserted element is placed in a different chunk that was empty before the insertion.

In both cases, the elements that were already in the container need not be moved in memory. Hence references to them are still valid. Iterators are different, because they need addtional book-keeping (for example to reach the next chunk when you increment an iterator to the last element in a contiguous chunk). The same holds for inserting an element at the end. Inserting elements in the middle however requires to rearrange already existing elements.

what is the explanation of deque can any one help me?

http://www.cplusplus.com/reference/deque/deque/

You can push elements to a deque on both ends.

Example:
You can use a deque as "history".
The oldest items are in front.
Now you have easy access on the newest element and the oldest. (It is good for a undo function)

What is the reasoning for a deque to have a subscript operator?

Doesn't the fact that deque's can be randomly accessed ruin the very integrity of the deque data structure?

No. You are just hung up on the name for it. We do have a clear definition of a "queue" in mind, so this is a poor choice of words perhaps, but a data structure is not defined by its name.

A date structure is data (duh) with a specific set of associated operations. The standard library defined deque with a subscript operator. So that's the data structure. Great care was taken to make sure the various requirements on the operations don't conflict, so the integrity of deque as a data structure is held up quite nicely.



Related Topics



Leave a reply



Submit