Infopage about the C++ lab of NPRG041.

• Taught by: Miroslav Kratochvil, contact: exa.exa@gmail.com (please include the course name/code in the subject)

• Meeting point: MS MFF, SW1, every Monday at 14:00, winter semester

• Reading material:

  • Any good book about C++, there are lots of them in the faculty library.
  • Cplusplus.com — especially following sections:
    • Containers (list, vector, set, map, string, …)
    • Commandline I/O in iostream
    • File I/O and in-memory I/O
    • complex — compare to lab approach
    • …

• When in any doubt, mail me.

Lab requirements#

You should do the homework (see below), create a small project in C++ (also below) and attend the course reasonably (at least adequately to your current knowledge of the topic).

To get the credit, you also need to pass the test. Tests take place in the exam period, register via SIS.

Homework#

There are 2 assignments. You should submit some (at least partial) solution to both assignments, I’ll notify you&give some time for corrections in case your solutions are not sufficient.

BONUS points gained from the homework can be applied to simplify your semester project. Usage:

1. I complain about something that’s obviously wrong in your project
2. You say you have a bonus point and use it
3. I forget about both problem&bonus point, and move on to next thing.

Assignment A (due 2016/12/31): Efficient mergesort on a neat linked-list class#

Take the List class we have produced on the second lesson, and improve it in following ways:

• make it generic, so it can also contain other types than integers
• add support for list assignment and construction from other lists
• make sure that destruction of list objects works right and there are no memory access violation nor leaks
• add functionality:
  • .clear() should empty the list, .empty() should report whether it’s empty, .size() should report list length
  • concatenation using operator +
  • removal of N elements by operator -
  • “merge” operator % that merges two sorted lists as in mergesort
  • .push_back(), .back(), .pop_back() and front-equivalents
  • .begin() and .end() should return reasonable iterators that work with C++11-style range-based for-loop syntax.
• consider adding at least two of following features: (more than 2 is considered as an optional BONUS)
  • both .front() and .back() (and related .pop_ and .push_) operations that work in O (1)
  • move constructor
  • O (1) .size()
  • proper support of constantness and const-iterators
• maintain reasonable code quality and readability, use comments — another (sufficiently skilled) programmer should be able to proof-read your code in less than 15 minutes
• contain the result in header file List.h (and optionally List.cpp) and submit using the SIS study group interface to corresponding fields.

Only restriction on your code is that you must manage the memory allocation by hand, using raw pointers and “new” and “delete” operators. Library tools like unique_ptr, shared_ptr, STL containers, etc. are not allowed.

The resulting class should be able to power this implementation of mergesort (source code is informative only, there might be mistakes, and you can do reasonable modifications). This mergesort is quite allocation-intensive (there are lots of small reallocations of the lists), you can attempt to rewrite it for less reallocations and observe the resulting speedup (it should be significant).

Assignment B (due 2017/03/31): Ultra-safe sparse matrix with rows and cols (a.k.a. MATLAB)#

UPDATE: use this skeleton code.

Write an implementation of sparse matrix of some type called smatrix<T>, that supports interesting ways of accessing content by rows or columns, and _never crashes_.

Sparse matrix is defined as a matrix that contains an overwhelming majority of zero elements. That fact is usually exploited to save memory, so the implementations only store indexes of non-zero elements.

• Do not use raw pointers nor raw memory allocation — wrap everything in provided, safe STL containers and/or smart pointers. If you really want to work with raw pointers, wrap them in something to make them provably safe.
• To save space, store only non-zero elements of the matrix. Zero matrices even of enormous size should have almost-zero memory requirements.
• Support standard ways of copying, constructing, destructing and moving the matrices around.
  • smatrix<int> m=other_matrix;
• Support for .resize(), .width(), .height() and similar helpers.
• Support following functionality:
  • trivial algorithms for adding (voluntary: and multiplication no Strassen!)
  • Operations on whole rows and columns:
    • m.row(1)=m.row(5); copies the whole row
    • m.row(6)[2]==m.col(2)[6]
  • standard access using brackets:
    • m.resize(50000,50000);
    • m[234][346]=31337;
  • Mixed assignment of whole rows/cols or submatrices:
    • m.col(5)=m.row(333).transpose();
    • m.col(5).transpose().transpose() = m.col(6);
    • m.submatrix(0,0,5,5)=m.submatrix(10,0,5,5); copies a 5x5 submatrix of the matrix m to another place
  • (optional) Following code should produce a 1x1 matrix (it’s a dot product): m.row(123) * m.row(50).transpose()
  • (optional) Following code should produce a symmetric product matrix: m.col(5) * m.row(5)
  • Sizing works on subregions:
    • m.col(5).width()==1
    • m.col(5).height()==m.height()
  • combinations of all previous things should work too.
• For performance reasons, the operations should not create temporary matrices where it’s not required, and provide references instead.
  • E.g. this should modify the contents of m: auto row = m.row(12345); row[5]=3; row[6]=row[88];
  • and this should not modify the contents of m: auto row = m.row(1345).make_a_copy(); row[5]=3;
  • You can probably invent better syntax&name than .make_a_copy()
  • For clarity, you can also (optionally) have something like .make_a_reference() which creates a “proper” and safe reference type to the matrix.
• All operations should always be memory-safe:
  • assignment out of the specified matrix range should do nothing
  • assignment should not work on const objects or references
  • reading out of specified matrix range should return the zero element
  • on problematic situations that “should fail in a reasonable world” (e.g. multiplication of matrices with unmatching sizes etc.), choose&document any simple method to produce a partial, incorrect or fallback result that doesn’t fail.
• 3 optional BONUS POINTS for extra memory safety:
  • If the matrix object disappears, usage of its reference won’t crash the program. So, for example, returning a proper reference-type to function-local matrix should not be “dangerous”.
  • Iterator support ( for(auto elem:m.row(5)) ... ), that is also “safe” in the same sense — using iterator that points to a deallocated matrix doesn’t crash the program.
  • One way to ensure this kind of safety is to employ a variant of “shared pointer” — not to deallocate the matrix data until there’s something (reference, iterator, whatever) pointing to them. This can lead to ugly memory leaks (e.g. one dangling reference to one element in a gigantic matrix). Try an alternative approach — invalidate all references (turn them into dummies that do nothing) when the matrix data is destroyed.
• Use reasonable code quality guidelines.
• Contain the result in header file smatrix.h (and optionally smatrix.cpp) and submit using the SIS study group interface to corresponding fields.

NOTE: Although the specification seems terribly overcomplicated, this is basically an “assignment reading exercise”. After some thinking and generalization, the implementation should be pretty straightforward (except for the BONUS, which requires a bit of setup). You probably want to have a general type for all “possibly-transposed submatrix references”, e.g. all rows, cols, transposed rows, double-transposed rows and submatrices should have the same type.

Project#

Every student should create an individual project and submit it to get the credit. Topic is variable, but should be discussed and agreed upon before the end of November. Size of the project is not an issue, but at least around 500 lines of (condensed and neat) code is a good guideline.

Erasmus students may need a completely different time limit. If you are from Erasmus, contact us for details.

Bad topics:

• Boring libraries
• Boring games
• Anything that does not behave C++-ish (e.g. code without a single class construction)
• Anything that requires complicated or very specific user interface (e.g. bank account simulator, unless the interface is solved neatly in some novelty C++ way)
• Anything that has 100000 implementations already hanging around the internet
• Also, there’s already too many of checkers, worms, tetris, pacman, snake, tictactoe, etc.

Good topics:

• Small fast games (fun!)
• Convenient data structures with demos (useful!)
• Physics-like simulations of something (collisions etc. are cool)

Deadlines:

• Topic agreed upon, written in SIS: November 30th, 2016. Send me an e-mail to make sure the topic is confirmed and added to SIS.
• “Beta” version showing some work done: March 31st, 2017
• Final version inc. documentation: May 28, 2017

Timeline#

2016/10/03#

• Introduction on how to compile and run basic C program in various environments. Some info about C programming language, origins, background, internals, pointers.
• Unfinished crude example to create a linked list.

2016/10/10#

• Giving the unfinished linked list example from last time some sensible, reasonable, neat and complete form.
• Wrapping it in a class!
• Some differences between C and C++, references, overloading.
• Libraries and header files
• source code here

2016/10/17#

• Programmer gets lazier and gets neater classes with overloaded operators.
• Construction/destruction/copying, const-antness.
• What is the actual output of C++ compiler anyway? (see what the CPU sees!)

2016/10/24#

• Strings!!!!1
• Copy construction, safe destruction, hint of move semantics.
• The code we produced is here

2016/10/31#

• Overview of templates.
• STL sneak peek:
  • standard containers and their uses
  • iterator concept

2016/11/07#

• Inheritance&polymorphism
• Usage example — polymorphic container
• How to make something like unique_ptr
• Source code here

2016/11/14#

• File I/O in STL
  • getline!
  • istream/ostream/fstream/stringstream.str
  • open/close, good/bad/eof/fail
• explode(), implode()

Simple stuff we didn’t manage to do on time:

• raw IO: put/get, read/write
• manipulators: endl, flush, setbase/dec/oct/hex, setfill, setprecision, setw, skipws, showpos, showpoint, showbase, boolalpha

2016/11/21#

• advanced operators, conversion operators
• proxy classes, “properties”
• fun with array-alikes

2016/11/28#

• STL practice session (GoL, postfix calculator)

2016/12/5#

• a tokenizer and recursive descent parser of some expressions
• code here

2016/12/12#

• Linking with other people’s code and libraries.
• LZO example. Corrected source code here. The mistake I did on the lesson was………swapping the arguments of string::resize(n, c)! :D

2016/12/19#

• By popular demand: Eye candy (OpenGL and related practices).

Stuff in the queue#

• Wrapping complexity, containing danger, programming safely by holding invariants.
• Practical stuff:
  • data structures (i.e. why everyone hates RB-trees)
  • tiny compilers & virtual machines

Bonus material#

• The Art Of UNIX Programming (online version) by E.S.Raymond is a brilliant material not only about the origins of current computing practice and the C++ programming language (that emerged together with UNIX), but also contains almost all of the most important insights about software development gained in last 50 years. Surprisingly, all of them still apply. Sometimes a bit philosophical. If you are developing a large system (or a part of some) for the first time, this book will tell you what design mistakes you are almost certainly going to make, what are they called, and how to avoid them.