Please check my presentation on С++ standard library

[SAn]

I have made a presentation on C++ standard library for my students. (Final version will be in Russian, I have written it in English at the first place so you guys can read it).

Link: http://dl.dropbox.com/u/2637905/CPP_Library_Eng.pdf

May be there is something wrong in it, or something should be added? I'm planning to add additional slide with image clarifying work of bidirectional iterator on tree-like container.

[SeppJ]

May be there is something wrong in it,

That's quite a lot to read. Are there any parts you think we should have a look at? I doubt anybody in this forum will proofread 60+ Pages.

or something should be added?

In the recent 2011 standard several new features were added to the standard library. You mention the hash map, maybe you want to mention the others, too? As additions to the standard library are relatively easy to do (compared to changes to the core language), these new features will be amongst the first parts of C++11 to become widespread. In fact, many compilers have already added the new features to their standard library years ago.

[SAn]

Concerning C++11 features, I have mentioned "foreach" loop, move constructors, and unordered containers. I think I can also add "uniform initialization" and additional algorithms from standard library.

The things I am not sure:

• Slide 5 is my guess. I have not seen any info why math functions are present both in std:: namespace and :: namespace.
• Does standard requires that std::vector can be created in O(1) time in case of trivial constructors?
• I have read in a book that std::deque does not invalidate references to its elements but invalidates iterators when elements added. Is it true? How can it be?
• I am not sure that "Search, inserting and removal of elements in best implementations [of hash arrays] can be done in O( ln( ln(N) ) ) average time" (slide 47).
• Is it safe to assign invalid iterator to valid iterator? What operations are possible with invalid iterators without triggering undefined behaviour?

[Nexus]

SAn schrieb:

Slide 5 is my guess. I have not seen any info why math functions are present both in std:: namespace and :: namespace.

Those in global namespace are relicts from C, included with <math.h> . They are not especially relevant for C++, except for compatibility reasons.

SAn schrieb:

Does standard requires that std::vector can be created in O(1) time in case of trivial constructors?

I think the std::vector default constructor is always O(1), and the ones taking an iterator range or creating multiple elements at once O(n). Independent of the element constructors. I haven't looked up the standard, but that seems reasonable...

SAn schrieb:

I have read in a book that std::deque does not invalidate references to its elements but invalidates iterators when elements added. Is it true? How can it be?

Here I'm not sure, maybe someone else knows.

SAn schrieb:

I am not sure that "Search, inserting and removal of elements in best implementations [of hash arrays] can be done in O( ln( ln(N) ) ) average time" (slide 47).

Isn't at least search amortized O(1)? See also the Documentation of Boost.Unordered...

SAn schrieb:

Is it safe to assign invalid iterator to valid iterator? What operations are possible with invalid iterators without triggering undefined behaviour?

No, this is not safe. The only defined operation on an invalid iterator consists in assigning another, valid iterator to it.

[SeppJ]

Nexus schrieb:

SAn schrieb:

I have read in a book that std::deque does not invalidate references to its elements but invalidates iterators when elements added. Is it true? How can it be?

Here I'm not sure, maybe someone else knows.

I don't know for sure whether this is backed by the standard but at least I have an explanation:
When the deque adds new elements it does not move the old elements but instead just gets a new block of memory and puts new elements there. Thus, references to old elements remain valid.
On the other hand, a deque iterator needs to know, where to find the other elements because it is a random_access iterator. If the iterator were to carry all the information about the memory blocks used by the deque by itself it would get invalid if a new block is added as it can no longer find the new elements. I don't know why the iterator would carry all this information by itself and not just a reference to the deque's own storage. Maybe this is some kind of optimization. Or the standard does not want to be too strict.

[314159265358979]

SAn schrieb:

Does standard requires that std::vector can be created in O(1) time in case of trivial constructors?

Here is a list of all constructors and their complexity: http://en.cppreference.com/w/cpp/container/vector/vector

SAn schrieb:

I have read in a book that std::deque does not invalidate references to its elements but invalidates iterators when elements added. Is it true? How can it be?

The C++0x working draft n3290 says:

n3290 schrieb:

Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

and

n3290 schrieb:

Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.

SAn schrieb:

I am not sure that "Search, inserting and removal of elements in best implementations [of hash arrays] can be done in O( ln( ln(N) ) ) average time" (slide 47).

Average case is O(1), worst case O(N). See n3290

SAn schrieb:

Is it safe to assign invalid iterator to valid iterator? What operations are possible with invalid iterators without triggering undefined behaviour?

The only defined operation is to assign a valid iterator to it. Other operations result in UB.

Here are just a few things i noticed

• On slide 13 there is a typing mistake. <ifstream> should be <istream>
• On slide 30 you write:

(int *) malloc(...)

In C you don't need to cast explicitly because a void* is implicitly convertable to a T*

• Slide 32: "The ability to change memory buffer size which is present in C (function realloc()) is not used". This is not strictly true. See: http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/

• Slide 33 - Your 'Array' class.

Array(int const size = 0)

this should better be:  

```cpp
Array(std::size_t size) // no default size

• Copy ctor - you should use the std::copy algortihm
• Copy operator = You could implement the copy & swap idiom. If you don't use the std::copy as in the copy ctor.
• Functions that don't take parameters can be written

i_dont_take_anything();

instead of

i_dont_take_anything(void);

• Slide 36 - vector: "Typical applications – array or stack of objects"
  You should be using vector all the time until you have a good reason not to do so.

• "The Big four" should be "The Big three". The default ctor doesn't belong to them because the compiler doesn't generate one when a user-defined copy ctor is present. This should be "The Big five" under C++11. (move ctor, move op
  However, this rule doesn't only apply to elements stored in a vector. "The Big three/five" is a general rule, no matter what you want to do with your class.

• Slide 38 - deque: "That is accomplished by use of circular memory buffer." The C++ standard doesn't say, that deque should be implemented that way. Other implementations are possible, e.g. an array of arrays.

• Slide 38 - deque: "Typical application of deque – the queue of objects" is like "Use a double ended queue when you need a double ended queue.".

• Slide 40 - list: "Typical applications – stack and queue without ability to access random element". Again, this is _how_ you can use it but not _where_ it can be used. A list is used when one needs to perform many insertions or deletions.

• Slide 42 - set: "The difference of set from vector is that order of elements is not preserved" The difference is that elements in set are always in sorted order.

• Slide 42 - set: "Containers without the “multi” prefix do not store “equal” elements (see below) – each value can occur not more than once" I would rewrite this like "The multi-containers allow insertion of equal elements.".

• Slide 42 - set: "To allow objects of user class to be stored in set or multiset, it should (in addition to The Big Four) have operator<" A class can also define a function object used for comparison instead of op <.

• You could mention std::forward_list when talking about the new unordered containers from C++11.

• Slide 50 - Iterators:

• "The simplest iterator – forward iterator" The simplest iterators are input and output iterators.

• "You can obtain iterator to the “first” (in some sense) container element" This is an ability of a container, not of an iterator.

• "Iterator allows to go to the next container element" This is not a special ability of an iterator type. That's what the term "iterator" means.

• "You can check that you have passed the “last” container element" This is, again, not a special a ability. An iterator without this is not an iterator.

• "When using iterator to iterate over the elements from the beginning to the end each container element will be processed exactly once (iterators do not skip elements or visit them multiple times)" That's wrong. Iterators could skip odd numbers or something.

• Slide 58 - algortihms: "Algorithms are defined in the <algorithm> header file" The numeric algorithms are in <numeric>, you should mention them.

• You show complicated algortihms but not the simpler. For example: std::copy, std::find and their _if versions.

Mein Englisch ist voll toll.

[SAn]

Thank you! I will fix presentation and publish it under Creative Commons license.