e-x-a.org » NPRG041 C++ programming (cs/en) 2018/19

Infopage about the C++ lab of NPRG041.

  • Taught by: Miroslav Kratochvil, contact: kratochvil@ksi.mff.cuni.cz (please include the course name/code in the subject)
  • Meeting point: MS MFF, fall semester 2018
    • Czech group: every Tuesday at 15:40 in SW2
    • English group: every Wednesday at 15:40 in SW1
  • Reading material:
  • When in any doubt, mail me.

Lab requirements

To get the credit, you have to attend the course reasonably (at least accordingly to your knowledge of the topic), do the homework (see below) and finish an individual project (also below).

You will be assigned several points for finishing the homework. These will be added to the points from the final test, therefore improving your final grade for the whole course.

Depending on many factors, students from Erasmus programs may need a completely different set of rules to fit into different time limits. If you are an ERASMUS student, contact us!

Homework

Assignment A (deadline: November 23rd)

We have learned to use the constructors and destructors so that a class can behave like a normal variable, but safely keep an associated resource (e.g. allocated memory, open file, or so.)

Apply this to implement a variable-length array type, called Array. Your implementation should be a work-alike of the std::vector, only reasonably simpler.

Requirements:

  • Make sure your code is portable to all three major C++ compilers (gcc, clang, msvc) and does not produce warnings (use -Wall with gcc and clang).
  • Do not use STL, your solution should be based on “raw” programming with low-level memory primitives.
  • Produce a reasonably short, neat, well-formatted and commented code. Use an automatic code formatter, i.e. astyle or clang-format. Check your code with automatic linter for common errors, e.g. cppcheck.
  • Code should never crash, UNLESS subjected to usage that is documented as an invalid action that causes undefined behavior (i.e. out-of-bounds access by library user)
  • Code should not leak memory. You can use valgrind to check for memory leaks automatically.
  • The implementation should be as efficient as possible — Do not allocate memory unnecessarily (esp. not on construction of empty container), use correct const-antness, references, etc.
  • Required functionality:
    • Support for any contained type, using a template.
    • Safe default constructor, copy constructor, copy assignment operator and destructor.
    • implementations of empty, push_back, pop_back, back, front, swap, size, clear, assignable version of operator[] that behave as usual with STL containers. Note that you will have to implement 2 overloaded variants of operator[] and several other accessor functions — one for accessing constant array elements (that returns a const-reference) and the second for mutable contents.
    • swap that swaps contents of 2 Arrays in O(1)
    • append that adds content from another array to the end, i.e. a.append(b) causes a to contain contents from original a followed by b.
    • reserve that pre-allocates memory for contents, so that successive pushing to the back of the array doesn’t need to reallocate the array frequently. Note that any other action than adding elements (eg. copying the array, popping elements, downsizing) is free to remove the effect of reserve preallocation.
    • resize that changes the number of elements stored in the array. Note the difference between reserve and resize — resize should construct the objects, reseve should never construct anything; just prepare the memory.

Remember that you need to call constructors and destructors of the objects contained in your array, so that they are correctly initialized and destroyed after use!

You can implement following bonus features to patch up other inefficiencies in the code:

  • Move semantics, i.e. the “rule of five”, optionally with emplace_back.
  • begin, end, and associated iterators, to make the container compatible with the usual range-based for loops.

Place your resulting solution to file cpparray.hpp and upload it to the correct field in the study group interface in SIS.

As a test, you can use this file which should work correctly with your implementation of Array. (Note that there’s a possibility to use std::vector instead of Array for the test — this can serve as a guideline if you are not sure about exact functionality of something.) The default test is small and may not crash even if your implementation contains errors; try increasing S to a larger value (say, 100) to increase the failure probability.

NOTES: It is important to understand the semantic difference between “raw allocated memory” (which is the result of reserve() operation) and “allocated memory with constructors ran on it” (which is the result of resize()) — if the user only reserves the space for objects, none should be actually initialized (imagine the objects hold some large resource or lock something; the user would not like to consume these resources before he places the actual objects into the container). You can allocate raw memory using either malloc(size) or using operator new(size). Memory can be deallocated without calling a destructor using either free(ptr) or operator delete(ptr). The constructors can be ran manually on raw memory using the “placement new” syntax — new(ptr) Type(constructor_args); destructors are ran using the “pointer destruct” syntax — ptr->~Type(). Compare with ptr=new Type() and delete ptr, which combine both memory allocation and object initialization/destruction. This difference is something that is vital for understanding the RAII model of C++ and drawing a bold line between memory allocation (which is one resource) and object lifetime (which is a completely different resource that only requires the space provided by the previous one). Anyway, this gets philosophical very easily; for that reason you will not be penalized if your implementation does not do this completely right. The only thing you need to ensure is that all objects in the valid array size (indexes 0 to size()-1) have been initialized and will be deinitialized upon removal.

Assignment B

TBA

Project

Each student has to 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 and largely depends on the topic, around 500 lines of (neat) C++ code is a good guideline (on the other hand, packing the same functionality into a smaller program using e.g. advanced language features is even better).

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)
  • Database workalikes, e.g. “evidence of hotel guests”, “evidence of soccer results”, etc.; unless the underlying database storage is somehow interesting.
  • 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!)
  • Convenience programming libraries (convenient!)
  • Efficient data structures with demos (useful!)
  • Physics-like simulations of something (collisions, gravity, particles, etc. look cool)
  • Networking (internet!)
  • Compilers, transpilers, virtual machines, typecheckers or interpreters for small programming languages.

Deadlines:

  • Topic agreed upon, written down in SIS: November 30th, 2018. Send me an e-mail to make sure the topic is confirmed and added to SIS.
  • Recommended time for submitting final version: March 2019.
  • Final version incl. documentation or example demonstration: May 10th, 2019. Projects that are first submitted after this deadline will not be evaluated at all. Resubmissions and corrections are possible.

Submission guidelines:

  • Make the code portable — it should not depend on the platform unless it is, by design, tied to that platform. Windows-specific projects should work on Windows in the computer lab, UNIX projects should work on Linuxes in the computer lab.
  • Do not over-engineer, avoid feature creep. The simplest project that satisfies the following conditions will do:
    • There’s a reasonable amount of C++ that shows you know what you’re doing
    • It does not crash, in particular it does not dereference invalid pointers, cause leaks, or torture the memory in any other way.
    • It doesn’t contain any inefficiencies that could be fixed by better C++. (Repeat: const references! avoid allocation!)
    • It provably does what the topic says, and it can be demonstrated on data of reasonable size.
    • It has sufficient comments. If you are unsure if you should add comment somewhere, try to tear the surrounding program block or function out of context, and ask yourself if anyone can still fully understand what it does (and why). If not, it needs comments.
    • If the topic is a data structure, include a comparison with a naive approach or some C++ counterpart (std::chrono provides timers). Note that your data structure does not need to “win” the comparison (that’s the topic of the HPC course), you should only provide a reasonable testing framework to assess the performance.
  • If you think the project is ready, either pack it up and mail it to me, or send me a git link.
  • Having received your program, I should be able to convince myself that it works in less than around 15 minutes. You can help it a lot:
    • Include a file INSTALL (.md) that describes how to make it work on a fitting computer configuration. (Best: How to make it work on computers in MFF’s computer lab.)
    • Include a file DEMO or TUTORIAL that describes what should I do with the compiled program to see all the important functionality as quickly as possible.
    • If the DEMO requires some data for the demonstration, include it! (Advice: If I’m forced to create testing data by hand, it will take more than 15 minutes. Also, result will contain lots of hideous corner cases.)
    • If there’s lot of source code, include INTERNALS file that describes which parts of the functionality can be found in which part/file of the code. This is sometimes also called “programmers documentation”. Imagine it as a signpost, compare with artist’s impression thereof.
    • If the documentation files are not very big, pack their contents into one nice README with corresponding sections.

Lab timeline

Source code from the labs will be available here.

Week 1 (October 2nd and 3rd)

Quick introduction into C programming (we didn’t manage to do much stuff).

Week 2 (Oct 9th, 10th)

Managing your memory manually, pointers, strings and lists.

Week 3 (Oct 16th, 17th)

C++-style IO, using structs as objects with methods, operators, overloading, references.

Week 4 (Oct 23th, 24th)

Rule of three, application to linked-list class.

Week 5 (Oct 30th, 31st)

STL crash-course — containers and their usage, concept of iterators.

Week 6 (Nov 7th)

Czech lab was cancelled due to some other event. English lab: custom iterators, some more I/O with files, look at proxy classes.

Week 7 (Nov 13th, 14th)

Czech lab: custom iterators, file IO.

English lab: run-time polymorphism

Bonus material

  • Do not, never, ever use reinterpret_cast for converting pointers. Using a pointer converted by reinterpret_cast works by accident and may cause undefined behavior, EXCEPT in the case you reinterpret the pointer back EXACTLY to the original type (so you basically don’t do any conversion), provided the byte sizes of all values in the conversion chain are EQUAL. There are two legal usages: one for printing out a pointer address value as an integer, which you are usually not ever supposed to do; and one for converting binary data (e.g. creating floats from mantissa and exponent bits by hand), which you usually do not want to do. You want static_cast, or possibly dynamic_cast when downcasting base class pointers to derived class pointers. If you still want to use reinterpret_cast, remember there may be architectures where sizeof(char*) != sizeof(int*).
  • 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 and gave rise to C++), but also contains almost all 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.
  • Doug Lea’s Malloc — a webpage about the original default allocator of most C/C++ libraries, which makes an extremely good read about allocators. (anyway — you probably use that guy’s code several times per second just by silently watching this website)
  • If you would like to create a game for the semestral project and have no idea where to start with the graphic output, try OpenGL. There are lots of ways to get an OpenGL viewport for your program, the easiest of them is probably the GLUT library. You might also want to see SDL that is traditionally used for portable games, or a newer alternative SFML. Following sites provide a good introduction to modern OpenGL: https://open.gl/ and https://learnopengl.com/.
  • If you would like your game to be a bit more advanced (and save yourself a lot of coding), use a graphics/game engine like Magnum (from a former MFF student), Ogre3D or Urho3D.
  • If you like template programming but the syntax seems unwieldy, use this :]

...