Vector
Vector is a STL of
C++ library. We can use it alternative to array,link list and stack. To know
the accessing rules read the things are given below.
First of all we have to use a header
#include <vector>
·
Vectors are declared with the following
syntax:
vector<type>
variable_name (number_of_elements);
The number
of elements is optional. You could declare it like this:
vector<type>
variable_name;
// A vector with 5 elements each having the value 99 vector<int> v2(5, 99);
Inserting and Removing Elements
Methods
push_back and
pop_back insert and remove (respectively) elements
at the end of the vector. For situations where we need to insert or remove at
an arbitrary position, we have methods
remove
and
remove. We notice that
these methods are inefficient with a
vector
(they take linear time, since all the remaining elements from the given
position to the end have to be shifted). However, for situations where we must
support these operations, class
vector
does provide the facilities to do so.
student_marks.push_back (mark); //
push marks at the last position of the vector.
student_marks.pop_back (); //
pop from the last position of the
vector.
Acessing Elements of a Vector
There are a number of ways to access the elements of a vector. For the moment,
I will focus on two of them, one safe and one unsafe. And as a reminder, C++
vectors (and other STL containers), like raw C/C++ arrays, are accessed with
indices starting at zero. This means that the first element is at position 0 in
the vector, and the last element is at position (number of elements)-1.
The vector class contains a
member function at() for accessing individual elements of a vector. This is the
safe way of accessing elements, since attempting to access an element
beyond the valid range will cause an exception to be thrown. However, the raw
data stored in the vector can still be accessed using the usual [] operator,
just like in a raw array. Unfortunately, just like with a raw array of data,
overrunning the end of the vector using the [] operator can cause weird and
unexpected things to occur, such as program crashes or unexpected results. It
may also return garbage data that follows the meaningful data of the vector,
which has the potential to be disastrous if it is used in subsequent
operations. The following two code snippets demonstrate each of these access
methods:
Example
|
// vector::at
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector (10); // 10 zero-initialized ints
unsigned int i;
// assign some values:
for (i=0; i<myvector.size(); i++)
myvector.at(i)=i;
cout << "myvector contains:";
for (i=0; i<myvector.size(); i++)
cout << " " << myvector.at(i);
cout << endl;
return 0;
}
|
Output:
myvector contains: 0 1 2 3 4 5 6 7 8 9
|
reference back ( );
const_reference back ( ) const;
Access last element
Returns a reference to the last
element in the vector container.
Unlike member
vector::end,
which returns an iterator just past this element, this function returns a
direct reference.
Parameters
none
Return value
A reference to the last element
in the vector.
Member types reference and const_reference are the reference types to the
elements of the vector container (for the default storage allocation model, allocator, these are T&
and const T& respectively).
Example
|
// vector::back
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
myvector.push_back(10);
while (myvector.back() != 0)
{
myvector.push_back ( myvector.back() -1 );
}
cout << "myvector contains:";
for (unsigned i=0; i<myvector.size() ; i++)
cout << " " << myvector[i];
cout << endl;
return 0;
}
|
Output:
myvector contains: 10 9 8 7 6 5 4 3 2 1 0
|
size_type capacity () const;
Return size of allocated storage capacity
Returns the size of the
allocated storage space for the elements of the
vector container.
Notice that, in vectors, the capacity is not necessarily equal to the number of
elements that conform the underlying vector content (this can be obtained with
member
vector::size), but
the capacity of the actual allocated space, which is either equal or greater
than the content size.
Notice also that this capacity does not suppose a limit to the size of the
vector. If more space is required to accomodate new elements in the
vector, the capacity is
automatically expanded, or can even be explicitly modified by calling member
vector::reserve.
The real limit on the size a
vector
object can reach is returned by member
vector::max_size.
Parameters
none
Return Value
The size of the currently
allocated storage capacity in the
vector,
measured in the number elements it could hold.
Member type
size_type is an unsigned
integral type.
Example
|
// comparing size, capacity and max_size
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
// set some content in the vector:
for (int i=0; i<100; i++) myvector.push_back(i);
cout << "size: " << (int) myvector.size() << "\n";
cout << "capacity: " << (int) myvector.capacity() << "\n";
cout << "max_size: " << (int) myvector.max_size() << "\n";
return 0;
}
|
A possible output for this program could be:
size: 100
capacity: 141
max_size: 1073741823
|
bool empty () const;
Test whether vector is empty
Returns
whether the vector container is
empty, i.e. whether its size
is
0
.
Example
|
// vector::empty
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
int sum (0);
for (int i=1;i<=10;i++) myvector.push_back(i);
while (!myvector.empty())
{
sum += myvector.back();
myvector.pop_back();
}
cout << "total: " << sum << endl;
return 0;
}
|
The example initializes the content of the vector to a sequence of numbers
(form 1 to 10). It then pops the elements one by one until it is empty and
calculates their sum.
Output:
void clear ( );
Clear content
All the
elements of the vector are dropped: their destructors are called, and then they
are removed from the vector
container, leaving the container with a size of
0
.
Parameters
none
Return value
none
Example
|
// clearing vectors
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
unsigned int i;
vector<int> myvector;
myvector.push_back (100);
myvector.push_back (200);
myvector.push_back (300);
cout << "myvector contains:";
for (i=0; i<myvector.size(); i++) cout << " " << myvector[i];
myvector.clear();
myvector.push_back (1101);
myvector.push_back (2202);
cout << "\nmyvector contains:";
for (i=0; i<myvector.size(); i++) cout << " " << myvector[i];
cout << endl;
return 0;
}
|
Output:
myvector contains: 100 200 300
myvector contains: 1101 2202
iterator erase ( iterator position );
iterator erase ( iterator first, iterator last );
Erase elements
Removes
from the vector container either a single element (position) or a range
of elements (
[first,last)
).
This effectively reduces the vector size by the number of
elements removed, calling each element's destructor before.
Because vectors keep an array format, erasing on positions other than the
vector end also moves all
the elements after the segment erased to their new positions, which may not
be a method as efficient as erasing in other kinds of sequence containers (deque, list).
This invalidates all iterator and references to position (or first)
and its subsequent elements.
Parameters
All parameters are of member type
iterator
, which in vector
containers are defined as a random access iterator type.
position
Iterator
pointing to a single element to be removed from the vector.
first, last
Iterators
specifying a range within the vector to be removed:
[first,last)
. i.e., the range includes all the elements between first
and last, including the element pointed by first but not the
one pointed by last.
Return value
A
random access iterator pointing to the new location of the element that
followed the last element erased by the function call, which is the vector end if the operation erased
the last element in the sequence.
Example
|
// erasing from vector
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
unsigned int i;
vector<unsigned int> myvector;
// set some values (from 1 to 10)
for (i=1; i<=10; i++) myvector.push_back(i);
// erase the 6th element
myvector.erase (myvector.begin()+5);
// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);
cout << "myvector contains:";
for (i=0; i<myvector.size(); i++)
cout << " " << myvector[i];
cout << endl;
return 0;
}
|
Output:
myvector contains: 4 5 7 8 9 10
|
|
reference front ( );
const_reference front ( ) const;
Access first element
Returns
a reference to the first element in the vector container.
Unlike member vector::begin,
which returns an iterator to this same element, this function returns a direct
reference.
Parameters
none
Return value
A
reference to the first element in the vector.
Member types
reference
and
const_referenceare the reference types to the elements of the vector container (for the
default storage allocation model, allocator,
these are T&and const T&respectively).
Example
|
// vector::front
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
myvector.push_back(78);
myvector.push_back(16);
// now front equals 78, and back 16
myvector.front() -= myvector.back();
cout << "myvector.front() is now " << myvector.front() << endl;
return 0;
}
|
Output:
myvector.front() is now 62
|
Get allocator
Returns the allocator object
used to construct the vector.
Parameters
none
Return Value
The allocator.
Member type allocator_type is defined to
the same as the second template parameter used to instantitate this specific
vector class (its Allocator type).
Example
|
// vector::get_allocator
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
int * p;
unsigned int i;
// allocate an array of 5 elements using vector's allocator:
p=myvector.get_allocator().allocate(5);
// assign some values to array
for (i=0; i<5; i++) p[i]=i;
cout << "The allocated array contains:";
for (i=0; i<5; i++) cout << " " << p[i];
cout << endl;
myvector.get_allocator().deallocate(p,5);
return 0;
}
|
The example shows an elaborate way to allocate memory for an array of ints using the same allocator used by the vector.
Output:
The allocated array contains: 0 1 2 3 4
|
Request a change in capacity
Requests that the
capacity of the allocated
storage space for the elements of the
vector
container be at least enough to hold
n elements.
This informs the
vector of a
planned increase in
size,
although notice that the parameter
n informs of a minimum, so the
resulting capacity may be any capacity equal or larger than this.
When
n is greater than the current
capacity, a reallocation
is attempted during the call to this function. If successful, it grants that no
further automatic reallocations will happen because of a call to
vector::insert or
vector::push_back until
the vector
size surpasses
at least
n (this preserves the validity of iterators on all these future
calls).
A reallocation invalidates all previously obtained iterators, references and
pointers to elements of the vector.
In any case, a call to this function never affects the elements contained in
the vector, nor the vector
size
(for that purposes, see
vector::resize
or
vector::erase, which
modify the vector
size and
content).
Parameters
n
Minimum amount desired as capacity
of allocated storage.
Member type size_type is an unsigned
integral type.
Return Value
none
If the requested size to allocate is greater than the maximum size (
vector::max_size) a
length_error exception is thrown.
In case of reallocation, this is performed using
Allocator::allocate(),
which may throw its own exceptions (for the default
allocator,
bad_alloc is thrown if the
allocation request does not succeed).
Example
|
// vector::reserve
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main ()
{
vector<int> content;
size_t filesize;
ifstream file ("test.bin",ios::in|ios::ate|ios::binary);
if (file.is_open())
{
filesize=file.tellg();
content.reserve(filesize);
file.seekg(0);
while (!file.eof())
{
content.push_back( file.get() );
}
// print out content:
vector<int>::iterator it;
for (it=content.begin() ; it<content.end() ; it++)
cout << hex << *it;
}
return 0;
}
|
This example reserves enough capacity in a vector of
ints to store the content of an entire file, which
is then read character by character (each character stored as an element in the
vector). By reserving a
capacity
for the
vector of at least the
size of the entire file, we avoid all the automatic reallocations that the
object
content could suffer each time that a new element surpassed the
size of its previously allocated storage space.
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
Return reverse iterator to reverse beginning
Returns a reverse iterator
referring to the last element in the vector container.
rbegin refers to the element
right before the one that would be referred to by member
end.
Notice that unlike member
vector::back,
which returns a reference to this same element, this function returns a
reverse
random access iterator.
Parameters
none
Return Value
A reverse iterator to the
reverse beginning of the sequence.
Both reverse_iterator and const_reverse_iterator are member types. In the vector class template, these are reverse random
access iterators, defined as reverse_iterator<iterator>
and reverse_iterator<const_iterator>
respectively.
Example
|
// vector::rbegin/rend
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
for (int i=1; i<=5; i++) myvector.push_back(i);
cout << "myvector contains:";
vector<int>::reverse_iterator rit;
for ( rit=myvector.rbegin() ; rit < myvector.rend(); ++rit )
cout << " " << *rit;
cout << endl;
return 0;
}
|
Notice how the reverse iterator iterates through the vector in a reverse way by
increasing the iterator. Output:
myvector contains: 5 4 3 2 1
|
reverse_iterator rend();
const_reverse_iterator rend() const;
Return reverse iterator to reverse end
Returns a reverse iterator
referring to the element right before the first element in the vector, which is
considered its
reverse end.
rend refers to the character
right before the one that would be referred to by member
begin.
Parameters
none
Return Value
A reverse iterator to the
reverse end of the sequence.
Both reverse_iterator and const_reverse_iterator are member types. In the vector class template, these are reverse random
access iterators, defined as reverse_iterator<iterator>
and reverse_iterator<const_iterator>
respectively.
Example
|
// vector::rbegin/rend
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> myvector;
for (int i=1; i<=5; i++) myvector.push_back(i);
cout << "myvector contains:";
vector<int>::reverse_iterator rit;
for ( rit=myvector.rbegin() ; rit < myvector.rend(); ++rit )
cout << " " << *rit;
cout << endl;
return 0;
}
|
Notice how the reverse iterator iterates through the vector in a reverse way by
increasing the iterator. Output:
void swap ( vector<T,Allocator>& vec );
Swap content
Exchanges
the content of the vector by the content of vec, which is another vector
of the same type. Sizes may differ.
After the call to this member
function, the elements in this container are those which were in vec
before the call, and the elements of vec are those which were in this.
All iterators, references and pointers remain valid for the swapped vectors.
Notice that a global algorithm function exists with this same name, swap, and the same behavior.
Parameters
vec
Another vector container of the same type as
this whose content is swapped with that of this container.
Return value
none
Example
|
// swap vectors
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
unsigned int i;
vector<int> first (3,100); // three ints with a value of 100
vector<int> second (5,200); // five ints with a value of 200
first.swap(second);
cout << "first contains:";
for (i=0; i<first.size(); i++) cout << " " << first[i];
cout << "\nsecond contains:";
for (i=0; i<second.size(); i++) cout << " " << second[i];
cout << endl;
return 0;
}
|
Output:
first contains: 200 200 200 200 200
second contains: 100 100 100
2D Vector
// An empty vector of vectors. The space between the 2 '>' signs is necessary vector<vector<int> > v2d;
vector<vector<int> > items[5][5];
vector<vector<int> > items ( 5, vector<int> ( 5 ) );
Vector < Vector <int>
> matrix2d; //this should be initialized as 255x255 2D vector
// Declare size of two
dimensional array and initialize.
|
vector< vector<int>
> vI2Matrix(3, vector<int>(2,0));
|
|
|
|
|
// If you intend creating many vectors of vectors, the following's tidier typedef vector<vector<int> > IntMatrix; IntMatrix m;
// Now we'll try to create a 3 by 5 "matrix".First, create a vector with 5 elements vector<int> v2(5, 99);
// Now create a vector of 3 elements. Each element is a copy of v2 vector<vector<int> > v2d2(3,v2);
// Print out the elements
for(int i=0;i<v2d2.size(); i++)
{
for (int j=0;j<v2d2[i].size(); j++)
cout << v2d2[i][j] << " "; cout << endl;
}
}
|
