% lec 13: templates & STL # 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)](http://en.cppreference.com/w/cpp/language/variable_template) # min `min(lhs, rhs)`: returns `lhs` if `lhs < rhs`, or `rhs` otherwise ```c++ int min(int lhs, int rhs) { if (lhs < rhs) return lhs; return rhs; } ``` ```c++ 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](https://github.com/torvalds/linux/blob/master/include/linux/kernel.h#L707) ```c #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 ```c++ template // alternative: class T T min(T lhs, T rhs) { if (lhs < rhs) return lhs; // require: operator < defined for T return rhs; } ``` . . . ```c++ #include int main(int argc, char **argv) { std::string h("hello"), w("world"); std::cout << ::min(h, w) << std::endl; std::cout << ::min(10, 20) << std::endl; } ``` . . . q: `::min("hello", "world")`? q: `::min("hello", "world")`? # class templates recall: [lec 11's vector.cc](l11/vector.cc) templated vector: int, double, string ```c++ template 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](http://courses.cs.washington.edu/courses/cse333/15wi/papers/night-watch.html)! [Grand C++ Error Explosion Competition from John Regehr](http://blog.regehr.org/archives/1088) ```c++ struct x0 struct A <_T1*, x0(_T1*_T2> binary_function<_T1*, _T2, x0{ } ``` . . . g++ 4.8 (attu) will produce _5 MB_ error messages! advice: be prepared # linking problems ```c++ // min.h template T min(T lhs, T rhs); ``` ```c++ // min.cc #include "min.h" template T min(T lhs, T rhs) { if (lhs < rhs) return lhs; return rhs; } ``` ```c++ // test.cc #include "min.h" #include int main(int argc, char **argv) { std::cout << ::min("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 ```c++ // min.cc template std::string min(std::string, std::string); template int min(int, int); ``` solution 2: move implementation to header files ```c++ // min.h (no min.cc) template T min(T lhs, T rhs) { if (lhs < rhs) return lhs; return rhs; } ``` # more template syntax [template parameters: types, non-types, template template](http://en.cppreference.com/w/cpp/language/template_parameters) [template specialization](http://en.cppreference.com/w/cpp/language/template_specialization) [template metaprogramming](http://en.wikibooks.org/wiki/C++_Programming/Templates/Template_Meta-Programming) examples: [fibonacci](l13/fib/) 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](http://www.cplusplus.com/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 ```c++ #include #include #include int main() { std::list nums; for (int i = 0; i < 100; ++i) nums.push_back(i); std::list::iterator iter = nums.begin(); std::advance(iter, 10); std::cout << "11th element: " << *iter << std::endl; } ``` [draw list] . . . `auto`, vector, running time of `advance`, output all elements # how to implement iterator mimic a pointer operator overloading: `++`, `--`, `*`, `->`, `==`, `!=` example: [libcxx's list iterator](https://github.com/llvm-mirror/libcxx/blob/master/include/list#L233) # see you on Wednesday! next lecture: STL (cont.) & smart pointers