Infopage about the C++ lab of NPRG041.
- Taught by: Miroslav Kratochvil, contact: firstname.lastname@example.org (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:
- Very probably any good book about C++ will do. There are some in the faculty library. Because MFF students are generally more apprehending than the common programming crowd, I highly suggest you go directly to the Standard . (click on the 2014 Programming Language C++ link in Published standards)
- Cplusplus.com — especially following sections:
- When in any doubt, mail me.
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!
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:
.length()with standard behavior
operator+=that work as string concatenation
- multiplication using
operator*by a scalar value N, which works as concatenating the string N times with itself
operatorthat accesses n-th character of the array
- comparison operators
- 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
.c_str()that provides a
const char*that points to string data (and can be used in C functions)
.sub(first,n)that returns a substring that starts at position
firstand contains at most
ncharacters (or less, if there aren’t sufficient characters in string). Argument
nshould default to “take all characters to the end of the string”.
operator+that works with simple types that can be converted to string, e.g.
CString("aaa")+3 == CString("aaa3");the accepted types should include
- being a
const(i.e. the constant methods should be marked constant, non-changed reference parameters also, etc.)
- Choice of memory allocation “API” is yours, you may use
deleteas well as
- 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
str.sub(x)with too large
- 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.
intis 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
-Wallparameter, 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
(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
= 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 — Simple Grep
You certainly know the
grep utility from UNIX systems. The assignment is to
write a simple reimplementation of that. Let’s call it
sgrep receives a single command-line argument, which is a regular
expression. Then it processes
the input line-by-line and prints out the lines that match the regex.
Your program should accept a simple subset of the regular expression patterns:
- Single characters, like
- Single character choices, like
[a-z](which means the same thing as
[a-zA-Z](which basically means “any english letter”).
- Negation of character choice —
[^abc]which matches any character that is not
- “Any” character, the
- Escaped characters — any character prefixed by
\is not a special character, but the literal character. Backlash is entered as
\.means a literal dot in output, not “any character” as above.
- Kleene star —
a*may match empty string, or
aaaa, or generally any number of repetitions of
- Alternatives —
ab|cdmay match either
)for grouping stuff
- All these patterns concatenated and combined, like
After parsing the regular expression from the argument (
argv argument of
main() ), your programm should read the standard input line-by-line, decide
which lines match the given regular expression (WHOLE line must match the
grep), and print them out of they do.
Example usage input:
$ ./sgrep 'aba*cd' --on windows, it would be: # sgrep.exe 'aba*cd' xxx abcd abaacd xabcdx abd
If there are parentheses in the input, the program should instead print the matched content of the parentheses, one by one, separated by a newline:
$ ./sgrep 'a([bc]([de]*))' ab acdedddeee ade
b --first line, first paren --first line, second paren is empty! cdedddeee --second line, first paren dedddeee --second line, second paren
The main requirement of assignment B is to never use manual memory management. Preferably not even raw pointers nor anything that can get broken easily. Exploit STL as much as you can, preferably smart pointers and other data structures, to get the safest and cleanest code possible. Except for the STL regex library, of course.
Your program should also behave as a reasonable command-line utility:
- never crash
- do not leak memory during the processing
- behave silently — output only the exactly required output, unless there is an non-recoverable error that needs to be reported (e.g. a wrongly formatted regex pattern on input)
- behave reasonably in case of mis-invocation — report the error to standard error output and return a corresponding exitcode
On the other hand, you may ignore several practical and efficiency-related measures that are present in traditional
- You can load whole lines into memory, ignoring the fact that multiple-terabyte lines are a common sight nowadays. Do not load the whole input into memory though (inputs in the test cases will be larger than the memory available).
- Your regular expression matching doesn’t have to be particularly fast, but it should not be extremely slow either. Find a balance between speed and code readability that fits you.
- You may use “unbounded” recursion, of depth roughly equal to the length of supplied regular expression (ignoring the fact that evil users will give you really long regular expressions).
- You do not have to compile the regular expression to a finite state machine (or any similar machine) — interpreting it is OK.
- If the content of the parentheses is ambiguous (e.g. when matching pattern
aaaa), print out any valid matching.
- Do not handle any kind of complicated character encodings — all input and regex characters will be plain ASCII single-byte characters with ASCII value lower or equal to 127.
- Do not try to solve problems inherent to regular expressions — for example, matching a pattern like
.*.*.*.*.*.*a.*in a word
abbbbbbbbbbbbbbbbbbbbis just slow; you don’t need to worry about it.
- You may reject regular expressions that match stuff in a really wrong way (like
Points for solution will also be derived from the usual criteria:
- Readability/maintainability/portability of the code
- Use an automatic code formatting tool to keep the formatting concise.
- Try compiling the code for other platforms
- Add comments to code when its complete meaning is not instantly obvious
- Avoid compiler warnings (compile with
- Avoid repetitive code, use the SPOT rule (see here), exploit generics and/or macros to remove the repetitions.
- Appropriate types of all data
- Reasonable solutions of all underspecified/ambiguous corner cases from the assignment. E.g. when given pattern
[a-], you may either match both characters
a, or report a syntax error that
-is used wrongly (and should be used as
[a\-]instead), or use any other reasonable behavior as long as you describe it in the comments.
Submit your solution to SIS using the study group interface (as usual). The
corresponding field for the .cpp file (no headers this time!) is
DU2 - sgrep.cpp
for Czech group, and
HW2 - sgrep.cpp for English group.
UPDATE: Because this is a C++ lab (not a formal grammars lab), recommended structure of tokens/parsers/matchers is provided here.
UPDATE 2: checking your solution. To verify that your solution works as expected, you can compare its output to the output of standard UNIX utilities
- When matching a regular expression without parentheses, output of your
./sgrep regexregexshould be the same as the output of
grep -E ^regexregex$(except for minor differencies or incompatibilities between used regex syntaxes, which you can fix by hand).
- When matching a regular expression with parentheses, the output of
./sgrep regexregexshould be the same as the output of
sed -E -ne 's/^regexregex$/\1\n\2\n\3\n...\9/p'(again modulo some syntax incompatibilities and the adjustment of backreferences (
\2, ...) by hand)
UPDATE 3: You may submit the assignment solution after the deadline, with appropriate score penalization. The penalization for delay of
n full days after 2017/12/17 is computed as
floor(n*n/8) (so a few days delay is mostly OK).
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).
- 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.
- Small fast games (fun!)
- Convenience programming libraries (convenient!)
- Convenient data structures with demos (useful!)
- Physics-like simulations of something (collisions etc. are cool)
- Networking (internet!)
- Compilers, transpilers, virtual machines, typecheckers or interpreters for small programming languages.
- 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: April 14th, 2018
- Final version incl. documentation: May 15th, 2018
- 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, all other 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, leak or otherwise torture memory; 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::chronoprovides 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
TUTORIALthat describes what should I do with the compiled program to see all the important functionality as quickly as possible.
- If the
DEMOrequires 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
INTERNALSfile 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
READMEwith corresponding sections.
- Include a file
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
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
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)
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.
Week 9 (2017/11/28,29)
Recursive Descent Parsing —- a straight-forward way to convert a formal grammar to a tokenizers and parsers. AST as a really vital data structure.
Week 10 (2017/12/5,6)
Using the previous approach to write an interpreter. Using preprocessor to generate repetitive code.
Week 11 (2017/12/12,13)
UNIXifying the interpreter, smart pointers and move references.
Week 12 (2016/12/19,20)
A bit of practice —- implementing the postfix calc, various goodies from STL iterator/algorithm library.
We still have 2 labs left now, so if you want to practice something specific, send me an e-mail.
Practice for the exam.
Extra stuff we managed to fit in the czech lab: Computing with templates, low-level program loading (dynamically linked libraries), simple HTTP-like server.
- 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. 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 :]