C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 7 of n

Sign in to queue

Description

Welcome to another installment of C9 Lectures covering the powerful general C++ library, STL. Joining us once again is the great Stephan T. Lavavej, Microsoft's keeper of the STL cloth (this means he manages the partnership between the owners of STL (dinkumware) and Microsoft, including, of course, bug fixes and enhancements to the STL that ships as part of Visual C++). Simply, Stephan is a C++ library developer.

As is Stephan's nature, he elaborates on technical details in very substantive way. The Standard Template Library, orSTL, is a C++ library of container classes, algorithms, and iterators. STL provides many fundamental algorithms and data structures. Furthermore, the STL is a general-purpose library: its components are heavily parameterized, such that almost every component in the STL is a template.

In part 7, Stephan continues to dig into STL algorithms, specifically insert iterators, sorting and related functions.

Enjoy! Learn!

Books mentioned by Stephen:

The C++ Standard Library: A Tutorial And Reference by Nicolai M. Josuttis
Effective STL by Scott Meyers

[STL Introduction lecture links]

Part 1 (sequence containers)

Part 2 (associative containers)

Part 3 (smart pointers)

Part 4 (Nurikabe solver) - see Wikipedia's article and Stephan's updated source code

Part 5 (Nurikabe solver, continued)

Part 6 (algorithms and functors)

Part 7 (algorithms and functors, continued)

Part 8 (regular expressions)

Part 9 (rvalue references)

Part 10 (type traits)

Embed

Download

Download this episode

More episodes in this series

Related episodes

The Discussion

  • User profile image
    Adam​Speight2008

    Why does the MinMax function have that complexity?

    FUNCTION: MinMax( seq, comparer_lessthan) --> pair(,)
    _min = seq.begin
    _max = seq.begin
    for each element in seq
    if comparer_lessthan(element, _min) then _min=element
    if comparer_lessthan(_max,element) then _max=element
    next
    return new pair(_min,_max)

    O(n)

     

    or if the STL would let you do

    FUNCTION: MinMax( seq, comparer_lessthan) --> pair(,)
    _min = LB(seq.begin,seq.end)
    _max = _min + UB(_min.begin, seq.end)
    return new pair(_min,_max)

    Best Case: O(log n)  ' both are the last element.

    Worst Case: O(2 log n) ' first and last elements.

    Average Case: 0( (2 log n) / 3)

    If I've missed something in the algorithms implementation, could you point be to a source (as I would be interesting in look at it.) 

  • User profile image
    NotFredSafe

    Because binary search only works on sorted ranges? Wink

  • User profile image
    STL

    minmax_element() has O(N) asymptotic complexity, but it provides an exact complexity guarantee that's even better. Your first implementation performs 2N comparisons. The STL performs at most 1.5N comparisons. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf 25.4.7 [alg.min.max]/36.

    As for your second implementation, lower_bound() and upper_bound() require sorted sequences, while minmax_element() accepts arbitrary sequences. Finding the minimum and maximum of a sorted sequence can be done in O(1) time. :->

  • User profile image
    NotFredSafe

    Stephan, at 6:39 you write *it++ = elem. I wonder if this code is indeed well-defined for output iterators and opened a question on stack overflow. Could you comment on this issue? Thanks!

  • User profile image
    Adam​Speight2008

    I made slight booboo in the algorithm I forgot to add the element you are looking for.

    Can't get link to work, Timestamp 33m00

    The section where you are on about the lower and upper bounds of a group of elements (equal to the value you're looking for) in a sorted sequence y.

    Not the lowest and highest values.

    FUNCTION: MinMax( seq, comparer_lessthan, value) --> pair(,)
    _min = LB(seq.begin,seq.end,value)
    _max = _min + UB(_min.begin, seq.end,value)
    return new pair(_min,_max)

  • User profile image
    STL

    That's straight out of the Output Iterator requirements. N3126 24.2.4 [output.iterators] Table 105 "Output iterator requirements (in addition to Iterator)" contains "*r++ = o".

  • User profile image
    STL

    AdamSpeight2008: You're thinking of equal_range(), which is required to behave as if it returns make_pair(lower_bound(first, last, value), upper_bound(first, last, value)), and is required to perform at most 2 * log2(last - first) + O(1) comparisons (N3126 25.4.3.3 [equal.range]/2-3).

    STL implementations are permitted to perform fewer comparisons, and ours does.

  • User profile image
    Adam​Speight2008

    Ah! I see where the _min iterator would be affected, so let's say a copy is passed to UB.

    Let see if I've got this right minmax_element returns the smallest and largest element from an underordered sequece? 

     

  • User profile image
    Adam​Speight2008

    I found out hows it is implemented,

  • User profile image
    STL

    Here's an example:

    C:\Temp>type meow.cpp
    #include <algorithm>
    #include <array>
    #include <iostream>
    #include <iterator>
    #include <ostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    template <typename FwdIt> void print_minmax(FwdIt first, FwdIt last) {
        const auto p = minmax_element(first, last);
    
        cout << "Minimum element (" << *p.first << ") found at index " << distance(first, p.first) << endl;
        cout << "Maximum element (" << *p.second << ") found at index " << distance(first, p.second) << endl;
    }
    
    template <typename FwdIt, typename Comp> void print_minmax(FwdIt first, FwdIt last, Comp comp) {
        const auto p = minmax_element(first, last, comp);
    
        cout << "Minimum element (" << *p.first << ") found at index " << distance(first, p.first) << endl;
        cout << "Maximum element (" << *p.second << ") found at index " << distance(first, p.second) << endl;
    }
    
    int main() {
        const array<int, 25> a = {
            83, 79, 13, 17, 53, 59, 29, 2, 37, 11, 47, 97, 19, 31, 5, 43, 41, 89, 73, 7, 3, 23, 67, 61, 71 };
    
        print_minmax(a.begin(), a.end());
    
        vector<string> v;
        v.push_back("The Eye of the World");
        v.push_back("The Great Hunt");
        v.push_back("The Dragon Reborn");
        v.push_back("The Shadow Rising");
        v.push_back("The Fires of Heaven");
        v.push_back("Lord of Chaos");
        v.push_back("A Crown of Swords");
        v.push_back("The Path of Daggers");
        v.push_back("Winter's Heart");
        v.push_back("Crossroads of Twilight");
        v.push_back("Knife of Dreams");
        v.push_back("The Gathering Storm");
        v.push_back("Towers of Midnight");
        v.push_back("A Memory of Light");
    
        print_minmax(v.cbegin(), v.cend(), [](const string& l, const string& r) { return l.size() < r.size(); });
    }
    
    C:\Temp>cl /EHsc /nologo /W4 meow.cpp
    meow.cpp
    
    C:\Temp>meow
    Minimum element (2) found at index 7
    Maximum element (97) found at index 11
    Minimum element (Lord of Chaos) found at index 5
    Maximum element (Crossroads of Twilight) found at index 9

  • User profile image
    Spetum

    Just thank you, STL

  • User profile image
    Garp

    Same here :)
     
    Stephan, are you going to tell us everything about functors in a next episode?

  • User profile image
    STL

    There's always more to tell. I'm getting close to exhausting the simple topics, so it's probably time to begin introducing C++0x features. Lambdas (which I've shown a little), perfect forwarding, and perfect returning are all relevant to functors.

    Is there anything else that people want to see?

  • User profile image
    Mr Crash

    @STL:

    Good interesting stuff as always  Smiley


    > Is there anything else that people want to see?

    1. perhaps a how to and how not to write ex a base64 encoder/decoder that interacts with the stl streams 

    2. (perhaps this is more of a question) when to use lambdas and when to use bind, bind2nd, mem_fn.

    i've read that lambdas can replace these functions but when should you use functions like bind, bind2nd,mem_fn. instead of lambdas ?

    3. Talk more about common mistakes / gotchas

    4. How to optimize the usage of STL, ex making sure you use the right container/algorithm for the right job, etc..

    5. How not to use the STL, guess this is the same as 3.

    6. How to add new features / functionality to complement the STL.. ( connected with 1. )

     

    How about that ?  Wink  Smiley

     

     

  • User profile image
    Heavens​Revenge

    At least the need for manual loops has almost been completely eliminated Tongue Out.

    int main (int argc, char *argv[])
    {    
        unsigned int fact = 0;
        cout << endl << "What factorial do you want to calculate?  ";
        cin >> fact;    
        vector <unsigned int> vec(fact);
        iota (vec.begin(), vec.end(), 1);
        cout << endl;
        cout << "Factorial is: " << accumulate (vec.begin(), vec.end(), 1, multiplies<unsigned int>() );
        cout << endl;
        return 0;
    }

    I've been spraining my brain recently with how to implement Shear-sort, its absolutely cool,entertaining and fast.  Shell & Radix soort used to be my favs, but now its shearsort.  Have a look at it, you also may find it fairly entertaining.

  • User profile image
    Spetum

    @STL: I/O handle, Socket, file Processing in the STL(Standard Template Library)..

    But I'd like to close and learn to the "vector, string" and Lambda expression for char* processing.

    As well, furthermore , Stephan tries to emphasize that "C++(STL) is more effective and efficient than other languages." just my hope or wish..

    Thank you for your lectures.

  • User profile image
    Deraynger

    @STL: Template metaprogramming, as mentioned in the previous Video comments (you answered that it might be in part 8 Tongue Out)

  • User profile image
    geeyef

    @STL: Thanks for another great lecture.

    > Is there anything else that people want to see?

    Aside from what you've just mentioned, I'd like clarification on using r-value reference.  MSDN help doesn't really show how to use it effectively, just syntactically.

  • User profile image
    STL

    Thanks for the suggestions!

    [Mr Crash]
    > when to use lambdas and when to use bind, bind2nd, mem_fn.
    > i've read that lambdas can replace these functions but when should you use functions like bind, bind2nd,mem_fn. instead of lambdas ?

    bind() supersedes bind1st() and bind2nd().
    mem_fn() supersedes mem_fun() and mem_fun_ref().

    But lambdas supersede all of them. Lambdas are easier to read, easier to write, and more efficient. In the few cases where lambdas aren't sufficient, you should use handwritten functors. (One case is a map's comparator, where you want an easily named and default-constructible type. Other cases include templated or recursive functors.)

    [HeavensRevenge]
    > Shell & Radix soort used to be my favs, but now its shearsort.

    My favorite special-purpose sort uses a suffix tree to sort the suffixes of a string. A string of length N has N suffixes ("meow" has the suffixes "meow", "eow", "ow", and "w"; one convention is to count the whole string, but not the empty string, as a suffix). Using a general-purpose sort takes O(N^2 log(N^2)) = O(2 * N^2 log(N)) = O(N^2 log(N)), which is slower than quadratic. (It would perform N log N comparisons, but each comparison takes O(N) time in the worst case; consider the string "aaaaaaaab".) Suffix trees take O(N) time. That's not a typo, it really is linear time.

  • User profile image
    WalderFrey

    @STL:
    "Is there anything else that people want to see?"
    Wide character support, e.g. wstring, wofstream etc.
    Locales

  • User profile image
    Heavens​Revenge

    For general purpose, I believe the complexity of shearsort is something like O(n^1/2 (log n)) or equivalent to: Shearsort Im glad my tablet functionality comes in handy every once in a while Tongue Out

    But I AM quite pleased to have heard you mention that your STL implements an IntroSort Smiley its pretty awesome since SGI's STL implementation has IntroSort as the default too.

    This URL is awesome since you can customize, this is how I compare sorts haha, when their bad implementation doesn't bug out of course Tongue Out

    http://home.westman.wave.ca/~rhenry/sort/duel.php?width=600&height=1000&alg1=ShearSort&alg2=IntroSort

    I made it be around screen width(each 600 wide), both sorts using 1000 entries to sort, Comparing side-by-side my new fav Shearsort with the also impressive IntroSort. The bigger N, the better Shearsort can do, since its complexity stays way down,  and is excellently-parallel n-way per "shear".

  • User profile image
    STL

    [WalderFrey]
    > Wide character support, e.g. wstring, wofstream etc. Locales

    Unfortunately, that's a complicated topic, I'm not an expert there (I know stuff, but I like to teach things only when I'm an expert), and iostreams/locales aren't part of the STL proper (string is a borderline case). So I don't think I'll be covering Unicode in this series.

    [HeavensRevenge]
    > For general purpose, I believe the complexity of shearsort is something like O(n^1/2 (log n))

    The best that a serial general-purpose sort can do is O(N log N). That's a theorem that CS students prove in Algorithms 101. std::sort() is now required by C++0x to be worst-case O(N log N). In C++98/03, it was permitted to be average O(N log N), worst-case O(N^2), i.e. the behavior of a plain quicksort.

    The STL currently doesn't contain parallel algorithms. I've asked for parallel_sort() from the Concurrency Runtime team, but haven't gotten it yet. :->

  • User profile image
    Michael Hamilton

    Recursive lambdas don't actually look so bad:
    std::function<int(int)> factorial = [&factorial](int n) -> int {      return n <= 1 ? 1 : n * factorial(n-1);};
    std::cout << factorial(4);
    They do not work with "auto" however... And you couldn't just slap this inside an algorithm as you need to define a variable, and if you're doing that anyway you may as well just be making a named functor for it.
    Source: http://cottonvibes.blogspot.com/2010/07/c0x-autos-lambdas-and-lambda-recursion.html
     

  • User profile image
    blah

    I would've much rather seen the standard library draft text on the monitor rather than your wm7 advertisement.

  • User profile image
    STL

    If you watch carefully, near the end of the video, I accidentally brushed the TV's capacitive buttons with my arm, switching its input from my laptop (which has a background of the Carina Nebula) to one of the studio's computers (which has the background that you saw). I didn't even notice that this had happened until after I had finished recording the video, as my right eye is blind.

  • User profile image
    Deraynger

    Didn't even realize that it was a mistake nor did I realize that your right eye is blind.

    ...impatiently waiting for your next video! Keep up these awesome videos!

  • User profile image
    NotFredSafe

    ...impatiently waiting for your next video! Keep up these awesome videos!

    Seconded!

  • User profile image
    STL

    On Friday (Nov 5), I filmed Part 8 (regex) and Part 9 (rvalue references). They'll be coming your way soon!

  • User profile image
    Deraynger

    @STL: Cool, that's great!

  • User profile image
    Sam

    @STL: > Is there anything else that people want to see?How about making a simple yet extensible calculator using STLi think a lot the STL will come in handy.
    What do you think about that suggestion ?
    Keep the videos coming, please :)

  • User profile image
    Garp

    Starting to feel the effects of withdrawal and it ain't pretty!

  • User profile image
    NotFredSafe

    , Garp wrote

    Starting to feel the effects of withdrawal and it ain't pretty!

     

    Agreed, I need my STL fix now!

  • User profile image
    Deraynger

    10 days later, still no video Sad

  • User profile image
    NotFredSafe

    , Deraynger wrote

    10 days later, still no video Sad

    Oh well, the joy of anticipation... Wink

  • User profile image
    Deraynger

    , NotFredSafe wrote

    *snip*

    Oh well, the joy of anticipation... Wink

    Yes, except that the joy could be in anticipation for the 9th Video, after having watched the 8th video Smiley

  • User profile image
    NotFredSafe

    Oh Stephan, where art thou?

  • User profile image
    STL

Comments closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to send us feedback you can Contact Us.