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 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

Watch STL 1 of n on Microsoft Learn

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

Watch STL 2 of n on Microsoft Learn

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.

Watch STL 3 of n on Microsoft Learn

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.

Watch STL 4 of n on Microsoft Learn

Watch STL 5 of n on Microsoft Learn

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.

Watch STL 6 of n on Microsoft Learn

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_inserter
• 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 first 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
• minmax 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.

Watch STL 7 of n on Microsoft Learn

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 C strings (const char*)
  • 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.

Watch STL 8 of n on Microsoft Learn

STL 9: Rvalue References in C++ 11

• L-values are named objects. R-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
• 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.

Watch STL 9 of n on Microsoft Learn

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_floating_point: 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.

Watch STL 10 of 10 on Microsoft Learn