What really is a deque in STL

0 votes
I was looking at STL containers and trying to figure out what they really are (i.e. the data structure used) when I came across the deque: at first, I thought it was a double linked list, which would allow insertion and deletion from both ends in constant time, but the promise made by the operator [] to be done in constant time concerned me. Arbitrary access in a linked list should be O(n), right?

And how can it add elements in constant time if it's a dynamic array?

It should be noted that reallocation may occur, and thus O(1), like a vector, is an amortised cost.

So I'm curious about this structure that permits arbitrary access in constant time while never requiring relocation to a larger location.
Jun 9 in C++ by Nicholas
• 5,020 points
17 views

1 answer to this question.

0 votes

A deque is defined somewhat recursively: fundamentally, it keeps a double-ended queue of fixed-size pieces. Each chunk is a vector, and the queue of chunks ("map" in the figure below) is likewise a vector.

image

schematic of the memory layout of a deque
The map is internally represented as a T** in the GCC standard library implementation. Each data block is a T* with a defined size __deque buf size (which is determined by sizeof(T)).

answered Jun 10 by Damon
• 4,960 points

Related Questions In C++

0 votes
1 answer

What is a lambda expression in C++11?

In C++11, what is a lambda expression? A: It's the object of an autogenerated class with overloading operator() const under the hood.  Closure is a type of object that is produced by the compiler.  This 'closure' idea is similar to C++11's bind notion.  Lambdas, on the other hand, usually produce better code.  Full inlining is also possible with calls through closures. Q: When do you think I'd utilise one? A: Define "simple and tiny logic" and request that the compiler generate the code from the preceding question.  You tell the compiler the expressions you wish to be inside the operator ().  The compiler will produce everything else for you. Q: What kind of problem do they tackle that couldn't be solved before they were introduced? A: It's some form of syntactic sugar, like using operators instead of functions for custom add, subtract, and other operations... However, wrapping 1-3 lines of genuine logic to some classes, and so on, saves additional lines of needless code!  Some engineers believe that if the number of lines is reduced, there is a lower likelihood of mistakes (which I agree with). Example of usage auto x = [=](int arg1){printf("%i", ...READ MORE

answered Jun 15 in C++ by Damon
• 4,960 points
26 views
0 votes
1 answer

What is a Class and Object in C++?

A Class is like a blueprint, an ...READ MORE

answered Jun 21 in C++ by Damon
• 4,960 points
21 views
0 votes
0 answers

What is the fastest way to transpose a matrix in C++?

I have a reasonably large matrix that I need to transpose.  Assume, for example, that my matrix is a b c d e f g h ...READ MORE

Jul 15 in C++ by Nicholas
• 5,020 points
11 views
0 votes
0 answers

What is a stream in C++?

I've been hearing a lot about streams, ...READ MORE

4 days ago in C++ by Nicholas
• 5,020 points
7 views
0 votes
1 answer

Syntax of priority queue

We must first include the queue header file in order to establish a priority queue in C++. #include <queue> Once we import this file, we ...READ MORE

answered May 31 in C++ by Damon
• 4,960 points
16 views
0 votes
1 answer

Sorting a vector of custom objects

A simple example using std::sort struct MyStruct { ...READ MORE

answered Jun 1 in C++ by Damon
• 4,960 points
41 views
0 votes
1 answer

lower_bound == upper_bound

Lower bound: the initial greater-or-equal element. Upper bound: ...READ MORE

answered Jun 21 in C++ by Damon
• 4,960 points
41 views
0 votes
1 answer

Comparison of C++ STL collections and C# collections

This is what I know Array - C ...READ MORE

answered Jun 9 in C# by rajiv
• 1,620 points
32 views
0 votes
1 answer

In C++, what is a virtual base class?

When employing multiple inheritance, virtual base classes are used to prevent several "instances" of a particular class from appearing in an inheritance hierarchy. Consider the following example: class A { public: void Foo() {} ...READ MORE

answered Jun 10 in C++ by Damon
• 4,960 points
24 views
0 votes
1 answer

What is the best way to use a HashMap in C++?

The ordered and unordered map containers (std::map and std::unordered map) are included in the standard library.  The items in an ordered map are sorted by key, and insert and access are in O (log n).  For ordered maps, the standard library often use red black trees.  However, this is only an implementation detail.  Insert and access are in O in an unordered map (1).  It is simply another term for a hashtable. An illustration using (ordered) std::map: #include <map> #include <iostream> #include <cassert> int main(int argc, char ...READ MORE

answered Jun 10 in C++ by Damon
• 4,960 points
47 views
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP