The vector class implements a dynamic array that provides
fast insertion at the end, fast random access to its components, and
automatically resizes itself when components are inserted or
deleted.
Default Constructor
- vector<T> v;
- Construct an empty vector v which can hold values of
type T.
Copy Constructor
There is, of course, only one copy constructor, but there are two
syntactic forms that invoke it, and both are shown.
- vector<T> v(otherVector);
- Construct v as a copy of otherVector, whose
component type must be T. The copy has the same size as the
original, but the capacity of the copy will be the same as its size,
not equal to the capacity of the original.
- vector<T> v = otherVector;
- Copy constructor (alternate usage syntax).
Other Constructors
- vector<T> v(num);
- Construct a vector v of size num and capacity
num containing num values, each equal to the
default value of type T.
- vector<T> v(num, val);
- Construct a vector v of size num and capacity
num containing num values, each equal to
val, which must be of type T, and which may be
supplied by a variable, a literal or named constant, or a function
call.
- vector<T> v(inIterBegin, inIterEnd);
- Construct v containing values from the range
[inIterBegin,inIterEnd) in another (not necessarily vector)
container, but whose component type is the same as the component type
of v.
Destructor
- v.~vector<T>()
- Destroy all components of v and free the associated
memory.
Assignment operator
- v1 = v2
- Assign v2 to v1, and return the common value.
The vector on the left of an assignment receives the values and size
of the one on the right. The capacity of the vector on the left will
be the maximum of its original capacity and the size of the vector on
the right. (The capacity of the vector on the right is
irrelevant.)
Relational operators
Vectors are compared in the "lexicographic ordering" sense. This
essentially means that the two vectors are compared by comparing their
values pairwise, starting at the beginning, with each comparison
looking at two values in corresponding positions, until a determination
of the relationship between the two vectors can be made. Only vectors
of the same component type can be compared of course, and the
== and < operators must be defined for the
component type.
- v1 == v2
- Return true if v1 and v2 have the same
component type and the same size, and the components in each pair of
corresponding locations have the same value; otherwise return
false.
- v1 != v2
- Return true if v1==v2 returns false;
otherwise return false.
- v1 < v2
- Return true if, in the pairwise comparison of values
from v1 and v2, in the first pair in which the two
values differ, the one from v1 is less than the one from
v2; otherwise return false.
- v1 <= v2
- Return true if either v1<v2 or
v1==v2 is true; otherwise return
false.
- v1 > v2
- Return true if v2<v1 is true;
otherwise return false.
- v1 >= v2
- Return true if either v1>v2 or
v1==v2 is true, otherwise return
false.
operator[ ]
- v[i]
- Return a reference (or const_reference) to the
component of v with index i. (Index values start at
0, and there is no checking for an index out of bounds.)
Each of the member functions in this section has both a
const and a non-const version.
- v.at(i)
- Return a reference (or const_reference) to the
component of v with index i. (Throws an
out_of_range exception if i is not a valid index
for v.)
- v.front()
- Return a reference (or const_reference) to the
first component of v.
- v.back()
- Return a reference (or const_reference) to the
last component of v.
- v.begin()
- Return an iterator (or const_iterator) pointing
to the first component of v.
- v.end()
- Return an iterator (or const_iterator) pointing
to one-past-the-last component of v.
- v.rbegin()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to the last component of
v.
- v.rend()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to one-before-the-first
component of v.
- v.max_size()
- Return a value of type size_type giving the maximum
possible size of v, which will depend on the size of the
component type T of the vector object, and the amount of
available memory.
- v.size()
- Return a value of type size_type giving the number of
values currently in v.
- v.capacity()
- Return a value of type size_type giving the number of
values v can hold before reallocation becomes necessary to
accommodate additional values.
- v.empty()
- Return true if v is empty (contains zero
values); otherwise return false.
Note that when values are assigned using assign(), the new
capacity is the maximum of the old capacity and the new size. On
the other hand, when values are added using insert() or
push_back(), the capacity remains the same unless reallocation
must take place, in which case the new capacity will be determined by
the reallocation algorithm.
- v.assign(num, val)
- Assign num copies of val to v,
overwriting the entire previous contents of v.
- v.assign(inIterBegin, inIterEnd)
- Assign to v the values from the range
[inIterBegin,inIterEnd) in another (not necessarily vector)
container, but whose values are also of type T, overwriting
the entire previous contents of v.
- v.insert(iter, val)
- Insert val into v immediately before the value
pointed to by iter, and return an iterator pointing
at the new component with value val.
- v.insert(iter, num, val)
- Insert num copies of val into v,
immediately before the value pointed to by iter.
- v.insert(iter, inIterBegin, inIterEnd)
- Insert into v, immediately before the value pointed to
by iter, values from the range
[inIterBegin,inIterEnd) in another (not necessarily vector)
container, but whose values must be of the same type as the values of
v.
- v.push_back(val)
- Add val to the end of v, increasing the size of
v by one, and also increasing the capacity of v if
v was full before the new value was added.
- v.clear()
- Delete all values of v. The size of v is
reduced to zero, but the capacity of v is unaffected.
- v.erase(iter)
- Delete the value of v pointed to by iter and
return an iterator pointing at the following value, or to
one-past-the-last if the value deleted was the last one. The size of
v is reduced by one, but the capacity of v is
unaffected.
- v.erase(iterBegin, iterEnd)
- Delete all values of v from the range
[iterBegin,iterEnd) and return iterEnd. The size of
v is reduced by iterEnd-iterBegin (a value of type
difference_type), but the capacity of v is
unaffected.
- v.pop_back()
- Delete the last value of v. The size of v is
reduced by one, but the capacity of v is unaffected.
- v.reserve(num)
- Set capacity of v to at least num. (If
num is less than the current capacity of v, nothing
happens.)
- v.resize(num)
- Change size of v to num. (If v must be
lengthened, default values of its component type are added to the end
of v. If v is shortened, values at the end are
lost.) If num <= the current capacity of v, the
capacity of v remains the same; otherwise, the capacity of
v is >= num.
- v.resize(num, val)
- Change size of v to num. (If v must be
lengthened, copies of val are added to the end of
v. If v is shortened, values at the end are lost,
and the value of val is not used.) If num <= the
current capacity of v, the capacity of v remains
the same; otherwise, the capacity of v is >=
num.
- v.swap(otherVector)
- Exchange values in v with those in otherVector.
The sizes and capacities are swapped as well.
- v.getallocator()
- Return the allocator of v. (This is possibly the most
infrequently used of all member functions of the vector class.)
- Differences in the use of v[i] and v.at(i)
- The "safer" choice to access an element of v via an
index i is v.at(i) rather than v[i]. This
is because v.at(i) throws an out_of_range exception
if i is not a valid index value for v, unlike
v[i], which behaves just as if v were an ordinary
array, and thus does not give you any warning if your index goes out
of bounds. If it does go out of bounds, you may get a run-time error,
or your program may simply use whatever is stored at the invalid
location as though it were a piece of valid data.
- Reallocation caused by adding one or more values to a vector
-
If one or more values are added to a vector object, a
reallocation may be necessary. In particular, for example,
if a new value is added to a full vector object via the
push_back() member function, a reallocation will
take place. Essentially, that process goes like this. First, new
memory is allocated. Then the original vector is copied to this new
memory and the new value is added to the end. Finally, the old
vector's memory is deallocated.
In order that this reallocation (which is clearly an "expensive"
operation) not take place each time a new value is added, the
reallocation algorithm generally creates more new memory space than
just enough required to hold the original vector plus the newly
added value. Doubling the memory required by the original vector
has been a common (but not universal) scheme. It is easy to check
empirically the algorithm used in your C++ implementation by
writing a short test program that displays the size and capacity of
a vector each time you add a new value, starting with an empty
vector. The observed sequence may not be "fixed", however; that is,
if you start with a vector that is not empty, and that has been
created with its size and capacity the same, and then
start to add values one at a time, you may get a different sequence
of capacities. It is the use of these reallocation algorithms that
gives the "amortized constant time" performance of value insertion
at the end of a vector object.
- Danger of invalidation of iterators, references and pointers
- Although it may not be strictly true in all situations, it is
probably safest to assume that any member function that inserts or
removes values or changes the size or capacity of a vector will
invalidate any iterators, references or pointers already associated
with values of that vector.
- Implementation
- Standard C++ does not say how the STL containers and algorithms
must be implemented. It does, however, state certain constraints,
such as complexity constraints, to which each implementation must
adhere. Thus it is much better to base your programs on the STL's
performance guarantees, rather than upon any assumption about how a
particular feature, like the vector class, may be
implemented.
- Some performance and usage issues
- Vector value insertion and deletion take place in "amortized
constant time" if performed at the end of a vector, and in linear
time if performed at the beginning or internally. A vector should be
used if the conceptual requirement of the application is a "dynamic
array", especially if fast random access is required and most or all
insertions and deletions need only happen at the end of the
container. If many insertions and deletions will need to be made at
both ends, a deque should be used instead of a vector.
- The vector<bool> specialization
-
This specialization of the vector class may occasionally be useful,
but you need to be aware that it is not exactly like a "normal"
vector. For example, a vector<bool>::iterator is not
a random access iterator. Thus template code that works with other
kinds of vectors might not work with vector<bool>.
The vector<bool> class does, however, add a
convenient member function:
- v.flip()
- Reverse all bits in a vector<bool> object
v. Somewhat surprisingly, perhaps, you can also "flip" a
single bit of a vector<bool> object using
v[i].flip(). (Note that, in this latter case, the
flip() being used is not the member function.)
There are two groups of sample programs. The first group involves
only STL vectors and generic C++, while the second group involves other
STL features in addition to vectors. The programs should be studied in
the sequence given, since the description of each new sample program in
the sequence mentions only the new features illustrated for the first
time in that particular program, and features seen in earlier sample
programs will continue to reappear in later programs.
All of the programs have been compiled and run successfully under
Microsoft Visual Studio .NET 2005.
Programs involving only vectors (and generic C++)
- vector01.cpp | Windows_executable | program_output (text)
- Illustrates vector constructors, accessing vector values with
v[i], the typedef vector<T>::size_type, and
the member functions size() and empty(). Also
illustrates how ordinary array pointers can be used, in certain
situations, in the same way that STL iterators are used.
- vector02.cpp | Windows_executable | program_output (text)
- Illustrates the similarities and differences between
v[i] and v.at(i).
- vector03.cpp | Windows_executable | program_output (text)
- Illustrates member function max_size(), and how the
maximum size for a vector object depends on the size of its component
type.
- vector04.cpp | Windows_executable | program_output (text)
- Illustrates push_back() and shows the difference between
size() and capacity(). Allows the user to
experiment with the reallocation algorithm for his or her C++
implementation.
- vector05.cpp | Windows_executable | program_output (text)
- Illustrates typical uses of the default (random-access) iterator
for the vector class, shows additional uses of member functions
begin() and end(), and also shows the use of
operators =, +, -, ++, --, != and * with
vector class iterators.
- vector06.cpp | Windows_executable | program_output (text)
- Illustrates the default (random-access) vector class iterator in
additional situations, and shows the use of operators ->,
[ ], <, >, <=, >=,
+=, -= and == with vector class
iterators.
- vector07.cpp | Windows_executable | program_output (text)
- Illustrates reverse iterators for the vector class, as well as
member functions rbegin() and rend().
- vector08.cpp | Windows_executable | program_output (text)
- Illustrates a typical use of a const iterator.
- vector09.cpp | Windows_executable | program_output (text)
- Illustrates member functions front() and
back().
- vector10.cpp | Windows_executable | program_output (text)
- Illustrates the overloaded assignment operator = and the
assign() member function.
- vector11.cpp | Windows_executable | program_output (text)
- Illustrates the insert() member function.
- vector12.cpp | Windows_executable | program_output (text)
- Illustrates clear(), erase() and
pop_back() member functions.
- vector13.cpp | Windows_executable | program_output (text)
- Illustrates the reserve() and resize() member
functions.
- vector14.cpp | Windows_executable | program_output (text)
- Illustrates the swap() member function.
- vector15.cpp | Windows_executable | program_output (text)
- Illustrates how to shrink the capacity of a vector. Shows how to
simulate the "missing" member functions "trim" and "reset".
- vector16.cpp | Windows_executable | program_output (text)
- Illustrates a vector of vectors.
- vector17.cpp | Windows_executable | program_output (text)
- Illustrates the use of a vector of strings to read and display a
file of text.
- vector18.cpp | Windows_executable | program_output (text)
- Illustrates how the relational operators can be used to compare
one vector with another.
Programs involving additional vector features and vectors in
combination with other STL features
- vector_a.cpp | Windows_executable | program_output (text)
- Illustrates the use of stream iterators and the copy
algorithm for I/O of vector values.
- vector_b.cpp | Windows_executable | program_output (text)
- Illustrates how to display the name of the underlying type
represented by each typedef defined by a vector class.
- vector_c.cpp | Windows_executable | program_output (text)
- Illustrates initialization of a vector with values from
non-vector containers (in this case, a deque and a list).
- vector_d.cpp | Windows_executable | program_output (text)
- Illustrates the use of several STL algorithms
(accumulate, count, max,
max_element, min, min_element, and
sort) with vector objects.
- vector_e.cpp | Windows_executable | program_output (text)
- Illustrates the use of several additional STL algorithms
(count_if, for_each, and transform) with
vector objects, and also shows the use of a built-in function object,
as well as programmer-defined functions being passed as parameters to
an STL algorithm.
- vector_f.cpp | Windows_executable | program_output (text)
- Illustrates the specialized container type
vector<bool>.
For enhanced readability in each of the prototypes given below, each
parameter in each parameter list appears on a separate line. Also, some
formatting liberties are taken, in the interest of greater readability.
For example, rather than aligning all prototypes at the left margin,
const and non-const versions of a member function are
aligned in such a way as to allow the reader to more easily compare the
two visually.
Template specification for the vector class
template<class T,
class Allocator = allocator<T> >
class vector { ... }
Constructors
explicit vector(const Allocator& a = Allocator());
explicit vector(size_type num,
const T& val = T(),
const Allocator& a = Allocator());
template<class InIterator>
vector(InIterator inIterBegin,
InIterator inIterEnd,
const Allocator& a = Allocator());
Copy Constructor
vector(const vector<T, Allocator>& otherVector);
Destructor
~vector();
assign
void assign(size_type num,
const T& val);
template<class InIterator>
void assign(InIterator inIterBegin,
InIterator inIterEnd);
at
reference at(size_type i);
const_reference at(size_type i) const;
back
reference back();
const_reference back() const;
begin
iterator begin();
const_iterator begin() const;
capacity
size_type capacity() const;
clear
void clear();
empty
bool empty() const;
end
iterator end();
const_iterator end() const;
erase
iterator erase(iterator iter);
iterator erase(iterator iterBegin,
iterator iterEnd);
front
reference front();
const_reference front() const;
get_allocator
allocator_type get_allocator() const;
insert
iterator insert(iterator iter,
const T& val);
void insert(iterator iter,
size_type num,
const T& val);
template<class InIterator>
void insert(iterator iter,
InIterator inIterBegin,
InIterator inIterEnd);
max_size
size_type max_size() const;
operator[ ]
reference operator[](size_type i);
const_reference operator[](size_type i) const;
pop_back
void pop_back();
push_back
void push_back(const T& val);
rbegin
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
rend
reverse_iterator rend();
const_reverse_iterator rend() const;
reserve
void reserve(size_type num);
resize
void resize(size_type num,
T val = T());
size
size_type size() const;
swap
void swap(vector<T, Allocator>& otherVector);