Microsoft's Stephan T. Lavavej (STL) introduces the Standard Template Library (also STL).
- Containers, Iterators and Algorithms
- Associative Containers
- Smart Pointers - unique_ptr and shared_ptr
- Detailed STL Example - Nurikabe Solver
- Algorithms and Functors
- Algorithms and Sorting
- Regular Expressions in C++ 11
- RValue References in C++ 11
- Type Traits for Template Meta Programming
STL advanced topics:
- shared_ptr internals
- Template Meta Programming
- STL Validation in Debug Mode
- More about Rvalue References
- An Introduction to Boost Libraries
- Generic Pretty Printer for STL Containers
STL 1: Containers, Iterators and Algorithms
This video explains the basics of STL with a vector example. The relationship between containers, iterators and algorithms is explored with examples. The following topics are covered:
- Sequence containers
- Using vectors and vector memory management
- Accessing a vector via an iterator. begin() and end() usage is covered
- Using algorithms on iterators
- sort is used to demonstrate algorithms
- sorting with different comparators is also described
- Introduces auto variable declaration and lambda functions from C++11
STL 2: Associative Containers
We move on to associative containers. The map is covered in detail. The topics covered are:
- map is introduced:
- map insertion and entry update
- array indexing syntax for map
- key and value pairing in a map
- red black tree implementation of the map
- map performance guarantees
- unordered_map (C++11 or TR1):
- hash table based organization
- unordered_map performance guarantees
- map vs unordered_map
- Deleting multiple entries from a vector
- Pitfalls and performance issues with the loop and erase
- Using the remove and erase algorithms for efficient implementation of multiple entry remove
STL 3: Smart Pointers - unique_ptr and shared_ptr
- Developing a uniform solution for erase handling across different types of STL containers
- Unique pointer (unique_ptr)
- A unique pointer has the ownership to the pointed object
- The pointed object is destroyed when the unique pointer is destroyed
- Ownership can be transferred using move
- Ownership transfer is implicit when unique pointer is returned from a method/function
- Shared pointer (shared_ptr)
- Shared pointers share ownership to an object
- Many shared pointers may point to the same object
- The pointed object is destroyed when all the shared pointers
pointing to the object are destroyed
- The shared pointers pointing to the object maintain a common reference counter
- The reference counter is incremented when a new shared pointer points to the object
- The reference counter is decremented when a shared pointer to the object is destroyed
- The pointed object is deleted when the reference counter goes to zero.
- Shared pointers may be used in STL containers
- For example, you could declare a vector of shared pointers.
STL 4 and 5: Detailed STL Example - Nurikabe Solver
The following two videos solve the Nurikabe puzzle to demonstrate STL.
- Various aspects of STL are demonstrated.
- We would recommend coming back to these videos after you have covered the remaining videos in this series.
STL 6: Algorithms and Functors
- Non modifying algorithms
- for_each: Iterates over all elements to perform an operation
- count: Counts the elements that match the passed value
- count_if: Counts elements that match a certain criterion
- find: Finds a matching element (linear time)
- find_if: Find an element that matches a certain criterion
- equal: Compares sequences match
- Note that lengths are not compared
- The second sequence should be at least as the first sequence
- Functions, function objects and functors
- Functions are plain functions
- Function objects are instances of classes that have overridden "()"
- Compilers tend to do a better job inlining function objects and lambda.
- Functor is a general term that refer to a regular function or function object. Anything that can be called with "()"
- Using lambda expressions with STL. The C++ 11 lambda syntax is explained.
- Modifying/Mutating algorithms
- copy: Copies from an input iterators into an output iterator
- The output sequence should have enough space the elements to be copied.
- replace_if: Replaces a element that matches a certain criterion.
- transform: Transforms the elements in a container
- all_of, any_of, none_of from C++ 11 are recommended.
- copy: Copies from an input iterators into an output iterator
STL 7: Algorithms and Sorting
- back_inserter: Returns an insert_iterator
- Dereferencing and incrementing an insert_iterator adds a new element using push_back.
- For example, passing to to a back_inserter to copy will add elements
- Range constructs can be done in a constructor
- v.insert(iterator point, first, last): More efficient than back_insertor
- ostream_iterator: Writing to this iterator writes to ostream (not needed in C++ 11 as lambdas provide a cleaner design
- binary_search: Not very useful as it just tells you the element is present or absent
- lower_bound: Returns the last position where a value can be
inserted and still maintain sorted order. If the element does not exist,
lower_bound returns the first position where the new element could be
- begin() is returned if the element has to be inserted as the first element
- end() is returned if the element has to be inserted as the last element
- upper_bound: Returns the last position where a value can be inserted and still maintain sorted order
- equal_range: Returns a pair of iterators, containing the lower bound and upper bound.
- STL uses "less than" as the default comparators.
- Custom comparators should behave like "less than" (strict weak ordering), i.e. x compared to x should always return false
- Otherwise STL will return invalid results
- Order of "same" elements is not guaranteed, Use stable_sort if the order of "same" elements needs to be preserved.
- partial_sort allows you to sort a small subset of the full collection.
- nth_element: If this sequence was sorted, what will be the nth_element?
- Union and intersections can be obtained for sequences
- min can be used to obtain the least element
- max returns the largest element
- min_max returns the minimum and the maximum. This is more efficient than calling min and max separately.
- Lexicographical comparisons should be used for dictionary type sorting.
- Most algorithms are in <algorithm> header file, but some are in
- accumulate: Iterate to perform a binary operation value.
Initial value can be specified here.
- The default version uses plus
- iota: Used to initialize a sequence of increasing numbers. (C++ 11 only)
- accumulate: Iterate to perform a binary operation value. Initial value can be specified here.
- transform has two overloads:
- unary: Perform a unary operation on an input sequence and write to an output sequence. In place transformation can be carried out by passing the same sequence as input as well as output.
- binary: Takes elements from the first and the second sequences, performs a binary operation and then writes the results to the output sequence. Lets you perform pair wise transformation on two sequences.
STL 8: Regular Expressions in C++ 11
- Perl type regular expression
- regex: Typedef for using regular strings
- wregex: Typedef for using unicode
- regex_match: Does the regex match the entire string?
- match_results: For strings or unicode strings
- smatch: Results for regular strings
- cmatch: Results for const strings
- Capture group handling and reporting is supported
regex_search: Searches for fragments of the large string that match the
specified regular expression.
- sub_match contains iterators for start and end of the match
- The string can be extracted from the individual matches
- Search and replace strings that match the regular expression
- The replacements can be controlled at capture group level
- regex_iterator: Used to look at all instances of the matching
- sregex_iterator for regular strings
- wregex_iterator for unicode strings
- regex_token_iterator: Use to generate tokens from a string
- Need to address escape regex strings for C++
- Regular expression tree generation from the string definition of a regular expression is time consuming. This generation should be done once and reused multiple times.
STL 9: Rvalue References in C++ 11
- L-values are name objects. R-values values are temporaries
- C++ uses the copy constructor whenever an object needs to be copied.
This happens in cases like:
- Passing a parameter by value
- Returning an object by value
- Assigning an object
- The problem here is that a copy constructor might sometimes result in
redundant copies. For example:
- myvalue = MethodReturningValue() results in:
- a copy constructor creating an object on return from MethodReturningValue()
- Another copy constructor is called for the assignment
- myvalue = MethodReturningValue() results in:
- C++ 11 defines a move constructor so that this double copy can be
- In the above example:
- The method returns a value with a copy constructor
- Now the compiler knows that this is a temporary object so the second time it calls the move constructor
- The move constructor does not copy the object, instead it just replaces the contents of the object
- A move constructor has a signature of:
- ClassA(ClassA&& rvalue) -- Note the absence of const and double ampersand
- Compare this to a copy constructor:
- ClassA(const ClassA& lvalue)
- In the above example:
- C++ 11 version of standard template library will use move constructor to
reuse a temporary object
- When objects of a class are saved by value in STL containers, defining the move constructor will improve performance as unnecessary copying will be avoided.
STL 10: Type Traits for Template Meta Programming
- Type traits enable template meta programming with template argument deduction.
- The type traits header allows you to check the type of the typename in a
template and define methods that are appropriate for that type. For example:
- true_type and false_type are two separate types (they are equivalent of bool in runtime code). Queries about types return true type or false type
- is_integral : Is the type an integer?
- is_floatingpoint: Is it a floating point type?
- is_pointer: Is it a pointer type?
- true_type and false_type can be used to define different overloads for a method, this way you can control the overload that gets called for different types.
Advanced STL 1: shared_ptr internals
- Introduction to shared_ptr and unique_ptr video is a prerequisite
- shared_ptr can work in two modes:
- Explicit new is called and the pointer is saved into a shared_ptr
- make_shared (C++11) is used to construct the object.
- make_shared should be the preferred approach as a single buffer is used
to store the shared_ptr's internal housekeeping as well as the user
- The explicit new approach requires allocation of two buffers; one for internal housekeeping and second one for user allocated memory
- shared_ptr internally reference counts the pointers to the allocated memory. Memory is freed when the reference counter drops to 0
- weak_ptr and shared_ptr interplay is also discussed.
Advanced STL 2: Template Meta Programming
- Partitioning algorithm
- Changed from bidirectional iterators to forward direction iterator in C++11
- STL uses a faster algorithm when a forward direction iterator is
- This is accomplished with template meta programming.
- The algorithm selection is done at compile time, not runtime.
- Optimizing algorithms for specific user types
- For example, memcmp can be used to compare containers if the STL container contained integer
- Again, the memcmp selection is done at compile time
Advanced STL 3: STL Validation in Debug Mode
- This tutorial describes the debug checks that are added in the debug mode build in Visual Studio.
- Iterator debugging support in Visual Studio is covered.
- An undocumented compiler switch for analyzing the class layout is
described towards the end of the video (about 5:00 minutes from the end)
- You may skip this video if you do not use Visual Studio for your C++ development
Advanced STL 4: More about Rvalue References
- An introduction to Rvalue references is a prerequisite to this video.
- Rvalue references enable support move semantics and perfect forwarding
- With C++11, adding a move constructor and a move assignment operator for
classes will speed up STL execution as the compiler can use move semantics
- C++11 adds push_back method that takes Rvalue reference as an input. The compiler will use this method when it knows for sure that the object being passed is a temporary
- Normally, LValue references cannot bind to RValue references
- There is special handling for temporaries created from conversion. A temporary created from a Lvalue reference can bind to a Rvalue reference.
Advanced STL 5: An Introduction to Boost Libraries
- Installing and navigating through Boost
- A bimap is a data structure that represents bidirectional relations between elements of two collections.
- Boost file system is described with an example
- Recursive directory Iterator is used for manipulating files in a directory
- Directory iterators can be passed to STL algorithms
- Portable way of dealing with files
Advanced STL 6: Generic Pretty Printer for STL Containers
- A pretty printer for STL containers is built using template meta programming techniques.
- Vectors, sets, maps and tuples are supported.
- Nested lists can be easily printed.
- Learn how to write code that will target pretty printing of specific data structures.
- Jump to 40:40 if you just want to see how to use the pretty printer.
- pretty_printer.cpp can be downloaded from here.