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

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

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
Issue: Ruby/Python's solution is to just not declare types; C++'s solution allows duck typing within a statically typed language!

Review

iterators
algorithms: sort, reverse, fill

Copyright © 2016 Robert W. Hasker