Class template devector

boost::container::devector

Synopsis

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

template<typename T, typename A = void, typename Options = void> 
class devector {
public:
  // types
  typedef T                                                   value_type;            
  typedef implementation_defined                              allocator_type;        
  typedef allocator_type                                      stored_allocator_type; 
  typedef allocator_traits< allocator_type >::pointer         pointer;               
  typedef allocator_traits< allocator_type >::const_pointer   const_pointer;         
  typedef allocator_traits< allocator_type >::reference       reference;             
  typedef allocator_traits< allocator_type >::const_reference const_reference;       
  typedef allocator_traits< allocator_type >::size_type       size_type;             
  typedef allocator_traits< allocator_type >::difference_type difference_type;       
  typedef pointer                                             iterator;              
  typedef const_pointer                                       const_iterator;        
  typedef implementation_defined                              reverse_iterator;      
  typedef implementation_defined                              const_reverse_iterator;

  // construct/copy/destruct
  devector() noexcept;
  explicit devector(const allocator_type &) noexcept;
  devector(size_type, reserve_only_tag_t, 
           const allocator_type & = allocator_type());
  devector(size_type, size_type, reserve_only_tag_t, 
           const allocator_type & = allocator_type());
  explicit devector(size_type, const allocator_type & = allocator_type());
  explicit devector(size_type, default_init_t, 
                    const allocator_type & = allocator_type());
  devector(size_type, const T &, const allocator_type & = allocator_type());
  template<typename InputIterator> 
    devector(InputIterator, InputIterator, 
             const allocator_type & = allocator_type() BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or< void BOOST_MOVE_I dtl::is_convertible< InputIterator BOOST_MOVE_I size_type > BOOST_MOVE_I dtl::is_not_input_iterator< InputIterator > >::type *=0));
  devector(const devector &);
  devector(const devector &, const allocator_type &);
  devector(devector &&) noexcept;
  devector(devector &&, const allocator_type &);
  devector(const std::initializer_list< T > &, 
           const allocator_type & = allocator_type());
  devector & operator=(const devector &);
  devector & operator=(devector &&) noexcept(allocator_traits_type::propagate_on_container_move_assignment::value||allocator_traits_type::is_always_equal::value);
  devector & operator=(std::initializer_list< T >);
  ~devector();

  // public member functions
  template<typename InputIterator> 
    void assign(InputIterator, InputIterator last );
  void assign(size_type, const T &);
  void assign(std::initializer_list< T >);
  allocator_type get_allocator() const noexcept;
  const allocator_type & get_stored_allocator() const noexcept;
  allocator_type & get_stored_allocator() 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, default_init_t);
  void resize(size_type, const T &);
  void resize_front(size_type);
  void resize_front(size_type, default_init_t);
  void resize_front(size_type, const T &);
  void resize_back(size_type);
  void resize_back(size_type, default_init_t);
  void resize_back(size_type, const T &);
  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> reference emplace_front(Args &&...);
  void push_front(const T &);
  void push_front(T &&);
  void pop_front() noexcept;
  template<class... Args> reference emplace_back(Args &&...);
  void push_back(const T &);
  void 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 last );
  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(allocator_traits_type::propagate_on_container_swap::value||allocator_traits_type::is_always_equal::value);
  void clear() noexcept;

  // private member functions
  size_type pos_to_index(const_iterator) const;
  bool should_move_back(const_iterator) const;
  size_type front_capacity() const;
  size_type back_capacity() const;

  // private static functions
  static iterator unconst_iterator(const_iterator);
};

Description

A vector-like sequence container providing front and back operations (e.g: push_front/pop_front/push_back/pop_back) with amortized constant complexity.

Models the SequenceContainer, ReversibleContainer, and AllocatorAwareContainer concepts.

Requires:

T shall be MoveInsertable into the devector.
T shall be Erasable from any devector<T, allocator_type, GP>.
GrowthFactor, and Allocator must model the concepts with the same names or be void.

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.

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:

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. Such methods also throw length_error if the capacity exceeds max_size().

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

Template Parameters

```
typename T
```
```
typename A = void
```
```
typename Options = void
```
A type produced from boost::container::devector_options.

`devector` public construct/copy/destruct

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

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

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

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

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

Postcondition: empty() && capacity() >= n.

Exceptions: Strong exception guarantee.

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

Postcondition: empty() && front_free_capacity() >= front_free_cap && back_free_capacity() >= back_free_cap.

Exceptions: Strong exception guarantee.

Complexity: Constant.
```
explicit devector(size_type n, 
                  const allocator_type & allocator = allocator_type());
```
Effects: Constructs a devector with n value_initialized elements using the specified allocator.

Requires: T shall be DefaultInsertable into *this.

Postcondition: size() == n.

Exceptions: Strong exception guarantee.

Complexity: Linear in n.
```
explicit devector(size_type n, default_init_t, 
                  const allocator_type & allocator = allocator_type());
```
Effects: Constructs a devector with n default-initialized elements using the specified allocator.

Requires: T shall be [DefaultInsertable] into *this.

Postcondition: size() == n.

Exceptions: Strong exception guarantee.

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

Requires: T shall be CopyInsertable into *this.

Postcondition: size() == n.

Exceptions: Strong exception guarantee.

Complexity: Linear in n.
```
template<typename InputIterator> 
  devector(InputIterator first, InputIterator last, 
           const allocator_type & allocator = allocator_type() BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or< void BOOST_MOVE_I dtl::is_convertible< InputIterator BOOST_MOVE_I size_type > BOOST_MOVE_I dtl::is_not_input_iterator< InputIterator > >::type *=0));
```
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() == boost::container::iterator_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().

Exceptions: Strong exception guarantee.

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

Requires: T shall be CopyInsertable into *this.

Postcondition: *this == x.

Exceptions: Strong exception guarantee.

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

Throws: Nothing.

Postcondition: *this has the same value rhs had before the operation. rhs is left in an unspecified but valid state.

Exceptions: Strong exception guarantee if not noexcept.

Complexity: Constant.
```
devector(devector && rhs, const allocator_type & allocator);
```
Effects: Moves rhs's resources to *this, using the specified allocator.

Throws: If allocation or T's move constructor throws.

Postcondition: *this has the same value rhs had before the operation. rhs is left in an unspecified but valid state.

Exceptions: Strong exception guarantee if not noexcept.

Complexity: Linear if allocator != rhs.get_allocator(), otherwise constant.

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

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

```
devector & operator=(const devector & rhs);
```
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(allocator_traits_type::propagate_on_container_move_assignment::value||allocator_traits_type::is_always_equal::value);
```
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.

Complexity: Constant if allocator_traits_type:: propagate_on_container_move_assignment is true or this->get>allocator() == x.get_allocator(). Linear otherwise.
```
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  BOOST_CONTAINER_DOCIGN);
```
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.

const allocator_type & get_stored_allocator() const noexcept;

allocator_type & get_stored_allocator() noexcept;

```
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 minimum number of elements that can be inserted into devector using position-based insertions without requiring a reallocation. Note that, unlike in typical sequence containers like vector, capacity(), capacity() can be smaller than size(). This can happen if a user inserts elements in a particular way (usually inserting at front up to front_free_capacity() and at back up to back_free_capacity()).

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);
```
Effects: If sz is greater than the size of *this, additional value-initialized elements are inserted. Invalidates iterators if reallocation is needed. If sz is smaller than than the size of *this, elements are erased from the extremes.

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(size_type sz, default_init_t);
```
Effects: Same as resize(sz) but creates default-initialized value-initialized.
```
void resize(size_type sz, const T & c);
```
Effects: If sz is greater than the size of *this, copies of c are inserted at extremes. If sz is smaller than than the size of *this, elements are popped from the extremes.

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_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, default_init_t);
```
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 default_initializable.

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, default_init_t);
```
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 default initializable.

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 reserve(size_type new_capacity);
```
Effects: Ensures that at least n elements can be inserted 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 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: 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 size(). Invalidates iterators.

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: out_of_range, if n >= size().

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

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

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> reference 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 constant 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 constant 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 constant in the size of *this. (Constant, if front_free_capacity() > 0)
```
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> reference 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 constant in the size of *this. (Constant, if back_free_capacity() > 0)
```
void push_back(const T & x);
```
defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
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 constant 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 constant in the size of *this. (Constant, if back_free_capacity() > 0)
```
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);
```
defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
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  BOOST_CONTAINER_DOCIGN);
```
Effects: Copy constructs elements before the element pointed by position using each element in the range 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 `O(log(N)) reallocations 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(allocator_traits_type::propagate_on_container_swap::value||allocator_traits_type::is_always_equal::value);
```
Effects: exchanges the contents of *this and b.

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: Constant.
```
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() == old capacity.

Complexity: Linear in the size of *this.

Remarks: Does not free memory.

`devector` private member functions

size_type pos_to_index(const_iterator i) const;

bool should_move_back(const_iterator i) const;

```
size_type front_capacity() const;
```
```
size_type back_capacity() const;
```

`devector` private static functions

static iterator unconst_iterator(const_iterator i);