Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/deque/deque"

From cppreference.com
< cpp‎ | container‎ | deque
m (1 revision: import content)
(Version fix.)
 
(14 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
{{cpp/container/constructor|deque}}
+
{{cpp/container/deque/title|deque}}
 +
{{cpp/container/deque/navbar}}
 +
{{dcl begin}}
 +
{{dcl|num=1|since=c++11|
 +
deque() : deque(Allocator()) {}
 +
}}
 +
{{dcl rev begin|num=2}}
 +
{{dcl|until=c++11|1=
 +
explicit deque( const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl|since=c++11|
 +
explicit deque( const Allocator& alloc );
 +
}}
 +
{{dcl rev end}}
 +
{{dcl|num=3|since=c++11|1=
 +
explicit deque( size_type count, const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl rev begin|num=4}}
 +
{{dcl|until=c++11|1=
 +
explicit deque( size_type count, const T& value = T(),
 +
                const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl|since=c++11|1=
 +
deque( size_type count, const T& value,
 +
      const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl rev end}}
 +
{{dcl|num=5|1=
 +
template< class InputIt >
 +
deque( InputIt first, InputIt last, const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl|num=6|since=c++23|1=
 +
template< container-compatible-range<T> R >
 +
deque( std::from_range_t, R&& rg, const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl|num=7|
 +
deque( const deque& other );
 +
}}
 +
{{dcl|num=8|since=c++11|
 +
deque( deque&& other );
 +
}}
 +
{{dcl rev begin|num=9}}
 +
{{dcl|since=c++11|until=c++23|
 +
deque( const deque& other, const Allocator& alloc );
 +
}}
 +
{{dcl|since=c++23|
 +
deque( const deque& other, const std::type_identity_t<Allocator>& alloc );
 +
}}
 +
{{dcl rev end}}
 +
{{dcl rev begin|num=10}}
 +
{{dcl|since=c++11|until=c++23|
 +
deque( deque&& other, const Allocator& alloc );
 +
}}
 +
{{dcl|since=c++23|
 +
deque( deque&& other, const std::type_identity_t<Allocator>& alloc );
 +
}}
 +
{{dcl rev end}}
 +
{{dcl|num=11|since=c++11|1=
 +
deque( std::initializer_list<T> init, const Allocator& alloc = Allocator() );
 +
}}
 +
{{dcl end}}
 +
 
 +
Constructs a new {{tt|deque}} from a variety of data sources, optionally using a user supplied allocator {{c|alloc}}.
 +
 
 +
@1@ The default constructor since C++11. Constructs an empty {{tt|deque}} with a default-constructed allocator.
 +
@@ If {{tt|Allocator}} is not {{named req|DefaultConstructible}}, the behavior is undefined.
 +
 
 +
@2@ The default constructor until C++11. Constructs an empty {{tt|deque}} with the given allocator {{c|alloc}}.
 +
 
 +
@3@ Constructs a {{tt|deque}} with {{c|count}} default-inserted objects of {{tt|T}}. No copies are made.
 +
@@ If {{tt|T}} is not {{named req|DefaultInsertable}} into {{c/core|std::deque<T>}}, the behavior is undefined.
 +
 
 +
@4@ Constructs a {{tt|deque}} with {{c|count}} copies of elements with value {{c|value}}.
 +
{{rrev|since=c++11|
 +
If {{tt|T}} is not {{named req|CopyInsertable}} into {{c/core|std::deque<T>}}, the behavior is undefined.
 +
}}
 +
 
 +
@5@ Constructs a {{tt|deque}} with the contents of the range {{range|first|last}}. Each iterator in {{range|first|last}} is dereferenced exactly once.
 +
{{rev begin}}
 +
{{rev|until=c++11|
 +
If {{tt|InputIt}} does not satisfy the requirements of {{named req|InputIterator}}, overload {{v|4}} is called instead with arguments {{c|static_cast<size_type>(first)}}, {{c|last}} and {{c|alloc}}.
 +
}}
 +
{{rev|since=c++11|
 +
{{cpp/enable if|{{tt|InputIt}} satisfies the requirements of {{named req|InputIterator}}}}.
 +
 
 +
If {{tt|T}} is not {{named req|EmplaceConstructible}} into {{c/core|std::deque<T>}} from {{c|*first}}, the behavior is undefined.
 +
}}
 +
{{rev end}}
 +
 
 +
@6@ Constructs a {{tt|deque}} with the contents of the range {{c|rg}}. Each iterator in {{c|rg}} is dereferenced exactly once.
 +
@@ If {{tt|T}} is not {{named req|EmplaceConstructible}} into {{c/core|std::deque<T>}} from {{c|*ranges::begin(rg)}}, the behavior is undefined.
 +
 
 +
@7-10@ Constructs a {{tt|deque}} with the contents of {{c|other}}.
 +
 
 +
:@7@ The copy constructor.
 +
{{rrev|since=c++11|
 +
The allocator is obtained as if by calling {{c multi|std::allocator_traits<Allocator>::|    select_on_container_copy_construction|        (other.get_allocator())}}.
 +
}}
 +
 
 +
:@8@ The move constructor. The allocator is obtained by move construction from {{c|other.get_allocator()}}.
 +
 
 +
:@9@ Same as the copy constructor, except that {{c|alloc}} is used as the allocator.
 +
:@@ If {{tt|T}} is not {{named req|CopyInsertable}} into {{c/core|std::deque<T>}}, the behavior is undefined.
 +
 
 +
:@10@ Same as the move constructor, except that {{c|alloc}} is used as the allocator.
 +
:@@ If {{tt|T}} is not {{named req|MoveInsertable}} into {{c/core|std::deque<T>}}, the behavior is undefined.
 +
 
 +
@11@ Equivalent to {{c|deque(il.begin(), il.end(), alloc)}}.
 +
 
 +
===Parameters===
 +
{{par begin}}
 +
{{par|alloc|allocator to use for all memory allocations of this container}}
 +
{{par|count|the size of the container}}
 +
{{par|value|the value to initialize elements of the container with}}
 +
{{par|first, last|the range to copy the elements from}}
 +
{{par|other|another container to be used as source to initialize the elements of the container with}}
 +
{{par|init|initializer list to initialize the elements of the container with}}
 +
{{par|rg|a container compatible range}}
 +
{{par end}}
 +
 
 +
===Complexity===
 +
@1,2@ Constant.
 +
 
 +
@3,4@ Linear in {{c|count}}.
 +
 
 +
@5@ Linear in {{c|std::distance(first, last)}}.
 +
 
 +
@6@ Linear in {{c|ranges::distance(rg)}}.
 +
 
 +
@7@ Linear in {{c|other.size()}}.
 +
 
 +
@8@ Constant.
 +
 
 +
@9@ Linear in {{c|other.size()}}.
 +
 
 +
@10@ Linear in {{c|other.size()}} if {{c|1=alloc != other.get_allocator()}}, otherwise constant.
 +
 
 +
@11@ Linear in {{c|init.size()}}.
 +
 
 +
===Exceptions===
 +
Calls to {{c|Allocator::allocate}} may throw.
 +
 
 +
===Notes===
 +
{{cpp/container/lwg2321-note|8}}
 +
 
 +
{{feature test macro|__cpp_lib_containers_ranges|[[cpp/ranges/to#container compatible range|Ranges-aware]] construction and insertion; overload {{v|6}}|value=202202L|std=C++23}}
 +
 
 +
===Example===
 +
{{example
 +
|code=
 +
#include <deque>
 +
#include <iostream>
 +
#include <string>
 +
 
 +
template<typename T>
 +
std::ostream& operator<<(std::ostream& s, const std::deque<T>& v)
 +
{
 +
    s.put('{');
 +
    for (char comma[]{'\0', ' ', '\0'}; const auto& e : v)
 +
        s << comma << e, comma[0] = ',';
 +
    return s << "}\n";
 +
}
 +
 
 +
int main()
 +
{
 +
    // C++11 initializer list syntax:
 +
    std::deque<std::string> words1{"the", "frogurt", "is", "also", "cursed"};
 +
    std::cout << "1: " << words1;
 +
   
 +
    // words2 == words1
 +
    std::deque<std::string> words2(words1.begin(), words1.end());
 +
    std::cout << "2: " << words2;
 +
   
 +
    // words3 == words1
 +
    std::deque<std::string> words3(words1);
 +
    std::cout << "3: " << words3;
 +
   
 +
    // words4 is {"Mo", "Mo", "Mo", "Mo", "Mo"}
 +
    std::deque<std::string> words4(5, "Mo");
 +
    std::cout << "4: " << words4;
 +
   
 +
    const auto rg = {"cat", "cow", "crow"};
 +
#ifdef __cpp_lib_containers_ranges
 +
    std::deque<std::string> words5(std::from_range, rg); // overload (6)
 +
#else
 +
    std::deque<std::string> words5(rg.begin(), rg.end()); // overload (5)
 +
#endif
 +
    std::cout << "5: " << words5;
 +
}
 +
|output=
 +
1: {the, frogurt, is, also, cursed}
 +
2: {the, frogurt, is, also, cursed}
 +
3: {the, frogurt, is, also, cursed}
 +
4: {Mo, Mo, Mo, Mo, Mo}
 +
5: {cat, cow, crow}
 +
}}
 +
 
 +
===Defect reports===
 +
{{dr list begin}}
 +
{{dr list item|wg=lwg|dr=144|std=C++98|before=the complexity requirement of overload {{v|5}} was the same<br>as that of the corresponding overload of {{lc|std::vector}}|after=changed to linear complexity}}
 +
{{dr list item|wg=lwg|dr=237|std=C++98|before=the complexity requirement of overload<br>{{v|5}} was linear in {{c|first - last}}|after=changed to linear in<br>{{c|std::distance(first, last)}}}}
 +
{{dr list item|wg=lwg|dr=438|std=C++98|before=overload {{v|5}} would only call overload {{v|4}}<br>if {{tt|InputIt}} is an integral type|after=calls overload {{v|4}} if {{tt|InputIt}}<br>is not an {{named req|InputIterator}}}}
 +
{{dr list item|wg=lwg|dr=2193|std=C++11|before=the default constructor was explicit|after=made non-explicit}}
 +
{{dr list item|wg=lwg|dr=2210|std=C++11|before=overload {{v|3}} did not have an allocator parameter|after=added the parameter}}
 +
{{dr list item|paper=N3346|std=C++11|before=for overload {{v|3}}, the elements in<br>the container were value-initialized|after=they are default-inserted}}
 +
{{dr list end}}
 +
 
 +
===See also===
 +
{{dsc begin}}
 +
{{dsc inc|cpp/container/dsc assign|deque}}
 +
{{dsc inc|cpp/container/dsc operator{{=}}|deque}}
 +
{{dsc end}}
 +
 
 +
{{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}}

Latest revision as of 22:43, 10 November 2024

 
C++
 
Containers library
 
std::deque
Member types
Member functions
Non-member functions
(until C++20)(until C++20)(until C++20)(until C++20)(until C++20)
Deduction guides(C++17)
 
deque() : deque(Allocator()) {}
 (1) (since C++11)
(2)
explicit deque( const Allocator& alloc = Allocator() );
 (until C++11)
explicit deque( const Allocator& alloc );
 (since C++11)
explicit deque( size_type count, const Allocator& alloc = Allocator() );
 (3) (since C++11)
(4)
explicit deque( size_type count, const T& value = T(),
                const Allocator& alloc = Allocator() );
 (until C++11)
deque( size_type count, const T& value,
       const Allocator& alloc = Allocator() );
 (since C++11)
template< class InputIt >
deque( InputIt first, InputIt last, const Allocator& alloc = Allocator() );
 (5)
template< container-compatible-range<T> R >
deque( std::from_range_t, R&& rg, const Allocator& alloc = Allocator() );
 (6) (since C++23)
deque( const deque& other );
 (7)
deque( deque&& other );
 (8) (since C++11)
(9)
deque( const deque& other, const Allocator& alloc );
 (since C++11)
(until C++23)
deque( const deque& other, const std::type_identity_t<Allocator>& alloc );
 (since C++23)
(10)
deque( deque&& other, const Allocator& alloc );
 (since C++11)
(until C++23)
deque( deque&& other, const std::type_identity_t<Allocator>& alloc );
 (since C++23)
deque( std::initializer_list<T> init, const Allocator& alloc = Allocator() );
 (11) (since C++11)

Constructs a new deque from a variety of data sources, optionally using a user supplied allocator alloc.

1) The default constructor since C++11. Constructs an empty deque with a default-constructed allocator.
If Allocator is not DefaultConstructible, the behavior is undefined.
2) The default constructor until C++11. Constructs an empty deque with the given allocator alloc.
3) Constructs a deque with count default-inserted objects of T. No copies are made.
If T is not DefaultInsertable into std::deque<T>, the behavior is undefined.
4) Constructs a deque with count copies of elements with value value.

If T is not CopyInsertable into std::deque<T>, the behavior is undefined.

(since C++11)
5) Constructs a deque with the contents of the range [first, last). Each iterator in [first, last) is dereferenced exactly once.

If InputIt does not satisfy the requirements of LegacyInputIterator, overload (4) is called instead with arguments static_cast<size_type>(first), last and alloc.

(until C++11)

This overload participates in overload resolution only if InputIt satisfies the requirements of LegacyInputIterator.

If T is not EmplaceConstructible into std::deque<T> from *first, the behavior is undefined.

(since C++11)
6) Constructs a deque with the contents of the range rg. Each iterator in rg is dereferenced exactly once.
If T is not EmplaceConstructible into std::deque<T> from *ranges::begin(rg), the behavior is undefined.
7-10) Constructs a deque with the contents of other.
7) The copy constructor.

The allocator is obtained as if by calling std::allocator_traits<Allocator>::
    select_on_container_copy_construction
        (other.get_allocator()).

(since C++11)
8) The move constructor. The allocator is obtained by move construction from other.get_allocator().
9) Same as the copy constructor, except that alloc is used as the allocator.
If T is not CopyInsertable into std::deque<T>, the behavior is undefined.
10) Same as the move constructor, except that alloc is used as the allocator.
If T is not MoveInsertable into std::deque<T>, the behavior is undefined.
11) Equivalent to deque(il.begin(), il.end(), alloc).

Contents

[edit] Parameters

alloc - allocator to use for all memory allocations of this container
count - the size of the container
value - the value to initialize elements of the container with
first, last - the range to copy the elements from
other - another container to be used as source to initialize the elements of the container with
init - initializer list to initialize the elements of the container with
rg - a container compatible range

[edit] Complexity

1,2) Constant.
3,4) Linear in count.
5) Linear in std::distance(first, last).
6) Linear in ranges::distance(rg).
7) Linear in other.size().
8) Constant.
9) Linear in other.size().
10) Linear in other.size() if alloc != other.get_allocator(), otherwise constant.
11) Linear in init.size().

[edit] Exceptions

Calls to Allocator::allocate may throw.

[edit] Notes

After container move construction (overload (8)), references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this. The current standard makes this guarantee via the blanket statement in [container.reqmts]/67, and a more direct guarantee is under consideration via LWG issue 2321.

Feature-test macro Value Std Feature
__cpp_lib_containers_ranges 202202L (C++23) Ranges-aware construction and insertion; overload (6)

[edit] Example

Run this code
#include <deque>
#include <iostream>
#include <string>
 
template<typename T>
std::ostream& operator<<(std::ostream& s, const std::deque<T>& v)
{
    s.put('{');
    for (char comma[]{'\0', ' ', '\0'}; const auto& e : v)
        s << comma << e, comma[0] = ',';
    return s << "}\n";
}
 
int main()
{
    // C++11 initializer list syntax:
    std::deque<std::string> words1{"the", "frogurt", "is", "also", "cursed"};
    std::cout << "1: " << words1;
 
    // words2 == words1
    std::deque<std::string> words2(words1.begin(), words1.end());
    std::cout << "2: " << words2;
 
    // words3 == words1
    std::deque<std::string> words3(words1);
    std::cout << "3: " << words3;
 
    // words4 is {"Mo", "Mo", "Mo", "Mo", "Mo"}
    std::deque<std::string> words4(5, "Mo");
    std::cout << "4: " << words4;
 
    const auto rg = {"cat", "cow", "crow"};
#ifdef __cpp_lib_containers_ranges
    std::deque<std::string> words5(std::from_range, rg); // overload (6)
#else
    std::deque<std::string> words5(rg.begin(), rg.end()); // overload (5)
#endif
    std::cout << "5: " << words5;
}

Output: 

1: {the, frogurt, is, also, cursed}
2: {the, frogurt, is, also, cursed}
3: {the, frogurt, is, also, cursed}
4: {Mo, Mo, Mo, Mo, Mo}
5: {cat, cow, crow}

[edit] Defect reports

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

DR Applied to Behavior as published Correct behavior
LWG 144 C++98 the complexity requirement of overload (5) was the same
as that of the corresponding overload of std::vector 		changed to linear complexity
LWG 237 C++98 the complexity requirement of overload
(5) was linear in first - last 		changed to linear in
std::distance(first, last)
LWG 438 C++98 overload (5) would only call overload (4)
if InputIt is an integral type 		calls overload (4) if InputIt
is not an LegacyInputIterator
LWG 2193 C++11 the default constructor was explicit made non-explicit
LWG 2210 C++11 overload (3) did not have an allocator parameter added the parameter
N3346 C++11 for overload (3), the elements in
the container were value-initialized 		they are default-inserted

[edit] See also

 assigns values to the container
(public member function) [edit]
assigns values to the container
(public member function) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/deque/deque&oldid=177600"