.. _dm852_2016:

DM852 - Introduction to Generic Programming
===========================================

.. note:: This is the 2016 version of the course.

Schedule
--------

- Tuesdays 12:15 -- 14:00, IMADAs seminar room
- Some Thursdays (see below) 16:15 -- 18:00, IMADAs seminar room or U17

.. _dm852_16_1: ../../_static/teaching/dm852_16/01.pdf
.. _dm852_16_2: ../../_static/teaching/dm852_16/02.pdf
.. _dm852_16_3: ../../_static/teaching/dm852_16/03.pdf
.. _dm852_16_4: ../../_static/teaching/dm852_16/04.pdf
.. _dm852_16_4_ex: ../../_static/teaching/dm852_16/04/
.. _dm852_16_5: ../../_static/teaching/dm852_16/05.pdf
.. _dm852_16_5_ex: ../../_static/teaching/dm852_16/05/
.. _dm852_16_6: ../../_static/teaching/dm852_16/06.pdf
.. _dm852_16_6_ex: ../../_static/teaching/dm852_16/06/
.. _dm852_16_7: ../../_static/teaching/dm852_16/07.pdf
.. _dm852_16_7_ex: ../../_static/teaching/dm852_16/07/
.. _dm852_16_8: ../../_static/teaching/dm852_16/08.pdf
.. _dm852_16_8_ex: ../../_static/teaching/dm852_16/08/
.. _dm852_16_9: ../../_static/teaching/dm852_16/09.pdf
.. _dm852_16_9_ex: ../../_static/teaching/dm852_16/09/
.. _dm852_16_10: ../../_static/teaching/dm852_16/10.pdf
.. _dm852_16_10_ex: ../../_static/teaching/dm852_16/10/
.. _dm852_16_11: ../../_static/teaching/dm852_16/11.pdf
.. _dm852_16_11_ex: ../../_static/teaching/dm852_16/11/
.. .. _dm852_16_12: ../../_static/teaching/dm852_16/12.pdf
.. _dm852_16_12_ex: ../../_static/teaching/dm852_16/12/
.. _dm852_16_13: ../../_static/teaching/dm852_16/13.pdf
.. _dm852_16_13_ex: ../../_static/teaching/dm852_16/13/
.. _dm852_16_14: ../../_static/teaching/dm852_16/14.pdf
.. _dm852_16_14_ex: ../../_static/teaching/dm852_16/14/
.. _dm852_16_15: ../../_static/teaching/dm852_16/15.pdf
.. _dm852_16_15_ex: ../../_static/teaching/dm852_16/15/
.. _dm852_16_16: ../../_static/teaching/dm852_16/16.pdf
.. _dm852_16_16_ex: ../../_static/teaching/dm852_16/16/
.. _dm852_16_17: ../../_static/teaching/dm852_16/17.pdf
.. .. _dm852_16_17_ex: ../../_static/teaching/dm852_16/17/
.. _dm852_16_18: ../../_static/teaching/dm852_16/18.pdf
.. _dm852_16_18_ex: ../../_static/teaching/dm852_16/18/

.. (to make vim reset the syntax highlighting)

+------+----------+-------------------------------------------------+----------------------------+
| Week | Day      | Notes                                           | Material                   |
+======+==========+=================================================+============================+
| 36   | Tuesday  | Intro, tools, **[BS]** Ch. 22, 2--4, most of 8, | `1 <dm852_16_1_>`_,        |
|      |          | 9.5                                             | `2 <dm852_16_2_>`_         |
|      +----------+-------------------------------------------------+----------------------------+
|      | Thursday | **[BS]** Ch. 9, part of 17                      | `3 <dm852_16_3_>`_         |
+------+----------+-------------------------------------------------+----------------------------+
| 37   | Tuesday  | **[DA]**, **[BS]** Ch. 5, 14.3, part of 18      | `4 <dm852_16_4_>`_,        |
|      |          |                                                 | `Code <dm852_16_4_ex_>`_   |
+------+----------+-------------------------------------------------+----------------------------+
| 38   | Tuesday  | **[BS:10]**, **[BS]** Part of ch. 17 and 18     | `5 <dm852_16_5_>`_,        |
|      |          |                                                 | `Code <dm852_16_5_ex_>`_   |
|      +----------+-------------------------------------------------+----------------------------+
|      | Thursday | **[BS]** Part of ch. 19, beginning of ch. 20    | `6 <dm852_16_6_>`_,        |
|      |          |                                                 | `Code <dm852_16_6_ex_>`_   |
+------+----------+-------------------------------------------------+----------------------------+
| 39   | Tuesday  | **[BS]** Part of ch. 20                         | `7 <dm852_16_7_>`_,        |
|      |          |                                                 | `Code <dm852_16_7_ex_>`_   |
+------+----------+-------------------------------------------------+----------------------------+
| 40   | Tuesday  | **[BS]** Part of ch. 20 and 21                  | `8 <dm852_16_8_>`_,        |
|      |          |                                                 | `Code <dm852_16_8_ex_>`_   |
+------+----------+-------------------------------------------------+----------------------------+
| 41   | Tuesday  | See also **[AOD]** and **[SM]**                 | `9 <dm852_16_9_>`_,        |
|      |          |                                                 | `Code <dm852_16_9_ex_>`_   |
|      +----------+-------------------------------------------------+----------------------------+
|      | Thursday | (U17) (Partial) template specialization         | `10 <dm852_16_10_>`_,      |
|      |          |                                                 | `Code <dm852_16_10_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 42   |          | Fall break                                      |                            |
+------+----------+-------------------------------------------------+----------------------------+
| 43   |          | No lectures                                     |                            |
+------+----------+-------------------------------------------------+----------------------------+
| 44   | Tuesday  | Tag dispatching and more algorithms.            | `11 <dm852_16_11_>`_,      |
|      |          |                                                 | `Code <dm852_16_11_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 45   | Tuesday  | No lecture                                      |                            |
|      +----------+-------------------------------------------------+----------------------------+
|      | Thursday | ``std::rotate``, Smart pointer introduction.    | `Code <dm852_16_12_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 46   | Tuesday  | More smart pointers (see also **[HS]**),        | `13 <dm852_16_13_>`_,      |
|      |          | and empty base optimisation (EBO).              | `Code <dm852_16_13_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 47   | Tuesday  | Argument-depedent lookup (ADL) (see also        | `14 <dm852_16_14_>`_,      |
|      |          | **[AK]**), intrusive smart pointer, and         | `Code <dm852_16_14_ex_>`_  |
|      |          | initial graph library discussion.               |                            |
|      +----------+-------------------------------------------------+----------------------------+
|      | Thursday | More on polymorphism (see also beginning of     | `15 <dm852_16_15_>`_,      |
|      |          | **[CW]**), static polymorphism with CRTP,       | `Code <dm852_16_15_ex_>`_  |
|      |          | Boost.Iterator.                                 |                            |
+------+----------+-------------------------------------------------+----------------------------+
| 48   | Tuesday  | SFINAE (see also **[WB2]** and **[BF]**).       | `16 <dm852_16_16_>`_,      |
|      |          |                                                 | `Code <dm852_16_16_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 49   | Tuesday  | Visitors for graph algorithms                   | `17 <dm852_16_17_>`_       |
|      |          | (see also **[BGL]**).                           |                            |
+------+----------+-------------------------------------------------+----------------------------+
| 50   | Tuesday  | Language support for concepts: Concepts TS      | `18 <dm852_16_18_>`_,      |
|      |          | **[AS]** (see also **[CPP]** and **[AS2]**).    | `Code <dm852_16_18_ex_>`_  |
+------+----------+-------------------------------------------------+----------------------------+
| 51   | Tuesday  |                                                 |                            |
+------+----------+-------------------------------------------------+----------------------------+


Projects
--------

- Mandatory Assignment
- Exam Project



Literature
----------

-	| **[BS]** Programming: Principles and Practice Using C++, Second Edition
	| Author: Bjarne Stroustrup
	| ISBN-10: 0321992784
	| ISBN-13: 9780321992789
- **[DA]** `Exception-Safety in Generic Components <http://dx.doi.org/10.1007/3-540-39953-4_6>`__, David Abrahams, 2001
- **[BS:10]** `"New" Value Terminology <http://www.stroustrup.com/terminology.pdf>`__,
  Bjarne Stroustrup, 2010
- **[AS]** Generic Programming with Concepts Lite
  (`Part I <https://www.youtube.com/watch?v=qwXq5MqY2ZA>`__,
  `Part II <https://www.youtube.com/watch?v=NZeTAnW5LL0>`__,
  `Slides <https://github.com/CppCon/CppCon2014/tree/master/Presentations/Generic%20Programming%20with%20Concepts%20Lite>`__),
  Andrew Sutton, 2014.


Additional Resources
--------------------

- `Course description <http://natfak.sdu.dk/laeseplan/kursusbeskrivelse.php?lang=en&kursuskode=DM852>`__
- Language reference: `C++ reference <http://cppreference.com>`__
- `ISO C++ <http://isocpp.org>`__
- `C++ FAQ <https://isocpp.org/faq>`__
- `GNU make <https://www.gnu.org/software/make/manual/make.html>`__
- Online `Compiler Explorer <http://gcc.godbolt.org/>`__
- 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
- **[AOD]** `Lambdas from First Principles: A Whirlwind Tour of C++ <https://www.youtube.com/watch?v=WXeu4fj3zOs>`__,
  Arthur O'Dwyer, 2015
- **[SM]** `Type Deduction and Why You Care <https://www.youtube.com/watch?v=wQxj20X-tIU>`__,
  Scott Meyers, 2014
- **[WB]** |WBTitle|_, Walter E. Brown, 2016
- **[HS]** `Leak-Freedom in C++... By Default <https://www.youtube.com/watch?v=JfmTagWcqoE>`__,
  Herb Sutter, 2016.
- **[AK]** `A Personal Note About Argument-Dependent Lookup <http://www.drdobbs.com/cpp/a-personal-note-about-argument-dependent/232901443>`__, Andrew Koenig, 2012.
- **[BGL]** The `Boost Graph library <http://www.boost.org/doc/libs/release/libs/graph/doc/table_of_contents.html>`__.
- **[BI]** The `Boost Iterator library <http://www.boost.org/doc/libs/release/libs/iterator/>`__.
- **[CW]** `On Understanding Types, Data Abstraction, and Polymorphism <http://doi.acm.org/10.1145/6041.6042>`_,
  Luca Cardelli and Peter Wegner, ACM Comput. Surv., 1985.
- **[BF]** `Notes on C++ SFINAE <http://www.bfilipek.com/2016/02/notes-on-c-sfinae.html>`__,
  Bartlomiej Filipek, 2016.
- **[WB2]** `Proposing Standard Library Support for the C++ Detection Idiom <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4436.pdf>`__,
  Walter E. Brown, 2015.
- **[CPP]** `Constraints and Concepts <http://en.cppreference.com/w/cpp/language/constraints>`__,
- **[AS2]** `Concepts TS draft on Github <https://github.com/cplusplus/concepts-ts>`__.
  CPPReference.



.. |WBTitle| replace:: What C++ Programmers Need to Know about Header ``<random>``
.. _WBTitle: https://www.youtube.com/watch?v=6DPkyvkMkk8

Installing GCC 6
----------------

Ubuntu
......

.. code-block:: bash

	sudo add-apt-repository ppa:ubuntu-toolchain-r/test
	sudo apt-get update
	sudo apt-get install g++-6

From Source
...........

(See also https://gcc.gnu.org/wiki/InstallingGCC)

1. Download and unpack the sources, e.g.::

	wget ftp://gd.tuwien.ac.at/gnu/gcc/releases/gcc-6.2.0/gcc-6.2.0.tar.gz
	tar xzf gcc-6.2.0.tar.gz

2. Download prerequisites::

	cd gcc-6.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=<where you want to install it> --program-suffix=-6 --disable-multilib
	make -j <number of threads to compile with>
	make install


.. _dm852_16_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`.