The Standard Library

The Standard Library includes container classes: classes whose purpose is to contain other objects. There are classes for vectors, lists, etc. Each of these classes can contain any type of object (as long as the object can be copied safely - if it can't, use pointers to elements instead). You can, for example, use a vector<int> (meaning 'a vector of ints') in much the same way as you would use an ordinary C array, except that vector eliminates the chore of managing dynamic memory allocation by hand.

   vector<int> v(3);    // Declare a vector (of size 3 initially) of ints
   v[0] = 7;
   v[1] = v[0] + 3;
   v[2] = v[0] + v[1];  // v[0] == 7, v[1] == 10, v[2] == 17  
   v.push_back(13);     // add another element - the vector has to expand

Note the use of the push_back function - adding elements this way will make the container expand.

The Standard Library also includes about 70 algorithms that manipulate the data stored in containers - reverse, insert, unique, transform etc. Note that these operations act on the elements without explicit use of loops.

To use these features you need to include the corresponding header file. For example, #include <vector> is needed for vectors. CUED users can read the Standard C++ Library Class Reference. See the C++ and the STL document for examples.

Iterators

Iterators are like pointers. They save algorithm writers the worry of having to deal with the internals of containers. They come in various types: random access, bidirectional, forward, reverse, input, output. They can be const. Some containers support only some Iterator types (you can't for example randomly access a list). See the documentation for details.

Strings

In older C++ books and in C books, strings are arrays of characters - C-style strings. Except when speed is vital, C++ strings are preferable to these. For some operators (concatenation, for example) strings may be a lot faster than C's character arrays. Also

They grow on demand
The Standard Library algorithms work on them
Other containers use them
Natural constructions like s=s1+s2; are possible

String objects have many features in common with other Standard Library objects. Since strings are familiar to you, it's useful to look at the facilities in more detail to prepare you for other Standard Library components.

Iterators

The following routines provide iterators (pointers) of various kinds, depending on whether you want to go forwards or backwards through the string and whether you want to change the string. The same kind of routines exist for vector etc.

// Iterators - note the various types
 iterator       begin();
 const_iterator begin() const;
 iterator       end();
 const_iterator end() const;
 reverse_iterator       rbegin();
 const_reverse_iterator rbegin() const;
 reverse_iterator       rend();
 const_reverse_iterator rend() const;

Size

These routines (similar ones exist for other containers) give you size information. reserve() doesn't change size or initialize elements - resize() does. capacity() - size() = reserved size.

// Capacity
   size_type       size() const;
   size_type       length() const;
   size_type       max_size() const;
   void            resize(size_type, charT);
   void            resize(size_type);
   size_type       capacity() const;
   void            reserve(size_type);
   bool            empty() const;

Routines

These string-specific routines (only a selection is shown below) provide the functionality that C people are used to. The names aren't too hard to remember, and the default arguments are reasonable. The routines are overloaded, so find can be used to look for strings, characters or even C-strings.

Note also that the c_str routine returns a C string.

   const charT* c_str() const;
   size_type find(const basic_string&,
                  size_type = 0) const;
   size_type find(charT, size_type = 0) const;
   size_type rfind(const basic_string&,
                   size_type = npos) const;
   size_type rfind(charT, size_type = npos) const;
   size_type find_first_of(const basic_string&,
                           size_type = 0) const;
   size_type find_last_of(const basic_string&,
                          size_type = npos) const;
   size_type find_first_not_of(const basic_string&,
                               size_type = 0) const;
   size_type find_last_not_of(const basic_string&,
                              size_type = npos) const;
   basic_string substr(size_type = 0, size_type = npos) const;
   int compare(const basic_string&) const;
   int compare(size_type, size_type, const basic_string&) const;

The case history (section 21) has many examples of string usage. Here are 2 short programs -

#include <iostream>
#include <string>
using namespace std;

int main()
{
 string s1= "pine";
 string s2= "apple";
 cout << "length of s1 is " << s1.length() << endl;
 string s3= s1+s2;
 cout << "s1 + s2 = " << s3 << endl;
 string s4= s3.substr(2,4);
 cout << "s3.substr(2,4)=" << s4 << endl;
 
 cout << "s3.find(\"neap\")=" << s3.find("neap") << endl;
 cout << "s3.rfind('p')=" << s3.rfind('p') << endl; 
 return 0;
}

To get a line of text (that may include spaces) from the user, do

#include <iostream>
#include <string>
using namespace std;

int main()
{
 string str;
 cout <<"Type a string ";
 getline(cin,str);
 cout <<"you typed " << str << endl;
 return 0;
}

vector

Standard Library Vectors can have various element types and like other containers can be initialised in various ways:

vector <int> v; // an empty integer vector
vector <int> v(5); // 5 elements, initialised to the default 
                   // value of the elements, in this case 0.
                   // Vector resizing is expensive, so set to 
                   // the max size if you can. 
vector <int> v(5,13); // 5 elements initialised to 13 
vector <int> w(v.begin(),v.end());  // initialised from another container.

Many routines are available for vectors. For example, if you have a vector of strings, you can remove all the strings beginning with 'p' by doing the following

   // for this method you need to sort the items first
   sort(fruit.begin(), fruit.end());
   // create an iterator p1 for use with a vector of strings
   // and set it to point to the first string to remove 
   vector<string>::iterator p1=
        find_if(fruit.begin(), fruit.end(), initial('p'));
   // create and set p2 to point to the first string after
   // those that begin with 'p'
   vector<string>::iterator p2=
        find_if(p1, fruit.end(), initial_not('p'));
   // Now erase
   fruit.erase(p1, p2);

Note that you can't do the following (searching from each end of the vector) because forward and reverse iterators are different types, and you can't use erase with mixed types.

  sort(fruit.begin(), fruit.end());
  vector<string>::iterator p1=
        find_if(fruit.begin(), fruit.end(), initial('p'));
  vector<string>::reverse_iterator p2=
        find_if(fruit.rbegin(), fruit.rend(), initial('p'));
  fruit.erase(p1, p2);

These above examples use the standard algorithms, which are always useful as a fallback option, but the vector class has a more specialised routine which is likely to be faster

fruit.remove_if(initial('p'));

Remember that

vector elements can move! insert, for instance, changes its 1st argument.
vector doesn't have arithmetic operations: valarray (which is described later) does.
vector doesn't have range-checking by default.

Queues

Variations include

deque - (pronounced deck) double-ended queue. One of the basic containers.

queues - items are pushed into the back of the container and removed from the front. The underlying container can be vector or a deque. The items can be whatever you like. For instance you could create a queue of messages

// create a message structure
struct Message{ ... }

// wait until an item appears on the queue, then process it.
void server(queue<Message> &q)
{
  while(!q.empty()) {
    Message& m = q.front();
    m.service();q.pop();
  }
}

priority queues - items are pushed into the back of the container and removed from the front in order of priority. The underlying container can be vector, amongst other things. In the following example the priority is determined by comparing the value of the integers in the queue using less.

 #include <queue>
 #include <vector>
 #include <iostream>
 using namespace std;

 int main()
 {
   // Make a priority queue of int using a vector container
   priority_queue<int, vector<int>, less<int> > pq;
 
   // Push a couple of values
   pq.push(1);
   pq.push(7);
   pq.push(2);
   pq.push(2);
   pq.push(3);
   // Pop all the values off
   while(!pq.empty()) {
     cout << pq.top() << endl;
     pq.pop();
   }
 return 0;
 }

list

Lists are useful when items are likely to be inserted/deleted from the middle of long sequences. This example creates a vector then copies it into a list, reversing as it does so.

     #include <vector>
     #include <list>
     #include <algorithm>
     #include <iostream>
     using namespace std;

     int main()
     {
     vector<int> V;
     V.push_back(0);
     V.push_back(1);
     V.push_back(2);

     list<int> L(V.size());
     reverse_copy(V.begin(), V.end(), L.begin());
     exit(0);
     }

map

A map stores a mapping from one set of data (e.g. Names) to another (e.g. Phone numbers). The following example shows how to set up an ``associative array" - an array where you can use a string as an index. It records how many times each word appears on cin, the standard input.

int main()
{

string buf;
map<string, int> m;
while (cin>>buf) m[buf]++;
 // write out result (see next example)
}

A map keeps items in order and has no duplicate keys. Variations include

hash_map - an unsorted map.
multi_map - can have duplicate keys
set - a map with ignored values

// read in lines of the form 
//  red 7
//  blue 3
//  red 4

void readitems(map<string, int>& m)
{
  string word;
  int val=0;
      while(cin>>word>>val) m[word]+=val;
}

int main()
{
map<string, int>tbl;
readitems(tbl);
int total=0;
// We want to create an iterator p for use with this type of map.
// Since we're not going to change the map values using it,
// we'll make a const_iterator. We could do this using
//    map<string, int>::const_iterator p
// but if we wanted to create other iterators of this type
// it would be tedious. So we use 'typedef' to make 'CI' a
// shorthand for the long expression.

typedef map<string, int>::const_iterator CI;
   for (CI p=tbl.begin(); p!=tbl.end(); ++p) {
      total+=p->second;
      cout<<p->first << '\t' << p->second << '\n';
   }
   cout << "total\t" << total << endl;
   return !cin;
}

Here's a fragment using multimap showing how to print out all the values associated a particular key (in this case the string ``Gold"). It uses typedef as in the above example, and the useful equal_range function which returns an iterator to the first and last elements with a particular key value. Pairing up variables is so common that a facility called pair declared in the <utility> file is available to assist in their creation. The pair used here holds 2 iterators, but it can hold 2 items of different types too.

void f(multimap<string,int>&m)
{
typedef multimap<string, int>::iterator MI;
pair <MI,MI> g = m.equal_range("Gold");
   for (MI p=g.first; p!=g.second; ++p) {
      // print the value out
   }
}

In maps, m["blah"]=1; overwrites, m.insert(val) doesn't.

bitset

This provides efficient operators on bits.

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
const unsigned int width = 32;
bitset<width> b1=23;
bitset<width> b2 = 1023;
bitset<width> b3;
 cout << "Type in a binary number (type a non-binary digit to end) ";
 cin >> b3;
 cout << "You typed " << b3 << endl; 
 cout << "b2 flipped=" << b2.flip() << endl;
 cout <<  "b1=" << b1 << endl;
return 0;
}

valarray

valarrays are designed for doing fast vector calculations. They can be initialised in various ways

// v1 is a vector of 2000 integer elements each initialised to 7
valarray<int> v1(7,2000); 

// v2 is initialised to the first 4 elements of d
const double d[]= {1.0, 1.0, 2.0, 3.0, 5.0};
valarray<double> v2(d,4);

// v3 is a copy of v2
valarray<double> v3=v2;

Operations include

v2 = 5;           // sets each element to 5
v3 *= .5;         // halve each element
v2 = v3.shift(2); // copy the elements of v3 shifted 2 to the left, into v2
                  // filling spaces with 0.0
v3 = v2.cshift(-2) //copy the elements of v2 shifted 2 to the right, into v3
                  // filling the spaces with elements that have fallen off
                  // the other end
v2= v2*cos(v3);

A slice is what you get when you take every nth element of a valarray. This is especially useful if the valarray represents the values in a 2D array - slices are the rows or columns. A slice needs to know the index of the first element, the number of elements and the 'stride' - the step-size.

slice_array<double>& v_even= v2[slice(0,v2.size()/2,2);
slice_array<double>& v_odd= v2[slice(1,v2.size()/2,2);
v_odd *=2 ; // double each odd element of v2

A gslice lets you extract subarrays from a valarray that represent the values in a 2D array.

A mask array lets you pick out arbitrary elements. It needs to contain bool values and shouldn't be bigger than the valarray it's used with. When used as a subscript, the valarray elements corresponding to the true elements of the mask array will be chosen.

bool b[]= { true, false, true, true};
valarray<bool>mask(b,4);
valarray<double>v4= v[mask];

There's also an indirect array.

valarrays are built for speed - they aren't intended to grow, and operations aren't error-checked - if you multiply together 2 valarrays of different lengths the behaviour is undefined.

Algorithms

Algorithms (in <algorithm>) operate on containers, including strings. They may not always be the fastest option but they're often the easiest. They fall into 6 groups

Search algorithms - search(), count_if(), etc.
Sorting algorithms - sort(), merge(), etc.
Deletion algorithms - remove(), unique(), etc.
Numeric algorithms - partial_sum(), inner_product(), etc.
Generation algorithms - generate(), for_each(), etc.
Relational algorithms - equal(), min(), etc.

Algorithms usually take as their first 2 arguments iterators to mark the range of elements to be operated on. For example, to replace 'A' by 'B' in a string str one could do

  replace(str.begin(), str.end(), 'A', 'B');

Here's one way to count how many instances of a particular character there are in a string using the find algorithm.

int count (const string& s, char c)
{
string::const_iterator i=find(s.begin(), s.end(),c);
int n=0;
  while(i!=s.end()){
    ++n;
    i=find(i+1, s.end(),c);
  }
  return n;
}

Here's a way to count the number of 'z' characters in a C-style string using the count algorithm. Note how the character array can be used like other containers.

void g(char cs[], int sz)
{
  int i1 = count(&cs[0], &cs[sz], 'z');
}

Here's the count algorithm again, this time being used to find a particular complex number in a list.

void f(list<complex>&lc)
{
int i1 = count(lc.begin(), lc.end(), complex(1,3));
}

Other algorithms include next_permutation and prev_permutation

int main()
{
char v[]="abcd";
  cout << v << '\t';
  while (next_permutation(v, v+4))
      cout << v << '\t';
}

random_shuffle,

char v[]="abcd";
  cout << v << '\t';
  for (int i=5;i;i--) {
     random_shuffle(v, v+4);
     cout << v << '\t';
  }

and a routine to cycle elements

rotate (first, middle, last)

rotate ``swaps" the segment that contains elements from first through middle-1 with the segment that contains the elements from middle through last.

Set algorithms

Set algorithms include

includes()
set_union()
set_intersection()
set_difference()
set_symmetric_difference()

The following, while demonstrating some of these routines, uses 2 ideas that are often useful

an output stream can be thought of as a container, so you can ``copy'' other containers onto it. The line
```
copy(s1.begin(), s1.end(), ostream_iterator<int>(cout," "));
```
also puts spaces between the integers being printed. For now, don't worry if you don't understand the mechanics - it's useful so just use it!
Sometimes you won't know how many resulting elements will be produced by an operation, you just want them all added to a container. inserter (which calls the container's insert() routine), front_inserter (which calls the container's push_front() routine - which vectors for example don't have) or back_inserter (which calls push_back()) do that for you.

 #include <algorithm>
 #include <set>
 #include <iostream>
 #include <iterator> // needed for ostream_iterator
 using namespace std;

 int main()
 {
   //Initialize some sets
   int a1[10] = {1,2,3,4,5,6,7,8,9,10};
   int a2[6]  = {2,4,6,8,10,12};

   set<int> s1(a1, a1+10), s2(a2, a2+6), answer ;
   cout << "s1=";
   copy(s1.begin(), s1.end(),
        ostream_iterator<int>(cout," "));
   cout << "\ns2=";
   copy(s2.begin(), s2.end(),
        ostream_iterator<int>(cout," "));

   //Demonstrate set_difference
   set_difference(s1.begin(), s1.end(),
                  s2.begin(), s2.end(), inserter(answer,answer.begin()));
   cout << "\nThe set-difference of s1 and s2 =";
   copy(answer.begin(), answer.end(),
        ostream_iterator<int>(cout," "));
   cout << endl;
   return 0;
 }

Using member functions

Algorithms can use the member functions of objects they're manipulating.

void print_list(set<Employee*>& s)
{
for_each(s.begin(), s.end(), mem_fun(&Employee::print));
}

Predicates

Some algorithms can be given a function to modify their behaviour. For example, the find_if algorithm can find items that conform to a particular condition as specified by a function. A predicate is a function object (an object that behaves like a function) that returns a bool showing whether or not an item matches the condition.

Creating predicates

<functional> supplies common conditions that can operate on various types: e.g., greater_equal<int>(), plus<double>(), logical_or<int>() etc. The following does a vector multiplication of a and b, putting the answer in res to which elements are added one at a time.

void discount(vector<double>& a, vector<double>& b, vector<double>& res)
{
transform(a.begin(), a.end(), b.begin(), back_inserter(res), multiplies<double>());
// vector multiplication
}

Adapters

Note: These are sometimes useful but look complicated, so don't worry if you don't understand them. Examples are online .

Adapters are ways to adapt existing predicates - they take and return a function that we can then use with Standard Library algorithms. There are 4 types -

binder: - to use a 2-arg function object as a 1-arg function. less is a binary predicate. If we want make a unary predicate from it we can do bind2nd(less<int>(),7)).
member function adapter: - to use a member function
pointer to function adapter: - to use a pointer to a member function
negator: - to negate an existing predicate

These can be combined -

... find_if ( ....... not1(bind2nd(ptr_fun(strcmp), "funny")));

Department of Engineering

IT Services

The Standard Library

Iterators

Strings

Iterators

Size

Routines

vector

Queues

list

map

bitset

valarray

Algorithms

Set algorithms

Using member functions

Predicates

Creating predicates

Adapters