Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

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

Download

Right click “Save as…”

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, or STL, 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 3, Stephan focuses on shared_ptr and unique_ptr. You will also learn a bit about exception safety and, of course, get another challenging homework assignment. 

Part 1
Part 2

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)

Tags:

Follow the Discussion

  • Its been a while since I've commented on C9. I must say that I'm loving these STL videos by STL.

    I've got numerous books on C++ including C++ Cookbook with numerous boost recipies.

    One interest of mine is Graphs. This will definatly make programming in C++ sooo much easier.

  • CharlesCharles Welcome Change

    Thanks for posting again! We're glad you like this series. You will see more STL by STL. Also, you will see much more C++ content in the coming months - the language and tooling continue to evolve and Microsoft mind and muscle are firmly behind helping to push the native stack forward.

     

    C

  • Been a long time since I've posted here too Smiley  STL, I'm curious if you know why unique_ptr has array new/delete support but shared_ptr doesn't?

     

    And a slight correction: having the same initialism is fun, but shared_ptr etc. were not added to SGI's Standard Template Library, but to the C++ Standard Library.

  • Shame we couldnt see the code as you were talking us through it. Couldnt make it out on the screen behind you.

  • lol post the code for the homework in the comments? This one might get quite long.

  • @Stephan T. Lavavej: Pls post the code. During your talk, which was amazing btw, the code was only displayed in the backgroud screen. Thanks!

  • Interesting video as well.

     

    +1 on the request of posting code.

     

    And comparing the ref-counted deterministic resource management offered by shared_ptr vs. garbage-collector systems, are the performance of ref-counted systems better than those offered by GC?

    I found this article in which there is a detailed comparison of resource management techniques, and in the "Performance" paragraph it seems to show that a tracing GC can offer better performance than a ref-counted system:

     

    Resource management

    http://blogs.msdn.com/b/brada/archive/2005/02/11/371015.aspx

     

    And, as a side question: does it exist a tracing garbage collector for C++? The language is so powerful that I think it could be possible to write one. So people could still enjoy the advantages of C++ (e.g. portability on different platforms, not requiring download and installation of .NET framework, not wasting time for just-in-time compilation of code, etc.) and don't pay too much attention to memory allocation, cleanup, cycles, etc.

     

    Thanks, and looking forward for the next STL video.

     

  • CharlesCharles Welcome Change

    Sorry about that. There was a minor glitch in the production process and we have corrected this. Updated version with code-on-screen is being processed now.

    C

  • It is good to hear that C++ isn't dead at MS yet.  The impression one tends to get just by viewing C9 is that if you aren't developing in WPF/Silverlight/XNA or other .Net technology, you might as well develop for other OSs.  Enjoying this series.  It has been a way to get my coworkers to learn about and use STL where appropriate.  Many of them are old-school C programmers who picked up C++/MFC as needed, but never really carried through with it as it has progressed.  Thanks again.

  • CharlesCharles Welcome Change

    Really? http://channel9.msdn.com/tags/C++/

     

    C++ is not only not dying, but MS is pumping up the volume of the technology, from compilers to language and libraries and of course IDE enhancements and debuggers and builders (and linkers and....). This will become more obvious in the coming months. Bookmark the above tag...

     

    C

  • CharlesCharles Welcome Change

    The screencaptures are now in place inside the video. Again, sorry for the inconvenience. Please watch this again to see his code up close and personal. Smiley

     

    Stephan, you simply rock, man.

    C

  • Thanks, we can now clearly read the code.

     

    I would have used simple C++ overload... but the template metaprogramming technique presented by STL is very cool!

    May some other lesson be dedicated to the template metaprogramming subject?

    Thanks.

     

  • STLSTL

    Let's see if I can post a 5 KB comment.

     

    Here's the solution that I presented, slightly modified (I renamed a template parameter), and with test cases:


    C:\Temp>type meow.cpp
    #include <algorithm>
    #include <deque>
    #include <forward_list>
    #include <list>
    #include <map>
    #include <set>
    #include <unordered_map>
    #include <unordered_set>
    #include <vector>

    namespace meow {
        namespace detail {
            struct vectorlike_tag { };
            struct listlike_tag { };
            struct associative_tag { };

            template <typename C> struct container_traits;


            template <typename T, typename A>
                struct container_traits<std::vector<T, A>> {
                typedef vectorlike_tag category;
            };

            template <typename T, typename A>
                struct container_traits<std::deque<T, A>> {
                typedef vectorlike_tag category;
            };


            template <typename T, typename A>
                struct container_traits<std::list<T, A>> {
                typedef listlike_tag category;
            };

            template <typename T, typename A>
                struct container_traits<std::forward_list<T, A>> {
                typedef listlike_tag category;
            };


            template <typename T, typename C, typename A>
                struct container_traits<std::set<T, C, A>> {
                typedef associative_tag category;
            };

            template <typename T, typename C, typename A>
                struct container_traits<std::multiset<T, C, A>> {
                typedef associative_tag category;
            };

            template <typename T, typename C, typename A>
                struct container_traits<std::unordered_set<T, C, A>> {
                typedef associative_tag category;
            };

            template <typename T, typename C, typename A>
                struct container_traits<std::unordered_multiset<T, C, A>> {
                typedef associative_tag category;
            };

            template <typename K, typename V, typename C, typename A>
                struct container_traits<std::map<K, V, C, A>> {
                typedef associative_tag category;
            };

            template <typename K, typename V, typename C, typename A>
                struct container_traits<std::multimap<K, V, C, A>> {
                typedef associative_tag category;
            };

            template <typename K, typename V, typename C, typename A>
                struct container_traits<std::unordered_map<K, V, C, A>> {
                typedef associative_tag category;
            };

            template <typename K, typename V, typename C, typename A>
                struct container_traits<std::unordered_multimap<K, V, C, A>> {
                typedef associative_tag category;
            };


            template <typename Container, typename X>
                void erase_helper(Container& c, const X& x, vectorlike_tag) {

                c.erase(std::remove(c.begin(), c.end(), x), c.end());
            }

            template <typename Container, typename Predicate>
                void erase_if_helper(Container& c, Predicate p, vectorlike_tag) {

                c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
            }


            template <typename Container, typename X>
                void erase_helper(Container& c, const X& x, listlike_tag) {

                c.remove(x);
            }

            template <typename Container, typename Predicate>
                void erase_if_helper(Container& c, Predicate p, listlike_tag) {

                c.remove_if(p);
            }


            template <typename Container, typename X>
                void erase_helper(Container& c, const X& x, associative_tag) {

                c.erase(x);
            }

            template <typename Container, typename Predicate>
                void erase_if_helper(Container& c, Predicate p, associative_tag) {

                for (auto i = c.begin(); i != c.end(); ) {
                    if (p(*i)) {
                        c.erase(i++);
                    } else {
                        ++i;
                    }
                }
            }
        }

        template <typename Container, typename X> void erase(Container& c, const X& x) {
            detail::erase_helper(c, x, typename detail::container_traits<Container>::category());
        }

        template <typename Container, typename Predicate> void erase_if(Container& c, Predicate p) {
            detail::erase_if_helper(c, p, typename detail::container_traits<Container>::category());
        }
    }

    #include <iostream>
    #include <numeric>
    #include <ostream>
    using namespace std;
    using namespace meow;

    template <typename Container> void print(const Container& c) {
        for (auto i = c.begin(); i != c.end(); ++i) {
            cout << *i << " ";
        }

        cout << endl;
    }

    int main() {
        vector<int> v(7);

        iota(v.begin(), v.end(), 1);
        print(v);
        for_each(v.begin(), v.end(), [](int& n) { n *= 11; });
        print(v);

        cout << "--" << endl;

        list<int> l(v.begin(), v.end());
        set<int> s(v.begin(), v.end());

        erase(v, 44);
        print(v);
        erase_if(v, [](int n) { return n % 2 == 0; });
        print(v);

        cout << "--" << endl;

        erase(l, 33);
        print(l);
        erase_if(l, [](int n) { return n % 2 != 0; });
        print(l);

        cout << "--" << endl;

        erase(s, 22);
        print(s);
        erase_if(s, [](int n) { return n > 40 && n < 70; });
        print(s);
    }

    C:\Temp>cl /EHsc /nologo /W4 meow.cpp
    meow.cpp

    C:\Temp>meow
    1 2 3 4 5 6 7
    11 22 33 44 55 66 77
    --
    11 22 33 55 66 77
    11 33 55 77
    --
    11 22 44 55 66 77
    22 44 66
    --
    11 33 44 55 66 77
    11 33 77

  • shared_ptr is heavier than a GC, but most things don't need to be manually allocated or shared so you should be using it so little that it doesn't matter.

     

    I don't think it would be easy for a C++ GC to reach the performance of the .NET GC, because .NET is so much stricter about what you can do with an object, ie. there's nothing stopping me from holding a pointer to a member of an object and using an offset to compute the actual object's address.  I believe the .NET GC also defragments the heap, seems unlikely with C++.

  • STLSTL

    [Tominator2005]
    > One interest of mine is Graphs. This will definatly make programming in C++ sooo much easier.

    Check out the Boost Graph Library: http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/table_of_contents.html

    There's a whole book about it too.

    [PhrostByte]
    > STL, I'm curious if you know why unique_ptr has array new/delete support but shared_ptr doesn't?

    I'm not exactly sure. (I'm on the Standardization Committee's mailing lists, but I haven't attended their meetings.) There was some discussion of defining shared_ptr<T[]>, but it appeared to have been rejected as too controversial with insufficient implementation experience. The strongest argument against it was that specializations should behave like the primary template (vector<bool> being an obvious offender), but shared_ptr<T[]> would actually be significantly different (it would have to prohibit derived-to-base conversions, for example). Given that, it should be differently named instead of being a specialization. boost::shared_array exists, but was not incorporated into TR1/C++0x.

    The biggest mystery to me is actually why unique_ptr<T[]> was retained, given the controversy with shared_ptr. There could be a rationale there, or it could be an oversight. (If there's a rationale, I'd guess that it's because unique_ptr is zero overhead, so providing an array form could be useful to someone who needs a dynamically allocated array with a runtime length (std::array has a compiletime length), needs exception safety (owning raw pointers lead to leaktrocity), and doesn't need the flexibility and doesn't want to pay the minor costs of std::vector (which is at least as large as three pointers). On the other hand, shared_ptr has overhead (minor, but nonzero). It is difficult for me to imagine a scenario in which shared_ptr<vector<T>> is unacceptable, but shared_array would be acceptable.)

    > And a slight correction: having the same initialism is fun, but shared_ptr etc. were not added to SGI's Standard Template Library, but to the C++ Standard Library.

    Like most people, I use "STL" to refer to "the parts of the C++ Standard Library that were derived from or strongly influenced by Stepanov's original work". This usage doesn't lead to confusion. In that interpretation, shared_ptr is very clearly part of the STL, while iostreams are not (and for std::string, flip a coin).

    [Sys64738]
    > And comparing the ref-counted deterministic resource management
    > offered by shared_ptr vs. garbage-collector systems, are the
    > performance of ref-counted systems better than those offered by GC?

    There's a major difference between universal refcounting and shared_ptr's refcounting. The vast majority of resources in a C++ program won't be managed by refcounting. For example, vector maintains no reference count. Its destructor simply deallocates its memory (and any owned by its elements, recursively). Thanks to C++'s deterministic destruction, the compiler knows when to destroy vectors on the stack. A local vector's lifetime is known at compiletime, so tracking it is O(0). shared_ptr uses reference counting to track the lifetimes of dynamically allocated objects, but it's certainly not the case that everything in a C++ program is held by shared_ptr.

    The other major difference between C++'s resource management system and GC is that C++'s system is resource-agnostic, while GC isn't. C++ destructors don't care what they're destroying, and can be used to manage memory, files, sockets, locks, textures, fonts, HWNDs, whatever equally. They don't care whether they're being invoked for local objects or dynamically allocated objects (vector elements, shared_ptr-owned objects, etc.) either. In contrast, non-deterministic GC handles memory much better than non-memory resources. *Usually*, nobody will notice if you hang onto memory for longer than absolutely necessary. Hanging onto non-memory resources for longer than necessary is a big deal, though. Keeping a file open, holding onto a texture (in video memory!), etc. could have observable and undesirable effects. (And "finalizers" are an incomprehensible nightmare.)

    > And, as a side question: does it exist a tracing garbage collector for C++?

    As I'm strongly opposed to universal GC, I'm about the furthest thing from an expert here, but the http://en.wikipedia.org/wiki/Boehm_garbage_collector is well known.

    > and don't pay too much attention to memory allocation, cleanup, cycles, etc.

    One of the goals of my videos is to demonstrate that C++ (uniquely!) can be used to write code that doesn't concern itself with the details of resource management, without falling into the tar pit that is universal GC. In fact, in Part 3 I drew big NO signs around new/delete and new[]/delete[].

    > I would have used simple C++ overload... but the template metaprogramming technique presented by STL is very cool!

    As I mentioned, I was concerned that the template metaprogramming here consumed more effort than it saved, but I figured I'd demonstrate it anyways. (The N=2 of vector/deque and list/forward_list is really the worst case for simplifying code. When N=lots, as with (unordered_)?(multi)?(map|set), the savings are clearer.)

    > May some other lesson be dedicated to the template metaprogramming subject?

    Template metaprogramming is relatively advanced, but I might use it in future installments.

    (In an "Inside the STL" series, template metaprogramming would feature prominently, as it powers most of our ingenious tricks.)

    PhrostByte: Yes, my reaction is very much "if you want .NET, you know where to find it".

  • Hi Charles and Stephan,

    I would like to recommend another excellent book for template metaprogramming, it is Modern C++ Design.

  • Another fantastic video. So now it's official - Stephan is a frickin' rock star.

     

    Think about it. Three great videos - that's three more than Bon Jovi!

  • Couldn't you've used the container traits defined in the std:: containers, instead of creating your own traits, to find out the type of container? I remember something about traits in Effective C++, but am not exactly sure anymore.

  • STLSTL

    There aren't any container traits. Perhaps you're thinking of std::iterator_traits. In this case, iterator traits are not applicable, because both std::list and std::set have bidirectional iterators, but they have different erasure patterns.

    (Nice Dopefish avatar!)

  • I love these lectures, however exercise code at the beginning felt a bit disconnected from the topic. Too much too fast, especially when I only have basic grasp of templating (like, generics in C#). Otherwise, I want more Smiley

  • Ok, you're right, they're std::iterator_traits. Never really used templates etc., just basic containers/iterators without any fancy things.

    Thanks for the info on that.

     

    The Dopefish Lives! Tongue Out

  • STLSTL

    About Part 3's homework problem: my Nurikabe solver currently solves Wikipedia's "moderately difficult" 10x9 example in 128 ms (on my Q9450). See if you can do better!

  • I had a question on your implementation of the homework assignment from part 2. When you used your container_traits classes was there a particular reason why you didn't just create an additional set of specialized classes to implement the specialized erase methods? Was it just for simplicity of demonstration or is there a technical reason? I would think eliminating the need for the ignored argument would ultimately be a better solution since you wouldn't have to hope for an optimization by the compiler.

     

    Something like this:

    namespace meow
    {
      namespace detail
      {
        struct vectorlike_tag {};
        struct listlike_tag {};
        struct associative_tag {};

        template <typename C> struct container_traits;

        template<typename T,typename A> struct container_traits<std::vector<T,A>>
        {
          typedef vectorlike_tag category;
        };

        template<typename T,typename A> struct container_traits<std::deque<T,A>>
        {
          typedef vectorlike_tag category;
        };

        template<typename T,typename A> struct container_traits<std::list<T,A>>
        {
          typedef listlike_tag category;
        };

        template<typename T,typename C, typename A> struct container_traits<std::set<T,C,A>>
        {
          typedef associative_tag category;
        };

        template<typename C> struct erase_helper;

        template<> struct erase_helper<vectorlike_tag>
        {
          template<typename Container, typename X>
          static void erase( Container& c, const X& x )
          {
            c.erase( std::remove(c.begin(), c.end(), x), c.end() );
          }
        };

        template<> struct erase_helper<listlike_tag>
        {
          template<typename Container, typename X>
          static void erase( Container& c, const X& x )
          {
            c.remove(x);
          }
        };

        template<> struct erase_helper<associative_tag>
        {
          template<typename Container, typename X>
          static void erase( Container& c, const X& x )
          {
            c.erase(x);
          }
        };
      }

      template <typename Container, typename X> void erase( Container& c, const X& x )
      {
        detail::erase_helper< typename detail::container_traits<Container>::category >::erase(
          c, x );
      }
    }

  • STLSTL

    That's equivalent, but it's basically the same amount of code.  (When there are two equivalent ways of saying something, I'll usually choose the shorter one.)  I actually used to use static member functions of explicitly/partially specialized classes before I began maintaining the STL, where Dinkumware's convention is to use overload resolution.  If you like using specializations, go for it!

     

    Note that because the helpers will be inlined, the compiler will easily be able to optimize out nameless empty arguments.  It's okay to assume a basic level of competency on the optimizer's part.

  • I'm trying to use unique_ptr but have run into a snag.  When I declare a unique_ptr in a container in a class that is exported I get an error:

    using namespace std;

     
    class
     __declspecdllexport ) T
    {
    public:

        //unique_ptr<int> i;
        vector<unique_ptr<int>> v;
    };

     

    The error is as follows:

      error C2248: 'std::unique_ptr<_Ty>::operator =' :
    cannot access private member declared in class 'std::unique_ptr<_Ty>'

    Oddly enough, if add in the line that is currently commented out the error goes away.

     

    fyi, I'm also getting a warning that vector and unique_ptr need to have dll-interface to be used by clients, but I don't think that's a probelm since my clients will be linking with STL anyway:

    warning C4251: 'T::v' : class 'std::unique_ptr<_Ty>'
    needs to have dll-interface to be used by clients of class 'T'
  • STLSTL

    I just finished filming Parts 4 and 5! They'll be making their way to you soon.

     

    geeyef: When you dllexport T, the compiler has to generate its copy constructor and copy assignment operator immediately, because whoever's linking against your DLL might want to copy construct or copy assign T.  This is different from how C++ ordinarily works, where the copy constructor and copy assignment operator will only be generated when you attempt to use them for the first time.

     

    vector<unique_ptr<int>> isn't copy constructible or copy assignable, because that would require copying its elements, which are non-copyable (but movable).  Therefore, compilation fails.  The compiler errors are saying this, but as usual they're hard to understand if you're not an expert (and the compiler doesn't talk about the ultimate reason involving dllexport).

     

    When you add a unique_ptr<int> data member, its copy ctor/copy assign are private and unimplemented.  The compiler sees that they're private, and does not attempt to generate T's copy ctor/copy assign.  vector<stuff> has a public copy ctor/copy assign, so when it's the only data member, the compiler behaves differently (it's only when it tries to instantiate the copy ctor/copy assign that compilation explodes).

     

    With vector<unique_ptr<int>> as the only data member, you can add this to make it compile:

     

    private:
        T(const T&);
        T& operator=(const T&);
    };

    That will prevent the compiler from attempting to generate a copy ctor/copy assign which will explode.

     

    C4251 is essentially ignorable here.  You should be aware that using the STL in your DLL's interface (as opposed to just its implementation) forces you to play by the STL's rules - in particular, mixing major versions is forbidden.  You can't compile such a DLL with VC10 and have somebody compiling with VC9 or VC11 link against it, because the STL intentionally breaks binary compatibility between major versions.

  • Matt HouserMatt Houser

    Loved the video.
    During unique_ptr, you mention that copy ctr is private, but returning from a function will work.  I'm wondering if you could briefly explain the C++ mastery that's used to accomplish this.
    Thanks,
    ...Matt

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    The problem with a shared pointer to a vector is that you have to dereference twice to get at the data, so what is really needed is a form of a vector featuring shared storage and reference counting; I would say not having this is an oversight.

    My question at Installment 1 got drowned together with my comment it was in, and I would really like to know: STL is optimised for time, do you know a library optimised for space?  I mean, get along with virtual functions but do not create the M*N*X implementations effect.

    As a related thought about safe destruction, observe that there is no object in the STL to safely hold a standard message catalogue.

    Thanks,
    Chris

  • Stephan,

    Great series.  These lectures are not only informative but the energy you show really has me delving into the STL.  Being as though this is very new to me I have a request.  In your example above (part of homework part 2) could you add/supply an example of how to use the erase_if for an associative container (preferably map).  Having difficulty getting the predicate correct.

    Thanks,

    Mike

  • asefaasefa

    it is more better,add some more information.

  • jkjk

    You ought to rename from C9LecturesLavavejSTLp3Capture_2MB_ch9 to C9LecturesSTLLavavejP3_2MB_ch9 - helps keeps the lectures sorted offline :D

  • RahulRahul

    Amazing conceptual presentation.

  • RahulRahul

    unique_ptr is non copy-constructor. same object stoed in memory cant be reference by more than one pointer. therefore lets say.
    unique_ptr <int> u (new (11));
    unique_ptr <int> u1 (u) ; // throws an error.

    so, to eliminate this exception, helper function move() taken into account for unique_ptr. But this may be highly expensive [consumes much CPU cycles] due to moving the entire elements [or chunk of memory] from one refernce pointer ot another.

    However, shared_ptr can support copy constructor.

    But is there any way to reference a memory object by a new pointer rather than moving the whole array from one pointer reference to new one. ?

    Thank you very much for your spotlight.
    Really, Mr. Stephane i am a very big fan of yours...
    Hats off to an amazing and interesting coneptual facts.
    Thank you once again...

    Regards,
    Rahul

  • JavierJavier

    Stephan,

    A couple of comments:
    (1) The erase_helper for vector-like containers does not return the iterator to the removed elements, which would allow to perform additional cleanup--like deleting objects, etc.

    (2) I did not see std::array, which could be considered a pseudo-container.

    Regards,

    Javier.

  • Stephan,

    I vaguely remember you using a container<smart_ptr<type>> and using some sort of indirection comparator that would dereference the pointer. However, I can't seem to find a reference to it and it's not in any of the video descriptions. I don't want to spend 8-10 hour rewatching all these videos if possible.

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.