Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template stable_vector

boost::container::stable_vector

Synopsis

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

template<typename T, typename Allocator = void> 
class stable_vector {
public:
  // types
  typedef T                                                                       ;            
  typedef ::boost::container::allocator_traits< ValueAllocator >::         ;               
  typedef ::boost::container::allocator_traits< ValueAllocator >::   ;         
  typedef ::boost::container::allocator_traits< ValueAllocator >::       ;             
  typedef ::boost::container::allocator_traits< ValueAllocator >:: ;       
  typedef ::boost::container::allocator_traits< ValueAllocator >::       ;             
  typedef ::boost::container::allocator_traits< ValueAllocator >:: ;       
  typedef ValueAllocator                                                          ;        
  typedef node_allocator_type                                                     ; 
  typedef implementation_defined                                                  ;              
  typedef implementation_defined                                                  ;        
  typedef implementation_defined                                                  ;      
  typedef implementation_defined                                                  ;

  // construct/copy/destruct
  () ;
  (const allocator_type &) ;
  (size_type);
  (size_type, default_init_t);
  (size_type, const allocator_type &);
  (size_type, default_init_t, const allocator_type &);
  (size_type, const T &, 
                const allocator_type & = allocator_type());
  template<typename InputIterator> 
    (InputIterator, InputIterator, 
                  const allocator_type & = allocator_type());
  (const stable_vector &);
  (value_type >, 
                const allocator_type & = allocator_type());
  (stable_vector &&) ;
  (const stable_vector &, const allocator_type &);
  (stable_vector &&, const allocator_type &);
  stable_vector & (const stable_vector &);
  stable_vector & 
  (stable_vector &&) ;
  stable_vector & (value_type >);
  ~();

  // public member functions
  void (size_type, const T &);
  template<typename InputIterator> void (InputIterator, InputIterator);
  void (value_type >);
  allocator_type () ;
  const stored_allocator_type & () ;
  stored_allocator_type & () ;
  iterator () ;
  const_iterator () ;
  iterator () ;
  const_iterator () ;
  reverse_iterator () ;
  const_reverse_iterator () ;
  reverse_iterator () ;
  const_reverse_iterator () ;
  const_iterator () ;
  const_iterator () ;
  const_reverse_iterator () ;
  const_reverse_iterator () ;
  bool () ;
  size_type () ;
  size_type () ;
  void (size_type);
  void (size_type, default_init_t);
  void (size_type, const T &);
  size_type () ;
  void (size_type);
  void ();
  reference () ;
  const_reference () ;
  reference () ;
  const_reference () ;
  reference (size_type) ;
  const_reference (size_type) ;
  iterator (size_type) ;
  const_iterator (size_type) ;
  size_type (iterator) ;
  size_type (const_iterator) ;
  reference (size_type);
  const_reference (size_type) ;
  template< Args> reference (Args &&...);
  template< Args> iterator (const_iterator, Args &&...);
  void (const T &);
  void (T &&);
  iterator (const_iterator, const T &);
  iterator (const_iterator, T &&);
  iterator (const_iterator, size_type, const T &);
  iterator (const_iterator, value_type >);
  template<typename InputIterator> 
    iterator (const_iterator, InputIterator, InputIterator);
  void () ;
  iterator (const_iterator) ;
  iterator (const_iterator, const_iterator) ;
  void (stable_vector &) ;
  void () ;

  // friend functions
  bool (const stable_vector &, const stable_vector &);
  bool (const stable_vector &, const stable_vector &);
  bool (const stable_vector &, const stable_vector &);
  bool (const stable_vector &, const stable_vector &);
  bool (const stable_vector &, const stable_vector &);
  bool (const stable_vector &, const stable_vector &);
  void (stable_vector &, stable_vector &) ;
};

Description

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

Here are the details taken from 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.

Template Parameters

  1. typename T

    The type of object that is stored in the stable_vector

  2. typename Allocator = void

    The allocator used for all internal memory management

stable_vector public construct/copy/destruct

  1. () ;

    Effects: Default constructs a stable_vector.

    Throws: If allocator_type's default constructor throws.

    Complexity: Constant.

  2. (const allocator_type & al) ;

    Effects: Constructs a stable_vector taking the allocator as parameter.

    Throws: Nothing

    Complexity: Constant.

  3. (size_type n);

    Effects: Constructs a stable_vector and inserts n value initialized values.

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

    Complexity: Linear to n.

  4. (size_type n, default_init_t);

    Effects: Constructs a stable_vector and inserts n default initialized values.

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

    Complexity: Linear to n.

    Note: Non-standard extension

  5. (size_type n, const allocator_type & a);

    Effects: Constructs a stable_vector that will use a copy of allocator a and inserts n value initialized values.

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

    Complexity: Linear to n.

  6. (size_type n, default_init_t, const allocator_type & a);

    Effects: Constructs a stable_vector that will use a copy of allocator a and inserts n default initialized values.

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

    Complexity: Linear to n.

    Note: Non-standard extension

  7. (size_type n, const T & t, 
                  const allocator_type & al = allocator_type());

    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 throws or T's default or copy constructor throws.

    Complexity: Linear to n.

  8. template<typename InputIterator> 
      (InputIterator first, InputIterator last, 
                    const allocator_type & al = allocator_type());

    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 throws or T's constructor taking a dereferenced InIt throws.

    Complexity: Linear to the range [first, last).

  9. (const stable_vector & x);

    Effects: Copy constructs a stable_vector.

    Postcondition: x == *this.

    Complexity: Linear to the elements x contains.

  10. (value_type > il, 
                  const allocator_type & l = allocator_type());

    Effects: Constructs a stable_vector that will use a copy of allocator a and inserts a copy of the range [il.begin(), il.last()) in the stable_vector

    Throws: If allocator_type's default constructor throws or T's constructor taking a dereferenced initializer_list iterator throws.

    Complexity: Linear to the range [il.begin(), il.end()).

  11. (stable_vector && x) ;

    Effects: Move constructor. Moves x's resources to *this.

    Throws: If allocator_type's copy constructor throws.

    Complexity: Constant.

  12. (const stable_vector & x, const allocator_type & a);

    Effects: Copy constructs a stable_vector using the specified allocator.

    Postcondition: x == *this.

    Complexity: Linear to the elements x contains.

  13. (stable_vector && x, const allocator_type & a);

    Effects: Move constructor using the specified allocator. Moves x's resources to *this.

    Throws: If allocator_type's copy constructor throws.

    Complexity: Constant if a == x.get_allocator(), linear otherwise

  14. stable_vector & (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.

  15. stable_vector & 
    (stable_vector && x) ;

    Effects: Move assignment. All x's values are transferred to *this.

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

    Throws: If allocator_traits_type::propagate_on_container_move_assignment is false and (allocation throws or T's move constructor throws)

    Complexity: Constant if allocator_traits_type:: propagate_on_container_move_assignment is true or this->get>allocator() == x.get_allocator(). Linear otherwise.

  16. stable_vector & (value_type > il);

    Effects: Make *this container contains elements from il.

    Complexity: Linear to the range [il.begin(), il.end()).

  17. ~();

    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

  1. void (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.

  2. template<typename InputIterator> 
      void (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.

  3. void (value_type > il);

    Effects: Assigns the the range [il.begin(), il.end()) to *this.

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

  4. allocator_type () ;

    Effects: Returns a copy of the internal allocator.

    Throws: If allocator's copy constructor throws.

    Complexity: Constant.

  5. const stored_allocator_type & () ;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  6. stored_allocator_type & () ;

    Effects: Returns a reference to the internal allocator.

    Throws: Nothing

    Complexity: Constant.

    Note: Non-standard extension.

  7. iterator () ;

    Effects: Returns an iterator to the first element contained in the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  8. const_iterator () ;

    Effects: Returns a const_iterator to the first element contained in the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  9. iterator () ;

    Effects: Returns an iterator to the end of the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  10. const_iterator () ;

    Effects: Returns a const_iterator to the end of the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  11. reverse_iterator () ;

    Effects: Returns a reverse_iterator pointing to the beginning of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  12. const_reverse_iterator () ;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  13. reverse_iterator () ;

    Effects: Returns a reverse_iterator pointing to the end of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  14. const_reverse_iterator () ;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  15. const_iterator () ;

    Effects: Returns a const_iterator to the first element contained in the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  16. const_iterator () ;

    Effects: Returns a const_iterator to the end of the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  17. const_reverse_iterator () ;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  18. const_reverse_iterator () ;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  19. bool () ;

    Effects: Returns true if the stable_vector contains no elements.

    Throws: Nothing.

    Complexity: Constant.

  20. size_type () ;

    Effects: Returns the number of the elements contained in the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  21. size_type () ;

    Effects: Returns the largest possible size of the stable_vector.

    Throws: Nothing.

    Complexity: Constant.

  22. void (size_type n);

    Effects: Inserts or erases elements at the end such that the size becomes n. New elements are value initialized.

    Throws: If memory allocation throws, or T's value initialization throws.

    Complexity: Linear to the difference between size() and new_size.

  23. void (size_type n, default_init_t);

    Effects: Inserts or erases elements at the end such that the size becomes n. New elements are default initialized.

    Throws: If memory allocation throws, or T's default initialization throws.

    Complexity: Linear to the difference between size() and new_size.

    Note: Non-standard extension

  24. void (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.

  25. size_type () ;

    Effects: Number of elements for which memory has been allocated. capacity() is always greater than or equal to size().

    Throws: Nothing.

    Complexity: Constant.

  26. void (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.

  27. void ();

    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().

  28. reference () ;

    Requires: !empty()

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

    Throws: Nothing.

    Complexity: Constant.

  29. const_reference () ;

    Requires: !empty()

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

    Throws: Nothing.

    Complexity: Constant.

  30. reference () ;

    Requires: !empty()

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

    Throws: Nothing.

    Complexity: Constant.

  31. const_reference () ;

    Requires: !empty()

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

    Throws: Nothing.

    Complexity: Constant.

  32. reference (size_type n) ;

    Requires: size() > n.

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

    Throws: Nothing.

    Complexity: Constant.

  33. const_reference (size_type n) ;

    Requires: size() > n.

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

    Throws: Nothing.

    Complexity: Constant.

  34. iterator (size_type n) ;

    Requires: size() >= n.

    Effects: Returns an iterator to the nth element from the beginning of the container. Returns end() if n == size().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  35. const_iterator (size_type n) ;

    Requires: size() >= n.

    Effects: Returns a const_iterator to the nth element from the beginning of the container. Returns end() if n == size().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  36. size_type (iterator p) ;

    Requires: begin() <= p <= end().

    Effects: Returns the index of the element pointed by p and size() if p == end().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  37. size_type (const_iterator p) ;

    Requires: begin() <= p <= end().

    Effects: Returns the index of the element pointed by p and size() if p == end().

    Throws: Nothing.

    Complexity: Constant.

    Note: Non-standard extension

  38. reference (size_type n);

    Requires: size() > n.

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

    Throws: range_error if n >= size()

    Complexity: Constant.

  39. const_reference (size_type n) ;

    Requires: size() > n.

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

    Throws: range_error if n >= size()

    Complexity: Constant.

  40. template< Args> reference (Args &&... args);

    Effects: Inserts an object of type T constructed with std::forward<Args>(args)... in the end of the stable_vector.

    Returns: A reference to the created object.

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

    Complexity: Amortized constant time.

  41. template< Args> iterator (const_iterator p, Args &&... args);

    Requires: p must be a valid iterator of *this.

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

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

    Complexity: If p is end(), amortized constant time Linear time otherwise.

  42. void (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.

  43. void (T && x);

    Effects: Constructs a new element in the end of the stable_vector and moves the resources of x to this new element.

    Throws: If memory allocation throws.

    Complexity: Amortized constant time.

  44. iterator (const_iterator p, const T & x);

    Requires: p must be a valid iterator of *this.

    Effects: Insert a copy of x before p.

    Returns: An iterator to the inserted element.

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

    Complexity: If p is end(), amortized constant time Linear time otherwise.

  45. iterator (const_iterator p, T && x);

    Requires: p must be a valid iterator of *this.

    Effects: Insert a new element before p with x's resources.

    Returns: an iterator to the inserted element.

    Throws: If memory allocation throws.

    Complexity: If p is end(), amortized constant time Linear time otherwise.

  46. iterator (const_iterator p, size_type n, const T & t);

    Requires: p must be a valid iterator of *this.

    Effects: Insert n copies of x before p.

    Returns: an iterator to the first inserted element or p if n is 0.

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

    Complexity: Linear to n.

  47. iterator (const_iterator p, value_type > il);
    Requires: p must be a valid iterator of *this.

    Requires: p must be a valid iterator of *this.

    Effects: Insert a copy of the [il.begin(), il.end()) range before p.

    Returns: an iterator to the first inserted element or p if first == last.

    Complexity: Linear to distance [il.begin(), il.end()).

  48. template<typename InputIterator> 
      iterator (const_iterator p, InputIterator first, InputIterator last);

    Requires: pos must be a valid iterator of *this.

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

    Returns: an iterator to the first inserted element or p if first == last.

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

    Complexity: Linear to distance [first, last).

  49. void () ;

    Effects: Removes the last element from the stable_vector.

    Throws: Nothing.

    Complexity: Constant time.

  50. iterator (const_iterator p) ;

    Effects: Erases the element at p.

    Throws: Nothing.

    Complexity: Linear to the elements between p and the last element. Constant if p is the last element.

  51. iterator (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 p and the last element.

  52. void (stable_vector & x) ;

    Effects: Swaps the contents of *this and x.

    Throws: Nothing.

    Complexity: Constant.

  53. void () ;

    Effects: Erases all the elements of the stable_vector.

    Throws: Nothing.

    Complexity: Linear to the number of elements in the stable_vector.

stable_vector friend functions

  1. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x and y are equal

    Complexity: Linear to the number of elements in the container.

  2. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x and y are unequal

    Complexity: Linear to the number of elements in the container.

  3. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x is less than y

    Complexity: Linear to the number of elements in the container.

  4. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x is greater than y

    Complexity: Linear to the number of elements in the container.

  5. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x is equal or less than y

    Complexity: Linear to the number of elements in the container.

  6. bool (const stable_vector & x, const stable_vector & y);

    Effects: Returns true if x is equal or greater than y

    Complexity: Linear to the number of elements in the container.

  7. void (stable_vector & x, stable_vector & y) ;

    Effects: x.swap(y)

    Complexity: Constant.


PrevUpHomeNext