Next : List, Previous : Sequences,
Top : Table of Contents
Vector
vector is a kind of sequence
(See Sequences.)
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, though hints can be given to improve efficiency. See Reversible
Container.
template class Allocator = allocator>
class vector {
public:
// typedefs:
typedef iterator;
typedef const_iterator;
typedef Allocator::pointer pointer;
typedef Allocator::reference reference;
typedef Allocator::const_reference const_reference;
typedef size_type;
typedef difference_type;
typedef T value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// allocation/deallocation:
vector();
vector(size_type n, const T& value = T());
vector(const vector& x);
template
vector(InputIterator first, InputIterator last);
~vector();
vector& operator=(const vector& x);
void reserve(size_type n);
void swap(vector& x);
// accessors:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
size_type size() const;
size_type max_size() const;
size_type capacity() const;
bool empty() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void resize (size_type);
void resize (size_type, T);
// insert/erase:
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template
void insert(iterator position, InputIterator first, InputIterator last);
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
template
bool operator==(const vector& x, const vector& y);
template
bool operator<(const vector& x, const vector& y);
| iterator |
Typedef on vector |
iterator is a random access iterator referring to
T. The exact type is implementation dependent and determined
by Allocator.
| const_iterator |
Typedef on vector |
const_iterator is a constant random access iterator
referring to const T. The exact type is implementation
dependent and determined by Allocator. It is guaranteed that
there is a constructor for const_iterator out of
iterator.
| size_type |
Typedef on vector |
size_type is an unsigned integral type. The exact type is
implementation dependent and determined by Allocator.
| difference_type |
Typedef on vector |
difference_type is a signed integral type. The exact type
is implementation dependent and determined by Allocator.
| vector (InputIterator first, InputIterator last) |
Constructor on vector |
The constructor template <class InputIterator>
vector(InputIterator first, InputIterator last) makes only N calls
to the copy constructor of T (where N is the distance between first and last) and no reallocations if
iterators first and last are of forward, bidirectional, or random access
categories. It does at most 2N calls to the copy constructor of T and \log N reallocations if they are just input iterators,
since it is impossible to determine the distance between first and last
and then do copying.
| capacity () |
Method on vector |
| reserve () |
Method on vector |
The member function capacity returns the size of the allocated storage in the vector. The member function reserve is a directive that informs vector of a planned change in
size, so that it can manage the storage allocation accordingly. It does
not change the size of the sequence and takes at most linear time in the
size of the sequence. Reallocation happens at this point if and only if
the current capacity is less than the argument of reserve.
After reserve, capacity is greater or equal to
the argument of reserve if reallocation happens; and equal to
the previous value of capacity otherwise. Reallocation
invalidates all the references, pointers, and iterators referring to the
elements in the sequence. It is guaranteed that no reallocation takes
place during the insertions that happen after reserve takes
place till the time when the size of the vector reaches the size specified
by reserve.
| insert (iterator position, const T& x = T());
|
Method on vector |
| insert (iterator position, size_type n, const
T& x); |
Method on vector |
| insert (iterator position, InputIterator first,
InputIterator last); |
Method on vector |
insert causes reallocation if the new size is greater
than the old capacity. If no reallocation happens, all the iterators and
references before the insertion point remain valid. Inserting a single
element into a vector is linear in the distance from the insertion point
to the end of the vector. The amortized complexity over the lifetime of a
vector of inserting a single element at its end is constant. Insertion of
multiple elements into a vector with a single call of the insert member
function is linear in the sum of the number of elements plus the distance
to the end of the vector. In other words, it is much faster to insert many
elements into the middle of a vector at once than to do the insertion one
at a time. The insert template member function pre-allocates enough storage
for the insertion if the iterators first and
last are of forward, bidirectional or random access category.
Otherwise, it does insert elements one by one and should not be used for
inserting into the middle of vectors.
| erase (iterator position); |
Method on vector |
| erase (iterator first, iterator last); |
Method on vector |
erase invalidates all the iterators and references after
the point of the erase. The destructor of T is called the
number of times equal to the number of the elements erased, but the
assignment operator of T is called the number of times equal
to the number of elements in the vector after the erased elements.
To optimize space allocation, a specialization for bool
is provided:
class vector {
public:
// bit reference:
class reference {
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
void flip(); // flips the bit
};
// typedefs:
typedef bool const_reference;
typedef iterator;
typedef const_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bool value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// allocation/deallocation:
vector();
vector(size_type n, const bool& value = bool());
vector(const vector& x);
template
vector(InputIterator first, InputIterator last);
~vector();
vector& operator=(const vector& x);
void reserve(size_type n);
void swap(vector& x);
// accessors:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
size_type size() const;
size_type max_size() const;
size_type capacity() const;
bool empty() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// insert/erase:
void push_back(const bool& x);
iterator insert(iterator position, const bool& x = bool());
void insert (iterator position, size_type n, const bool& x);
template
void insert (iterator position, InputIterator first, InputIterator last);
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
void swap(vector::reference x,
vector::reference y);
bool operator==(const vector& x,
const vector& y);
bool operator<(const vector& x,
const vector& y);
| reference |
Typedef on vector<bool> |
reference is a class that simulates the behavior of
references of a single bit in vector<bool>.
Every implementation is expected to provide specializations of
vector<bool> for all supported memory models.
At present, it is not possible to templatize a specialization.
That is, the user cannot write:
template class Allocator = allocator>
class vector { /* ... */ };
Therefore, only vector<bool,allocator> is provided.
