STL Vector, List

1. The List ADT

• An Abstract Data Type (ADT) is a user/programmer defined data type (vs. system defined data types such as int, double).
• ADT's are abstract, in that they only provide high-level definitions of operations (such as insertion and deletion), and implementation details (such as how data is stored, how insertion is done) are hidden.
• C++ classes can be conveniently used to define ADT's, because a class name becomes a data type.

• A "list" is a general, one-dimensional list of elements.  Typical operations include:
  • insertion, deletion
  • accessing an element
  • knowing the size of the list
  • search for a given element
• A List ADT can be implemented as an array (as in []) or a linked list.  A (singly) linked list looks like:

  

2. Intro to STL

• Standard Template Library (STL) is part of the standard C++ library. It is a collection of pre-made classes and functions.
• STL classes are template classes -- classes and functions are templates, and the user instantiates a specific data type (e.g. int, double, char) according to the application.
• A good introductory reference on STL :
  • http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/tut.html 
• The STL vector and list classes implement a list ADT.  Vector and list are also "container" classes.
  • vector is implemented as an array (i.e., [])
  • list is implemented as a doubly-linked list, which looks like:

    

• The element type (the data type of the elements) must be specified in angle brackets, because STL are template classes.  For instance,

    vector<int> ivec;      // vector of int's
    vector<char> cvec;     // vector of char's
    vector<Critter> crvec; // vector of Critter's

• Vector and list include the following (public) methods.  For more information, look at the C++ Reference API on vector and list.

  vector	list
  int size() const -- returns the number of elements
  void clear() -- resets the list to an empty list
  bool empty() const -- returns true if the list is empty, or false otherwise
  void push_back(const Object& x) -- adds an element (x) to the end of the list
  void pop_back() -- removes the last element in the list
  const Object& front() const -- returns the first element in the list (but does not remove it)
  const Object& back() const -- returns the last element in the list (but does not remove it)
  Object& operator[](int index) -- returns the element at the parameter index position (0-based), with no bounds-checking
  Object& at(int index) -- returns the element at the parameter index position (0-based), with bounds-checking
  	void push_front(const Object& x) -- add the element x in front of the list
  	void pop_front() -- removes the first element in the list

• An example program:

  #include <iostream>
  #include <vector>    // STL vector class
  #include <list>      // STL list class
  using namespace std;
  
  int main()
  {
    vector<int> vec; // a vector of int's, initially empty
    list<char> lst;  // a list of char's, initially empty
  
    // populate the vector and list
    for (int i = 0; i < 4; i++)
      vec.push_back(i*2); // vec contains int's
  
    lst.push_back('a');   // lst contains char's
    lst.push_front('9');
  
    // vector has two ways to access elements by index.
    cout << vec[1];    // operator[] with index 1 (i.e., vec.operator[](1))
    cout << vec.at(3); // the method at() with index 3
  
    // size() is defined for both containers
    cout << vec.size();
    cout << lst.size();
  
    // try removing all elements from vec until empty
    while (!vec.empty())
      vec.pop_back();

3. Iterators

• Iterators are essentially a generalization of pointers.  An iterator associated with a container points to an element in the list/container.

       +-------+   +-------+   +-------+   +-------+
  ..-->| 5 | o---->| 3 | o---->| 1 | o-----| 5 | o---->...
       +-------+   +-------+   +-------+   +-------+
                               ^
                               |
                             +-|-+
                          it | o |
                             +---+

• By using iterators, we can:
  • Traverse a list -- by using the increment (++), decrement (--) and comparison (==, !=, < etc.) operators.
  • Insert a new element in the middle of the list or delete an existing element pointed to by the iterator.

3.1 Declaring, Obtaining and Moving iterators

• An iterator is associated with a specific list, and the type of the list is a part of the data type of an iterator.

    vector<int>::iterator vi;
    vector<char>::iterator vc;
    list<int>::iterator li;
    list<Critter>::iterator lc;

• Iterators can be obtained by the method begin() and end() in a vector or a list.  Note: end() returns a position "past-the-end" of the vector array/list!
  

  Range: [ beg = vec.begin(), end = vec.end() )

    +-----------+
  v | 5 | 9 | 3 |
    +-----------+
    ^           ^
    |           |
   beg         end

• Once you obtain an iterator which points to somewhere in the list, you can access the element pointed by the iterator by dereferencing it (by *).

    cout << *beg; // returns the element in the list pointed by 'beg'

• Also you can advance or rewind an iterator just in the same way as you do with pointers, by using the ++ and -- operators.  A typical loop to traverse a list looks like:

  vector<int> vec;
  //..Assume some values are added in vec.
  
  vector<int>::iterator it;
  for (it = vec.begin(); it != vec.end(); it++)
    cout << *it;

3.2 Insertion, Deletion using Iterators

• STL vector and list include methods which insert or delete an element at a position in the list pointed by an iterator.
  • iterator insert(iterator pos, const Object& x) -- Inserts x at/before the position currently pointed by pos.  Returns a new iterator pointing at the inserted element.
  • iterator erase(iterator pos) -- Removes the element pointed by pos.  Returns a new iterator which points to the element that followed pos prior to the call.

vector<int> vec; 

/** Add some elements in the vector */
vec.push_back(7);  // [7]
vec.push_back(3);  // [7, 3]
vec.push_back(5);  // [7, 3, 5]

/** Insert and elements using iterators */
vector<int>::iterator it;
it = vec.begin();
it++;              // it points to 3
vec.insert(it, 1); // [7, 1, 3, 5]

it = vec.begin();  // reset it to point to the beginning
it++;
it++;  // it points 3

vector<int>::it2, it3;
it2 = vec.erase(it);  // delete 3, it2 points to 5
it3 = vec.erase(it2); // delete 5, it3 points to the end of the list

if (it3 == vec.end())
  cout << "End of the list\n";
else
  cout << "ERROR!!\n";

• Both vector and list includes the two methods above.  However, the running time complexity is different.

3.3 Const_iterators

• There are two kinds of iterators: iterators (which are non-const) and const_iterators.

• Const_iterators must be used to point to containers which are const objects.  Typically this situation happens when a container is passed to a function by const reference.

  int main()
  {
    vector<int> vec;
    //.. Assume some values are added in vec.
  
    printVector(vec);
    ...
  }
  
  void printVector(const vector<int> & v) // v is a const object
  {
    vector<int>::const_iterator cit; // const_iterator, NOT iterator
  
    for (cit = v.begin(); cit != v.end(); cit++)
      cout << *cit << " ";
  }

3.4 Comparing iterators

• To compare iterators for equality (i.e., two iterators point to the same element in the list), we can use == and != for both vector and list.

• In addition, vector iterators allow ordering operators <, > etc. (to see one iterator is before/after another iterator).

  vector<int>::iterator it;
  for (it = vec.begin(); it < vec.end(); it++) // < instead of != works, ONLY for vector
    cout << *it;

4. STL Algorithms

• STL contains a set of several general routines for processing containers. They are regular (template) functions, and defined in the <algorithm> library.
  For an online reference on STL algorithms, look at the C++ Reference API (under algorithm).

• Typical algorithms for sequential container are grouped into two kinds of functions:
  • Non-mutating functions -- make no modification to the container
    • e.g. searching, counting etc.
  • Mutating functions -- make modification
    • e.g. swap, fill, reverse etc.

  #include <iostream>
  #include <vector>
  #include <algorithm> 
  using namespace std;
  
  int main()
  {
     vector<char> v(5);
  
     // Assume some char's are inserted in v
  
     vector<char>::iterator it;
     it = find( v.begin(), v.end(), 'e' );  // search 'e' between the two iterators
     if (it != v.end())
       cout << "Element found!!\n";
     else
       cout << "Element not found..\n";
  
     reverse( v.begin(), v.end() ); // reverse elements in the specified range
  
     sort( v.begin(), v.end() ); // sort elements in the specified range

EXERCISES:

1. Write a code segment that removes all even integers from an STL vector (of int's).
2. Write another code segment that reverses an STL list (of int's).
3. Write a function called myVectorFind which works similar to the STL find algorithm.  Assume the vector contains char's.  The prototype of the function is:

     vector<char>::iterator myVectorFind(vector<char>::iterator start, vector<char>::iterator end, char x);