Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://en.cppreference.com/w/cpp/language/../container/deque.html below:

std::deque - cppreference.com

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.

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, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location. On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++).

The complexity (efficiency) of common operations on deques is as follows:

• Random access - constant O(1).
• Insertion or removal of elements at the end or beginning - constant O(1).
• Insertion or removal of elements - linear O(n).

std::deque meets the requirements of Container, AllocatorAwareContainer, SequenceContainer and ReversibleContainer.

However, std::deque objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression.

[edit]

If erasing at end - only erased elements and the past-the-end iterator.
Otherwise - all iterators are invalidated.

It is unspecified when the past-the-end iterator is invalidated.

The past-the-end iterator is also invalidated unless the erased
elements are at the beginning of the container and the last
element is not erased.

If the new size is bigger than the old one - all iterators are invalidated.
Otherwise - none iterators are invalidated.

The past-the-end iterator may be invalidated (implementation defined).

The past-the-end iterator is also invalidated.

• When inserting at either end of the deque, references are not invalidated by insert and emplace.
• push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.
• When erasing at either end of the deque, references to non-erased elements are not invalidated by erase, pop_front and pop_back.
• A call to resize with a smaller size does not invalidate any references to non-erased elements.
• A call to resize with a bigger size does not invalidate any references to elements of the deque.

#include <deque>
#include <iostream>
 
int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
 
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
 
    // Iterate and print values of deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

Output:

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4