Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.
NAME
vector
- A sequence that supports random access iterators.
SYNOPSIS
#include <vector>
template <class T, class Allocator = allocator<T> >
class vector ;
DESCRIPTION
vector<T,_Allocator> is a type of sequence that supports
random access iterators. In addition, it supports amortized
constant time insert and erase operations at the end.
Insert and erase in the middle take linear time. Storage
management is handled automatically. In vector, iterator is
a random access iterator referring to T. const_iterator is
a constant random access iterator that returns a const T&
when dereferenced. A constructor for iterator and
const_iterator is guaranteed. size_type is an unsigned
integral type. difference_type is a signed integral type.
Any type used for the template parameter T must provide the
following (where T is the type, t is a value of T and u is a
const value of T):
Copy constructors T(t) and T(u)
Destructor t.~T()
Address of &t and &u yielding T* and const T*
respectively
Assignment t = a where a is a
(possibly const) value of T
SPECIAL CASE
Vectors of bit values, that is boolean 1/0 values, are
handled as a special case by the standard library, so that
they can be efficiently packed several elements to a word.
The operations for a boolean vector, vector<bool>, are a
superset of those for an ordinary vector, only the implemen-
tation is more efficient.
Two member functions are available to the boolean vector
data type. One is flip(), which inverts all the bits of
the vector. Boolean vectors also return as reference an
internal value that also supports the flip() member func-
tion. The other vector<bool>-specific member function is a
second form of the swap() function
INTERFACE
template <class T, class Allocator = allocator<T> >
class vector {
public:
// Types
typedef T value_type;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
class iterator;
class const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename std::reverse_iterator<iterator>
reverse_iterator;
typedef typename std::reverse_iterator<const iterator>
const_reverse_iterator;
// Construct/Copy/Destroy
explicit vector (const Allocator& = Allocator());
explicit vector (size_type, const Allocator& = Allocator
());
vector (size_type, const T&, const Allocator& = Alloca-
tor());
vector (const vector<T, Allocator>&);
template <class InputIterator>
vector (InputIterator, InputIterator,
const Allocator& = Allocator ());
~vector ();
vector<T,Allocator>& operator= (const vector<T, Alloca-
tor>&);
template <class InputIterator>
void assign (InputIterator first, InputIterator last);
void assign (size_type, const);
allocator_type get_allocator () const;
// Iterators
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;
// Capacity
size_type size () const;
size_type max_size () const;
void resize (size_type);
void resize (size_type, T);
size_type capacity () const;
bool empty () const;
void reserve (size_type);
// Element Access
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;
// Modifiers
void push_back (const T&);
void pop_back ();
iterator insert (iterator, const T&);
void insert (iterator, size_type, const T&);
template <class InputIterator>
void insert (iterator, InputIterator, InputIterator);
iterator erase (iterator);
iterator erase (iterator, iterator);
void swap (vector<T, Allocator>&);
void clear()
};
// Non-member Operators
template <class T>
bool operator== (const vector<T,Allocator>&,
const vector <T,Allocator>&);
template <class T>
bool operator!= (const vector<T,Allocator>&,
const vector <T,Allocator>&);
template <class T>
bool operator< (const vector<T,Allocator>&,
const vector<T,Allocator>&);
template <class T>
bool operator> (const vector<T,Allocator>&,
const vector<T,Allocator>&);
template <class T>
bool operator<= (const vector<T,Allocator>&,
const vector<T,Allocator>&);
template <class T>
bool operator>= (const vector<T,Allocator>&,
const vector<T,Allocator>&);
// Specialized Algorithms
template <class T, class Allocator>
void swap (const vector<T,Allocator>&, const
vector<T,Allocator>&);
CONSTRUCTORS
explicit vector(const Allocator& alloc = Allocator());
The default constructor. Creates a vector of length
zero. The vector will use the allocator alloc for all
storage management.
explicit vector(size_type n);
Creates a vector of length n, containing n copies of the
default value for type T. Requires that T have a default
constructor. The vector will use the allocator Alloca-
tor() for all storage management.
vector(size_type n, const T& value,
const Allocator& alloc = Allocator());
Creates a vector of length n, containing n copies of
value. The vector will use the allocator alloc for all
storage management.
vector(const vector<T, Allocator>& x);
Creates a copy of x.
template <class InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& alloc = Allocator());
Creates a vector of length last - first, filled with all
values obtained by dereferencing the InputIterators on
the range [first, last). The vector will use the alloca-
tor alloc for all storage management.
DESTRUCTOR
~vector();
The destructor. Releases any allocated memory for this
vector.
ITERATORS
iterator
begin();
Returns a random access iterator that points to the first
element.
const_iterator
begin() const;
Returns a random access const_iterator that points to the
first element.
iterator
end();
Returns a random access iterator that points to the
past-the-end value.
const_iterator
end() const;
Returns a random access const_iterator that points to the
past-the-end value.
reverse_iterator
rbegin();
Returns a random access reverse_iterator that points to
the past-the-end value.
const_reverse_iterator
rbegin() const;
Returns a random access const_reverse_iterator that
points to the past-the-end value.
reverse_iterator
rend();
Returns a random access reverse_iterator that points to
the first element.
const_reverse_iterator
rend() const;
Returns a random access const_reverse_iterator that
points to the first element.
ASSIGNMENT OPERATOR
vector<T, Allocator>&
operator=(const vector<T, Allocator>& x);
Erases all elements in self then inserts into self a copy
of each element in x. Returns a reference to self.
ALLOCATOR
allocator_type
get_allocator() const;
Returns a copy of the allocator used by self for storage
management.
REFERENCE OPERATORS
reference
operator[](size_type n);
Returns a reference to element n of self. The result can
be used as an lvalue. The index n must be between 0 and
the size less one.
const_reference
operator[](size_type n) const;
Returns a constant reference to element n of self. The
index n must be between 0 and the size less one.
MEMBER FUNCTIONS
template <class InputIterator>
void
assign(InputIterator first, InputIterator last);
Erases all elements contained in self, then inserts new
elements from the range [first, last).
void
assign(size_type, const T& t);
Erases all elements contained in self, then inserts n
instances of the value of t.
reference
at(size_type n);
Returns a reference to element n of self. The result
can be used as an lvalue. The index n must be between 0
and the size less one.
const_reference
at(size_type) const;
Returns a constant reference to element n of self. The
index n must be between 0 and the size less one.
reference
back();
Returns a reference to the last element.
const_reference
back() const;
Returns a constant reference to the last element.
size_type
capacity() const;
Returns the size of the allocated storage, as the number
of elements that can be stored.
void
clear() ;
Deletes all elements from the vector.
bool
empty() const;
Returns true if the size is zero.
iterator
erase(iterator position);
Deletes the vector element pointed to by the iterator
position. Returns an iterator pointing to the element
following the deleted element, or end() if the deleted
element was the last one in this vector.
iterator
erase(iterator first, iterator last);
Deletes the vector elements in the range (first, last).
Returns an iterator pointing to the element following the
last deleted element, or end() if there were no elements
in the deleted range.
void
flip();
Flips all the bits in the vector. This member function
is only defined for vector<bool>.
reference
front();
Returns a reference to the first element.
const_reference
front() const;
Returns a constant reference to the first element.
iterator
insert(iterator position, const T& x);
Inserts x before position. The return value points to
the inserted x.
void
insert(iterator position, size_type n, const T& x);
Inserts n copies of x before position.
template <class InputIterator>
void
insert(iterator position, InputIterator first,
InputIterator last);
Inserts copies of the elements in the range [first, last]
before position.
size_type
max_size() const;
Returns size() of the largest possible vector.
void
pop_back();
Removes the last element of self.
void
push_back(const T& x);
Inserts a copy of x to the end of self.
void
reserve(size_type n);
Increases the capacity of self in anticipation of adding
new elements. reserve itself does not add any new ele-
ments. After a call to reserve, capacity() is greater
than or equal to n and subsequent insertions will not
cause a reallocation until the size of the vector exceeds
n. Reallocation does not occur if n is less than capa-
city(). If reallocation does occur, then all iterators
and references pointing to elements in the vector are
invalidated. reserve takes at most linear time in the
size of self. reserve throws a length_error exception if
n is greater than max_size().
void
resize(size_type sz);
Alters the size of self. If the new size (sz) is greater
than the current size, then sz-size() instances of the
default value of type T are inserted at the end of the
vector. If the new size is smaller than the current
capacity, then the vector is truncated by erasing
size()-sz elements off the end. If sz is equal to capa-
city then no action is taken.
void
resize(size_type sz, T c);
Alters the size of self. If the new size (sz) is greater
than the current size, then sz-size() c's are inserted at
the end of the vector. If the new size is smaller than
the current capacity, then the vector is truncated by
erasing size()-sz elements off the end. If sz is equal to
capacity then no action is taken.
size_type
size() const;
Returns the number of elements.
void
swap(vector<T, Allocator>& x);
Exchanges self with x, by swapping all elements.
void
swap(reference x, reference y);
Swaps the values of x and y. This is a member function
of vector<bool> only.
NON-MEMBER OPERATORS
template <class T, class Allocator>
bool operator==(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns true if x is the same as y.
template <class T, class Allocator>
bool operator!=(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns !(x==y).
template <class T>
bool operator<(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns true if the elements contained in x are
lexicographically less than the elements contained in y.
template <class T>
bool operator>(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns y < x.
template <class T>
bool operator<=(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns !(y < x).
template <class T>
bool operator>=(const vector<T, Allocator>& x,
const vector<T, Allocator>& y);
Returns !(x < y).
SPECIALIZED ALGORITHMS
template <class T, class Allocator>void
swap(vector <T, Allocator>& a, vector <T, Allocator>& b);
Efficiently swaps the contents of a and b.
EXAMPLE
//
// vector.cpp
//
#include <vector>
#include <iostream>
ostream& operator<< (ostream& out,
const vector<int, allocator>& v)
{
copy(v.begin(),v.end(),ostream_iterator<int,char>(out,"
"));
return out;
}
int main(void)
{
// create a vector of doubles
vector<int> vi;
int i;
for(i = 0; i < 10; ++i) {
// insert values before the beginning
vi.insert(vi.begin(), i);
}
// print out the vector
cout << vi << endl;
// now let's erase half of the elements
int half = vi.size() >> 1;
for(i = 0; i < half; ++i) {
vi.erase(vi.begin());
}
// print ir out again
cout << vi << endl;
return 0;
}
Output :
9 8 7 6 5 4 3 2 1 0
4 3 2 1 0
WARNINGS
Member function templates are used in all containers pro-
vided by the Standard Template Library. An example of this
feature is the constructor for vector<T,_Allocator> that
takes two templated iterators:
template <class InputIterator>
vector (InputIterator, InputIterator,
const Allocator = Allocator());
vector also has an insert function of this type. These
functions, when not restricted by compiler limitations,
allow you to use any type of input iterator as arguments.
For compilers that do not support this feature we provide
substitute functions that allow you to use an iterator
obtained from the same type of container as the one you are
constructing (or calling a member function on), or you can
use a pointer to the type of element you have in the con-
tainer.
For example, if your compiler does not support member func-
tion templates you can construct a vector in the following
two ways:
int intarray[10];
vector<int> first_vector(intarray, intarray + 10);
vector<int> second_vector(first_vector.begin(),
first_vector.end());
but not this way:
vector<long>
long_vector(first_vector.begin(),first_vector.end());
since the long_vector and first_vector are not the same
type.
Additionally, if your compiler does not support default tem-
plate parameters, you will need to supply the Allocator tem-
plate argument. For instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
allocator, Containers, Iterators, lexicographical_compare