administrivia

• midterm last Friday
• hw2 due tomorrow
• no exercises due this week
  • ex12 due next Tuesday
  • ex13 due next Wednesday
  • ex14 no need to turn in
• upcoming topics
  • this week: finish up C++
  • guest lecture on Rust: systems programming at Mozilla
  • next week: C/C++ revisited & systems topics

feedback

can you start lectures 5 min late? need to run across campus.

start on time! I want to use the full 50 minutes.

today’s plan

templates

Standard Template Library (STL) intro

templates: “type-safe” macros

function templates

class templates

variable templates (C++14)

min

min(lhs, rhs): returns lhs if lhs < rhs, or rhs otherwise

int min(int lhs, int rhs) {
  if (lhs < rhs) return lhs;
  return rhs;
}

std::string min(std::string lhs, std::string rhs) {
  if (lhs < rhs) return lhs;
  return rhs;
}

what about float, double, your own classes?

how to avoid repeated code?

C: macro hacking

linux/kernel.h

#define min(x, y) ({                            \
        typeof(x) _min1 = (x);                  \
        typeof(y) _min2 = (y);                  \
        (void) (&_min1 == &_min2);              \
        _min1 < _min2 ? _min1 : _min2; })

requires gcc extensions

error-prone: side effect, type checking

what are the first three lines doing?!

C++ function templates

template <typename T>        // alternative: class T
T min(T lhs, T rhs) {
  if (lhs < rhs) return lhs; // require: operator < defined for T
  return rhs;
}

#include <iostream>
int main(int argc, char **argv) {
  std::string h("hello"), w("world");
  std::cout << ::min<std::string>(h, w) << std::endl;
  std::cout << ::min(10, 20) << std::endl;
}

class templates

recall: lec 11’s vector.cc

templated vector: int, double, string

template <typename T>
class vector {
  /* ... */
 private:
  size_t size_;
  T *data_;
};

templates: good part

type safe (compared to macros)

compile-time: no runtime overhead

problems with templates

code bloat

error message explosion

linking

error message explosion

C++ compilers are not very friendly to templated code

read The Night Watch!

Grand C++ Error Explosion Competition from John Regehr

struct x0 struct A<x0(x0(x0(x0(x0(x0(x0(x0(x0(x0(_T1,x0 (_T1> <_T1*, x0(_T1*_T2> 
binary_function<_T1*, _T2, x0{ }

linking problems

// min.h
template <typename T> T min(T lhs, T rhs);

// min.cc
#include "min.h"
template <typename T> T min(T lhs, T rhs) {
  if (lhs < rhs) return lhs;
  return rhs;
}

// test.cc
#include "min.h"
#include <iostream>
int main(int argc, char **argv) {
  std::cout << ::min<std::string>("hello", "world") << std::endl;
  std::cout << ::min(10, 20) << std::endl;
}

fix linking errors

remember templates are like macros

the C++ compiler won’t produce any code for templates until it sees actual types (“instantiation”)

solution 1: list all possible types

// min.cc
template std::string min<std::string>(std::string, std::string);
template int min<int>(int, int);

solution 2: move implementation to header files

// min.h (no min.cc)
template <typename T> T min(T lhs, T rhs) {
  if (lhs < rhs) return lhs;
  return rhs;
}

more template syntax

template parameters: types, non-types, template template

template specialization

template metaprogramming

examples: fibonacci via recursion/template/constexpr

advice: avoid complexity unless necessary

C++ standard library recap

STL: containers, algorithms, iterators, …

strings & regular expressions

I/O streams

multithreading

C library

many more …

STL history

originated in Ada

Alexander Stepanov, Meng Lee, and David Musser

presented at the 1993 C++ standardization meeting

influenced other parts of the C++ Standard Library

influenced other languages: Java, C#, …

STL overview

• containers
  • sequence: vector, list, deque, array, forward_list
  • associative: set, map, multiset, multimap
  • unordered associative: unordered_set, unordered_map, unordered_multiset, unordered_multimap
  • adaptors: stack, queue, priority_queue
  • misc: bitset, valarray

• algorithms: sort, find, copy, …

• iterators

C++ Primer or C++ reference

high-level idea: decomposition

• generic programming
  • M containers
  • N algorithms

• strawman: M * N implementations

• STL: M + N implementations
  • five types of iterators
  • containers expose iterators
  • algorithms operate on iterators

STL example

#include <iostream>
#include <iterator>
#include <list>

int main() {
  std::list<int> nums;
  for (int i = 0; i < 100; ++i) nums.push_back(i);
  std::list<int>::iterator iter = nums.begin();
  std::advance(iter, 10);
  std::cout << "11th element: " << *iter << std::endl;
}

[draw list]

how to implement iterator

mimic a pointer

operator overloading: ++, --, *, ->, ==, !=

example: libcxx’s list iterator

see you on Wednesday!

next lecture: STL (cont.) & smart pointers