13.51 <vector>

The <vector> header is one of the standard container template headers. It declares the vector class template and a few global function templates that operate on vector objects.

A vector is a sequence container that yields linear performance for inserting and erasing at any point in the container, except the end, for which performance is constant. A vector supports random access iterators. A vector is best thought of as a generalization of arrays.

See Chapter 10 for information about containers in.

template <typename T, typename A>
bool operator==(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator==(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The == operator returns true if x and y have the same size and their elements are equal, that is, x.size() == y.size() && equals(x.begin(), x.end(), y.begin( )).

See Also

equals in <algorithm>

template <typename T, typename A>
bool operator!=(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator!=(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The != operator returns ! (x == y).

template <typename T, typename A>
bool operator<(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator<(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The < operator determines whether x is less than y using the same algorithm as lexicographical_compare(x.begin( ), x.end( ), y.begin( ), y.end( )).

See Also

lexicographical_compare in <algorithm>

template <typename T, typename A>
bool operator<=(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator<=(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The <= operator returns ! (y < x).

template <typename T, typename A>
bool operator>(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator>(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The > operator returns (y < x).

template <typename T, typename A>
bool operator>=(const vector<T,A>& x, const vector<T,A>& y);
template <typename Alloc>
bool operator>=(const vector<bool,Alloc>& x, const vector<bool,Alloc>& y);

The >= operator returns ! (x < y).

template <typename T, typename Alloc>
void swap(vector<T,Alloc>& x, vector<T,Alloc>& y);
template <typename Alloc>
void swap(vector<bool,Alloc>& x, vector<bool,Alloc>& y);

The swap function template specialization is equivalent to calling x.swap(y).

See Also

swap in <algorithm>

template <typename T, typename Alloc = allocator<T> >
class vector {
public:
  typedef typename Alloc::reference reference;
  typedef typename Alloc::const_reference const_reference;
  typedef  . . .  iterator;
  typedef  . . .  const_iterator;
  typedef  . . .  size_type;
  typedef  . . .  difference_type;
  typedef T value_type;
  typedef Alloc allocator_type;
  typedef typename Alloc::pointer pointer;
  typedef typename Alloc::const_pointer const_pointer;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
   
  explicit vector(const Alloc& = Alloc(  ));
  explicit vector(size_type n, const T& value = T(  ), const Alloc& = Alloc(  ));
  template <class InpIt>
  vector(InpIt first, InpIt last, const Alloc& = Alloc(  ));
  vector(const vector<T,Alloc>& x);
  ~vector(  );
  vector<T,Alloc>& operator=(const vector<T,Alloc>& x);
  template <class InputIterator>
  void assign(InputIterator first, InputIterator last);
  void assign(size_type n, const T& u);
  allocator_type get_allocator(  ) const;
   
  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;
   
  size_type size(  ) const;
  size_type max_size(  ) const;
  void resize(size_type sz, T c = T(  ));
  size_type capacity(  ) const;
  bool empty(  ) const;
  void reserve(size_type n);
  // Element access
  reference operator[](size_type n);
  const_reference operator[](size_type n) const;
  const_reference at(size_type n) const;
  reference at(size_type n);
  reference front(  );
  const_reference front(  ) const;
  reference back(  );
  const_reference back(  ) const;
  // Modifiers
  void push_back(const T& x);
  void pop_back(  );
  iterator insert(iterator position, const T& x);
  void insert(iterator position, size_type n, const T& x);
  template <class InpIt>
  void insert(iterator position, InpIt first, InpIt last);
  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  void swap(vector<T,Alloc>&);
  void clear(  );
};

The vector class template is a standard sequence container that is like an array: adding or removing from the end of the vector takes constant time (amortized over many such operations), adding or removing from anywhere else takes linear time, and random access happens in constant time.

Elements of a vector are stored contiguously, just like an ordinary array. For most cases in which you need an array, you should use a vector instead because a vector offers greater safety (no need for dynamic memory and raw pointers, the at member function checks array bounds, etc.)

All iterators and references to a vector's elements become invalid when the vector's internal array is resized, which can happen for an insertion when the size matches the capacity, or when you explicitly change the size (e.g., by calling resize). You can ensure that an insertion does not force a resize by calling reserve to set the capacity prior to inserting one or more items. Iterators and references also become invalid when they are past (at a higher index) the point where an item is inserted or erased.

If you need a vector of Boolean values, consider using deque<bool> instead of vector<bool>. See vector<bool> for an explanation.

The following are the members of vector:

explicit vector(const Alloc& = Alloc( ))

Constructs an empty vector.

explicit vector(size_type n, const T& value = T( ), const Alloc& = Alloc( ))

Constructs a vector of size n, in which each element is initialized to value.

template <class InpIt>

vector(InpIt first, InpIt last, const Alloc& = Alloc( ))

Constructs an empty vector and copies [first, last) into the new vector unless InputIterator is an integral type, in which case the vector is constructed as though the arguments were cast as follows:

vector(static_cast<size_type>(first), static_cast<value_type>(last),
       alloc);

vector(const vector<T,Alloc>& v)

Constructs a copy of v.

vector<T,Alloc>& operator=(const vector<T,Alloc>& v)

Erases all the elements of the vector, then copies the elements from v into the vector.

template <class InputIterator>

void assign(InputIterator first, InputIterator last)

Erases all the elements of the vector, then copies the elements from [first, last) into the vector, unless InputIterator is an integral type, in which case the arguments are interpreted as though they were cast as follows:

assign(static_cast<size_type>(first), static_cast<value_type>(last));

void assign(size_type n, const T& value)

Erases all the elements of the vector, then inserts n copies of value.

const_reference at(size_type n) constreference at(size_type n)

Returns the element at index n. If n >= size( ), throws out_of_range.

reference back( )

const_reference back( ) const

Returns the last element of the vector. Behavior is undefined if the vector is empty.

iterator begin( )

const_iterator begin( ) const

Returns an iterator that points to the first element of the vector.

size_type capacity( ) const

Returns the number of elements the vector can store before it resizes itself.

void clear( )

Erases all elements of the vector.

iterator end( )

const_iterator end( ) const

Returns an iterator that points to one past the last element of the vector.

bool empty( ) const

Returns size( ) == 0.

iterator erase(iterator position)

Erases the element at position.

iterator erase(iterator first, iterator last)

Erases all the elements in the range [first, last).

reference front( )

const_reference front( ) const

Returns the first element of the vector. Behavior is undefined if the vector is empty.

locator_type get_allocator( ) const

Returns the allocator object.

iterator insert(iterator position, const T& x)

Inserts x before position.

void insert(iterator pos, size_type n, const T& x)

Inserts n copies of x at pos.

template <class InpIt>

void insert(iterator pos, InpIt first, InpIt last)

Inserts the elements in the range [first, last) starting at position pos, unless InputIterator is an integral type, in which case the arguments are interpreted as though they were cast as follows:

insert(pos, static_cast<size_type>(first), 
       static_cast<value_type>(last));

If an exception is thrown, such as bad_alloc when there is insufficient memory for a new element, the vector is unchanged, and all iterators and references remain valid. If the exception is thrown from an element's copy constructor or assignment operator, however, the behavior is unspecified.

size_type max_size( ) const

Returns the size of the largest possible vector.

reference operator[](size_type n)

const_reference operator[](size_type n) const

Returns the element at index n. If n >= size( ), the behavior is undefined.

void pop_back( )

Erases the last element of the vector. The behavior is undefined if the vector is empty.

void push_back(const T& x)

Inserts x as the new last element of the vector.

reverse_iterator rbegin( )

const_reverse_iterator rbegin( ) const

Returns a reverse iterator that points to the last element of the vector.

reverse_iterator rend( )

const_reverse_iterator rend( ) const

Returns a reverse iterator that points to one position before the first element of the vector.

void reserve(size_type n)

Ensures that capacity( ) is at least n. Call reserve to avoid the need to reallocate the vector repeatedly when you know the vector will grow by small increments to a large size, or when you want to ensure that iterators do not become invalid after inserting one or more items. Note that size( ) does not change.

void resize(size_type sz, T c = T( ))

Changes the size of this vector to n. If n > size( ), one or more copies of c are added to the end of the vector to reach the desired size. If the new size is smaller than the current size, elements are erased from the end to reach the new size.

size_type size( ) const

Returns the number of elements in the vector.

void swap(vector<T,Alloc>& that)

Exchanges all the elements in this vector with all the elements in that.

See Also

vector<bool> class, deque in <deque>, list in <list>

template <typename Alloc>
class vector<bool, Alloc> {
public:
  typedef bool const_reference;
  typedef  . . .  iterator;
  typedef  . . .  const_iterator;
  typedef  . . .  size_type;
  typedef  . . .  difference_type;
  typedef bool value_type;
  typedef Alloc allocator_type;
  typedef  . . .  pointer;
  typedef  . . .  const_pointer  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
   
  class reference;
  static void swap(reference x, reference y);
  void flip(  );
   . . .  // Same as vector<>  . . . 
};

The vector<bool> specialization is an interesting beast. It is an attempt to demonstrate how to define a container that uses a proxy to represent the elements of the container. The bool elements are packed into integers, and the vector<bool>::reference type is a proxy that represents a single bool element by keeping track of the bit number within the integer and the integer's index in the vector.

However, by using a proxy, vector<bool> violates the constraints of a container, so it cannot be used in many situations that call for a standard container. In particular, the pointer type cannot point to an element of the container because C++ does not have a type that can point to a single bit. Many algorithms require the pointer type, and so they cannot work with a vector<bool> object.

If you need to use a compact, fixed-size set of bits, use the bitset class template. If you need a standard container that contains bool elements, use deque<bool>.

In addition to the members of the vector<> template, vector<bool> also defines the following functions:

static void swap(reference x, reference y)

Swaps two bit values

void flip( )

Flips all the bits in the vector

See Also

vector class template, vector<bool>::reference class, bitset in <bitset>, deque in <deque>

class reference {
  friend class vector;
  reference(  );
public:
  ~reference(  );
  operator bool(  ) const;
  reference& operator=(const bool x);
  reference& operator=(const reference& x);
  void flip(  );
};

The reference class represents a single bit in a vector<bool>. The constructor is private, so only vector<bool> can create reference objects. The reference keeps track of the position of an individual bit in a vector<bool>, so you can get, set, or flip the bit. The following are the members of reference:

void flip( )

Flips or toggles the bit, that is, performs the equivalent of *this = ! *this

operator bool( ) const

Returns the bit value as a bool

reference& operator=(const bool x)

reference& operator=(const reference& x)

Assigns x to *this

See Also

vector<bool> class