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
• But, seeing an implementation helps explain how iterators work!
• code:

          class SList                     // list of strings
          {
             struct SNode                 // store string
             {
                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) { }
                SNode* operator++() // prefix version!
                {
                   return current = current->next;
                }
                SNode* operator++(int) // postfix version
                {
                   SNode* tmp = current;
                   current = current->next;
                   return tmp;
                }
                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 double using 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 ranged for loop makes it simple to process all elements:

            int empty_count = 0;
            for(auto const & item : todo)       // access element without copy
               if ( item.empty() )
                  ++empty_count;
    
            for(auto item : todo)                   // copies each string
               cout << item << endl;
    
            for(auto& item : todo)              // can modify element value
               item = "take a break";
    

• 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

Casting

• Standard (C-style) casting, which looks like Java:

          float x = ...;
          int y = (int)x;         // truncate
          int *zs = (int*)malloc(100 * sizeof(int)); // legal, but not recommended
          A *x = new B;           // assume B derived from A
          ... ((B*)x)->b_method() ...  // call a method from class B
  

  • Legal, but risky: if run-time type information is turned on, it will check, but otherwise there is no check
• Better alternatives: const_cast, dynamic_cast, static_cast
  • static_cast: compile time cast: static_cast<int>(x) - more explicit than the () notation
    • eg: cast to unsigned integer if know value is small enough?
  • dynamic_cast: run time cast: by default, adds checks; use for the B example: dynamic_cast<B*>(x)->b_method()
  • const_cast: cast away constness: use when the method is not const, but you know you can call it without changing the object's state
  • application: changing types at the implementation level
  • eg: a class returns a const string, but I need to pass it to a C routine that doesn't have a const string parameter
• Why is casting dangerous?
• Why is casting necessary?

Review

• iterators
• algorithms: sort, reverse, fill
• casting