Max Berger

In most containers that we have seen so far, the order of elements is important. The STL provides several sequence containers.

Most of these containers support the same operations. Then why bother having two implementations for it? Because every container performs differently on different operations!

Example:

We'll talk about the two template types "vector" and "list" (in the <vector> and <list> includes)

A vector is based on an array.

list is based on a liked list

You will learn more about the implementation issues in the data structures class.

Both vector and list support:

Only list supports:

Only vector supports:

Here are some examples:

#include <iostream>
#include <list>   // For list
#include <vector> // For vector

using namespace std; // All STL containers are 
                     // in the std namespace.

int main()
{

  vector<int> a;  // Declare a vector that takes int
  a.push_back(3); // add to end of vector
  a.push_back(24);
  a.push_back(42);
  
  // as long as we still have elements
  while (!a.empty()) { 
    // print the last element
    cout << a.back() << " ";
    // and remove it!
    a.pop_back();
  }
  cout << endl;
  // this (above) printed 42 24 3

  list<int> b; // declares a linked list that takes int
  // adds some elements to the end
  b.push_back(3);
  b.push_back(24);
  b.push_back(42);
  // as long as there are elements left
  while (!b.empty()) {
    // print the last element
    cout << b.back() << " ";
    // and remove it
    b.pop_back();
  }
  cout << endl;
  // this (above) printed 42 24 3

  list<int> c; // declares a linked list that takes int
  // adds some elements to the end
  c.push_back(3);
  c.push_back(24);
  c.push_back(42);
  // as long as there are elements left
  while (!c.empty()) {
    // print the first element
    cout << c.front() << " ";
    // and remove it
    c.pop_front();
  }
  cout << endl;
  // this (above) printed 3 24 42

  return 0;
}

So now that we see the use of different containers, lets see what we have available:

Practice: Implement a short program (the whole program) that

#include <iostream>
#include <deque>
using namespace std;
int main()
{
  deque<float> f;
  f.push_back(1.234);
  f.push_back(12.34);
  f.push_back(123.4);
  cout << f.front() << " ";
  cout << f.at(0) << " ";
  cout << f[0] << endl;
  f.pop_front();
  cout << "There are " << f.size() << " elements left!";
  cout << endl;
  return 0;
}

Since all the containers have a different implementation, we need a standard way of going through all the items.

These things are called "iterators".

We are already used to iterators, we just didn't know it: For vector and arrays we used integers. We ran theses from 0 to size()-1. Therefore this "int" was an iterator.

Iterators use a lot of operator overloading to behave similar to pointers.

Declaring: To declare an iterator use the subclass "iterator" for your specific data type. Example:

vector<int> a; // Your vector a
// ... a lot of a.push_back()

// The actual declaration:
vector<int>::iterator it;

There are two standard functions for iterators:

Iterators can be advanced with the ++ operator (some can go backwards with --) and compared with the == or != operator. To run over all element, you can therefore use:

it = a.begin();
while (it!=a.end()) {
  // ...
  it++;
}

Or quicker:

for (it = a.begin();it!=a.end();it++) { ... }

To get the element an iterator points to, you act as if iterator would be a pointer and use the dereference operator *. Example:

cout << *it;

Practice:

Assume you have given the following declaration:

list<char> l;
l.push_front('l');
l.push_back('a');
l.push_front('b');

Write a for loop that uses an iterator to iterate over l and print all the contents of the list.

list<char>::iterator li;
for (li=l.begin();li!=l.end();li++) 
  cout << *li;

Print just the second element (emulate at(1) )

list<char>::iterator li;
li = l.begin();
li++;  // can not use li = li+1 in this case
cout << *li;

All of these containers support insert() and erase(), but we had to introduce iterators first.

Warning: Iterators may become "invalid" after an insert or a delete operation! You should therefore use the return value if possible!

Example:

vector<int> v;
// ...
// same as p.pop_front(), would it exist.
v.erase(v.begin());

A more complex example: Delete all occurences of "42" in a list:

list<int> l;
// ...
list<int>::iterator i = l.begin();
while (i!=l.end()) {
  if ((*i) == 42) 
    i = l.erase(i);
  else
    i++;
}

Another example:

list<int>::iterator i = l.begin();
// insert the number 0 at the beginning
i = l.insert(i,0);
// make sure i points after the first element
i++;

Practice:

Assume this given deque:

deque<int> d;
// d gets filles with some values

Write a loop that inserts a 42 before every occurence of 0 in d. Two hints:

deque<int>::iterator i = d.begin();
while (i!=d.end()) {
  if (*i == 0) {
     i = d.insert(i,42);
     i++;
  }
  i++;
}

Possible test question:

For a server application you need to write a FIFO (first in, first out) queue, so that all incoming jobs are processed in the order they arrive. Which STL container would you use for such a queue and why (1-2 sentences)?

An associative container contains keys that can be quickly associated with values. There is:

To declare a map we need two datatypes, the key and the value datatype:

map<string,int> m;

We can then use keys of the given type as index to store and retrieve contents:

m["Jan"] = 1;
m["Feb"] = 2;
cout << m["Jan"] << endl;

Most operations on map can take a key as parameter where we usually have to use iterators, e.g. erase:

m.erase("Jan");

Trying to use an element that was not set works fine. If the valuetype is a class, then it will even create a new object for you (calls the default constructor).

cout << m["Mar"] << endl;

Practice:

To map from student id's to name it is usually wise to use a map, since we do not want to create an array with 10000000000 elments.

map<long,string> students;
students[123456789] = "Some";
students[987654321] = "One";
students[987654321] = "Else";

An iterator over a map<K,V> will give you a pair<K,V> for every element you access (this is the real pair which is differnt from the one we used in lab).

You can access the key in the member variable first, and the value in the member variable second. Thanks to operator overloading you may either use the dereference (*) or the dereference and access member (->) operator (or both, as you wish). Example:

for (map<string,int>::iterator i=m.begin();i!=m.end();i++) {
  cout << (*i).first << " " << i->second;
}

Practice:

Using an iterator, iterate over your students map defined earlier. For every student print something like this on the screen (remember: first is the key, second is the value):

Student: Max Berger
Student ID: 123456789

map<long,string>::iterator si;
for (si=students.begin();si!=students.end();si++) {
  cout << "Student: " << si->second << endl;
  cout << "ID: " << si->first << endl;
}

There are five categories of iterators:

We will hardly every see anything but bidirectional and random access iterators. But it is important to know the other types exist.

With the exception of output each of these iterators includes all of the above. (a bidi is also forward and input, etc.).

In this example we use the fact that we can do math with iterators to find the index of elements that match a certain value.

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);

for (vector<int>::iterator i=v.begin();i!=v.end();i++) {
  if ((*i) == 2) {
    cout << "I found the number 2 at index " << i - v.begin() << endl;
  }
} 

Practice:

Assume the vector definition from above. Write a for loop that uses an iterator to output every other element. Actually advance the iterator by 2. Here you'll have to use the < operator instead of !=.

for (vector<int>::iterator i=v.begin();i<v.end();i+=2) {
  cout << *i << endl;
}