Menu
I've read that accessing elements by position index can be done in constant time in a STL deque. As far as I know, elements in a deque may be stored in several non-contiguous locations, eliminating safe access through pointer arithmetic. For example:
abc->defghi->jkl->mnop
The elements of the deque above consists of a single character. The set of characters in one group indicate it is allocated in contiguous memory (e.g. abc is in a single block of memory, defhi is located in another block of memory, etc.). Can anyone explain how accessing by position index can be done in constant time, especially if the element to be accessed is in the second block? Or does a deque have a pointer to the group of blocks?
Update: Or is there any other common implementation for a deque?
261
std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.
If deque is implemented as a ring buffer on top of std::vector , which reallocates itself when it grows in size, then accessing by index is indeed O(1). when erasing elements from the deque, it may call as many assignment operators, as the distance from the elements being erased to the end of the deque is.
In C++, the STL deque is a sequential container that provides the functionality of a double-ended queue data structure. In a regular queue, elements are added from the rear and removed from the front. However, in a deque, we can insert and remove elements from both the front and rear. Deque Data Structure.
deque could be implemented as a circular buffer of fixed size array: Use circular buffer so we could grow/shrink at both end by adding/removing a fixed sized array with O(1) complexity. Use fixed sized array so it is easy to calculate the index, hence access via index with two pointer dereferences - also O(1)
STL deque accessing by index is O (1)? Bookmark this question. Show activity on this post. I've read that accessing elements by position index can be done in constant time in a STL deque. As far as I know, elements in a deque may be stored in several non-contiguous locations, eliminating safe access through pointer arithmetic. For example:
If deque is implemented as a ring buffer on top of std::vector, which reallocates itself when it grows in size, then accessing by index is indeed O (1). The standard provides evidence that such implementation was meant--at least it conforms to standard in complexity estimations.
deque rend() function in C++ STL: Returns a reverse iterator which points to the position before the beginning of the deque (which is considered its reverse end). deque cbegin() in C++ STL: Returns a constant iterator pointing to the first element of the container, that is, the iterator cannot be used to modify,...
deque insert () function in C++ STL: Inserts an element. And returns an iterator that points to the first of the newly inserted elements. deque rbegin () function in C++ STL: Returns a reverse iterator which points to the last element of the deque (i.e., its reverse beginning).
I found this deque implementation from Wikipedia:
Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.
I guess it answers my question.
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
