Class template devector

boost::container::devector

Synopsis

// In header: <boost/container/devector.hpp>

template<typename T, 
         typename SmallBufferPolicy = devector_small_buffer_policy<0>, 
         typename GrowthPolicy = devector_growth_policy, 
         typename Allocator = std::allocator<T> > 
class devector {
public:
  // types
  typedef T                                       value_type;            
  typedef Allocator                               allocator_type;        
  typedef value_type &                            reference;             
  typedef const value_type &                      const_reference;       
  typedef allocator_traits::pointer               pointer;               
  typedef allocator_traits::const_pointer         const_pointer;         
  typedef pointer                                 iterator;              
  typedef const_pointer                           const_iterator;        
  typedef unsigned int                            size_type;             
  typedef int                                     difference_type;       
  typedef std::reverse_iterator< iterator >       reverse_iterator;      
  typedef std::reverse_iterator< const_iterator > const_reverse_iterator;

  // construct/copy/destruct
  devector() noexcept;
  explicit devector(const Allocator &) noexcept;
  devector(size_type, reserve_only_tag, const Allocator & = Allocator());
  devector(size_type, size_type, reserve_only_tag, 
           const Allocator & = Allocator());
  devector(size_type, unsafe_uninitialized_tag, 
           const Allocator & = Allocator());
  explicit devector(size_type, const Allocator & = Allocator());
  devector(size_type, const T &, const Allocator & = Allocator());
  template<typename InputIterator> 
    devector(InputIterator, InputIterator, const Allocator & = Allocator());
  devector(const devector &);
  devector(const devector &, const Allocator &);
  devector(devector &&) noexcept(no_small_buffer||t_is_nothrow_constructible));
  devector(devector &&, const Allocator &) noexcept(no_small_buffer||t_is_nothrow_constructible));
  devector(const std::initializer_list< T > &, 
           const Allocator & = Allocator());
  devector & operator=(const devector &);
  devector & operator=(devector &&) noexcept((no_small_buffer||t_is_nothrow_constructible)&&(allocator_traits::propagate_on_move_assignment||allocator_traits::is_always_equal)));
  devector & operator=(std::initializer_list< T >);
  ~devector();

  // public member functions
  template<typename InputIterator> void assign(InputIterator, InputIterator);
  void assign(size_type, const T &);
  void assign(std::initializer_list< T >);
  allocator_type get_allocator() const noexcept;
  iterator begin() noexcept;
  const_iterator begin() const noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;
  const_iterator cbegin() const noexcept;
  const_iterator cend() const noexcept;
  const_reverse_iterator crbegin() const noexcept;
  const_reverse_iterator crend() const noexcept;
  bool empty() const noexcept;
  size_type size() const noexcept;
  size_type max_size() const noexcept;
  size_type capacity() const noexcept;
  size_type front_free_capacity() const noexcept;
  size_type back_free_capacity() const noexcept;
  void resize(size_type);
  void resize(size_type, const T &);
  void resize_front(size_type);
  void resize_front(size_type, const T &);
  void resize_back(size_type);
  void resize_back(size_type, const T &);
  void unsafe_uninitialized_resize_front(size_type);
  void unsafe_uninitialized_resize_back(size_type);
  void reserve(size_type);
  void reserve_front(size_type);
  void reserve_back(size_type);
  void shrink_to_fit();
  reference operator[](size_type) noexcept;
  const_reference operator[](size_type) const noexcept;
  reference at(size_type);
  const_reference at(size_type) const;
  reference front() noexcept;
  const_reference front() const noexcept;
  reference back() noexcept;
  const_reference back() const noexcept;
  T * data() noexcept;
  const T * data() const noexcept;
  template<class... Args> void emplace_front(Args &&...);
  void push_front(const T &);
  void push_front(T &&);
  void unsafe_push_front(const T &);
  void unsafe_push_front(T &&);
  void pop_front() noexcept;
  template<class... Args> void emplace_back(Args &&...);
  void push_back(const T &);
  void push_back(T &&);
  void unsafe_push_back(const T &);
  void unsafe_push_back(T &&);
  void pop_back() noexcept;
  template<class... Args> iterator emplace(const_iterator, Args &&...);
  iterator insert(const_iterator, const T &);
  iterator insert(const_iterator, T &&);
  iterator insert(const_iterator, size_type, const T &);
  template<typename InputIterator> 
    iterator insert(const_iterator, InputIterator, InputIterator);
  iterator insert(const_iterator, std::initializer_list< T >);
  iterator erase(const_iterator);
  iterator erase(const_iterator, const_iterator);
  iterator erase(iterator, iterator);
  void swap(devector &) noexcept(no_small_buffer||t_is_nothrow_constructible));
  void clear() noexcept;
};

Description

A vector-like sequence container providing front and back operations (e.g: push_front/pop_front/push_back/pop_back) with amortized linear complexity, small buffer optimization and unsafe methods geared towards additional performance.

Models the SequenceContainer, ReversibleContainer, and AllocatorAwareContainer concepts.

Requires:

T shall be MoveInsertable into the devector.
T shall be Erasable from any devector<T, Allocator, SBP, GP>.
SmallBufferPolicy, GrowthPolicy, and Allocator must model the concepts with the same names.

Definition: T is NothrowConstructible if it's either nothrow move constructible or nothrow copy constructible.

Definition: T is NothrowAssignable if it's either nothrow move assignable or nothrow copy assignable.

Definition: A devector d is small if it has a non-zero size small buffer and d.size() is smaller or equal than the size of the small buffer of d.

Exceptions: The exception specifications assume T is nothrow Destructible.

Most methods providing the strong exception guarantee assume T either has a move constructor marked noexcept or is CopyInsertable into the devector. If it isn't true, and the move constructor throws, the guarantee is waived and the effects are unspecified.

In addition to the exceptions specified in the Throws clause, the following operations of T can throw when any of the specified concept is required (assuming std::allocator is used):

DefaultInsertable: Default constructor
MoveInsertable: Move constructor
CopyInsertable: Copy constructor
DefaultConstructible: Default constructor
EmplaceConstructible: Constructor selected by the given arguments
MoveAssignable: Move assignment operator
CopyAssignable: Copy assignment operator

Furthermore, not noexcept methods throws whatever the allocator throws if memory allocation fails.

Remark: If a method invalidates some iterators, it also invalidates references and pointers to the elements pointed by the invalidated iterators.

Policies:

Models of the SmallBufferPolicy concept must have the following static values:

Type	Name	Description
`size_type`	`size`	The total number of elements that can be stored without allocation

devector_small_buffer_policy models the SmallBufferPolicy concept.

Models of the GrowthPolicy concept must have the following static methods:

Signature	Description
`size_type new_capacity(size_type old_capacity)`	Computes the new capacity to be allocated. The returned value must be greater than `old_capacity`. This method is always used when a new buffer gets allocated.
`bool should_shrink(size_type size, size_type capacity, size_type small_buffer_size)`	Returns `true`, if superfluous memory should be released.

devector_growth_policy models the GrowthPolicy concept.

`devector` public construct/copy/destruct

```
devector() noexcept;
```
Effects: Constructs an empty devector.

Postcondition: empty() && front_free_capacity() == 0 && back_free_capacity() == small buffer size.

Complexity: Constant.
```
explicit devector(const Allocator & allocator) noexcept;
```
Effects: Constructs an empty devector, using the specified allocator.

Postcondition: empty() && front_free_capacity() == 0 && back_free_capacity() == small buffer size.

Complexity: Constant.
```
devector(size_type n, reserve_only_tag, 
         const Allocator & allocator = Allocator());
```
Effects: Constructs an empty devector, using the specified allocator and reserves n slots as if reserve(n) was called.

Postcondition: empty() && front_free_capacity() == 0 && back_free_capacity() >= n.

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
devector(size_type front_cap, size_type back_cap, reserve_only_tag, 
         const Allocator & allocator = Allocator());
```
Effects: Constructs an empty devector, using the specified allocator and reserves front_cap + back_cap slots as if reserve_front(front_cap) and reserve_back(back_cap) was called.

Postcondition: empty() && front_free_capacity() == front_cap && back_free_capacity() >= back_cap.

Exceptions: Strong exception guarantee.

Complexity: Constant.

Remarks: This constructor can be used to split the small buffer between expected front and back insertions.
```
devector(size_type n, unsafe_uninitialized_tag, 
         const Allocator & allocator = Allocator());
```
Unsafe constructor, use with care.

Effects: Constructs a devector containing n uninitialized elements.

Postcondition: size() == n && front_free_capacity() == 0.

Exceptions: Strong exception guarantee.

Complexity: Constant.

Remarks: The devector does not keep track of initialization of the elements, the initially provided uninitialized elements must be manually initialized, e.g: through the pointer returned by data(). This constructor is unsafe because the user must take care of the initialization, before the destructor is called at latest. Failing that, the destructor would invoke undefined behavior if the destructor of T is non-trivial, even if the devectors destructor is called by the stack unwinding effect of an exception.
```
explicit devector(size_type n, const Allocator & allocator = Allocator());
```
Effects: Constructs a devector with n default-inserted elements using the specified allocator.

Requires: T shall be DefaultInsertable into *this.

Postcondition: size() == n && front_free_capacity() == 0.

Exceptions: Strong exception guarantee.

Complexity: Linear in n.
```
devector(size_type n, const T & value, 
         const Allocator & allocator = Allocator());
```
Effects: Constructs a devector with n copies of value, using the specified allocator.

Requires: T shall be CopyInsertable into *this.

Postcondition: size() == n && front_free_capacity() == 0.

Exceptions: Strong exception guarantee.

Complexity: Linear in n.
```
template<typename InputIterator> 
  devector(InputIterator first, InputIterator last, 
           const Allocator & allocator = Allocator());
```
Effects: Constructs a devector equal to the range [first,last), using the specified allocator.

Requires: T shall be EmplaceConstructible into *this from *first. If the specified iterator does not meet the forward iterator requirements, T shall also be MoveInsertable into *this.

Postcondition: `size() == std::distance(first, last)

Exceptions: Strong exception guarantee.

Complexity: Makes only N calls to the copy constructor of T (where N is the distance between first and last), at most one allocation and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes O(N) calls to the copy constructor of T and `O(log(N)) reallocations if they are just input iterators.

Remarks: Each iterator in the range [first,last) shall be dereferenced exactly once, unless an exception is thrown.
```
devector(const devector & x);
```
Effects: Copy constructs a devector.

Requires: T shall be CopyInsertable into *this.

Postcondition: this->size() == x.size() && front_free_capacity() == 0.

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of x.
```
devector(const devector & x, const Allocator & allocator);
```
Effects: Copy constructs a devector, using the specified allocator.

Requires: T shall be CopyInsertable into *this.

Postcondition: this->size() == x.size() && front_free_capacity() == 0.

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of x.
```
devector(devector && rhs) noexcept(no_small_buffer||t_is_nothrow_constructible));
```
Effects: Moves rhs's resources to *this.

Throws: If rhs small and T's move constructor throws.

Postcondition: rhs is left in an unspecified but valid state.

Exceptions: Strong exception guarantee if not noexcept.

Complexity: Linear in the size of the small buffer.
```
devector(devector && rhs, const Allocator & allocator) noexcept(no_small_buffer||t_is_nothrow_constructible));
```
Effects: Moves rhs's resources to *this, using the specified allocator.

Throws: If rhs small and T's move constructor throws.

Postcondition: rhs is left in an unspecified but valid state.

Exceptions: Strong exception guarantee if not noexcept.

Complexity: Linear in the size of the small buffer.

devector(const std::initializer_list< T > & il, 
         const Allocator & allocator = Allocator());

Equivalent to: devector(il.begin(), il.end()) or devector(il.begin(), il.end(), allocator).

```
devector & operator=(const devector & x);
```
Effects: Copies elements of x to *this. Previously held elements get copy assigned to or destroyed.

Requires: T shall be CopyInsertable into *this.

Postcondition: this->size() == x.size(), the elements of *this are copies of elements in x in the same order.

Returns: *this.

Exceptions: Strong exception guarantee if T is NothrowConstructible and the allocator is allowed to be propagated (propagate_on_container_copy_assignment is true), Basic exception guarantee otherwise.

Complexity: Linear in the size of x and *this.
```
devector & operator=(devector && x) noexcept((no_small_buffer||t_is_nothrow_constructible)&&(allocator_traits::propagate_on_move_assignment||allocator_traits::is_always_equal)));
```
Effects: Moves elements of x to *this. Previously held elements get move/copy assigned to or destroyed.

Requires: T shall be MoveInsertable into *this.

Postcondition: x is left in an unspecified but valid state.

Returns: *this.

Exceptions: Basic exception guarantee if not noexcept.

Remark: If x is small or the allocator forbids propagation, the contents of x is moved one-by-one instead of stealing the buffer.

Complexity: Linear in the size of the small buffer plus the size of *this and the size of x if the allocator forbids propagation.
```
devector & operator=(std::initializer_list< T > il);
```
Effects: Copies elements of il to *this. Previously held elements get copy assigned to or destroyed.

Requires: T shall be CopyInsertable into *this and CopyAssignable.

Postcondition: this->size() == il.size(), the elements of *this are copies of elements in il in the same order.

Exceptions: Strong exception guarantee if T is nothrow copy assignable from T and NothrowConstructible, Basic exception guarantee otherwise.

Returns: *this.

Complexity: Linear in the size of il and *this.
```
~devector();
```
Effects: Destroys the devector. All stored values are destroyed and used memory, if any, deallocated.

Complexity: Linear in the size of *this.

`devector` public member functions

```
template<typename InputIterator> 
  void assign(InputIterator first, InputIterator last);
```
Effects: Replaces elements of *this with a copy of [first,last). Previously held elements get copy assigned to or destroyed.

Requires: T shall be EmplaceConstructible from *first. If the specified iterator does not meet the forward iterator requirements, T shall be also MoveInsertable into *this.

Precondition: first and last are not iterators into *this.

Postcondition: size() == N, where N is the distance between first and last.

Exceptions: Strong exception guarantee if T is nothrow copy assignable from *first and NothrowConstructible, Basic exception guarantee otherwise.

Complexity: Linear in the distance between first and last. Makes a single reallocation at most if the iterators first and last are of forward, bidirectional, or random access categories. It makes O(log(N)) reallocations if they are just input iterators.

Remarks: Each iterator in the range [first,last) shall be dereferenced exactly once, unless an exception is thrown.
```
void assign(size_type n, const T & u);
```
Effects: Replaces elements of *this with n copies of u. Previously held elements get copy assigned to or destroyed.

Requires: T shall be CopyInsertable into *this and CopyAssignable.

Precondition: u is not a reference into *this.

Postcondition: size() == n and the elements of *this are copies of u.

Exceptions: Strong exception guarantee if T is nothrow copy assignable from u and NothrowConstructible, Basic exception guarantee otherwise.

Complexity: Linear in n and the size of *this.

void assign(std::initializer_list< T > il);

Equivalent to: assign(il.begin(), il.end()).

```
allocator_type get_allocator() const noexcept;
```
Returns: A copy of the allocator associated with the container.

Complexity: Constant.
```
iterator begin() noexcept;
```
Returns: A iterator pointing to the first element in the devector, or the past the end iterator if the devector is empty.

Complexity: Constant.
```
const_iterator begin() const noexcept;
```
Returns: A constant iterator pointing to the first element in the devector, or the past the end iterator if the devector is empty.

Complexity: Constant.
```
iterator end() noexcept;
```
Returns: An iterator pointing past the last element of the container.

Complexity: Constant.
```
const_iterator end() const noexcept;
```
Returns: A constant iterator pointing past the last element of the container.

Complexity: Constant.
```
reverse_iterator rbegin() noexcept;
```
Returns: A reverse iterator pointing to the first element in the reversed devector, or the reverse past the end iterator if the devector is empty.

Complexity: Constant.
```
const_reverse_iterator rbegin() const noexcept;
```
Returns: A constant reverse iterator pointing to the first element in the reversed devector, or the reverse past the end iterator if the devector is empty.

Complexity: Constant.
```
reverse_iterator rend() noexcept;
```
Returns: A reverse iterator pointing past the last element in the reversed container, or to the beginning of the reversed container if it's empty.

Complexity: Constant.
```
const_reverse_iterator rend() const noexcept;
```
Returns: A constant reverse iterator pointing past the last element in the reversed container, or to the beginning of the reversed container if it's empty.

Complexity: Constant.
```
const_iterator cbegin() const noexcept;
```
Returns: A constant iterator pointing to the first element in the devector, or the past the end iterator if the devector is empty.

Complexity: Constant.
```
const_iterator cend() const noexcept;
```
Returns: A constant iterator pointing past the last element of the container.

Complexity: Constant.
```
const_reverse_iterator crbegin() const noexcept;
```
Returns: A constant reverse iterator pointing to the first element in the reversed devector, or the reverse past the end iterator if the devector is empty.

Complexity: Constant.
```
const_reverse_iterator crend() const noexcept;
```
Returns: A constant reverse iterator pointing past the last element in the reversed container, or to the beginning of the reversed container if it's empty.

Complexity: Constant.
```
bool empty() const noexcept;
```
Returns: True, if size() == 0, false otherwise.

Complexity: Constant.
```
size_type size() const noexcept;
```
Returns: The number of elements the devector contains.

Complexity: Constant.
```
size_type max_size() const noexcept;
```
Returns: The maximum number of elements the devector could possibly hold.

Complexity: Constant.
```
size_type capacity() const noexcept;
```
Returns: The total number of elements that the devector can hold without requiring reallocation.

Complexity: Constant.
```
size_type front_free_capacity() const noexcept;
```
Returns: The total number of elements that can be pushed to the front of the devector without requiring reallocation.

Complexity: Constant.
```
size_type back_free_capacity() const noexcept;
```
Returns: The total number of elements that can be pushed to the back of the devector without requiring reallocation.

Complexity: Constant.
```
void resize(size_type sz);
```
Equivalent to: resize_back(sz)
```
void resize(size_type sz, const T & c);
```
Equivalent to: resize_back(sz, c)
```
void resize_front(size_type sz);
```
Effects: If sz is greater than the size of *this, additional value-initialized elements are inserted to the front. Invalidates iterators if reallocation is needed. If sz is smaller than than the size of *this, elements are popped from the front.

Requires: T shall be MoveInsertable into *this and DefaultConstructible.

Postcondition: sz == size().

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of *this and sz.
```
void resize_front(size_type sz, const T & c);
```
Effects: If sz is greater than the size of *this, copies of c are inserted to the front. Invalidates iterators if reallocation is needed. If sz is smaller than than the size of *this, elements are popped from the front.

Postcondition: sz == size().

Requires: T shall be CopyInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of *this and sz.
```
void resize_back(size_type sz);
```
Effects: If sz is greater than the size of *this, additional value-initialized elements are inserted to the back. Invalidates iterators if reallocation is needed. If sz is smaller than than the size of *this, elements are popped from the back.

Requires: T shall be MoveInsertable into *this and DefaultConstructible.

Postcondition: sz == size().

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of *this and sz.
```
void resize_back(size_type sz, const T & c);
```
Effects: If sz is greater than the size of *this, copies of c are inserted to the back. If sz is smaller than than the size of *this, elements are popped from the back.

Postcondition: sz == size().

Requires: T shall be CopyInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of *this and sz.
```
void unsafe_uninitialized_resize_front(size_type n);
```
Unsafe method, use with care.

Effects: Changes the size of the devector without properly initializing the extra or destroying the superfluous elements. If n < size(), elements are removed from the front without getting destroyed; if n > size(), uninitialized elements are added before the first element at the front. Invalidates iterators if reallocation is needed.

Postcondition: size() == n.

Exceptions: Strong exception guarantee.

Complexity: Linear in size() if capacity() < n, constant otherwise.

Remarks: The devector does not keep track of initialization of the elements: Elements without a trivial destructor must be manually destroyed before shrinking, elements without a trivial constructor must be initialized after growing.
```
void unsafe_uninitialized_resize_back(size_type n);
```
Unsafe method, use with care.

Effects: Changes the size of the devector without properly initializing the extra or destroying the superfluous elements. If n < size(), elements are removed from the back without getting destroyed; if n > size(), uninitialized elements are added after the last element at the back. Invalidates iterators if reallocation is needed.

Postcondition: size() == n.

Exceptions: Strong exception guarantee.

Complexity: Linear in size() if capacity() < n, constant otherwise.

Remarks: The devector does not keep track of initialization of the elements: Elements without a trivial destructor must be manually destroyed before shrinking, elements without a trivial constructor must be initialized after growing.
```
void reserve(size_type new_capacity);
```
Equivalent to: reserve_back(new_capacity)
```
void reserve_front(size_type new_capacity);
```
Effects: Ensures that n elements can be pushed to the front without requiring reallocation, where n is new_capacity - size(), if n is positive. Otherwise, there are no effects. Invalidates iterators if reallocation is needed.

Requires: T shall be MoveInsertable into *this.

Complexity: Linear in the size of *this.

Exceptions: Strong exception guarantee.

Throws: std::length_error if new_capacity > max_size().
```
void reserve_back(size_type new_capacity);
```
Effects: Ensures that n elements can be pushed to the back without requiring reallocation, where n is new_capacity - size(), if n is positive. Otherwise, there are no effects. Invalidates iterators if reallocation is needed.

Requires: T shall be MoveInsertable into *this.

Complexity: Linear in the size of *this.

Exceptions: Strong exception guarantee.

Throws: length_error if new_capacity > max_size().
```
void shrink_to_fit();
```
Effects: Reduces capacity() to max(size(), small buffer size) if the GrowthPolicy allows it (should_shrink returns true), otherwise, there are no effects. Invalidates iterators if shrinks. If shrinks and they fit, moves the contained elements back to the small buffer.

Requires: T shall be MoveInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Linear in the size of *this.
```
reference operator[](size_type n) noexcept;
```
Returns: A reference to the nth element in the devector.

Precondition: n < size().

Complexity: Constant.
```
const_reference operator[](size_type n) const noexcept;
```
Returns: A constant reference to the nth element in the devector.

Precondition: n < size().

Complexity: Constant.
```
reference at(size_type n);
```
Returns: A reference to the nth element in the devector.

Throws: std::out_of_range, if n >= size().

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
const_reference at(size_type n) const;
```
Returns: A constant reference to the nth element in the devector.

Throws: std::out_of_range, if n >= size().

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
reference front() noexcept;
```
Returns: A reference to the first element in the devector.

Precondition: !empty().

Complexity: Constant.
```
const_reference front() const noexcept;
```
Returns: A constant reference to the first element in the devector.

Precondition: !empty().

Complexity: Constant.
```
reference back() noexcept;
```
Returns: A reference to the last element in the devector.

Precondition: !empty().

Complexity: Constant.
```
const_reference back() const noexcept;
```
Returns: A constant reference to the last element in the devector.

Precondition: !empty().

Complexity: Constant.
```
T * data() noexcept;
```
Returns: A pointer to the underlying array serving as element storage. The range [data(); data() + size()) is always valid. For a non-empty devector, data() == &front().

Complexity: Constant.
```
const T * data() const noexcept;
```
Returns: A constant pointer to the underlying array serving as element storage. The range [data(); data() + size()) is always valid. For a non-empty devector, data() == &front().

Complexity: Constant.
```
template<class... Args> void emplace_front(Args &&... args);
```
Effects: Pushes a new element to the front of the devector. The element is constructed in-place, using the perfect forwarded args as constructor arguments. Invalidates iterators if reallocation is needed. (front_free_capacity() == 0)

Requires: T shall be EmplaceConstructible from args and MoveInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Amortized linear in the size of *this. (Constant, if front_free_capacity() > 0)
```
void push_front(const T & x);
```
Effects: Pushes the copy of x to the front of the devector. Invalidates iterators if reallocation is needed. (front_free_capacity() == 0)

Requires: T shall be CopyInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Amortized linear in the size of *this. (Constant, if front_free_capacity() > 0)
```
void push_front(T && x);
```
Effects: Move constructs a new element at the front of the devector using x. Invalidates iterators if reallocation is needed. (front_free_capacity() == 0)

Requires: T shall be MoveInsertable into *this.

Exceptions: Strong exception guarantee, not regarding the state of x.

Complexity: Amortized linear in the size of *this. (Constant, if front_free_capacity() > 0)
```
void unsafe_push_front(const T & x);
```
Effects: Pushes the copy of x to the front of the devector.

Requires: T shall be CopyInsertable into *this.

Precondition: front_free_capacity() > 0.

Postcondition: size() is incremented by 1, front_free_capacity() is decremented by 1

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
void unsafe_push_front(T && x);
```
Effects: Move constructs a new element at the front of the devector using x.

Requires: T shall be MoveInsertable into *this.

Precondition: front_free_capacity() > 0.

Postcondition: size() is incremented by 1, front_free_capacity() is decremented by 1

Exceptions: Strong exception guarantee, not regarding the state of x.

Complexity: Constant.
```
void pop_front() noexcept;
```
Effects: Removes the first element of *this.

Precondition: !empty().

Postcondition: front_free_capacity() is incremented by 1.

Complexity: Constant.
```
template<class... Args> void emplace_back(Args &&... args);
```
Effects: Pushes a new element to the back of the devector. The element is constructed in-place, using the perfect forwarded args as constructor arguments. Invalidates iterators if reallocation is needed. (back_free_capacity() == 0)

Requires: T shall be EmplaceConstructible from args and MoveInsertable into *this, and MoveAssignable.

Exceptions: Strong exception guarantee.

Complexity: Amortized linear in the size of *this. (Constant, if back_free_capacity() > 0)
```
void push_back(const T & x);
```
Effects: Pushes the copy of x to the back of the devector. Invalidates iterators if reallocation is needed. (back_free_capacity() == 0)

Requires: T shall be CopyInsertable into *this.

Exceptions: Strong exception guarantee.

Complexity: Amortized linear in the size of *this. (Constant, if back_free_capacity() > 0)
```
void push_back(T && x);
```
Effects: Move constructs a new element at the back of the devector using x. Invalidates iterators if reallocation is needed. (back_free_capacity() == 0)

Requires: T shall be MoveInsertable into *this.

Exceptions: Strong exception guarantee, not regarding the state of x.

Complexity: Amortized linear in the size of *this. (Constant, if back_free_capacity() > 0)
```
void unsafe_push_back(const T & x);
```
Effects: Pushes the copy of x to the back of the devector.

Requires: T shall be CopyInsertable into *this.

Precondition: back_free_capacity() > 0.

Postcondition: size() is incremented by 1, back_free_capacity() is decremented by 1

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
void unsafe_push_back(T && x);
```
Effects: Move constructs a new element at the back of the devector using x.

Requires: T shall be MoveInsertable into *this.

Precondition: back_free_capacity() > 0.

Postcondition: size() is incremented by 1, back_free_capacity() is decremented by 1

Exceptions: Strong exception guarantee, not regarding the state of x.

Complexity: Constant.
```
void pop_back() noexcept;
```
Effects: Removes the last element of *this.

Precondition: !empty().

Postcondition: back_free_capacity() is incremented by 1.

Complexity: Constant.
```
template<class... Args> 
  iterator emplace(const_iterator position, Args &&... args);
```
Effects: Constructs a new element before the element pointed by position. The element is constructed in-place, using the perfect forwarded args as constructor arguments. Invalidates iterators if reallocation is needed.

Requires: T shall be EmplaceConstructible, and MoveInsertable into *this, and MoveAssignable.

Returns: Iterator pointing to the newly constructed element.

Exceptions: Strong exception guarantee if T is NothrowConstructible and NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in the size of *this.
```
iterator insert(const_iterator position, const T & x);
```
Effects: Copy constructs a new element before the element pointed by position, using x as constructor argument. Invalidates iterators if reallocation is needed.

Requires: T shall be CopyInsertable into *this and and CopyAssignable.

Returns: Iterator pointing to the newly constructed element.

Exceptions: Strong exception guarantee if T is NothrowConstructible and NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in the size of *this.
```
iterator insert(const_iterator position, T && x);
```
Effects: Move constructs a new element before the element pointed by position, using x as constructor argument. Invalidates iterators if reallocation is needed.

Requires: T shall be MoveInsertable into *this and and CopyAssignable.

Returns: Iterator pointing to the newly constructed element.

Exceptions: Strong exception guarantee if T is NothrowConstructible and NothrowAssignable (not regarding the state of x), Basic exception guarantee otherwise.

Complexity: Linear in the size of *this.
```
iterator insert(const_iterator position, size_type n, const T & x);
```
Effects: Copy constructs n elements before the element pointed by position, using x as constructor argument. Invalidates iterators if reallocation is needed.

Requires: T shall be CopyInsertable into *this and and CopyAssignable.

Returns: Iterator pointing to the first inserted element, or position, if n is zero.

Exceptions: Strong exception guarantee if T is NothrowConstructible and NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in the size of *this and n.
```
template<typename InputIterator> 
  iterator insert(const_iterator position, InputIterator first, 
                  InputIterator last);
```
Effects: Copy constructs elements before the element pointed by position using each element in the rage pointed by first and last as constructor arguments. Invalidates iterators if reallocation is needed.

Requires: T shall be EmplaceConstructible into *this from *first. If the specified iterator does not meet the forward iterator requirements, T shall also be MoveInsertable into *this and MoveAssignable.

Precondition: first and last are not iterators into *this.

Returns: Iterator pointing to the first inserted element, or position, if first == last.

Complexity: Linear in the size of *this and N (where N is the distance between first and last). Makes only N calls to the constructor of T and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of T and allocates memory twice at most if they are just input iterators.

Exceptions: Strong exception guarantee if T is NothrowConstructible and NothrowAssignable, Basic exception guarantee otherwise.

Remarks: Each iterator in the range [first,last) shall be dereferenced exactly once, unless an exception is thrown.

iterator insert(const_iterator position, std::initializer_list< T > il);

Equivalent to: insert(position, il.begin(), il.end())

```
iterator erase(const_iterator position);
```
Effects: Destroys the element pointed by position and removes it from the devector. Invalidates iterators.

Requires: T shall be MoveAssignable.

Precondition: position must be in the range of [begin(), end()).

Returns: Iterator pointing to the element immediately following the erased element prior to its erasure. If no such element exists, end() is returned.

Exceptions: Strong exception guarantee if T is NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in half the size of *this.
```
iterator erase(const_iterator first, const_iterator last);
```
Effects: Destroys the range [first,last) and removes it from the devector. Invalidates iterators.

Requires: T shall be MoveAssignable.

Precondition: [first,last) must be in the range of [begin(), end()).

Returns: Iterator pointing to the element pointed to by last prior to any elements being erased. If no such element exists, end() is returned.

Exceptions: Strong exception guarantee if T is NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in half the size of *this plus the distance between first and last.
```
iterator erase(iterator first, iterator last);
```
Effects: Destroys the range [first,last) and removes it from the devector. Invalidates iterators.

Requires: T shall be MoveAssignable.

Precondition: [first,last) must be in the range of [begin(), end()).

Returns: Iterator pointing to the element pointed to by last prior to any elements being erased. If no such element exists, end() is returned.

Exceptions: Strong exception guarantee if T is NothrowAssignable, Basic exception guarantee otherwise.

Complexity: Linear in half the size of *this.
```
void swap(devector & b) noexcept(no_small_buffer||t_is_nothrow_constructible));
```
Effects: exchanges the contents of *this and b. Invalidates iterators to elements stored in small buffer before swapping.

Requires: instances of T must be swappable by unqualified call of swap and T must be MoveInsertable into *this.

Precondition: The allocators should allow propagation or should compare equal.

Exceptions: Basic exceptions guarantee if not noexcept.

Complexity: Linear in the size of the small buffer.

Remarks: If both devectors are small, elements are exchanged one by one. If exactly one is small, elements in the small buffer are moved to the small buffer of the other devector and the large buffer is acquired by the previously small devector. If neither are small, buffers are exchanged in one step.
```
void clear() noexcept;
```
Effects: Destroys all elements in the devector. Invalidates all references, pointers and iterators to the elements of the devector.

Postcondition: empty() && front_free_capacity() == 0 && back_free_capacity() == small buffer size.

Complexity: Linear in the size of *this.

Remarks: Does not free memory.