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

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, fall semester 2017
    • English group: every Tuesday at 17:20 in SW1
    • Czech group: every Wednesday at 10:40 in SW2
  • 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 — CString

Wrap a C-style string functionality in a STL-style string container. You are not allowed to use STL though: All memory management and required data structures need to be implemented by you.

The string class should support:

  • methods .empty(), .clear() and .length() with standard behavior
  • operator+ and operator+= that work as string concatenation
  • multiplication using operator* by a scalar value N, which works as concatenating the string N times with itself
  • operator[] that accesses n-th character of the array
  • comparison operators ==, !=, <, ...etc
  • rule of three (i.e. reasonable default and copy constructor, assignment using operator=, and destructor), class MUST NOT leak memory, free unallocated memory, or cause access to unallocated memory.
  • transparent assignment and construction from const char*
  • method .c_str() that provides a const char* that points to string data (and can be used in C functions)
  • method .sub(first,n) that returns a substring that starts at position first and contains at most n characters (or less, if there aren’t sufficient characters in string). Argument n should default to “take all characters to the end of the string”.
  • PHP-style operator+ that works with simple types that can be converted to string, e.g. CString("aaa")+3 == CString("aaa3"); the accepted types should include int, float and const char*.
  • being a const (i.e. the constant methods should be marked constant, non-changed reference parameters also, etc.)

Hints:

  • Choice of memory allocation “API” is yours, you may use new and delete as well as malloc() and free().
  • Your implementation can use a single pointer that points to the beginning of allocated string. The other implementation with three pointers (begin, end of string, end of allocated memory, as used in std::string) is also possible, but not required.
  • The implementation should not crash, except for reasonable cases that you document in comments (examples: out-of-bounds index given to operator[], or str.sub(x) with too large x)
  • You do not have to implement string operations by hand (but you can), use functions from <cstring> (see here, but make sure you understand their semantic, esp. the conditions when they crash).
  • You do not have to implement integer to string (and similar) conversions; use C-style conversion using snprintf().
  • The assignment (and the whole C++ course) is about programming nicely, not about algorithms or speed. Make sure that your code is easy to use, readable and portable:
    • Consider using a code formatter tool (astyle).
    • Use appropriate and portable types! E.g. int is NOT a good return type for your string::length(), for at least 2 good reasons.
    • Add comments where needed, make sure your variable names make sense and the code constructions are semantic.
    • Check if your code works on another platform (e.g. ssh to the computer laboratory and use GCC to compile it).
    • Avoid compiler warnings (with GCC you may turn on more warnings with -Wall parameter, which may point you to many problems in the code)

Save your solution to a .h file and (optionally) accompanying .cpp file, and submit them using the SIS study group interface — corresponding fields are marked DU1 (czech) or HW1 (english). Your score and comments to the solution will be available at the same place.

DEADLINE: Sunday November 19th, 23:59:59.999

UPDATE: If you are not sure whether your solution really works as expected, you can test it with the test program. (I have assumed that your class is called CString and is available in file CString.h, change that if required.)

UPDATE OF UPDATE: There was a mistake in the original test program on line 22 (there was = instead of originally intended +=). The result was that the program printed out lots of non-ascii garbage instead of what I originally intended (randomly looking strings of numbers and letters).

Assignment B

TBA on 2017/11/28. It will be noticeably more fun than assignment A.

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, but at least around 500 lines of (neat) C++ code is a good guideline.

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!)
  • Convenience programming libraries (convenient!)
  • Convenient data structures with demos (useful!)
  • Physics-like simulations of something (collisions etc. are cool)
  • Compilers, transpilers, virtual machines, typecheckers or interpreters for small programming languages.

Deadlines:

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

Lab timeline

Week 1 (2017/10/3,4)

Introduction to (and necessity of) C and low-level programming in general. How to compile C to assembly, how does linker link the symbols to produce executables.

Source code here. (Source from the labs will always appear there. Also, if you are new to programming on UNIX, you will certainly want to examine the makefile from 01/asm2/Makefile !)

Week 2 (2017/10/10,11)

Plain C programming practice (with pointers).

Sad face about how modern CPUs won’t ever process strings automagically.

Source code can be found on the usual place.

Week 3 (2017/10/17,18)

C++ leap: Encapsulation of various stuff in nice interfaces, a word about references.

Week 4 (2017/10/24,25)

Constructors and destructors, RAII (do NOT use new if you really don’t want heap memory), a tiny hint of resource ownership. We have applied the Rule of Three (copy constructor+copy assignment+destructor) to make sure that our list class will be handled as we expect in all cases, which makes it perfectly encapsulated (and basically as safe as we want to). Source code is on the usual place.

Week 5 (2017/10/31, 2017/11/01)

A bit about templates, STL containers and iterators.

Week 6 (2017/11/07,08)

A bit of I/O. Iterators on your own class.

Czech class was cancelled due to a sport event. The material from english class is available for study as always, I suggest you take a look at it. We’ll eventually run through it at the lab.

Week 7 (2017/11/14,15)

Run-time polymorphism, virtual, vtables, sneaky peek on smart pointers.

Czech class will be taught by Vlastimil Dort this week.

Week 8 (2017/11/20,21)

Conversion operators, proxy classes and their usage: get/set-style properties, safe array indexing.

Forecast

More smarter pointers.

Some valid uses of the pre-processor (guards, macros, portability).

Templates on steroids.

Programming practice:

  • STL container use cases.
  • Parsers, ASTs and interpreters.
  • Interfacing with external libraries and/or other programs, a bit of UNIX.

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 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 graphics, try OpenGL. Easiest way to do it is using e.g. GLUT, example programs are available here and here . Compile with gcc glut.cpp -o glut -lGL -lGLU -lglut . You might also want to see SDL that is traditionally used for portable games, or a newer alternative SFML. NeHe tutorials are good introduction to overall OpenGL programming, but have become somewhat obsolete and require bit of porting to work on modern platforms. Some googling will probably help. Red book is a classic reading.