STL Tutorials

Microsoft's Stephan T. Lavavej (STL) introduces the Standard Template Library (also STL).

  1. Containers, Iterators and Algorithms
  2. Associative Containers
  3. Smart Pointers - unique_ptr and shared_ptr
  4. Detailed STL Example - Nurikabe Solver
  5. Algorithms and Functors
  6. Algorithms and Sorting
  7. Regular Expressions in C++ 11
  8. RValue References in C++ 11
  9. Type Traits for Template Meta Programming

STL advanced topics:

  1. shared_ptr internals
  2. Template Meta Programming
  3. STL Validation in Debug Mode
  4. More about Rvalue References
  5. An Introduction to Boost Libraries
  6. 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 overriden "()"
      • 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 lamdba expressions with STL. The C++ 11 lamdba syntax is explained.
  • Modifying/Mutating algirithms
    • 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.

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 consturct 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 inserted.
    • 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 <numeric>
    • 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)
  • 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
  • regex_replace
    • 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 regular expression.
    • sregex_iterator for regular strings
    • wregex_iterator for unicode strings
  • regex_token_iterator: Use to generate tokens from a string
  • Notes:
    • 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 = MethodReturingValue() results in:
      • a copy constructor creating an object on return from MethodReturningValue()
      • Another copy constructor is called for the assignment
  • C++ 11 defines a move constructor so that this double copy can be avoided.
    • 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)
  • 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 allocated memory
    • 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 passed
      • 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)
    • /dlreportSingleClassLayout<ClassName>
  • 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 for temporaries.
    • 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.