DM852 - Introduction to Generic Programming, 2019 ================================================= `Course description `__ Schedule -------- (`Official schedule `__) .. _dm852_19_s01: ../../_static/teaching/dm852_19/s/01.pdf .. _dm852_19_s02: ../../_static/teaching/dm852_19/s/02.pdf .. _dm852_19_c02: ../../_static/teaching/dm852_19/c/02 .. _dm852_19_s03: ../../_static/teaching/dm852_19/s/03.pdf .. _dm852_19_c03: ../../_static/teaching/dm852_19/c/03 .. _dm852_19_e01: ../../_static/teaching/dm852_19/e/01_intro.pdf .. _dm852_19_s04: ../../_static/teaching/dm852_19/s/04.pdf .. _dm852_19_c04: ../../_static/teaching/dm852_19/c/04 .. _dm852_19_e02: ../../_static/teaching/dm852_19/e/02_ctor_dtor_op.pdf .. _dm852_19_s05: ../../_static/teaching/dm852_19/s/05.pdf .. _dm852_19_s06: ../../_static/teaching/dm852_19/s/06.pdf .. _dm852_19_c06: ../../_static/teaching/dm852_19/c/06 .. _dm852_19_s07: ../../_static/teaching/dm852_19/s/07.pdf .. _dm852_19_c07: ../../_static/teaching/dm852_19/c/07 .. _dm852_19_s08: ../../_static/teaching/dm852_19/s/08.pdf .. _dm852_19_c08: ../../_static/teaching/dm852_19/c/08 .. _dm852_19_s09: ../../_static/teaching/dm852_19/s/09.pdf .. _dm852_19_c09: ../../_static/teaching/dm852_19/c/09 .. _dm852_19_s10: ../../_static/teaching/dm852_19/s/10.pdf .. _dm852_19_c10: ../../_static/teaching/dm852_19/c/10 .. _dm852_19_s11: ../../_static/teaching/dm852_19/s/11.pdf .. _dm852_19_c11: ../../_static/teaching/dm852_19/c/11 .. _dm852_19_s12: ../../_static/teaching/dm852_19/s/12.pdf .. _dm852_19_c12: ../../_static/teaching/dm852_19/c/12 .. _dm852_19_c13: ../../_static/teaching/dm852_19/c/13 .. _dm852_19_e03: ../../_static/teaching/dm852_19/e/03/containers.pdf .. _dm852_19_e03c: ../../_static/teaching/dm852_19/e/03/code .. _dm852_19_s14: ../../_static/teaching/dm852_19/s/14.pdf .. _dm852_19_c14: ../../_static/teaching/dm852_19/c/14 .. _dm852_19_s15: ../../_static/teaching/dm852_19/s/15.pdf .. _dm852_19_c15: ../../_static/teaching/dm852_19/c/15 .. _dm852_19_s16: ../../_static/teaching/dm852_19/s/16.pdf .. _dm852_19_c16: ../../_static/teaching/dm852_19/c/16 .. _dm852_19_s17: ../../_static/teaching/dm852_19/s/17.pdf .. _dm852_19_c17: ../../_static/teaching/dm852_19/c/17 .. _dm852_19_s18: ../../_static/teaching/dm852_19/s/18.pdf .. _dm852_19_c18: ../../_static/teaching/dm852_19/c/18 .. _dm852_19_s19: ../../_static/teaching/dm852_19/s/19.pdf .. _dm852_19_c19: ../../_static/teaching/dm852_19/c/19 .. _dm852_19_s20: ../../_static/teaching/dm852_19/s/20.pdf .. _dm852_19_c20: ../../_static/teaching/dm852_19/c/20 +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | Week | Day | Notes and Material | (Additional) Reading | +======+==========+=======================================================================================================+====================================================+ | 6 | Monday | Course introduction (`slides `__), | | | | C++ introduction (`slides `__, `code `__) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Tuesday | C++ introduction (cont.), | (**[TMPL]** Appendix A, The ODR) | | | | Values, types, objects, and variables (`slides `__, `code `__) | | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | (no class) `Exercise suggestions `__ | | +----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ | | Friday | Values, types, objects, and variables (cont.), | | | | Operators, overloading, and friends (`slides `__, `code `__) | +------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ | 7 | | (no classes) `Exercises `__ | +------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ | 8 | Monday | (no class) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Tuesday | Regular Types (`slides `__) | **[DeSt]**, **[DA]** | | | | Inheritance and polymorphism (`slides `__, `code `__), | | | | | Exceptions (`slides `__, `code `__), | | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | Exceptions (cont.), | | | | | Conversions, Value Categories, and Moving (`slides `__, `code `__) | **[TMPL]** Appendix B, **[BS:10]** | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | (cancelled) | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 9 | Tuesday | Conversions, Value Categories, and Moving (cont.), | | | | | Template Basics (`slides `__, `code `__) | **[TMPL]** Ch. 1, 2, 3, (5), 10, (**[DV]**) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | Template Basics (cont.), | | | | | Iterators, Ranges, and Algorithms (`slides `__, `code `__) | (**[TMPL]** Ch. 8.1-8.3, 9, Appendix C) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | Iterators, Ranges, and Algorithms (cont.), | | | | Containers and Function Objects (`slides `__, `code `__) | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 10 | Monday | Template Argument Deduction (`slides `__, `code `__), | **[TMPL]** Ch. 15 (except 15.4, 15.5), | | | | ``std::move``, ``std::forward`` | (**[SM]**, **[TMPL]** Ch. 7 and **[RP]**) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Tuesday | Elaboration on copying, moving, value categories, and perfect forwarding (`code `__) | (**[TMPL]** Ch. 6.1) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | (no class) `Exercise `__ with `code `__. | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | Associated Types and Type Traits (`slides `__, `code `__), | (**[TMPL]** Ch. 19.1-3, 19.8, 19.10, 19.11) | | | | Tag Dispatching (`slides `__, `code `__) | | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 11 | Tuesday | Tag Dispatching (cont.) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | Smart Pointers, Empty Base Optimization, Argument-Dependent Lookup | **[TMPL]** Ch. 21.1, (**[HS]**, **[AK]**) | | | | (`slides `__, `code `__) | | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | Smart Pointers, Empty Base Optimization, Argument-Dependent Lookup (cont.) | | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 12 | Tuesday | Overview of Polymorphism and Static Polymorphism with CRTP | **[CW]**, **[TMPL]** Ch. 18, 21.2 | | | | (`slides `__, `code `__), | | | | | Graph library discussion | | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | Overview of Polymorphism and Static Polymorphism with CRTP (cont.), | | | | Graph library discussion (cont.) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | Constrained Templates and SFINAE | **[TMPL]** Ch. 8.4, 15.7, 19.4.1, 19.4.2 | | | | (`slides `__, `code `__) | | | | | | | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 13 | Tuesday | Constrained Templates and SFINAE (cont.), | (**[WB2]**) | | | | Concepts as a Language Construct (`slides `__, `code `__) | | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Thursday | (no class) | | +----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | | Friday | Visitors for Graph Algoritms (`slides `__, `code `__), | (**[BGL]**) | | | | Introduction to Exam Project | | +------+----------+-------------------------------------------------------------------------------------------------------+----------------------------------------------------+ | 14 | Sunday | **Mandatory assignment deadline** | +------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ | | +------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ | 19 | Sunday | **Exam project deadline** | +------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------+ Mandatory Assignment -------------------- This is a prerequisite ("forudsætningsprøve") for the exam. `Description <../../_static/teaching/dm852_19/a/desc.pdf>`__ and `example code <../../_static/teaching/dm852_19/a/benchmark.cpp>`__. .. attention:: Deadline: Sunday 7 April at 23:59 CEST. Exam Project ------------ `Description <../../_static/teaching/dm852_19/exam/desc.pdf>`__ and `code archive <../../_static/teaching/dm852_19/exam/code.tar.gz>`__ (**12 April**: ``desc.pdf`` and ``topological_sort.hpp`` updated due to a few typos, **29 April**: ``desc.pdf`` updated so it doesn't refer to a non-existing header file). .. attention:: Deadline: Sunday 12 May at 23:59 CEST. Literature ---------- - | **[TMPL]** C++ Templates, The Complete Guide, 2nd Edition | Authors: David Vandevoorde, Nicolai Josuttis, Douglas Gregor | Year: 2017 | ISBN: 9780321714121 | Source code for examples: `tar archive `__ - | **[DeSt]** Fundamentals of Generic Programming. James C. Dehnert and Alexander Stepanov. In Generic Programming, LNCS 1766, Spring, 2000. [`DOI `__ | `TR `__] | (see also `Revisiting Regular Types `__, Titus Winters) - **[DA]** `Exception-Safety in Generic Components `__, David Abrahams, 2001 - **[BS:10]** `"New" Value Terminology `__, Bjarne Stroustrup, 2010 - **[CW]** Section 1.1 to 1.4 of `On Understanding Types, Data Abstraction, and Polymorphism `_ (`PDF <../../_static/teaching/dm852_19/cardelli_wegner.pdf>`__), Luca Cardelli and Peter Wegner, ACM Comput. Surv., 1985. Additional Resources -------------------- - Language reference: `C++ reference `__ - `ISO C++ `__ - `C++ FAQ `__ - `GNU make `__ (`Makefile slides from DM548 <../../_static/teaching/dm852_19/makefiles.pdf>`__) - Online `Compiler Explorer `__ - **[DV]** |DVTitle|_, Daveed Vandevoorde, 2017. `A newer revision `__ is accepted for C++20 (and `implemented in GCC 9 `__). A proposal to avoid having to type ``typename`` in so many places. See also **[TMPL]** Ch. 17.1. - |BDJTTitle|_, Ben Deane and Jason Turner, C++Now 2017 (`slides `__). A talk on parsing JSON at compile-time. - `The World Map of C++ STL Algorithms `__, Jonathan Boccara, 2018. A blog post and video giving an overview of the standard algorithms. - **[SM]** `Type Deduction and Why You Care `__, Scott Meyers, CppCon 2014. - **[RP]** `How to Argue(ment) `__, Richard Powell, CppCon 2018 (`slides `__). A discussion on how to decide on which argument type to use. - **[WB]** |WBTitle|_, Walter E. Brown, 2016 - **[HS]** `Leak-Freedom in C++... By Default `__, Herb Sutter, CppCon 2016. - **[AK]** `A Personal Note About Argument-Dependent Lookup `__, Andrew Koenig, 2012. - **[BGL]** The `Boost Graph library `__. - **[BI]** The `Boost Iterator library `__. - **[WB2]** `Proposing Standard Library Support for the C++ Detection Idiom `__, Walter E. Brown, 2015. - Utility programs: - ``c++-filt``: demangle symbols - ``nm``: list symbols from compiled files (e.g., ``.o``, ``.a``, ``.so``, and executables). Use ``nm -C`` to demangle the symbols, or equivalently ``nm myFile | c++filt``. - ``valgrind``: detect errors related to memory .. |DVTitle| replace:: Down with ``typename``! .. _DVTitle: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0634r0.pdf .. |BDJTTitle| replace:: ``constexpr`` ALL the things! .. _BDJTTitle: https://www.youtube.com/watch?v=HMB9oXFobJc .. |WBTitle| replace:: What C++ Programmers Need to Know about Header ```` .. _WBTitle: https://www.youtube.com/watch?v=6DPkyvkMkk8 Installing GCC :math:`\geq` 6 ----------------------------- Note, if you use Ubuntu 18.04, the default GCC package is already new enough. That is, simply do: .. code-block:: bash sudo apt-get install g++ If you want to try an even newer version, see below. Ubuntu ...... .. code-block:: bash sudo add-apt-repository ppa:ubuntu-toolchain-r/test sudo apt-get update sudo apt-get install g++-8 From Source ........... (See also https://gcc.gnu.org/wiki/InstallingGCC) 1. Download and unpack the sources, e.g.:: wget ftp://ftp.fu-berlin.de/unix/languages/gcc/releases/gcc-8.2.0/gcc-8.2.0.tar.gz tar xzf gcc-8.2.0.tar.gz 2. Download prerequisites:: cd gcc-8.2.0 ./contrib/download_prerequisites 3. Configure, build, and install (see https://gcc.gnu.org/install/configure.html for information on the options), e.g.,:: mkdir build cd build ../configure --prefix= --program-suffix=-8 --disable-multilib make -j make install .. _dm852_19_install_boost: Installing the Boost Libraries ------------------------------ Ubuntu ...... Note, this may be a relatively old version. .. code-block:: bash sudo apt-get install libboost-all-dev From Source ........... See :ref:`install_boost`.