Copyright © 2016
Robert W. Hasker

Note 12: Containers and Algorithms

Ch. 9, 11, 12

Details on std::vector

• vector::operator[]: does not check ranges
  • speed is everything...?
  • solution: use .at()
  • see textbook for template class that adds range check to vector

Accessing elements in std::list

• need way to access elements of linked list without revealing representation
  • obvious choice: implement operator[] to index into list
    • What's the O()?
  • "cursor": special element in list that moves around; brittle
  • iterator: object used to represent current location
• method based on external class (not very much like STL - see below for STL-based iterators)

          class SIterator
          {
             SNode *current;
          public:
             SIterator(SNode *s) : current(s) { }
             const string& next() const { return current->item; }
             bool hasNext() const { return current != nullptr; }
             void operator++() // PREINCREMENT operator
             {
                assert(hasNext());
                current = current->next;
             }
          };
  

• Adding support for iterator in slist:

          class SList
          {
          public:
             ...
             SIterator iterator() const { return SIterator(head); }
             ...
          }; 
  

• Usage:

          SList names;
          ... add items to names
          for(SIterator it = names.iterator(); it.hasNext(); ++it)
          {
             SIterator dup_it = it;
             if ( dup_it.hasNext() )
                ++dup_it; // skip past current item in list
             while ( dup_it.hasNext() && it.next() != dup_it.next() )
                ++dup_it;
             if ( dup_it.hasNext() ) // stopped because found item
                cout << "Duplicate entry in list: " << dup_it.next() << endl;
          }
  

  • [what's the run-time efficiency of this algorithm?]
• can apply iterator concept to any container class

STL-like iterator

• this is a very simplified version of iterators as used in the STL; return types and use of const have been simplified, reverse iteration not supported
• code:

          class SList
          {
             struct SNode
             {
                string item;
                SNode *next;
                SNode(const string &s, SNode *n) : item(s), next(n) { }
             } *front;
          public:
             class iterator
             {
                SNode *current;
             public:
                iterator(SNode *start) : current(start) { }
                void operator++() // prefix version!
                {
                   current = current->next;
                }
                string& operator*() // de-reference (since no parameters)
                {
                   return current->item;
                }
                bool operator==(const iterator &other)
                {
                   return current == other.current;
                }
                bool operator!=(const iterator &other)
                {
                   return current != other.current;
                }
             }; // end of iterator
             iterator begin()
             {
                return iterator(front);
             }
             iterator end()
             {
                return iterator(nullptr);
             }
             ... other List operations to add/remove items ...
          };
  

STL Iterators

• Standard template library: provides iterators for all containers
  • Summing a list of doubles usnig an explicit iterator:

            list<double> nums;
            ...
            double sum;
            for(auto it = nums.begin(); it != nums.end(); ++it)
              sum += *it;
    

  • Searching a list of strings:

            list<string> todo;
            ...
            // find first "go to class", of amu
            list<string>::iterator pos = todo.begin();
            // better:
            auto pos = todo.begin();
            while ( pos != todo.end() && *pos != "go to class" )
               ++pos;
            if ( pos != todo.end() )
               cout << "Found it.";
    

  • The new for loop makes it simple to process all elements:

            int empty_count = 0;
            for(const auto& item : todo) 
               if ( item.empty() )
                  ++empty_count;
    

• vector, map, etc: all provide iterators
  • How does one build an iterator for a binary search tree?
  • many provide reverse iterators: rbegin(), rend()
  • what class is unlikely to provide a reverse iterator?
• What happens if you modify the collection while iterating over it?
  • linked list: if delete current node, advancing to next node is undefined
  • vector: if grow the array (copy it to a new location): iterator now points to old data
  • See SO FAQ for iterator invalidation rules.

Algorithms

• A whole list of functions which take STL objects as parameters
  • look up "algorithms" in Borland help
  • #include <algorithm>
• functions:
  • fill: fill container with a value
  • sort: sort a container (where < is defined for the underlying object)
  • reverse
  • max_element, min_element: extremums in a list (returned as iterators)
  • many others!
• use: pass iterators as arguments:
  • sorting a vector of numbers from high to low (could do both in one shot, but this illustrates reverse as well):

            vector<float> sizes;
            ... code to read sizes ...
            sort(sizes.begin(), sizes.end());    // O(N log N)
            reverse(sizes.begin(), sizes.end());
    

  • interestingly, can also use to sort an array:

            float nums[50];
            ... code to read numbers ...
            sort(&nums[0], &nums[50]);
    

    Note how the address of the element just past the last array element was used to mark the array end.
• see alg-examp.cpp

Review

• iterators
• algorithms: sort, reverse, fill