Share

C++ Standard Template Library - Video Tutorials

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

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.

Explore More