A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning (Figure below).
Figure a: Logical Structure of a Deque
To provide this ability, the deque is implemented typically as a bunch of individual blocks, with the first block growing in one direction and the last block growing in the opposite direction (Figure b).
Figure b: Internal Structure of a Deque
To use a deque, you must include the header file <deque>:
Note: In the original STL, the header file for deques was <deque.h>.
#include <deque>
There, the type is defined as a template class inside namespace std:
namespace std {
template <class T,
class Allocator = allocator<T> >
class deque;
}
As with vectors, the type of the elements is passed as a first template parameter and may be of any type that is assignable and copyable. The optional second template argument is the memory model, with allocator as the default.
Note: In systems without support for default template parameters, the second argument is typically missing.
We will be covering the following under the deque:
See Also:
No comments:
Post a Comment