These are designed to be general, efficient, and powerful rather than easy to use. Some of them allow you to easily access items inside the data structure, one at a time. To help you do this C++ has Iterators. An iterator is a kind of generalized subscript. An iterator selects one item in a data structure. An iterator can be moved to different items in the structure.
The C++ library also has a large number of useful Algorithms. These are designed to make it quick to create programs that do well known procedures efficiently.
#include | Description[See] |
---|---|
<algorithm> | ready-to-use functions that manipulate containers of all types [ Algorithms ] |
<bitset> | A subset of of a fixed and small set of items [ More ] |
<deque> | Double Ended Queue with pop and push at both ends plus indexing. [ More ] |
<list> | A randomly changing sequence of items [ Lists ] |
<map> | An collection of pairs of items indexed and ordered by the first one [ Maps and Sets ] |
<queue> | A Sequence of items with pop and push at opposite ends [ Queues ] |
<set> | An ordered collection of items [ Maps and Sets ] |
<stack> | A sequence of items with pop and push at one end only [ Stacks ] |
<utility> | Defines what a pair is and some other simple classes. |
<vector> | A dynamic array [ Vectors ] |
Name | Properties | Insert/Delete | Other Operators | Assignment/copy |
---|---|---|---|---|
stack | empty(), size() | pop(),push(T) | top() | operator = |
queue | empty(), size() | pop(),push(T) | front(), back() | operator = |
vector | empty(), size() | push_back(T), pop_back() | front(), back(), operator[index], at(index)[see note1], Iterators | operator = |
deque | empty(), size() | push_back(T), pop_back(), push_front(T), pop_front() | front(), back(), operator[index], | operator = |
list | empty(), size() | push_back(), pop_back(), push_front(T), pop_front(), insert(...), erase(...) | front(), back(), sort(), clear(), reverse(), merge(l), Iterators, | operator = |
string | empty(), length() | - | operator[index], substr, +(concatenate), Iterators, | operator = |
map, multimap | empty(), size() | - | operator[key_type], find(...), count(...), Iterators, | operator = |
set, multiset | empty(), size() | insert(...), erase(...) | find(...), count(...), Iterators, | operator = |
Purpose | Code |
---|---|
To be able to use STL vectors | #include <vector> |
To declare an empty vector of items with type T. | vector<T> v; |
To declare a vector of n items with type T. | vector<T> v(n); |
test to see if v is empty: | v.empty() |
find how many items are in v: | v.size() |
push t in T onto the end of v: | v.push_back(t) |
pop the back of v off v: | v.pop_back() |
get the front item of v: | v.front() |
change the front item: | v.front() = expression; |
get the back item of v: | v.back() |
change the back item: | v.back() = expression; |
Access the i'th item (0<=i<size()) without checking to see if it exists: | v[i] |
Assign a copy of v1 to v: | v = v1 |
Sorting and operating on all items efficiently | see Iterators below. |
. . . . . . . . . ( end of section Vectors) <<Contents | End>>
void reverse(string & x)
{
stack<char> s; //creates empty stack of characters
//Put characters from x onto the stack
for(int i=0; i<x.length(); ++i)
s.push(x[i]);
//take characters off of stack and put them back into x
for(int i=0; !s.empty(); ++i, s.pop())
x[i]=s.top();
}
Purpose | Code |
---|---|
To use stacks | #include <stack> |
Declare an empty stack of items of type T | stack<T> s; |
test to see if s is empty: | s.empty() |
find how many items are in s: | s.size() |
push a t of type T onto the top: | s.push(t) |
pop the top off s: | s.pop() |
get the top item of s | s.top() |
change the top item: | s.top() = expression; |
. . . . . . . . . ( end of section Stacks) <<Contents | End>>
// A simple example of putting three items into a queue and
// then taking them off the queue.
#include <iostream>
#include <queue>
int main()
{
queue<char> q;
q.push('a');
q.push('b');
q.push('c');
cout << q.front();
q.pop();
cout << q.front();
q.pop();
cout << q.front();
q.pop();
}
Purpose | Code |
---|---|
To be able to use STL Queues | #include <queue> |
To declare an empty queue of items of type T | queue<T> q; |
test to see if q is empty: | q.empty() |
find how many items are in q: | q.size() |
push a t:T onto the end of q: | q.push(t) |
remove the front from q: | q.pop() |
get the front item of q: | q.front() |
change the front item: | q.front() = expression; |
get the back item of q: | q.back() |
change the back item: | q.back() = expression; |
. . . . . . . . . ( end of section Queues) <<Contents | End>>
Purpose | Code |
---|---|
To be able to use STL deques | #include <deque> |
To declare an empty deque of items of type T | deque<T> l; |
test to see if l is empty: | l.empty() |
find how many items are in l: | l.size() |
push a t:T onto the end of l: | l.push_back(t) |
pop the last off l: | l.pop_back() |
push a t:T onto the start of l: | l.push_front(t) |
pop the front of l off l: | l.pop_front() |
get the front item of l: | l.front() |
change the front item: | l.front() = expression; |
get the back item of l: | l.back() |
change the back item: | l.back() = expression; |
Access the i'th item (0<=i<size()) without checking to see if it exists: | v[i] |
Assign a copy of q1 to q: | q = q1 |
Insert and erase items inside a Deque(slow) | [ Insert and Delete ] below. |
Efficiently visit each item in turn | see Iterators below. |
Here is an example:
//Using a list to sort a sequence of 9 numbers.
#include <iostream>
#include <list>
void print(list<int> a);//utility function print lists of ints
int main()
{
list<int> a;
//Put 9,8,7,6,5,4,3,2,1 onto the list
for(int i=0; i<9;++i)
a.push_back(9-i);// put new element after all the others
print(a); //here the list contains (9,8,7,6,5,4,3,2,1)
a.sort();//in the <list> library!
print(a); //here the list contains (1,2,3,4,5,6,7,8,9)
}
Purpose | Code |
---|---|
To be able to use STL lists | #include <list> |
To declare an empty list of items of type T | list<T> l; |
test to see if l is empty: | l.empty() |
find how many items are in l: | l.size() |
push a t:T onto the end of l: | l.push_back(t) |
pop the last off l: | l.pop_back() |
push a t:T onto the start of l: | l.push_front(t) |
pop the front of l off l: | l.pop_front() |
get the front item of l: | l.front() |
change the front item: | l.front() = expression; |
get the back item of l: | l.back() |
change the back item: | l.back() = expression; |
Sort the list: | l.sort() |
Clear the list: | l.clear() |
Merge a sorted list into a sorted list: | l.merge(list_of_sorted_elements) |
Reverse the list: | l.reverse() |
Assign a copy of q1 to q: | q = q1 |
Insert and delete items inside a List | [ Insert and Delete ] below. |
Efficiently visit each item in turn | see Iterators below. |
For example if iterator1 refers to a place in list1 and iterator2 to an element in list2 before this command:
list1.splice(iterator1, list2, iterator2);then the iterator2 item will be moved inside list1 afterwards. The iterators become invalid.
. . . . . . . . . ( end of section Lists) <<Contents | End>>
const int max = 10;
float a[max];
...
for(int i=0; i<max; ++i)
process(a[i]);
...Here is what must be done if the size of an array is determined at run time rather than at compile time:
int max;
...
float * a;
a= new float[max];
...
for(int i=0; i<max; ++i)
process(a[i]);
...
delete []a;Arrays are a primitive data structures. Once declared they stay the same size: no popping or pushing! No insert or erase. They can be accessed by using a subscript, and this access is extremely fast. There is no test for emptiness or a function to find their size! However there is a tricky expression you can use:
sizeof(array)/sizeof(array[0])There is no test to see if the item you ask for exists. Programs can easily crash themselves or the operating system by manipulating nonexistent array items.
C arrays were designed so that they could be accessed by using a variable that stores the address of an item. These variables are called pointers. They are used like this
for(float *p=a; p!=a+max; ++p)
process(*p);
...
C++ iterators have syntax based on C pointers. For any serial container c you process all the items by writing:
for( p=c.begin(); p!=c.end(); ++p)
process(*p);For any type T, list<T>, vector<T>, set<T>, etc. are Containers. So for any type T, there are iterator classes called
list<T>::iterator
vector<T>::iterator
set<T>::iteratorAll Containers have one or more iterators. Container class C has an iterator called
C::iteratorTo declare an iterator p for container of type C use:
C::iterator p;Iterators are often declared and initialized like this:
list<T>::iterator p=c.begin();
vector<T>::iterator p=c.begin();
set<T>::iterator p=c.begin();To move an iterator to the next item in a container write
++p;To see if an iterator has gone past the last item in c use this test:
p != c.end();To see the item that p refers to use *p.
For container classes C of objects type T and any object c of type C:
Table
Purpose | Code |
---|---|
Move iterator p onto the next object in c(if any!). | ++p |
Access the value selected by p in its container. | *p |
To change the value selected by p in its container. | *p = expression |
The iterator that refers to the first item in c | c.begin() |
The iterator that refers to one beyond c. | c.end() |
Test to see if iterator p has come to the end of container c: | p != c.end(); |
Make p refer to the same item as p1 | p = p1; |
The names for containers and iterators are long winded. C and C++ have a way to define a short name for a complex data type. The statement
typedef list< int> L;defines L to be short for list<int> and then
typedef L::iterator LI;defines LI to be the type list<int>::iterator.
Purpose | Code |
---|---|
Insert item x into List l before item pointed at by iterator p | l.insert(p, x); |
Erase the element pointed at by iterator q in List l | l.erase(q); |
#include <iostream>
#include <list>
void print(list <char> );// elsewhere
main()
{ list <char> l;
l.push_back('o'); l.push_back('a'); l.push_back('t');
print(l); // l is ('o', 'a', 't').
list <char>::iterator p;
p=l.begin();
cout <<" "<< *p<<endl; // p refers to the 'o' in ('o', 'a', 't')
l.insert(p, 'c');
// l is now ('c', 'o', 'a', 't') and p still refers to 'o'
cout <<" "<< *p<<endl;
print(l);
l.erase(p);
cout <<" "<< *p<<endl; // p refers to an 'o' but it is not in l!
print(l);
l.erase(l.begin()); //removes front of l
print(l);
}
For many containers we have a range that includes the whole container:
container.begin()
container.end()The above pair encloses the complete container. Given a container c, then c.begin() and c.end() form a range.
Suppose that first and last form a range and it is an iterator then:
for( it=first; it != last; it++)will refer to each element in the range [first..last) in turn. In the body of the for loop the value of the element is *it.
Here are two examples - one prints a list and the other a vector:
(print_list):
void print( list<int> &a)
{
for(list<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)
cout << *ai << " ";
cout << endl;
cout << "----------------"<<endl;
}
void print( vector<int> &a)
{
for(vector<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)
cout << *ai << " ";
cout << endl;
cout << "----------------"<<endl;
}You can see how alike the code for print_list and print_vector are.
Container_type::const_iteratorAll operations on iterators work with const_iterators, unless they change the value of the items the iterators refer to. For example if p is a const_iterator then you can not write '(*p) = something'. Further 'p->operation(...)' or '(*p).operation(...)' will only compile when the operation is declared to not change the object to which it applies. In other words it must be a const member function.
An iterator works well for handling existing items in a container.
It can access and change existing items. It is
not designed to add items.
A normal iterator can work incorrectly if it is used to add
data to a container before or after the container.
An inserter is a special kind of iterator that adds new items to
a container. The library <iterator> provides three ready made inserters:
(inserters):
Table
back_inserter(Container& C) | [ inserter.cpp ] |
front_inserter( Container& C) | [ front.inserter.cpp ] |
inserter(Container & C, Container_iterator p) (insert before p) | TBA |
. . . . . . . . . ( end of section Iterators) <<Contents | End>>
Purpose | Notation | Meaning |
---|---|---|
class name | pair<X, Y> | set of pairs (x,y) where x is in class X and y is in class Y. |
get first | pair.first | the first item in pair |
get second item | pair.second | the second item in pair |
make a new pair | make_pair(x,y) | constructs instance of pair<X,Y> with first=x and second=y. |
Maps are often used to organize information in a table or part of a data base.
In the C++ library <map> allows you to use a very clever data structure that stores pairs of items in it. If you declare a map<A,B> then it will store one B value paired with each A value. Maps give a new meaning to the subscript or array index operator []. If we have a map<A,B> f then 'f[a]=b' adds a new item to the map that associates 'a' with 'b'. We can then recall 'b' as the value f[a].
We can test to see if a map has a 'a' like this
if( f.find(a) != f.end() )
If we declare map<A,B> f then for each a in A we have the paired item f [ a ]. If p is an iterator then (*p).first will be the A in each pair in turn, and (*p).second is the associated B value.
Here is a example of a quick and dirty program to help me add up all the scores in particular class. All I have to do is type in all the points scored in the class as a sequence of names and scores.
adam 10 eve 15 adam 17 eve 5 eve 5 eve 4 adam 10It prints out a sorted list of names each with their total score:
#include <string>
#include <iostream>
#include <map>
typedef map<string,int> MSI; //abbreviation: MSI's are sets Mapping Strings to Ints
int main()
{
MSI score;
string si;//student id on input
int sc;//score for student with id si
while( cin>>si>>sc )
score[si] = score[si] + sc;
/* for each si on the input, score[si] is the sum of si's scores.
*/
for( MSI::iterator p= score.begin(); p!=score.end(); p++)
cout << (*p).first << "\t" << (*p).second <<endl;
}//main[ scoring.cpp ] It would be hard to write a program this simple that gave me equal flexibility with out using <map>.
Here [ fibcache.cpp ] is a way to use a map to keep values in a recursive function (fibonaci again) from re-evaluating the same value more than once.
If all you want to do is collect some items together and keep them in order you can use the C++ <set> template. Here is a simple example [ stlset.cpp ] of using the standard library set to accumulate a set of strings, print them, remove one, and print them again. Seeing that set is an ordered set of elements you also sort the data as it is stored.
If you need to store multiple copies of the same data in a map or set then use multimap and multiset instead. They are in the same libraries (<map> and <set> respectively) and work almost identically. However, in a set each items can appear only once, in a multiset an item can appear many times. Similarly in a multimap you can have more than one pair(x,y) with the same x value.
In general the standard C++ set<T> and map <T> only works if you have the "<" operator defined on data of type T. This is OK for all elementary data type and for strings. If you want T to be your own class you have to define an operator < in the class:
class T{
...
public:
bool operator<(T other){.....}
...
};// class T
Sets, multisets, and maps store the data in increasing size. So you can easily sort data by inserting it into a multimap (say) and then using an iterator to get it out in sorted order.
Similarly input and output streams can be treated like containers. In particular, you can attach an iterator to a stream and use read(istream_iterator) or write(ostream_iterator) functions on it! Because strings and streams have iterators they can be used as sources and targets for many of the algorithms in the <algorithm> library. See Algorithms.
sort(v.begin(), v.end());Here is a sample of the code:
//Sorting a vector with 9 integers
#include <iostream>
#include <vector>
#include <algorithm>
void print( vector<int> ) ;//utility function outputs a vector
int main()
{
vector<int> a;
// Place 9,8,7,6,5,4,3,2,1 into the vector
for(int i=0; i<9;++i)
a.push_back(9-i);// put new element after all the others
print(a); // elements of a are (9,8,7,6,5,4,3,2,1)
sort( a.begin(), a.end() ); //in the STL <algorithm> library
print(a); // elements are now in order.
}Here is a quick list of some simpler algorithms in <algorithm>. In each example the elements processed are in range [first .. end):
Name | Arguments | Returns | Note |
---|---|---|---|
for_each | (first, end, function) | void | apply a function to all items in range. |
find | (first, end, value) | iterator | find item in range that matches an item. |
count | (first, end, value) | number | count matching items in range. |
equal | (first, end, another) | bool | true iff all items in two ranges are equal. |
transform | (first, end, function) | void | apply transformation to items in range. |
copy | (first, end, another) | void | copy one range to another(works between containers of different types!). |
reverse | (first, end) | void | reverse items in range. |
rotate | (first, end) | void | end of range moved in front of start. |
Each instance of a template class is itself a class. It can be used as an element in any of the data structures mentioned here. Thus you can have a vector of lists of ints:
vector < list <int> > vli;or a list of vectors:
list < vector <int> > lvi;Or even a stack of vectors each containing a number of queues of strings:
stack< vector < queue < string > > > svqs;
Be careful however to put a space between the ">"s in declarations like these. C++ has a special meaning for the symbol ">>".
Here are some of the other ready-to-wear templates:
You can also create your own container classes! A Computer Science Data Structures (CS2) class like CSUSB's CS330 will teach you how these data structures are implemented. There are some useful resources on the world wide web, see [ See Also ] below.
There must be a space between the two ">" signs below:
stack< vector< T > > svt;
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 instead of using push_back to add new items, to use [...] as if it created new elements. It doesn't.
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, or a pop_front 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 our currant compiler you will find that 'at' generates an error. Use '[i]' (very carefully) instead!
On some older compilers and libraries when you need a <string> as well as either <list> or <vector> you need to
#include <string>before including the list or vector rather in the reverse order! Older string library appear to define some special versions of vector and list operators and the older compilers can not make up its mind which to use.
If the standard <list> and <vector> is not found then you are using an older C++ compiler.
On some older C++ libraries you are forced to indicate how the stack or queue is implemented whenever you declare one. You write either
stack< vector<T> > s;or
stack< list<T> > s;or
queue< list<T> > q;or
queue< vector<T> > q;If you are forced to do this... lookout for the space between ">" and ">"!
. . . . . . . . . ( end of section Errors) <<Contents | End>>
Also see my notes on the C++ language: [ STL in c++ ]
. . . . . . . . . ( end of section The C++ Standard Library) <<Contents | End>>
. . . . . . . . . ( end of section The C++ Standard Library) <<Contents | End>>