This is a short primer on vectors for CSE202 students.
Vectors are a powerful yet simple data structure
available as part of the
standard library (STL) for the language C++.
They should be used whenever you have an unknown number of
items all of the same type that you need to be kept in sequence
and we need to accesws them by their number in the sequence.
Example: a roster of students in a class.
Vectors are held in a special library and can be used in a file that has
at its beginning.
|Declare Empty|| vector<type> v;
|Declaration|| vector<type> v(initial_size);
|Mutators|| v.push_back(T)||v.pop_back(), ...
|Operators|| v[int]||v.at(int)|| v1=v2;||v1==v2, ...
Other operators exist but they are inefficient.
You need to remember the following facts about vectors:
- A vector is an object that contains a sequence of other objects inside it.
- The objects inside must all take up the same amount of storage.
- They are numbered starting with 0.
- If the whole vector is called v then the items in it are written v, v, v, ...
- The last item is v[v.size()-1] NOT v[v.size()].
- New items can be "pushed" onto the end of the vector using push_back(item).
- The last item can be "popped" off of a vector using pop_back().
- Vectors can therefore change size.
- We can find out the current size of a vector v: v.size()
- Vectors can be empty. If v is empty then v.empty() is true.
- For-loops are used to access every item in turn
for( int i=0; i < v.size(); i++) access(v[i]);
- If the items in a vector are pointers to objects you can save space (normally) and
speed up insertion, sorting and deletion.
- Pointers are all the same size so you can store pointers to different types of object in one vector.
Pointers are therefor polymorphic -- (multiple shapes).
- In real software development you put pointers in containers rather that the data
vector <*Data> v;
Suppose that T is any type or class - say int, float, double, or
the name of a class, then
declares a new and empty vector called v.
declares a new vector called v with N unknown elements in it.
Given object v declared like the above:
- test to see if v is empty:
- find how many items are in v:
- push t in T onto the end of v:
- pop the back of v off v:
- get the front item of v:
- change the front item:
v.front() = expression;
- get the back item of v:
- change the back item:
v.back() = expression;
- Access the i'th item (0<=i<size()) without checking to see if it exists:
- Assign a copy of v1 to v:
v = v1
- There are a libraries that manipulate vectors that will be described later.
Suppose that we want to input an unknown number of numbers and then print them
out forwards and then backwards, using a vector. We will push ints onto the back of a vector
called v. We will then print each item in v in turn. Finally we will print the
vector backwards. You can download the code from
[ Vector.cpp ]
but here are the highlights. First we must declare the facilities we want to use
void print( vector<int> ) ;//utility function outputs a vector of ints
void print_backwards( vector<int>);
Then we describe the main program:
cout <<"Input some numbers and then end the input\n";
Finally the two procedures that print out the data:
void print_backwards( vector<int> a)
for(int i=a.size()-1; i>=0; --i)
cout << a[i] << " ";
cout << endl;
cout << "----------------"<<endl;
void print( vector<int> a)
for(int i=0; i<a.size(); ++i)
cout << a[i] << " ";
cout << endl;
cout << "----------------"<<endl;
Down load (with a shift-click!) the above code from
[ Vector.cpp ]
, test it, and modify it to print out all the even numbered items (0,2,4,6,...)
and then all the odd ones(1,3,5,...).
A vector is a special kind of Container.
A Container is any data structure that holds a number of
objects of the same type.
The oldest example
of a Container in C++ is an array. In C you
had arrays and you would
write code like this:
const int MAX = 10;
for(int i=0; i<MAX; ++i)
Arrays are like vectors except that:
- They have a fixed size specified in the declaration.
- They are faster than vectors.
- You can not add or delete items from an array.
- The syntax is simpler.
- The absolutely no safety belt: if an index has wrong value, you crash.
The designers of the C++ library made sure that the <string>
library shares a lot of common features with <vector> and other sequential
containers. The main differences are (1) <string>s can only hold
characters, and (2)<string>s have some useful extra operations available.
[ string ]
which is a summary of the <string> library.
The way vectors and arrays work is best understood by looking at how they
are implemented. This means knowing what really happens when the computer
executes a piece of code which uses a vector or array. Recall that everything
inside a computer is a number. The data are numbers stored in locations. These
locations have addresses. These addresses are used by the computer to retrieve
items and to store them. A single variable is given a piece of storage when it is
then on the program uses the address in place of the symbolic name in the program.
An array or vector is a block of similar pieces of storage. The block of storage
starts at the start of the vector itself, the next block is one piece of storage
vector first item vector
second item vector
third item vector
and so on. The computer has a simple rule to find vector[i]. It looks at the
item that starts at i*length_of_one_item + address_of_vector.
It helps to draw diagrams of vectors and work out by hand, on these diagrams
what an algorithm, or your program is doing. Pretending to be a computer
can teach you a lot about a complex computation.
back::=a special item in a sequential container that has no items after it.
the iterator end() is always the next place after the back item.
container::=A data structure which contains a number of data items that can gain and lose items as the program runs. Examples include vectors, lists, stacks, ...
contiguous::=a way of implementing data structures so that a continuous block of storage is used and items are found by calculating the address. Vectors are a type of contiguous data structure available to C++ programmers.
front::=a special item in a sequential container that has no items before it.
generic::code= a function or class that is a template and can be used for data of many different types depending on its parameters.
increment::operation=moving an iterator/pointer/index on to the next iterator/pointer/index value commonly symbolized by ++ in C-like languages.
operation::=something that can be applied to an object to extract information from it or to change its state.
random_access::=being able to do things to items in a container in an unpredictable order typically by using an integer as an index or subscript.
template::= See http://cse.csusb.edu/cs202/templates.html
, notes on templates.
vector::container=a vector is a sequential container that is optimized to allow efficient random_access of items by using an index.
Vectors are are given in a contiguous block of storage space.
Vectors are useful whenever data must be stored in
one order accessed in a different one. A vector is
a dynamic array - an array that can grow when needed.
[ Vectors ]
You must always #include the header if you use the word
You must be sure that all indices or subscripts stay between 0 and size()-1 inclusive.
Trying to change the size of an array does not work.
If a program compiles, loads, crashes, and there is a subscript operator ([...])
then check to see if the subscripted item has been put into the container
before the subscripted element is accessed. A very common error is to
declare a vector with no length and
to use [...] as if it created new elements. It doesn't. Use 'push_back(..)'
to add new elements to a vector.
If you are unable to
show that a subscript is in range then use a condition like the following
to guard thing[i] from errors:
0<= i && i < thing.size()
If a program compiles, loads and crashes and it has a pop, pop_back,
function than make sure that there is an item to
be "popped"! In code you can use the empty function to guard statements
that contain "pop" from blowing up.
On some older compilers and libraries
when you need a <string> as well as <vector>
you need to
before including <vector>. Obscure errors happened if they
were in the reverse order! The older string library appeared to
define some special versions of vector operators
and the older compilers can not make up its mind which to use.
If the standard <vector> is not found then you are using an older C++
You can have vectors of vectors:
vector < vector <int> > matrix;
but you must put at least one space between the two ">" symbols.
The following is wrong:
vector < vector <int>> matrix;
. . . . . . . . . ( end of section Errors) <<Contents | End>>
. . . . . . . . . ( end of section C++ Vectors) <<Contents | End>>
accessor::=`A Function that accesses information in an object with out changing the object in any visible way".
In C++ this is called a "const function".
In the UML it is called a query.
Algorithm::=A precise description of a series of steps to attain a goal,
[ Algorithm ]
class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
constructor::="A Function in a class that creates new objects in the class".
Data_Structure::=A small data base.
destructor::=`A Function that is called when an object is destroyed".
Function::programming=A selfcontained and named piece of program that knows how to do something.
Gnu::="Gnu's Not Unix", a long running open source project that supplies a
very popular and free C++ compiler.
mutator::="A Function that changes an object".
object::="A little bit of knowledge -- some data and some know how". An
object is instance of a class.
objects::=plural of object.
Current paradigm for programming.
Semantics::=Rules determining the meaning of correct statements in a language.
a previous paradigm for programming.
STL::="The standard C++ library of classes and functions" -- also called the
"Standard Template Library" because many of the classes and functions will work
with any kind of data.
Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
Q::software="A program I wrote to make software easier to develop",
TBA::="To Be Announced", something I should do.
TBD::="To Be Done", something you have to do.
UML::="Unified Modeling Language".
void::C++Keyword="Indicates a function that has no return".