Class template stable

Class template stable_vector

boost::container::stable_vector

Synopsis

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

template<typename T, typename A = std::allocator<T> > 
class stable_vector {
public:
  // types
  typedef allocator_traits_type::reference        reference;             
  typedef allocator_traits_type::const_reference  const_reference;       
  typedef allocator_traits_type::pointer          pointer;               
  typedef allocator_traits_type::const_pointer    const_pointer;         
  typedef unspecified                             iterator;              
  typedef unspecified                             const_iterator;        
  typedef impl_type::size_type                    size_type;             
  typedef iterator::difference_type               difference_type;       
  typedef T                                       value_type;            
  typedef A                                       allocator_type;        
  typedef std::reverse_iterator< iterator >       reverse_iterator;      
  typedef std::reverse_iterator< const_iterator > const_reverse_iterator;
  typedef node_allocator_type                     stored_allocator_type; 

  // construct/copy/destruct
  stable_vector();
  explicit stable_vector(const A &);
  explicit stable_vector(size_type);
  stable_vector(size_type, const T &, const A & = A());
  template<typename InputIterator> 
    stable_vector(InputIterator, InputIterator, const A & = A());
  stable_vector(const stable_vector &);
  stable_vector(stable_vector &&);
  stable_vector& operator=(const stable_vector &);
  stable_vector& operator=(stable_vector &&);
  ~stable_vector();

  // public member functions
  template<typename InputIterator> void assign(InputIterator, InputIterator);
  void assign(size_type, const T &);
  allocator_type get_allocator() const;
  const stored_allocator_type & get_stored_allocator() const;
  stored_allocator_type & get_stored_allocator();
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;
  const_iterator cbegin() const;
  const_iterator cend() const;
  const_reverse_iterator crbegin() const;
  const_reverse_iterator crend() const;
  size_type size() const;
  size_type max_size() const;
  size_type capacity() const;
  bool empty() const;
  void resize(size_type, const T &);
  void resize(size_type);
  void reserve(size_type);
  reference operator[](size_type);
  const_reference operator[](size_type) const;
  reference at(size_type);
  const_reference at(size_type) const;
  reference front();
  const_reference front() const;
  reference back();
  const_reference back() const;
  void push_back(const T &);
  void push_back(T &&);
  void pop_back();
  iterator insert(const_iterator, const T &);
  iterator insert(const_iterator, T &&);
  void insert(const_iterator, size_type, const T &);
  template<typename InputIterator> 
    void insert(const_iterator, InputIterator, InputIterator);
  template<class... Args> void emplace_back(Args &&...);
  template<class... Args> iterator emplace(const_iterator, Args &&...);
  iterator erase(const_iterator);
  iterator erase(const_iterator, const_iterator);
  void swap(stable_vector &);
  void clear();
  void shrink_to_fit();
};

Description

Originally developed by Joaquin M. Lopez Munoz, stable_vector is std::vector drop-in replacement implemented as a node container, offering iterator and reference stability.

More details taken the author's blog: (Introducing stable_vector)

We present stable_vector, a fully STL-compliant stable container that provides most of the features of std::vector except element contiguity.

General properties: stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in std::vector. Like std::vector, iterators are random access. stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a stable_vector remain valid as long as the element is not erased, and an iterator that has been assigned the return value of end() always remain valid until the destruction of the associated stable_vector.

Operation complexity: The big-O complexities of stable_vector operations match exactly those of std::vector. In general, insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector does not internally perform any value_type destruction, copy or assignment operations other than those exactly corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of performance for the extra burden of doing more pointer manipulation and an additional allocation per element.

Exception safety: As stable_vector does not internally copy elements around, some operations provide stronger exception safety guarantees than in std::vector:

`stable_vector` public construct/copy/destruct

```
stable_vector();
```
Effects: Default constructs a stable_vector.

Throws: If allocator_type's default constructor throws.

Complexity: Constant.
```
explicit stable_vector(const A & al);
```
Effects: Constructs a stable_vector taking the allocator as parameter.

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
explicit stable_vector(size_type n);
```
Effects: Constructs a stable_vector that will use a copy of allocator a and inserts n default contructed values.

Throws: If allocator_type's default constructor or copy constructor throws or T's default or copy constructor throws.

Complexity: Linear to n.
```
stable_vector(size_type n, const T & t, const A & al = A());
```
Effects: Constructs a stable_vector that will use a copy of allocator a and inserts n copies of value.

Throws: If allocator_type's default constructor or copy constructor throws or T's default or copy constructor throws.

Complexity: Linear to n.
```
template<typename InputIterator> 
  stable_vector(InputIterator first, InputIterator last, const A & al = A());
```
Effects: Constructs a stable_vector that will use a copy of allocator a and inserts a copy of the range [first, last) in the stable_vector.

Throws: If allocator_type's default constructor or copy constructor throws or T's constructor taking an dereferenced InIt throws.

Complexity: Linear to the range [first, last).
```
stable_vector(const stable_vector & x);
```
Effects: Copy constructs a stable_vector.

Postcondition: x == *this.

Complexity: Linear to the elements x contains.
```
stable_vector(stable_vector && x);
```
Effects: Move constructor. Moves mx's resources to *this.

Throws: If allocator_type's copy constructor throws.

Complexity: Constant.
```
stable_vector& operator=(const stable_vector & x);
```
Effects: Makes *this contain the same elements as x.

Postcondition: this->size() == x.size(). *this contains a copy of each of x's elements.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Linear to the number of elements in x.
```
stable_vector& operator=(stable_vector && x);
```
Effects: Move assignment. All mx's values are transferred to *this.

Postcondition: x.empty(). *this contains a the elements x had before the function.

Throws: If allocator_type's copy constructor throws.

Complexity: Linear.
```
~stable_vector();
```
Effects: Destroys the stable_vector. All stored values are destroyed and used memory is deallocated.

Throws: Nothing.

Complexity: Linear to the number of elements.

`stable_vector` public member functions

```
template<typename InputIterator> 
  void assign(InputIterator first, InputIterator last);
```
Effects: Assigns the the range [first, last) to *this.

Throws: If memory allocation throws or T's constructor from dereferencing InpIt throws.

Complexity: Linear to n.
```
void assign(size_type n, const T & t);
```
Effects: Assigns the n copies of val to *this.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Linear to n.
```
allocator_type get_allocator() const;
```
Effects: Returns a copy of the internal allocator.

Throws: If allocator's copy constructor throws.

Complexity: Constant.
```
const stored_allocator_type & get_stored_allocator() const;
```
Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.
```
stored_allocator_type & get_stored_allocator();
```
Effects: Returns a reference to the internal allocator.

Throws: Nothing

Complexity: Constant.

Note: Non-standard extension.
```
iterator begin();
```
Effects: Returns an iterator to the first element contained in the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_iterator begin() const;
```
Effects: Returns a const_iterator to the first element contained in the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
iterator end();
```
Effects: Returns an iterator to the end of the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_iterator end() const;
```
Effects: Returns a const_iterator to the end of the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rbegin();
```
Effects: Returns a reverse_iterator pointing to the beginning of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
reverse_iterator rend();
```
Effects: Returns a reverse_iterator pointing to the end of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator rend() const;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cbegin() const;
```
Effects: Returns a const_iterator to the first element contained in the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_iterator cend() const;
```
Effects: Returns a const_iterator to the end of the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crbegin() const;
```
Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
const_reverse_iterator crend() const;
```
Effects: Returns a const_reverse_iterator pointing to the end of the reversed stable_vector.

Throws: Nothing.

Complexity: Constant.
```
size_type size() const;
```
Effects: Returns the number of the elements contained in the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
size_type max_size() const;
```
Effects: Returns the largest possible size of the stable_vector.

Throws: Nothing.

Complexity: Constant.
```
size_type capacity() const;
```
Effects: Number of elements for which memory has been allocated. capacity() is always greater than or equal to size().

Throws: Nothing.

Complexity: Constant.
```
bool empty() const;
```
Effects: Returns true if the stable_vector contains no elements.

Throws: Nothing.

Complexity: Constant.
```
void resize(size_type n, const T & t);
```
Effects: Inserts or erases elements at the end such that the size becomes n. New elements are copy constructed from x.

Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to the difference between size() and new_size.
```
void resize(size_type n);
```
Effects: Inserts or erases elements at the end such that the size becomes n. New elements are default constructed.

Throws: If memory allocation throws, or T's copy constructor throws.

Complexity: Linear to the difference between size() and new_size.
```
void reserve(size_type n);
```
Effects: If n is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged.

Throws: If memory allocation allocation throws.
```
reference operator[](size_type n);
```
Requires: size() > n.

Effects: Returns a reference to the nth element from the beginning of the container.

Throws: Nothing.

Complexity: Constant.
```
const_reference operator[](size_type n) const;
```
Requires: size() > n.

Effects: Returns a const reference to the nth element from the beginning of the container.

Throws: Nothing.

Complexity: Constant.
```
reference at(size_type n);
```
Requires: size() > n.

Effects: Returns a reference to the nth element from the beginning of the container.

Throws: std::range_error if n >= size()

Complexity: Constant.
```
const_reference at(size_type n) const;
```
Requires: size() > n.

Effects: Returns a const reference to the nth element from the beginning of the container.

Throws: std::range_error if n >= size()

Complexity: Constant.
```
reference front();
```
Requires: !empty()

Effects: Returns a reference to the first element of the container.

Throws: Nothing.

Complexity: Constant.
```
const_reference front() const;
```
Requires: !empty()

Effects: Returns a const reference to the first element of the container.

Throws: Nothing.

Complexity: Constant.
```
reference back();
```
Requires: !empty()

Effects: Returns a reference to the last element of the container.

Throws: Nothing.

Complexity: Constant.
```
const_reference back() const;
```
Requires: !empty()

Effects: Returns a const reference to the last element of the container.

Throws: Nothing.

Complexity: Constant.
```
void push_back(const T & x);
```
Effects: Inserts a copy of x at the end of the stable_vector.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Amortized constant time.
```
void push_back(T && t);
```
Effects: Constructs a new element in the end of the stable_vector and moves the resources of mx to this new element.

Throws: If memory allocation throws.

Complexity: Amortized constant time.
```
void pop_back();
```
Effects: Removes the last element from the stable_vector.

Throws: Nothing.

Complexity: Constant time.
```
iterator insert(const_iterator position, const T & x);
```
Requires: position must be a valid iterator of *this.

Effects: Insert a copy of x before position.

Throws: If memory allocation throws or x's copy constructor throws.

Complexity: If position is end(), amortized constant time Linear time otherwise.
```
iterator insert(const_iterator position, T && x);
```
Requires: position must be a valid iterator of *this.

Effects: Insert a new element before position with mx's resources.

Throws: If memory allocation throws.

Complexity: If position is end(), amortized constant time Linear time otherwise.
```
void insert(const_iterator position, size_type n, const T & t);
```
Requires: pos must be a valid iterator of *this.

Effects: Insert n copies of x before pos.

Throws: If memory allocation throws or T's copy constructor throws.

Complexity: Linear to n.
```
template<typename InputIterator> 
  void insert(const_iterator position, InputIterator first, 
              InputIterator last);
```
Requires: pos must be a valid iterator of *this.

Effects: Insert a copy of the [first, last) range before pos.

Throws: If memory allocation throws, T's constructor from a dereferenced InpIt throws or T's copy constructor throws.

Complexity: Linear to std::distance [first, last).
```
template<class... Args> void emplace_back(Args &&... args);
```
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the end of the stable_vector.

Throws: If memory allocation throws or the in-place constructor throws.

Complexity: Amortized constant time.
```
template<class... Args> 
  iterator emplace(const_iterator position, Args &&... args);
```
Requires: position must be a valid iterator of *this.

Effects: Inserts an object of type T constructed with std::forward<Args>(args)... before position

Throws: If memory allocation throws or the in-place constructor throws.

Complexity: If position is end(), amortized constant time Linear time otherwise.
```
iterator erase(const_iterator position);
```
Effects: Erases the element at position pos.

Throws: Nothing.

Complexity: Linear to the elements between pos and the last element. Constant if pos is the last element.
```
iterator erase(const_iterator first, const_iterator last);
```
Effects: Erases the elements pointed by [first, last).

Throws: Nothing.

Complexity: Linear to the distance between first and last plus linear to the elements between pos and the last element.
```
void swap(stable_vector & x);
```
Effects: Swaps the contents of *this and x.

Throws: Nothing.

Complexity: Constant.
```
void clear();
```
Effects: Erases all the elements of the stable_vector.

Throws: Nothing.

Complexity: Linear to the number of elements in the stable_vector.
```
void shrink_to_fit();
```
Effects: Tries to deallocate the excess of memory created with previous allocations. The size of the stable_vector is unchanged

Throws: If memory allocation throws.

Complexity: Linear to size().