Copyright © 2016
Robert W. Hasker

Note 10: C++ Templates

Textbook Ch. 13

Template Functions

In Java: must define operation for every type want to use:

        int max(int a, int b) { return a > b ? a : b; }
        double max(double a, double b) { return a > b ? a : b; }

With operator overloading, can even do it for user-defined types:
```
        complex max(complex a, complex b)
        {
           return a > b ? a : b;
        }
```
- code the same each time, all that's changed is the types!

parameterizing the type:

        template<typename T>
        T max(T a, T b)
        {
           return a > b ? a : b;
        }

Better: pass by const-reference:
```
        template<typename T>
        T max(const T &a, const T &b)
        {
           return a > b ? a : b;
        }
```
- No extra overhead for copying, but still not changing value
- now max can be applied to any object for which > is defined:
  - max(5, 29)
  - max('z', 'A')
  - complex nums[100]; ... max(nums[0], nums[1]) ...

Another example:

        template<typename Something>
        void swap(Something &x, Something &y)
        {
           Something t = x;
           x = y;
           y = t;
        }

Template Classes

real power of templates: define parameterized container classes

Stack of integers:

        class IntStack
        {
        protected:
           int height;
           int items[50];
        public:
           IntStack() : height(0) { }
           void push(int x) { items[height] = x; ++height; }
           int  pop() { height--; return items[height]; }
           int  top() const { return items[height - 1]; }
           int  size() const { return height; }
           bool isEmpty() const { return height <= 0; }
           bool isFull() const { return height >= 50; }
        };

Stack of arbitrary type:

        template<typename ItemType>
        class Stack
        {
        protected:
           int height;
           ItemType items[50];
        public:
           Stack() : height(0) { }
           void push(const ItemType &x) { items[height] = x; ++height; }
           ItemType pop() { height--; return items[height]; }
           ItemType top() const { return items[height - 1]; }
           int  size() const { return height; }
           bool isEmpty() const { return height <= 0; }
           bool isFull() const { return height >= 50; }
        };

heuristic: write template code using simple type, replace type by template type

use:

        Stack<int> nums; nums.push(42); cout << nums.pop();
        // reverse letters
        Stack<char> lets;
        char c;
        cin >> c;
        while ( cin.good() )
        {
           lets.push(c);
           cin >> c;
        }
        while ( !lets.isEmpty() )
           cout << lets.pop();

or even a stack of stacks:
```
        Stack<Stack<int>> ss;
```

Note: type checking is guaranteed!

Given Stack<char> lets;,

        lets.push(1e30);          // illegal!
        lets.push("some string"); // illegal!

This is why

        lets.pop()

doesn't need a type cast.

Java does not actually guarantee this:

import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    ArrayList<Integer> nums = new ArrayList<>();
    nums.add(20);
    test(nums);

    System.out.println(nums.get(0));
    System.out.println(nums.get(1));
  }

  public static void test(ArrayList myList) { // note: no item type
    myList.add("duck");
  }
}

which prints

        20
        duck

You do get a warning:

C:\> java java-template-bug.java 
Note: java-template-bug.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
20
duck

But: it shows that Java generics provide no strong guarantees...

caveat: put all code for C++ templates in .h file
- Issue: all operations must be inline
  - Recall: a call to an inlined function/method is replaced by the body of that function/method
  - Long functions: get a copy in each compilation unit, can lead to code bloat
  - Virtual functions: must have a copy in each compilation unit, more code bloat
- implementation trick: drive template class from non-template class, put most code in base class:
```
        class BaseContainer { ... };
        template<typename X> class Container : public BaseContainer{...};
```

note: can also parameterize sizes of arrays:

        template<typename ItemType, int size>
        class Stack
        {
        protected:
           int height;
           ItemType items[size];
        public:
           Stack() : height(0) { }
           void push(ItemType x) { items[height] = x; ++height; }
           ItemType pop() { height--; return items[height]; }
           bool isEmpty() const { return height <= 0; }
           bool isFull() const { return height >= size; }
        };

use:
```
        Stack<int, 1000> bigstack;
```

passing monstrosity as parameter to function:

        void dump(Stack<int, 1000> nums) { ...pop and print all... }

        dump(bigstack);
        Stack<int, 1001> xs;
        dump(xs); -- illegal!

alternatively:

        template<int size>
        void dump(Stack<int, size> nums) { ... }

        dump(bigstack);
        Stack<int, 1001> xs;
        dump(xs); // ok

usual solution: use typedef

Introduces type synonyms:

        typedef int num;
        ...
        num x, y;
        x = 100; y = x * x;
        int z = y;              // can mix int and num

Also useful for consistency with templates:

        typedef Stack<int, 1000> LgIntStack;
        ...
        LgIntStack nums;

Aside: older versions of C++ used class instead of typename:

        template<class ItemType, int size>
        class Stack
        {
        protected:
           int height;
           ItemType items[size];

This was just to minimize number of keywords
typename is preferred

Standard Template Library

STL: many template containers

Probably the most useful: std::vector:

        #include <vector>
        using namespace std; 

        ...
        vector<string> roster;
        string name;
        cin >> name;
        while ( cin.good() ) {
           roster.push_back(name);
           cin >> name;
        }
        cout << "Read " << roster.size() << names << endl;
        cout << "First name: " << roster[0] << endl;

Can use with pointers as well:

        class Student { ... };

        vector<Student*> csc2210_roster;
        csc2210_roster.push_back(new Student("Tricia", 1823435));
        csc2210_roster[0]->print();

Other useful containers:
- std::list - doubly linked lists
  - See list_iterator.cpp for adding elements, processing all elements
  - .begin, .end: explicit iteration over the container
  - Notice declaration allows specifying an allocator; ignore this
  - There's actually a full programming language embedded in C++ templates!
- std::set - red/black trees (or equivalent)
  - Example capturing repeated words in input: repeated_words.cpp
- std::multiset
- std::map - also red/black trees
```
        #include <map>

        ....

        map<string, int> ids;
        ids["Shareem"] = 934;
        if ( ids.find("Kira") == ids.end() )
          cout << "Kira not found." << endl;
```
- std::unordered_map - hash tables
- std::stack - LIFO stacks with proper abstraction (only operations affecting the top such as push and pop; no access to middle)
- std::queue - FIFO queues with proper abstraction (front, back, push_front, push_back)

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

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

Duck-typing

Section 5.8 of textbook
How are Python programs typed?
- For example, given the code
```
        def f(a, b, c):
          return (a + b) * c
```
- This works with
```
        x = f(1, 2, 3)
        y = f(3.5, 4.7, 8.9)
```
  type(x) would give int, type(y) would give float
- But this isn't templates! There's no way to constrain a, b
- An interesting example: f('ax', 'by', 3) returns axbyaxbyaxby - why?
  - 'ax' + 'by' gives 'axby'
  - string * n gives n copies of the string: so 'axby'*3 gives 'axbyaxbyaxby'
  - How this works: the runtime gets axby * 3 and just calls the multiplication method for a string
  - f('a', 'b', 'c') fails because 'ab' * 'c' undefined - there is no way to multiply two strings
In general, if have the code something.g where something is an object of type X, then the call succeeds if X or a superclass has method g
- That is, a variable is legal in a context as long as it can respond to any methods you call on that value
- This is known as duck typing
- [follow the link, review class Duck and class Whale]
- Why? Programmer convenience and flexibility
  - Programmer does not need to document ("declare") types - types checked by run time system
  - Can identify a concept - the ability to sort data - and apply that to any container holding data that can be ordered
  - It's like a hammer: yes, it can be used to drive nails into wood, but it can also drive any firm, tubular object with a firm head through or into any moderately soft material like cloth, plastic, plaster, even some metals
  - Practical applications: write any type of data to an output stream as long as it has a toString method, draw any object with a draw method, etc.
  - Java: uses inheritance to support this type of flexibility, but that requires using the somewhat restrictive Java type system
- In general, duck typing means checking types at runtime - flexible, but slow
C++: statically typed, so it cannot have duck-typing, right?
Well, consider std::list
- This has a sort method, so the code
```
        list<int> nums;
        int x;
        cin >> x;
        while ( cin ) {
           nums.push_back(x);
           cin >> x;
        }
        nums.sort()
        for(int x : nums) cout << x << endl;
```
  works fine.
- But what if I want a list of location objects (capturing lattitude and longitude for each point on Earth) and there's no way to compare locations
- list<location> places is legal as long as we there is no call places.sort()
- Another example: list<stack<string>> is legal, even though there is no < operation on stacks
- Thus C++ templates implement a form of duck typing

Challenge: this can mean you get messy errors with templates

          #include <iostream>
          #include <list>
          using namespace std;

          class location {
          public: 
            location(float lat, float lon) : _lattitude{lat}, _longitude{lon} { }
            float lattitude() const { return _lattitude; }
            float longitude() const { return _longitude; }
          private:
            float _lattitude, _longitude;
          };

          int main() {
            list<location> places_to_visit;
            places_to_visit.sort();
            return 0;
          }

Error:

-*- mode: compilation; default-directory: "c:/web/csc2210/notes/support/" -*-
Compilation started at Tue Nov  7 12:08:32

g++ --std=c++20 odd_template_error.cpp 
In file included from C:/ProgramData/chocolatey/lib/mingw/tools/install/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/list:63,
                 from odd_template_error.cpp:4:
C:/ProgramData/chocolatey/lib/mingw/tools/install/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/stl_list.h: In instantiation of 'bool std::__detail::_Scratch_list::_Ptr_cmp<_Iter, void>::operator()(std::__detail::_List_node_base*, std::__detail::_List_node_base*) const [with _Iter = std::_List_iterator<location>]':
C:/ProgramData/chocolatey/lib/mingw/tools/install/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/stl_list.h:203:18:   required from 'void std::__detail::_Scratch_list::merge(std::__detail::_List_node_base&, _Cmp) [with _Cmp = _Ptr_cmp<std::_List_iterator<location>, void>]'
C:/ProgramData/chocolatey/lib/mingw/tools/install/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/list.tcc:515:23:   required from 'void std::__cxx11::list<_Tp, _Alloc>::sort() [with _Tp = location; _Alloc = std::allocator<location>]'
odd_template_error.cpp:18:23:   required from here
C:/ProgramData/chocolatey/lib/mingw/tools/install/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/stl_list.h:188:34: error: no match for 'operator<' (operand types are 'location' and 'location')
  188 |           { return *_Iter(__lhs) < *_Iter(__rhs); }
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
[followed by another 100+ lines of error output]

That is, because templates are instatiated late and they use a form of duck typing, can get error messages that are too detailed to be useful

`inline`

Consider

        IntStack s;
        ...
        s.push(100);

Classical issue: overhead of calling push
C++: methods defined in class definition are inline

Impact:

        IntStack s; // see above
        s.push(42);
        int x = s.pop();

is compiled as

        ...
        s.items[s.height] = 42; ++s.height;
                int x = (s.height--, s.items[s.height]); // no calls

making further optimizations possible:

        ...
        s.items[s.height] = 42; ++s.height;
        int x = (s.height--, s.items[s.height]);

or even

        int x = 42;

Consider

        const int MILLION = 1000000;
        Vector nums(MILLION);
        for(int i = 0; i < MILLION; ++i)
           nums[i] = 1 / double(i);

Remember that nums[i] is a call to operator[]:

        for(int i = 0; i < MILLION; ++i) {
           int &tmp = (if ( i < 0 || i >= nums._size )
                          throw std::out_of_range("Illegal index into vector."),
                        &nums.elements[i]);
           tmp = 1 / double(i);
        }

Since no code changes nums._size, this is the same as

        const int MILLION = 1000000;
        Vector nums(1000000); // nums._size = 1000000
        for(int i = 0; i < 1000000; ++i) {
           int &tmp = (if ( i < 0 || i >= 1000000 )
                          throw std::out_of_range("Illegal index into vector."),
                        nums.elements[i]);
           tmp = 1 / double(i);
        }

But a little logic shows i is never out of range, giving

        const int MILLION = 1000000;
        Vector nums(1000000);
        for(int i = 0; i < 1000000; ++i)
           nums.elements[i] = 1 / double(i);

Other uses of inline:

        template<typename T> inline
        T max(T a, T b)
        {
           return a > b ? a : b;
        }

If a function is inline, its definition must be available to each call
Typically: inline functions are defined in header files
Inline is not compatible with virtual
- Virtual functions: code executed determined at runtime
- Must have address of function for this to work
- Inline functions have no address - substitute code at each call
Standard template library: most operations are inline, code "compiles away"
- Calling methods like push_back has no runtime overhead - just manipulate the container directly
- A method like .find would translate to a simple loop using the iterator
- Complex methods like .insert for a BST, .sort, will turn into library function calls, but still have minimal overhead
An issue with inline functions: if inline a large function with a complex loop, executable can be larger
- inline functions with big loops don't make much sense - relative cost of function call is small

Review

template functions: avoiding rewriting code for new types when underlying interface is the same
template classes: containers for multiple types
- Note quite different from Java templates (really, generics)
- No need for casting
- No run-time checks: if it compiles there's no type error
Standard containers, algorithm
Templates are duck-typed - implications to error messages
inline and templates

Copyright © 2016 Robert W. Hasker