Copyright © 2016
Robert W. Hasker

Note 14: Containers and Algorithms

Ch. 14 in zyBook

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 = 0.0;
            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.

Concepts

• C++20: added "concepts" and requires to templates
• Goal: improve error messages for templates; example from cppreference.com:

  std::list<int> l = {3,-1,10};
  std::sort(l.begin(), l.end());  // not legal: cannot index a linked list; should use merge sort
  //Typical compiler diagnostic without concepts:
  //  invalid operands to binary expression ('std::_List_iterator<int>' and
  //  'std::_List_iterator<int>')
  //                           std::__lg(__last - __first) * 2);
  //                                     ~~~~~~ ^ ~~~~~~~
  // ... 50 lines of output ...
  //
  //Typical compiler diagnostic with concepts:
  //  error: cannot call std::sort with std::_List_iterator<int>
  //  note:  concept RandomAccessIterator<std::_List_iterator<int>> was not satisfied
  

• Solution: can use concepts to declare requirements for using templates
• Result: able to build operations over arbitrary types without using inheritance and without losing type checking
• Issue: using inheritance means having to create objects; creating objects for large data sets is a lot of unnecessary overhead; concepts means can write procedural solutions with low overhead to process large amounts of data

Review

• iterators
• algorithms: sort, reverse, fill