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 - Advanced STL, 6 of 6

Download

Right click “Save as…”

There are two STLs: the Standard Template Library and Stephan T. Lavavej Smiley

Advanced STL covers the gory details of the STL's implementation -> you will therefore need to be versed in the basics of STL, competent in C++ (of course), and be able to pay attention! Stephan is a great teacher and we are so happy to have him on Channel 9—the only place you'll find this level of technical detail regarding the internals of the STL. There are no books. There are no websites. This is Stephan taking us into what is uncharted territory for most, even those with a more advanced STL skill set.

This is a very special episode—it was driven by you!

In Part 5, Niner KerrekSB commented that a great topic for this advanced series would be developing a generic mechanism for printing out STL containers (like a vector of ints). Then Sven Groot helped out with his usual brilliance. I love this Niner interaction!

You got STL to lecture on this stuff! That is HUGE Smiley

In fact, STL was so impressed that he decided to try it out himself and see how generic he could make it. He uses only those STL features available in VC10 SP1 (for example, variadic templates are not used in his solution because the feature is not implemented in VC 2010 SP1...).

What did Stephan come up with? Get STL's PrettyPrinter implementation, then watch this great episode to learn the details behind the code. Thanks STL, KerrekSB, and Sven Groot for an excellent exercise!

[Advanced STL]

Part 1 (shared_ptr - type erasure)

Part 2 (equal()/copy() - algorithm optimizations)

Part 3 (_ITERATOR_DEBUG_LEVEL, #pragma detect_mismatch, and /d1reportSingleClassLayout)

Part 4 (rvalue references v2.1 and associative container mischief)

Part 5 (deduplicator, using Boost.Bimap/Filesystem/ScopeExit) - see Stephan's deduplicate.cpp

Part 6 (container pretty printer) - see Stephan's pretty_printer.cpp


Watch STL's great introductory series on the STL

Tags:

Follow the Discussion

  • Josh KJosh K

    @STL
    at 05:56
    Can you post the code you were talking about ?
    I'm curious and want to read it.

    That code will hopefully work in vs next. If not there's always trusty gcc ;)

  • Another Cool Lecture by STL.

    @STL How would you write a pretty print function for a Binary Tree.

  • ChrisChris

    I have a std::function question that I started on Stack Overflow ( http://stackoverflow.com/questions/6628442/can-tr1function-swallow-return-values and http://stackoverflow.com/questions/6653531/workaround-to-allow-tr1function-to-swallow-return-values).

    To summarize, with the original boost::function I can hold a function that returns any type of value in a function wrapper that returns void, effectively "swallowing" the return value.

    int Foo();
    boost::function<void()> Bar = Foo;

    But this doesn't work in MSVC2008 using tr1::function (error C2562: 'std::tr1::_Callable_fun<_Ty>::_ApplyX' : 'void' function returning a value), and I'm told on Stack Overflow that it doesn't work in MSVC2010 either. Someone pointed out that the wording for the definitions of "callable" and the "INVOKE" meta-function that are used to describe std::function has changed between TR1 and C++0x, and that this change effectively rules out the boost::function behavior (since no types are implicitly convertible to void).

    Can you comment on this issue?

  • This is great, thanks so much! Smiley Very nice that you got the raw array covered without special treatment, I'll try to do improve our pretty printer similarly! In the meantime, have a look at this complete const_iterator/begin/end type trait -- does it work in MSVC? https://gist.github.com/1076849
  • petkepetke

    Good video. Keep em coming.

    Small nitpick. You probably meant:

    "typedef MyAlloc<U> other;"

    instead of

    "typedef U other;"

  • STLSTL

    Source code: https://skydrive.live.com/redir.aspx?cid=e66e02dc83efb165&resid=E66E02DC83EFB165!292

    Ivan, Part 5's comments> why would you want to "include subheader repeatedly"

    As I recall mentioning in an earlier video, VC10 simulates variadic templates like "template <typename T, typename... Args> shared_ptr<T> make_shared(Args&&... args)" with the preprocessor. We have a subheader, <xxshared>, that lacks idempotency guards and uses special macros. <memory> then includes <xxshared> repeatedly, defining the macros differently each time - for 0 arguments, 1 argument, 2 arguments, all the way up to 10 arguments. This "stamps out" overloads of make_shared<T>(), simulating the single variadic template.

    Josh K> That code will hopefully work in vs next.

    It contains an exact major version check for VC10 because VC11 will need something different. I can't say what, yet.

    Tominator2005> How would you write a pretty print function for a Binary Tree.

    It depends on how fancy you want to get. Do you want a linear string (e.g. with parentheses), or an ASCII art tree?

    Chris> Can you comment on this issue?

    Looks like we conform to C++0x (Howard Hinnant is a Committee member and knows what he's talking about). Which is nice, since I had previously identified this as a bug in our TR1 conformance.

    KerrekSB> does it work in MSVC?

    Yes, with VC10 SP1.

    petke> Small nitpick. You probably meant: "typedef MyAlloc<U> other;" instead of "typedef U other;"

    That's right, thanks for the correction.

  • STL, thanks for this episode! I didn't know about the global begin()/end(), I've now included that in our pretty-printer as well to handle static arrays -- cool. I also added the full type trait check for const_iterator, begin and end which I posted above.

    I like the generality you get with your formatter class, that's great!

    Perhaps a few notes about our own implementation:

    • A small aside: Type erasure isn't generally used in our approach, everything is done at compile time. TE only comes in when you use a custom delimiter class via "cout << custom_delims<MyDelimClass>(x) << endl;", where you erase the type of "x". The standard formatter doesn't need this, and neither do specializations of the standard formatter.
    • I'm curious about your special treatment of strings (because we also discussed that). Since we decided to overload op<< directly, I always assume that any string class will have defined that overload already and thus our template never comes in. But I suppose since you have an explicit print function, you do need to catch special cases like types with iterators that aren't containers...?
    • A final note on our design choice to overload op<<: The one thing I personally really really feared was the need to remember a function name, and I was ready to give anything to be able to just say "cout << x << endl;" without thinking. I like your more powerful general formatter, but the zero-memory op<<-overload is something I cherish a lot Wink

    Anyway, great episode, with lots to learn from it -- keep it up, and looking forward to next month!

    (Also, there appeared to be a bug in this website: After typing all this and submitting, I got a "system error" response, possibly because you were posting just before my submission. Not being able to go "back" in my browser (Iron), I could only press "reload" to repost, but with no avail - I finally resorted to tcpdump to capture the resubmit, URL-decoded the POST and recovered the raw HTML of this post. Phew.)

  • STLSTL

    > STL, thanks for this episode!

    You're welcome!

    > TE only comes in when you use a custom delimiter class

    Fair enough - I didn't look very closely at the guts of your implementation. But mine doesn't use type erasure anywhere. :->

    If you look at the STL, as a general principle, customization never involves additional costs. std::vector with a custom allocator or std::sort() with a custom comparator don't involve space or time costs beyond whatever's in the custom machinery itself. std::shared_ptr and std::function also follow this principle - they're performing type erasure anyways, so there's no additional cost for erasing custom deleters/allocators. (I have a todo to make them avoid storing empty allocators, which is something that we've already done to the containers.)

    > But I suppose since you have an explicit print function, you do need to catch special cases like types with iterators that aren't containers...?

    That's right. std::string could be handled within the general container machinery, by giving it a prefix and suffix of "\"" and a separator of "", but that would inefficiently print the string character-by-character. I built my pretty printer on top of iostreams, so performance is almost a lost cause anyways, but adding additional penalties would be even worse.

    > The one thing I personally really really feared was the need to remember a function name

    "print" is easy to remember. :->

    The problem with op<<() is that it mixes code and data. I believe that Boost.Format's machinery is ideal, with two exceptions - it needs variadic templates instead of its op%() trick for C++98/03, and it needs to be built from scratch instead of above iostreams. My ideal I/O mechanism would look like print("format string", stuff, stuff, stuff), with customization along the lines of my pretty printer.

    > keep it up, and looking forward to next month!

    I will have to think of something to talk about. For fun, I wrote a http://en.wikipedia.org/wiki/Dissociated_press implementation, but it's more intermediate-level than advanced.

  • Josh KJosh K

    @STL So you do not want to share it until vs next gets released ?
    I'm talking about the code that didn't work at 05:56.

  • CharlesCharles Welcome Change

    @STL and @EverybodyElse: At this point and given how this episode turned out, why not suggest topics for the next one?

    C

  • @STL: Your philosophy of not mixing code and data is interesting, perhaps I should rethink how I print things in general. Cheers.

    Speaking of, if iostreams is such a drag and you have an idea how to do it better, would you care to share? I'm sure many people would love to see a high-performance and easy to use alternative! (Can your solution can beat "printf("%06X", myMACaddr)" in compactness and ease of use? Wink )

    Also, I'm comparing our pretty-print implementations; for simple examples they produce identical assembly! Smiley

  • AndrejsAndrejs

    ļoti izsmeļoši

  • STLSTL

    Josh K> I'm talking about the code that didn't work at 05:56.

    Oh, I deleted that when it didn't work. ("Source control? What's that?")

    KerrekSB> Your philosophy of not mixing code and data is interesting, perhaps I should rethink how I print things in general.

    It's not original to me, but I forget where I learned it from. One problem with mixing code and data is that it wreaks havoc with i18n.

    KerrekSB> Speaking of, if iostreams is such a drag and you have an idea how to do it better, would you care to share?

    Well, it'd be better if I had an actual implementation, which I don't. The pretty printer is a sketch of the techniques I'd use, though.

    KerrekSB> (Can your solution can beat "printf("%06X", myMACaddr)" in compactness and ease of use? )

    When printing hex, I overwhelmingly want three things: zero padding, hexits equal to the width of the data type, and uppercase. I want to be able to say %X and have that work for unsigned char and unsigned long long equally.

    It looks like MAC addresses are 12 hexits, not 6. If they had their own type, they could be annotated with their width.

  • IvanIvan

    @ STL
    Another great video(although I cant seem to think in template way- I miss my precious if statements, and template tricks are above my level :) ). That being said I really like the advanced series on The Next Generation of C++ although it is harder to understand than the The Original Series :P

    BTW I have two STL questions
    1.
    often I use set s<T>
    and then I check if the element is in the set( .count ). Problem is that I think that sorted vector<T>(because it is in sequential memory locations ) + binary_search() is faster way to do it? Am I right?
    BTW I know you probably arent allowed to tell the details but if you were working on Office or VS GUI would you bother with this optimization?
    2. Also if I call MULTIset insert with 100 elements-how many malloc calls is that? 1(you know the required space because it is multiset) or 100.

    P.S. Tnx for drawing the dbl_linked list on the white-board-as an ComSci student I'm always trying to find a reason to claim that my college wasnt a waste of time. :)
    P.P.S Regarding my stupid question about multiple includes, I now remember that you mentioned the MACRO_TRICK I just forgot how it was done.

  • ChrisChris

    @STL: Any idea why INVOKE was changed in this way? Is there some rationale - some gotcha that I can't see? Or is there some obvious workaround/alternative that renders it unnecessary? This could be a good topic for the next talk :) - it would likely touch on the machinery of std::function, possibly std::bind, lambda functions, forwarding, variadic templates, etc. and how they interact.

  • @STL An ascii art tree would be good. That way you can see the way the tree set up,
    but one with Parentheses would be good too.

  • @STL: In regards to your comments around 12:56-13:10, will you be paying my company to do the upgrades and the necessary (and expensive) 3rd party library upgrades that would need to occur? Will you say something similar about Vs2010 when VsNext is issued? Just wondering. It's easy to say everybody should upgrade to the latest, just not easy to do. If you can convince my boss to pay for that, you're better than me. I'm sure he'll gladly accept free copies though if you or Charles or any other MS employee are willing to donate to my company. Smiley You should have seen the fight we had to undertake to move from VC6 to VS2008! So, in about another 7 years we may upgrade if current trends continue.
  • petkepetke

    I have a topic for you; std::codecvt. C++ and Unicode. How do you convert between the different encoding in a standard and portable way. Some say C++ support for unicode is embarrassing, but that's all changed with C++0x, right?

  • C++ unicode issues are something I would very much like to see some coverage of ... but it really doesn't fall into STL's area I don't think.  That's why (as I have suggested previously) I think there is room for a more general series of topics that ventures beyond STL's "turf" in the library.  The challenge would be to find someone of STL's caliber to deliver such lectures.  It would probably be a good place for rotating presenters.

  • CharlesCharles Welcome Change

    ,ryanb wrote

    ..... I think there is room for a more general series of topics that ventures beyond STL's "turf" in the library.  The challenge would be to find someone of STL's caliber to deliver such lectures.  It would probably be a good place for rotating presenters.

    Smiley

    Would you like to see a monthly show focusing on native dev with a rotating cast of characters and topics? Would you like a native-focused show that thrills and delights, educates and challenges? Well, hold on pardners... It's a comin'!

  • ,Charles wrote

    *snip*

    Smiley

    Would you like to see a monthly show focusing on native dev with a rotating cast of characters and topics? Would you like a native-focused show that thrills and delights, educates and challenges? Well, hold on pardners... It's a comin'!

    Yes please, thank you!  Smiley    Good stuff Charles ... keep it coming.

  • thanks for a good video

  • @petke, @ryanb: The C++ language standard has no notion of "encoding". Moreover, it has no notion of "text" and "binary representation of text". Any explicit Unicode-related operations are strictly outside the scope of the language.

    What C/C++ do do is to acknowledge that the historically misnamed type `char`, which should probably have been called `byte`, is insufficient for textual purposes, and it provides a platform-dependent, unspecified textual type `wchar_t` to hold a platform-dependent text character primitive. Acknowledging further that the outside world communicates in byte streams, the standard assumes that there exists a (platform-dependent) method to translate between fixed-width wide strings and variable-width byte streams, provided by `mbsrtowcs` and `wcsrtombs`. (I wrote a little rant about this on SO a while ago.)

    In this sense, the native MSVC environment only supports UCS-2, or otherwise it gives you varibable-width 16-bit strings internally with no genuine "character" functions built into the language. It's also worth noting that most file systems accept null-terminated byte strings as file names (again with no notion of encoding or textual semantics), and NTFS is one of the rare kind to use null-terminated 16-bit strings (not: unicode) as filenames, necessitating non-standard file functions like `_wfopen`.

    Personally, I think the notion of "text" is just very high-level, and instead of burdening a general purpose language like C or C++ with it, it's best left to something like ICU that can perform normalization and other deep text operations.

  • STLSTL

    Ivan> I cant seem to think in template way- I miss my precious if statements, and template tricks are above my level

    Try writing FizzBuzz with runtime recursion, avoiding runtime loops but using runtime conditionals.

    Then try writing FizzBuzz with templates (i.e. compiletime recursion), avoiding both runtime loops and runtime conditionals.

    This simple exercise is actually quite valuable.

    Ivan> often I use set s<T> and then I check if the element is in the set( .count ).

    I prefer s.find(key) != s.end() because it's equally efficient for sets and multisets.

    Ivan> Problem is that I think that sorted vector<T>(because it is in sequential memory locations ) + binary_search() is faster way to do it?

    It depends on what you're doing with your data.

    If you build up your data structure in one phase, then repeatedly access it in another phase, then it's probably going to be more efficient to build up a vector, sort it, and then do lots of binary searches.

    However, if your insertions are interleaved with lookups, and especially erasures, then a sorted vector is totally inappropriate and you definitely want a set.

    Ivan> if you were working on Office or VS GUI would you bother with this optimization?

    Only if (1) profiling identified the set as a bottleneck, and (2) I had the access pattern guarantee allowing me to use a sorted vector instead.

    By the way, I dealt with this kind of issue in my Nurikabe solver.

    > Also if I call MULTIset insert with 100 elements-how many malloc calls is that?

    100. The node-based containers (list, forward_list, set/multiset/map/multimap, and their unordered variants) store elements in separate nodes.

    Chris> Any idea why INVOKE was changed in this way?

    No, sorry. Might have been intentional, might not.

    Tominator2005> An ascii art tree would be good.

    Here's an ASCII art pretty printer for a Huffman tree:

    C:\Temp>type meow.cpp
    #include <stddef.h>
    #include <fstream>
    #include <ios>
    #include <iostream>
    #include <memory>
    #include <ostream>
    #include <queue>
    #include <string>
    #include <vector>
    using namespace std;
    
    vector<size_t> frequencies(const string& filename) {
        vector<size_t> ret(256, 0);
    
        vector<unsigned char> buf;
    
        const int N = 64 * 1024;
    
        for (ifstream file(filename, ios_base::binary); file; ) {
            buf.resize(N);
            file.read(reinterpret_cast<char *>(buf.data()), N);
            buf.resize(static_cast<size_t>(file.gcount()));
    
            for (auto i = buf.begin(); i != buf.end(); ++i) {
                ++ret[*i];
            }
        }
    
        return ret;
    }
    
    struct node {
        node(const unsigned char b, const size_t f)
            : byte(b), freq(f), left(), right() { }
    
        node(const shared_ptr<node>& l, const shared_ptr<node>& r)
            : byte(0), freq(l->freq + r->freq), left(l), right(r) { }
    
           unsigned char byte;
                  size_t freq;
        shared_ptr<node> left;
        shared_ptr<node> right;
    };
    
    struct freq_greater {
        bool operator()(const shared_ptr<node>& l, const shared_ptr<node>& r) const {
            return l->freq > r->freq;
        }
    };
    
    void helper(const shared_ptr<node>& p, const string& prefix, const string& next) {
        cout << prefix;
    
        if (!next.empty()) {
            cout << "|--";
        }
    
        if (p->left) {
            cout << "* f=" << p->freq << endl;
            cout << prefix + next + "|  " << endl;
            helper(p->left, prefix + next,  "|  ");
            cout << prefix + next + "|  " << endl;
            helper(p->right, prefix + next, "   ");
        } else {
            cout << "* f=" << p->freq << " b=" << static_cast<int>(p->byte) << endl;
        }
    }
    
    void print(const shared_ptr<node>& p) {
        helper(p, "", "");
    }
    
    int main() {
        const vector<size_t> freqs = frequencies("VS2010Express1.iso");
    
        priority_queue<shared_ptr<node>, vector<shared_ptr<node>>, freq_greater> pq;
    
        for (int i = 0; i < 256; ++i) {
            pq.push(make_shared<node>(i, freqs[i]));
        }
    
        while (pq.size() > 1) {
            const shared_ptr<node> x = pq.top();
            pq.pop();
            const shared_ptr<node> y = pq.top();
            pq.pop();
    
            pq.push(make_shared<node>(x, y));
        }
    
        const shared_ptr<node> root = pq.top();
        pq.pop();
    
        print(root);
    }
    
    C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL meow.cpp
    meow.cpp
    Generating code
    Finished generating code
    
    C:\Temp>dir *.iso | findstr VS2010Express1.iso
    07/12/2011  04:11 PM       727,351,296 VS2010Express1.iso
    
    C:\Temp>meow
    * f=727351296
    |
    |--* f=347426581
    |  |
    [...]
                   |
                   |--* f=20905813
                      |
                      |--* f=10200448 b=0
                      |
                      |--* f=10705365
                         |
                         |--* f=5324840 b=255
                         |
                         |--* f=5380525
                            |
                            |--* f=2689721 b=167
                            |
                            |--* f=2690804 b=166

    HomerSimpian> In regards to your comments around 12:56-13:10, will you be paying my company to do the upgrades and the necessary (and expensive) 3rd party library upgrades that would need to occur?

    Your company bought third party libraries without the right to rebuild them, or request new builds for updated toolsets?

    HomerSimpian> Will you say something similar about Vs2010 when VsNext is issued?

    Yes. As I'm living in the future with VC11, VC10 already feels old to me.

    HomerSimpian> It's easy to say everybody should upgrade to the latest, just not easy to do.

    It's not always easy to do the right thing.

    petke> I have a topic for you; std::codecvt.

    That's a complicated area and I'm not an expert there.

  • Julien NJulien N

    About the next topic, what about some more template meta programming? The former videos did use some of it (notably some enable_if) but nothing specific yet.

  • IvanIvan

    @STL
    First tnx for the answ and the FizzBuzz suggestion. Will look it up. To be clear my question about vector vs set was for case where there are no removals or new insertions. Disregarding my compsci knowledge erase-remove idiom is enough to scare me away from using vector in that way.
    BTW I prefer .count() instead of find() because it allows me to do the horrible if(s.count(74656)) .
    "Ivan> Also if I call MULTIset insert with 100 elements-how many malloc calls is that?

    100. The node-based containers (list, forward_list, set/multiset/map/multimap, and their unordered variants) store elements in separate nodes."
    Isnt that a wasted opportunity? Tp be clear I'm not talking about for (i=0;i<100;++i) ms.insert(v[i]), I'm talking about ms.insert(v.begin(),v.end());//v.size()==100
    this overload
    template<class InputIterator>
    void insert(
    InputIterator _First,
    InputIterator _Last
    );
    Is this inherent limitation of the C++ allocators or choice by library implementers?
    Again this might be a stupid question, but my knowledge of allocators is really limited...

  • @Ivan: Contiguous allocation is exactly the underlying idea of a vector. In an node-based container, you do want to have quick insertion and removal, so how could that work if elements didn't have their own memory? You'd end up with exactly the problem that vector has when you erase something from the middle. Or perhaps, since you don't require contiguousness, you would need a mechanism to free()  a smaller chunk from amidst a larger allocated region -- as far as I know, no OS supports that sort of memory management. (Note that free() is only defined on a pointer that was previously allocated, you cannot say things like free(p+1).)

  • new2STLnew2STL xkcd.com

    ,STL wrote

    Yes. As I'm living in the future with VC11, VC10 already feels old to me.

    Oh, this is unfair Stephan, you are tempting us. Wink

    For next topics, I recently got a translated version of Effective C++ and I get fascinated with std::function and his friends (like bind) and how it interact with the containers. Expanding std::function and bind looks a nice topic, with examples of how wrap old/legacy algorithm with STL (one example i like is the sorting the vector with C str wrapped functions) or using it in some pattern like a visitor or observers.

    As always, nice video, thank you @STL

    @Charles, keep it comming Big Smile

    (edited/added) I just remember another topic that could be nice (but don't know if it fits on "advanced"):std::hash, and how make our own types container/STL friendly.

  • ,KerrekSB wrote

    @petke, @ryanb: The C++ language standard has no notion of "encoding". Moreover, it has no notion of "text" and "binary representation of text". Any explicit Unicode-related operations are strictly outside the scope of the language.

    What C/C++ do do is to acknowledge that the historically misnamed type `char`, which should probably have been called `byte`, is insufficient for textual purposes, and it provides aplatform-dependent, unspecified textual type `wchar_t` to hold a platform-dependent text character primitive. Acknowledging further that the outside world communicates in byte streams, the standard assumes that there exists a (platform-dependent) method to translate between fixed-width wide strings and variable-width byte streams, provided by `mbsrtowcs` and `wcsrtombs`. (I wrote alittle rant about this on SO a while ago.)

    ...

    Personally, I think the notion of "text" is just very high-level, and instead of burdening a general purpose language like C or C++ with it, it's best left to something like ICU that can perform normalization and other deep text operations.

    Yes, Unicode/Multibyte operations are outside the scope of the language, which is why I said it is beyond the scope of this series (and I never suggested it should be part of the language).  But the fact that the language will physically handle the representation of different encodings has little to do with being able to work with those encodings in the real world.  Especially when a lot of us need to produce portable code in the real world, these platform dependent and encoding dependent differences make things very difficult (as you are well aware).  Having some coverage of strategies for structuring code (using the existing language features) to deal with these situations would be of value.   

    If normalization libraries and a common internal representation are the only means of working with mixed-encoding environments, that raises the question of whether a normalization library (such as ICU, already a quasi-standard) needs to be provided as a language standardized, portable library.

     

  • With the advent of domain specific libaries such as <atomic> and <thread> I'd say Unicode operations and data types could very well be part of the standard. It is exactly those platform specific functions and types that drive people to higher level languages like Java, even if those are heavily dumbed down; they at least provide this cross-platform functionality with easy to use interfaces.

    Of course, Qt could be an option but I despise it. It's not even a library, it's a complete application framework that takes over your programming environment with custom build-tools and tries to reinvent the STL.

  • IvanIvan

    @ KerrekSB
    IMHO you could have a vector of the adresses of the freed nodes so that map can use freed stuff for the new nodes. Ofc returning memory when (any node is deleted) to the os is a big no no because remembering when all the nodes allocated in one big alloc is hard(for me, it might be very very easy for someone smarter/more educated, best I can think of is atomic<size_t> n_block_nodes_in_use-when it reaches 0 you can return the memory). Again this leads to other problems you could alloocate 100x1M nodes, remove all but 20 and still end up with lets say 20X1M memory used(1 remaining node in each block). Then you end up with inserting memory usage balancing into the already hellish process of inserting a node in the RBTree. :)
    But still c++ vector also "wastes" memory. STL explained why. Standard smartly says that amortized cost of insertion must be O(1) when it is resized you get new_size=k+old_size(k=1.5 for VC, 2 for GCC if i remember corectly).

  • IvanIvan

    error in previous comment :ofc new_size=k*old_size, not + , it was a keyboard error, I dont think that you can have floating point size. :D

  • STLSTL

    Julien N> About the next topic, what about some more template meta programming? The former videos did use some of it (notably some enable_if) but nothing specific yet.

    This pretty printer involved significant template metaprogramming. At first, it might not appear to involve very much TMP, but it's recursively analyzing the type of a container and its elements.

    I could try to think of more.

  • @STL:

    Great video, thanks so much!

    Regarding the FizzBuzz task you recommended to Ivan, I guess I'll have to do the same thing.

    In C# I have no problems with generics (which is IMO far from templates), but I can imagine when using it. In C++ I have the problem (and it is a problem IMO), that I can't detect when templates would be valuable. In C# we have e.g. a generic Presenter (MVP), where we can pass some other class that the derived class depends on (IOC) or some other examples, where I know when to use generics when I see it. I'm sure I have a lot of code that could be optimized using templates. Of course I should be creating a few, so I see/learn the benefits of when to use them.

    C++/OpenGL I do for fun on some evenings, after doing C# all day at work (learnt a lot about C++ in the last 1.5 years -- if I compare myself to questions from KerrekSB etc. I've got tons to learn).

    I like this diagram for choosing containers: http://linuxsoftware.co.nz/cppcontainers.html (at the bottom. unordered_... not included), though I usually do look at a C++ reference site to see what's better for what case, i.e. inserting in middle, reading from middle, etc.

    Previous video you mentioned in the comments, you can't comment on legal things, but you can say if we can use your code commercially/non-commercially etc. like the code above for printing an ASCII tree.

    You actually used an ifstream this time Smiley I often use "pure" C++ classes (including ifstream). What I don't get, I recently saw this on cplusplus.com: ifstream provides an interface to read data from files as input streams. IMO that means, it's an interface, so I'm suppose to use an fstream if it's not meant to be an interface or to pass it an fstream to a function I could use Do(const ifstream& aStream);??? Or what am I misunderstanding. Does interface in this case mean a facade/wrapper, and not an interface (i.e. C#'s meaning of interface). Must be, since its functions are obviously not pure virtual.

    Another question that someone may know. If I inherit from a base class, is it a bad idea to do an inline on an overriden (for virtual)/implemented (pure virtual) function in the derived class (obviously)?

     

  • C64C64

    ,Charles wrote

    *snip*

    Smiley

    Would you like to see a monthly show focusing on native dev with a rotating cast of characters and topics? Would you like a native-focused show that thrills and delights, educates and challenges? Well, hold on pardners... It's a comin'!

     

    That sounds great: thanks Charles!

    I'm looking forward to some of the Windows devs, like Larry Osterman and someone from lower-level too (e.g. Doron Holan, device drivers).

    Some questions I'd like to ask to Larry is discussing why in their team they don't use C++ exceptions and prefer error codes, and what tools do they use to "develop Windows" (what editors? what debuggers? The great WinDBG? Some other tool?).

    Thanks.

     

     

  • C64C64

    Thanks for this lecture, STL.

    As next topic, I'd like to suggest developing a custom STL allocator: as an exercise, explain us how to convert this efficient pool allocator written in Win32/C++ to "STL/C++" Smiley

    Thanks.

     

  • STLSTL

    Deraynger> In C++ I have the problem (and it is a problem IMO), that I can't detect when templates would be valuable.

    Do you want to handle arbitrary types? Then you want templates.

    Deraynger> I like this diagram for choosing containers

    I strongly disagree with that diagram for several reasons:

    1. It gives terrible guidance around vector/deque/list. Absolutely horrible.

    2. It doesn't understand how limited the container adaptors are.

    3. It doesn't spell multimap and multiset properly. (That's not a big deal in and of itself, but if you can't spell a container's name correctly, you probably haven't used it very much...)

    4. It makes the whole process look way more complicated than it is.

    Here's what I recommend:

    1. Be familiar with the container adaptors: stack, queue, and priority_queue. They intentionally have very narrow, highly restricted interfaces (e.g. you can't iterate through a stack's elements). In fact, stack and queue don't do anything *except* restrict the interface of an underlying container. (priority_queue does a bit of real work by gluing the heap algorithms to an underlying container.) When your needs can be satisfied by a container adaptor, then use it. Otherwise, don't. (For example, I use a queue in my Nurikabe solver, and a priority_queue in my Huffman tree code above. Note that priority_queue::top() returns the "highest priority" element, but Huffman wants the lowest frequency nodes, so I use greater-than to reverse the ordering accordingly.)

    2. Be familiar with the ordered associative containers: set/multiset/map/multimap. It's pretty obvious when you need them, and it's pretty easy to determine whether you care about duplicates.

    3. Be aware of the unordered associative containers and their different guarantees. They're less convenient (no auto-sorting, no worst-case logarithmic guarantees) and harder to use (providing equality and a good hash is harder than providing less-than), so I recommend using them only when you know that you really want their properties.

    4. Be familiar with the sequence containers: vector, vector, vector, list, forward_list, and deque. vector is by far the best general-purpose sequence container - it is both extremely efficient and extremely powerful (random-access is a very important power). Use vector unless you specifically need the unique abilities of another container. This is actually pretty rare!

    4a. list is significantly less efficient than vector and significantly less powerful (it's bidi instead of random-access). Summarizing its advantages: (1) list has true O(1) push_front() whereas vector intentionally lacks push_front() because it would be O(N) (you have to specifically request that with insert() which is more verbose), (2) list::push_back() is true O(1) whereas vector::push_back() is amortized O(1) (this is a theoretical advantage but I have never seen it matter in practice), (3) list has true O(1) arbitrary insertion, but you have to have an iterator to the insertion location in the first place, making this not nearly as useful as it sounds at first, and (4) most importantly, as a node-based container, list insertion/erasure never invalidates iterators/pointers/references to other elements. list does other things (e.g. splicing), but those are the big ones as far as I'm concerned. Actually needing them is quite uncommon.

    4b. forward_list is slightly more space-efficient than list (one pointer per node instead of two, no sentinel node), but even less powerful (forward instead of bidi) and with a more unusual interface. I have extreme difficulty imagining real uses for forward_list. But in the ridiculously improbable event that you need it, it's there.

    4c. deque is the strangest container in the STL, and really in the world. In wall-clock terms, it supports amortized O(1) push_front() and push_back(), and is yet true O(1) random-access. It also has really special invalidation guarantees (it is the only STL container capable of invalidating iterators while preserving pointers and references). In absolute terms, it's not very efficient, especially in VC's implementation. You should use deque only when you need its strange properties, which is virtually never.

    Deraynger> Previous video you mentioned in the comments, you can't comment on legal things, but you can say if we can use your code commercially/non-commercially etc. like the code above for printing an ASCII tree.

    I can point to the notice at the bottom of every C9 page, which may or may not apply to my C9 code, and wouldn't be useful if it did!

    I could also ask my bosses and boss-like entities about releasing my C9 code under the Boost Software License, which would actually be useful. But that sounds like work.

    Deraynger> I recently saw this on cplusplus.com: ifstream provides an interface to read data from files as input streams.

    They didn't mean interface in the special polymorphic sense (even though iostreams is full of virtuals). Interpret this as: "ifstream is a thingy that reads data from files".

    Deraynger> IMO that means, it's an interface, so I'm suppose to use an fstream if it's not meant to be an interface

    ifstream is a thingy that reads data from files.
    ofstream is a thingy that writes data to files.
    fstream is a thingy that can read data from and write data to files.

    iostreams are hideously complicated in general, but this part is simple.

    Deraynger> Do(const ifstream& aStream);???

    Doing anything to an ifstream/ofstream/fstream involves modifying it, so const is erroneous here.

    Deraynger> If I inherit from a base class, is it a bad idea to do an inline on an overriden (for virtual)/implemented (pure virtual) function in the derived class (obviously)?

    The "inline" keyword (both when it's explicitly written, and implicitly granted to a member function defined in a class definition) has two effects. First, it's a non-binding hint to actually inline the function. This will typically be ignored for virtuals except in the presence of a very advanced compiler. Second, it grants the Partial ODR Exemption (also granted to templates) allowing header-only code. It has no other semantic effects.

  • @STL: Thanks so much for elaborating.

    STL> Do you want to handle arbitrary types? Then you want templates.

    To what extent is it arbitrary? If I have an interface/abstract base class, then it's not arbitrary anymore, although with templates I could probably skip the base class and use a template that checks that the class contains the functions I need.

    Deraynger> I like this diagram for choosing containers

    STL> I strongly disagree with that diagram for several reasons

    As I mentioned, I never really used the diagram, but "I usually do look at a C++ reference site to see what's better for what case, i.e. inserting in middle, reading from middle, etc."

    Regarding vectors, that's what I mainly use (especially for vertices etc.), map/multimap and in one case a stack<x, vector<x>()>.

    STL> I can point to the notice at the bottom of every C9 page, which may or may not apply to my C9 code, and wouldn't be useful if it did!

    [Edit] I sent an e-mail to C9 regarding the different questions. Theoretically I consider it quite open for interpretation, so IMO your code falls under user-posted content (see: http://channel9.msdn.com/info)">http://channel9.msdn.com/info), where you can provide a CC-license (which doesn't state it has to be the same as C9s CC-license), so you could theoretically say that we can use all of your posted code freely and commercially and the license is the following: http://creativecommons.org/licenses/by/3.0/, with the extra permissions that we can use it with or without a copyright notice with your name (provided you want that) Big Smile, and as the license states, it has to be visible that this license is used.

    I'll write when I get an answer from C9.

    STL> [Inlines]

    I use inline usually for tiny things (not even for calculations), but mainly just for setters/getters. But if I know that it shouldn't be for virtual functions, then I also won't use them there Smiley

     

    Small question. If I use a for_each, can't I create a member function (preferably non-static) defined in the same class, or is it like a functor, where a seperate class/struct is necessary?

    Thanks again for all your detailed answer (especially on the containers and the diagram).

     

    STL> The problem with op<<() is that it mixes code and data.

    Can you explain it, I don't get it Perplexed

    @Charles:

    Charles> Would you like to see a monthly show focusing on native dev with a rotating cast of characters and topics? Would you like a native-focused show that thrills and delights, educates and challenges? Well, hold on pardners... It's a comin'!]

    I'd love it!

  • IvanIvan

    @STL
    is it possible in C++(without adding something to the STL implementation) to add for example .sort() member function to vector? I presume not, but I never understood the reasons. Also I dont know why it isnt defined in the standard. I mean I know that some people dislike Object languages, but C++ is supposed to give options to programmer , right?

  • new2STLnew2STL xkcd.com

    @Ivan: C++ are based on 3 pilars: Containers, Iterators and Algorithm, this way they can provide a generic way to an algorithm like sort be applied to many type of containers through iterators interface. Here an except from sgi:

    "Iterators are central to generic programming because they are an interface between containers and algorithms: algorithms typically take iterators as arguments, so a container need only provide a way to access its elements using iterators. This makes it possible to write a generic algorithm that operates on many different kinds of containers, even containers as different as a vector and a doubly linked list. "

  • IvanIvan

    @ new2STL
    Yeah, but each container has begin and end. That makes implementing .sort() trivial.

  • new2STLnew2STL xkcd.com

    @Ivan: Each container have begin and end because this is the way C++ had to implement interfaces (C++ don't have the interface keyword like other languages) and decouple it from the algorithms.

    I can be wrong but, Sort as a member function looks like that sort belongs only to that container and need be implemented by it. Its not "C++ don't like Object", it was the solution they find when developing a library that fits on most generic way possible. As a member it only make inflate the container with a functionally that not belongs to it. Witch type of sort algorithm to use if an algorithm fits on more than one type of container, replicate code? Even if you think in sort member as a way to shortcut a call to sort(s_begin, s_end, d_begin) it only looks duplicating code and defeat the purpose of iterator (why make a iterator interface if sort will be on the object anyway?)

    It's like the pretty printer above, you could want overload ostream and operator <<, but other prefer a separate print(...). What I know from now reading more and more C++ books and articles (and I'm aligning to it) is make a print(...) could be more interesting for keep the algorithm generic, decoupled and self-contained. In the way to chose commodity or discipline, choose the later Wink

  • IvanIvan

    @new2STL
    I dont really reakly understand that it would be hard to implement it.
    Every .sort could be
    {
    sort(this->begin,this->end());
    }
    Maybe I'm wrong. :) That is why I would like STLs answer. He knows the standard very well and the reasons for certain decisions.

  • Knowing me knowing you, a-haaasss C++ rules and rocks!

    @Ivan the reason is: code duplication, maintenance and the like. You have std::sort which already does the job, why would you want to have another sort specific to a container? That's the whole beauty of generic programming. You've got an algorithm and it works on many different containers. Exponential growth (of number of algorithms/methods/fncs) is something what you want to avoid.

    C++ is beautiful in this and every other way.

  • IvanIvan

    @aasss
    like I replied before member function could be a wrapper around the real sort so I dont see a code duplication problem. Also why I want it? Because like I said it is easier for me to thing in object way. Again I would like STLs opinion because he is the expert.
    P.S. there is a std::count, map::count, multimap::count

  • MasfoMasfo

    As for next episodes, I would like to see piece on allocators, writing your own etc.

  • C64C64

    @aasss
    like I replied before member function could be a wrapper around the real sort so I dont see a code duplication problem. Also why I want it? Because like I said it is easier for me to thing in object way. Again I would like STLs opinion because he is the expert.
    P.S. there is a std::count, map::count, multimap::count

    Following your way of reason, you should add a sort() method to several containers, not only vector. Then why not adding also a binary_search() or search() method where applicable, to vector and to other containers? And add other do_some_cool_algorithm() method? Then the public interface of STL classes become bloated, contrary to STL's philosophy.

    As I understand it, the STL's philosophy has a strong decoupling between containers and algorithms (iterators are the "glue"), and they try to keep container public interfaces minimal.

    But I agree with you that is better waiting for STL's (Stephan) answer.

     

  • STLSTL

    STL> Do you want to handle arbitrary types? Then you want templates.

    Deraynger> To what extent is it arbitrary?

    In the template world, "arbitrary" means exactly what it says on the box: the whole universe of types, until you choose to constrain it.

    Deraynger> If I have an interface/abstract base class, then it's not arbitrary anymore, although with templates I could probably skip the base class and use a template that checks that the class contains the functions I need.

    Think back to the intro series, where I believe I ranted against pre-STL containers (now extinct) that required their elements to derive from a common base class. (If I didn't rant against them, I should have.) That's obnoxious (and inefficient!) for lots of reasons, but the simplest one is that int doesn't have a base class. Inheritance schemes can't handle the built-in types, while templates can.

    There is a time and place for inheritance (e.g. type erasure is powered by it), but it shouldn't be used when templates are more appropriate.

    Deraynger> IMO your code falls under user-posted content

    Remember that I am not a user, I am a Microsoft employee. The company owns everything I write on company time.

    Deraynger> I use inline usually for tiny things (not even for calculations), but mainly just for setters/getters.

    "getters" and "setters" are two of my least favorite words - especially "setters". Most classes should provide abstractions higher than the level of individual data members. When you provide a "getter", you're essentially exposing the existence of a data member. That's two steps away from having a public data member, which is thoughtcrime. (Two steps, because it's read-only, and the data member doesn't have to physically exist - but to outside users looking at the interface, it may as well, which is almost as bad.) "Setters" are even worse, only one step away from public data members.

    The correct way to design a class is to think about the abstraction you want, devise an interface to provide that abstraction, and finally implement it. Sometimes you do end up with member functions that directly return data members without doing anything else (or more rarely, directly modify without doing anything else), but it should not be an explicit goal of your design. If it happens too often, that may be a sign that your abstractions are too low-level.

    Deraynger> Small question. If I use a for_each, can't I create a member function (preferably non-static) defined in the same class, or is it like a functor, where a seperate class/struct is necessary?

    Are you asking about the operation provided to for_each() that will be executed on each element of the range? That has to be a functor. However, there are lots of ways to provide functors: function pointers, function object classes, lambdas, and helpers. mem_fn() from <functional> is such a helper - it takes a pointer-to-member-function (PMF) and returns a functor, because the syntax to invoke functors (which is func(obj, args) or func(*ptr, args)) differs from the syntax to invoke PMFs (which is (obj.*pmf)(args) or (ptr->*pmf)(args)). You can pass mem_fn(&YourClass::YourMethod) to an STL algorithm, which will adapt the syntax for you (but not quite as efficiently as a lambda due to optimizer limitations). Note that mem_fn() is super smart - the returned functor can be executed on objects/references, raw pointers, and smart pointers, and it just works.

    Also note that mem_fun() and mem_fun_ref() (note the extra U) are C++98/03 tech, and are vastly inferior to TR1/C++0x mem_fn() (note: no U).

    STL> The problem with op<<() is that it mixes code and data.

    Deraynger> Can you explain it, I don't get it

    Consider: cout << "I have " << n << " " << animals;

    Now suppose that I want to internationalize my program. I can use Unicode, and load strings at runtime for different languages. But what if I have to deal with a language where the word order is different from English (e.g. putting the number after the "kittens" or "puppies" that I have, etc.)? The order is controlled by the *code*. That is not good.

    With Boost.Format, this looks like format("I have %1% %2%") % n % animals. Now the order is controlled by the *data*, the string passed to boost::format. A language with a different word order can simply load the string "blah blah %2% %1%" and that'll reverse the order of n and animals.

    Ivan> is it possible in C++(without adding something to the STL implementation) to add for example .sort() member function to vector?

    No. Other languages have a feature called "extension methods", allowing people to glue member functions onto a class without being that class's author. In general, I believe that it's an anti-feature.

    Ivan> Also I dont know why it isnt defined in the standard.

    This was one of Alexander Stepanov's greatest insights, and I believe I talked about it in the intro series.

    Remember that sort() isn't the only STL algorithm. There's something like over a hundred of them, and they usually come in pairs (default version, functor version). There are also lots of STL containers. Do you really want the STL to define X * Y member functions, where X is the number of algorithms and Y is the number of containers? Even worse, what if when writing a custom container, you had to define X member functions to wrap the algorithms? That is a recipe for interface bloat (look at std::string for an example of a bloaty interface, which Herb Sutter has explained in his books).

    With the STL's container-iterator-algorithm scheme, we end up with X + Y definitions, which is much better than X * Y.

    (Additionally, algorithms taking iterators are more general for two reasons. First, you can operate on subranges of a container, which isn't necessary that often, but when you want it, you really want it. Second, you can use custom iterators that do something special. back_inserter() is an example.)

    There's no essential difference between (hypothetically) v.sort() and (actually) sort(v.begin(), v.end()). One puts the container on the outside, and one on the inside. It is slightly verbose to have to say begin and end in pairs, but the correct way to address that is to wrap pairs of iterators as ranges (which will probably appear in the STL someday in some form).

    There's also nothing stopping you from writing container-based algorithm wrappers like sort(v). The STL could provide such things in a separate namespace, but it hasn't done so. (It would have to be a separate namespace, for an interesting reason. Putting iterator-based algorithms and container-based algorithms in the same namespace would lead to conflicts between sort(RanIt, RanIt) and sort(Container, Comparator) - with 1998-era tech there's no way to prevent conflicts there, and it wouldn't be especially fun even today.)

    aasss> C++ is beautiful in this and every other way.

    Heh, even I wouldn't say that (and I love C++ more than just about anyone). It's a big, complicated language and it has warts. But unlike everything else, it allows you to write extremely efficient code with a high level of abstraction in an elegant manner. You just have to be willing to tolerate low-level verbosity and clumsiness when judging elegance. For example, I think my pretty printer is elegantly structured.

    Ivan> P.S. there is a std::count, map::count, multimap::count

    The STL does make exceptions to its general rule of insulating algorithms from containers via iterators. This happens when algorithms can be implemented more efficiently (or at all) with "secret" knowledge of a container's internals. You've provided an excellent example. std::count() takes input iterators and is O(N), which is optimal in general (you have to look at every element in the range), even if the iterators are stronger, like bidi or random-access (it doesn't need and can't take advantage of those powers). However, the associative containers like multimap are special, because they're autosorted. multimap::count() is O(K + log N) where K is count()'s return value. This is much better than O(N). (If you're familiar with the basics of multimap's representation, as covered in the intro series, and the basics of computational complexity, then it should be obvious why it's O(K + log N).)

    Similarly, std::sort() takes random-access iterators. list's bidirectional iterators are too weak for that, but list::sort() works through node relinking.

    Masfo> As for next episodes, I would like to see piece on allocators, writing your own etc.

    I would like to do allocators when I can show off VC11's new trickery here.

  • STL> There is a time and place for inheritance (e.g. type erasure is powered by it), but it shouldn't be used when templates are more appropriate.

    Ok, so I'll see about rewriting everything Tongue Out. I have an idea for you or the authors, provided you/they have enough time: Rewrite the Design Patterns: Elements of Reusable Object-Oriented Software book using templates instead of inheritance Big Smile

    STL> Remember that I am not a user, I am a Microsoft employee. The company owns everything I write on company time.

    Yes, I asked with enough details in the e-mail. But Your ASCII tree etc. was probably written in your own time. Anyhow, then I'll just have to rewrite the code from scratch provided that I ever sell a product containing your code.

    Deraynger> I use inline usually for tiny things (not even for calculations), but mainly just for setters/getters.

    STL> The correct way to design a class is to think about the abstraction you want, devise an interface to provide that abstraction, and finally implement it. Sometimes you do end up with member functions that directly return data members without doing anything else (or more rarely, directly modify without doing anything else), but it should not be an explicit goal of your design. If it happens too often, that may be a sign that your abstractions are too low-level.

    As I mainly do OpenGL stuff, I do need a getter/setter for X, Y, Z etc., of course providing other functions too, based on those members. So it is a bit low level, but necessary IMO. Otherwise I agree that the functions should provide other things than just get/set. Other areas are when using inline is when checking e.g.

    inline bool AreVertsEmpty(void) { return myTriangleStripVerts.empty() && myTriangleVerts.empty(); }

    I don't like calling them float GetX( void ) const and void SetX( float ), so I write them like float X( void ) const and void X( float ).

    STL> [mem_fn] & [op<<]

    Ok, thanks for the details.

  • Knowing me knowing you, a-haaasss C++ rules and rocks!

    @STL Beauty is very subjective term. One likes when violins are playing and the other when he has dirty socks Wink. To me C++ is beautiful. In every way. To you may not be but that just you and me and the way we see world (C++). There is no reason to discuss it further, those are very subjective and personal opinions.

    And as for you loving C++ just about more than anyone? Bet to dissagree. You may think you do but that's just you, you cannot possibly know other people's feeling.

    Regards.

    P.S.

    Would you mind and confirm that what you've said about not having member sort in vector and reasons for that is practically the same what I've said in my previous post?

  • IvanIvan

    @STL
    First again tnx for the great answers. I know that it is getting old but it is really interesting to hear opinion on this stuff from the expert. Regarding the MxN problem(see I was listening carefully before, here you used X and Y :) ).
    why there arent templates based on container types. I mean why cant you define your own sort template that works on every container that meets certain requirement(has any iterator, has rand_access iterator)? That would avoid the MxN problem, I think.
    Regarding multimap count I was a bit confused about the K part but then I remembered that it is a (multi)map. BTW does this mean that mm.count() is faster than count(mm.begin(),mm.end()); I presume that you can specialize count based on the input container..., but if you dont it will go through entire range(again I presume).

  • Re: the code at 37:33, which looks something like this:

    if (i != e) {
      for (;;) {
        print(*i);
        if (++i != e) {
          sep();
        } else {
          break;
        }
      }
    }

    wouldn't it be simpler and more readable to write it thus:

    if (i != e) {
      print(*i);
      while (++i != e) {
        sep();
        print(*i);
      }
    }

    It's 7 instead of 10 lines, and has a proper loop condition instead of an infinite loop with a break, which makes it easier to reason about.

  • Ivan: check out Boost.Range. It allows you to do this:

    using namespace boost::range::algorithm; // can't remember exact namespace
    sort(some_vector);
    auto r = equal_range(some_vector, 10);
    for_each(r, [](int i) { std::cout << i << std::endl; });

  • Knowing me knowing you, a-haaasss C++ rules and rocks!

    @STL As I've said beauty is very subjective and it's better not to discuss it. But as you've started I will end it.

    What for you is ugly and vile for me is merely a quirk which makes me love it even more.

    Just like a birthmark. Most people associate them as something unwanted but this birthmark my wife has over her upper lip is something what makes her special, beautiful, unique and one of a kind.

    Some people will say that birthmarks are vile and ugly. I say they give character.

    Regards

  • IvanIvan

    @STL
    "We do that for other algorithms, as I explained in Advanced Part 2. But not std::count(). Note that multimap::count()'s trick requires knowledge of the tree structure, not just bidirectional iterators. Therefore it must be a member function."
    Isnt it possible to check if the input container is map? Again my understanding of TMP is pathetic, but cant you do something like
    "if container is map"
    return container.count(element)?
    I presume you cant because you can only get info about built in types(like is_integral) and not about STL containers. And thre is no is_RB_TreeLike in standard :( :)
    BTW compiler probably has enough info to print a warning about that, but I presume that it would be a bad business decision because you dont want people complaining that MS compiler gives warnings on legit code.
    regarding the next topics:
    I read something about
    "implicitly-generated move operations" being broken. If you find it interesting you could do a quick video on it(I presume it is not 50 min lecture material).

    Also regarding map and memory allocation(I know , "not again"). Are allocators powerful enough to "present" map in memory as one "vector of nodes" and memory allocation is just adding one node to the vector and pointers to the nodes are indexes in the vector. Ofc you would need a stack of freed nodes, and you would be unable to free the memory because of the fragmentation (unless you do an evil O(n) moving of nodes and restamping of idxs) . Again this is just my not so smart implementation, recently I did an implementation of node based structure that had all the deletes "in one place"(no inserts between first and last delete) in the program so I did it that way. Ofc not with allocators, I had std::vector of nodes. I presume it is impossible to this with allocators but if you can it would be a cool episode even before VC11 is no longer top secret.

  • STLSTL

    Ivan> I presume you cant because you can only get info about built in types(like is_integral) and not about STL containers.

    The STL can and does conspire with itself. However, given an iterator to an element, we can't find the parent container (without additional machinery that's expensive at runtime - we have such machinery to power our debug checks, as I explained in Advanced Part 3). Therefore, iterator-based algorithms can't perform trickery that requires access to the parent container.

    (Technically, we could detect multimap iterators, and walk upwards until we found the root node. However, calling multimap::count() would be more efficient, since it can just start at the root node.)

    > I read something about "implicitly-generated move operations" being broken.

    That's "rvalue references v3", which isn't implemented in VC10. Additionally, the problems there were corrected before the Final Draft International Standard was released.

    > Are allocators powerful enough to "present" map in memory as one "vector of nodes"

    std::map gets memory from its allocator (by default std::allocator). It doesn't care where the memory comes from, only that the allocator obeys the STL's requirements (which, for example, forbid "internal storage" allocators that return memory from "inside" themselves). This allows you to use a pool allocator if you want.

    Note that Windows (which ultimately powers std::allocator/new/malloc()) already does something very much like this. Their Low Fragmentation Heap is a bucket-based heap for small allocation sizes, such as tree nodes.

  • BTW STL, could you update your MinGW distro? New minor GCC and major Boost are out.

  • new2STLnew2STL xkcd.com

    Off-topic: Great news everybody! New Visual Studio User Voice, a place for you make suggestions and vote for what wish in VS.Next  Big Smile

    [edited7-24] Adding an interesting blog I found about the theme I suggested before (more insight on functional header) Some interesting usages of std::function, he touch std::function, std::shared_ptr and lambdas for an event dispatcher. The other posts on blog are interesting too (Pushing and pulling data in C++0x). Perhaps can inspire some usages like use C++11 on UI (adding here the back of Kenny Kerr in MSDN Magazine in Windows with C++) Wink

  • CharlesCharles Welcome Change

    ,ryanb wrote

    *snip*

    Yes please, thank you!  Smiley    Good stuff Charles ... keep it coming.

    And so it is: http://channel9.msdn.com/Shows/C9-GoingNative/GoingNative-0-Help-us-fly-this-plane-Some-modern-C-Meet-Ale-Contenti

    C

     

  • JonasNoJonasNo

    @STL

    We could need your input on this:
    http://channel9.msdn.com/Forums/TechOff/C0x-vs2010-question-please-tell-me-what-im-doing-wrong

    Any way to remove the overhead ?

  • STLSTL

    spons: Please ask me at home about things I do at home, and vice versa for work.

    JonasNo> Any way to remove the overhead ?

    Reading and understanding a long, unstructured thread takes a lot of time, and I'm very busy right now. If you could condense it down to a specific question, I could give you a specific answer.

  • @STL: OK i'll try.

    Goal: Create a template class that will execute a function / functor / lambda, with an arg, when leaving the scope.
    Problem: Storing the function / functor / lambda efficiently without overhead.

    Suggestion One:

    template<typename T>  
    class test_c { 
    public:  
        explicit test_c(T p, std::function<void(T)> func)  
            : m_p(p), m_Func(func) { 
        }      
           
        ~test_c(void) {         
            m_Func(m_p); 
        } 
           
        T get(void) const {         
            return m_p; 
        } 
       
    private:     
        T m_p; 
        const std::function<void(T)> m_Func; 
    };

     

    Suggestion Two:

    template < typename RESULT_TYPE, typename PARAMETER_TYPE >class functor_base_t {
        public:
            virtual ~functor_base_t () {
                //
            }
            virtual RESULT_TYPE operator () ( PARAMETER_TYPE ) = 0;
    };
    
    template < typename RESULT_TYPE, typename PARAMETER_TYPE, typename FUNCTOR >
    class functor_handler_t : public functor_base_t< RESULT_TYPE, PARAMETER_TYPE > {
        FUNCTOR m_functor;
        public:
            functor_handler_t ( FUNCTOR functor ) : m_functor( functor ) {
                //
            }
            virtual ~functor_handler_t () {
                //
            }
            virtual RESULT_TYPE operator () ( PARAMETER_TYPE parameter ) {
                return m_functor( parameter );
            }
    };
    
    template < typename TYPE >
    class test_c {
        private:
            typedef void RESULT_TYPE;
            typedef TYPE PARAMETER_TYPE;
    
            PARAMETER_TYPE m_parameter;
            std::shared_ptr< functor_base_t< RESULT_TYPE, PARAMETER_TYPE > > m_functor_handler;
        public:
            template < typename FUNCTOR >
            explicit test_c ( PARAMETER_TYPE parameter, FUNCTOR functor ) :
                m_parameter( parameter ),
                m_functor_handler(
                    new functor_handler_t<
                        RESULT_TYPE,
                        PARAMETER_TYPE,
                        FUNCTOR
                    >( functor )
                )
            {
                //
            }
            ~test_c () {
                ( *m_functor_handler )( m_parameter );
            }
            PARAMETER_TYPE const & get () const {
                return m_parameter;
            }
    };

    Usage example:

    inline void normal_func ( int p ) {
        cout << "p: " << p << endl;
    }
    
    struct normal_struct_func {
        inline void operator() (int p) const {
            cout << "p: " << p << endl;
        }
    };
    
    template< typename T, typename Function >
    inline void test_f ( T p, Function func ) {
        func( p );
    }
    
    int main () {
        // test_f tests
        test_f( 11, [] ( int p ) { cout << "p: " << p << endl; } );
        test_f( 22, normal_func );
        test_f( 33, normal_struct_func() );
    
        // test_c tests
        test_c< int > tc1( 11, [] ( int p ) { cout << "p: " << p << endl; } );
        test_c< int > tc2( 22, normal_func );
        test_c< int > tc3( 33, normal_struct_func() );
    
        test_c< int * > tc4(
            new int,
            [] ( int * ptr ) {
                cout << "tc4: " << *ptr << endl;
                delete ptr;
            }
        );
        *tc4.get() = 44;
        test_c< int * > tc5(
            new int[ 3 ],
            [] ( int * arr ) {
                int const * i = &arr[ 0 ];
                int const * end = &arr[ 3 ];
                cout << "tc5: { ";
                if ( i != end ) {
                    cout << *i;
                    for ( ++i ; i != end; ++i )
                        cout << ", " << *i;
                }
                cout << " }" << endl;
                delete[] arr;
            }
        );
        tc5.get()[ 0 ] = 55;
        tc5.get()[ 1 ] = 56;
        tc5.get()[ 2 ] = 57;
    
    #define scoped test_c
    
        // 1:
        scoped<HMODULE> dll(LoadLibraryA("kernel32.dll"), [](HMODULE h){FreeLibrary(h);});
    
        // 2:
        scoped<int*> ptr2(new int, [](int *p){delete p;});
    
        // 3:
        scoped<int*> ptr3(new int[100], [](int *p){delete[] p;});
    
        // 4:
        scoped<int> ptr4(1974, [](int p){ cout << p << endl;});
    
        return 0;
    }
     

     

    Both suggestions have big overhead.

    So is there a way to minimize or remove the overhead ?

    Like a template that would work with the compiler and inline everything efficiently (as i should)

    Like in this example:

    inline void normal_function(int v) {
        cout << "normal_function: " << v << endl;
    }
    
    template <typename Function>
    class sop {
        Function f_;
    public:
        sop(Function fun) : f_(fun) {}
        ~sop() {
            f_();
        }
    };
    
    void t_sop()
    {
        auto l = [](){
            normal_function(123);
        };
        sop<decltype(l)> s(l);
    }
    
    int main()
    {
        t_sop();
        return 0;
    }
    
    Generated code in win32 release mode:
        t_sop();
    00291000  mov         eax,dword ptr [__imp_std::endl (292044h)]  
    00291005  mov         ecx,dword ptr [__imp_std::cout (292068h)]  
    0029100B  push        eax  
    0029100C  push        7Bh  
    0029100E  push        offset string "normal_function: " (292114h)  
    00291013  push        ecx  
    00291014  call        std::operator<<<std::char_traits<char> > (2910F0h)  
    00291019  add         esp,8  
    0029101C  mov         ecx,eax  
    0029101E  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (292050h)]  
    00291024  mov         ecx,eax  
    00291026  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (29204Ch)]  
    
     

     

    The main problem that cause the overhead is storing the function / functor / lambda.
    Lambdas are difficult to store efficiently for later use without 'auto'.
    auto so you know can't be use like this:

    class sop {
        auto f_; // Error: auto must be initialized
    public:
        template <typename Function>
        sop(Function fun) : f_(fun) {}
        ~sop() {
            f_();
        }
    };

    In my opinion i think the above code should work because auto is initialized in the constructor,.

    Anyway there you go. 

  • STLSTL

    JonasNo: Oh goody, something I've already written a solution for.

    Note that Suggestion One is more efficient than Suggestion Two, because std::function implements the Small Functor Optimization - resulting in zero dynamic memory allocations instead of two (you aren't using make_shared) for sufficiently small functors.

    The tricky thing about doing this (usually referred to as a "scope guard") is that in order to provide automatic rollback in the presence of exceptions, the machinery shouldn't throw exceptions of its own.

    So here's an E-mail that I sent to our internal C++ mailing list back in May:

    Here's ScopeWarden, which has the following properties:
     
    1. It stores a single raw pointer.
     
    2. It's non-copyable and non-movable.
     
    3. It doesn't copy or move the functor it's going to execute.
     
    4. It never emits exceptions.  Accordingly, it's marked __declspec(nothrow) to make the optimizer happier.
     
    5. It can't be constructed from a temporary functor, preventing obvious badness.
     
    6. Its helper macro, SCOPE_WARDEN(name, guts; guts; guts; ); , is template-friendly (as proven by map<int, string> below) thanks to variadic macros.
     
    7. SCOPE_WARDEN stamps out a lambda with a reference capture-default, [&], which means that it can access anything in its enclosing scope without performing a copy, and can both observe mutations and perform mutations.
     
    8. SCOPE_WARDEN even avoids constructing identifiers with unintentional double underscores.  The helper lambda for a ScopeWarden g2 is xxg2xx.

    C:\Temp>type meow.cpp
    #include <exception> // for std::terminate()
    #include <memory>    // for std::addressof()
    
    template <typename F> class ScopeWarden {
    public:
        explicit __declspec(nothrow) ScopeWarden(F& f) : m_p(std::addressof(f)) { }
    
        void __declspec(nothrow) dismiss() {
            m_p = nullptr;
        }
    
        __declspec(nothrow) ~ScopeWarden() {
            if (m_p) {
                try {
                    (*m_p)();
                } catch (...) {
                    std::terminate();
                }
            }
        }
    
    private:
        F * m_p;
    
        explicit ScopeWarden(F&&);
        ScopeWarden(const ScopeWarden&);
        ScopeWarden& operator=(const ScopeWarden&);
    };
    
    #define SCOPE_WARDEN(NAME, ...)                \
        auto xx##NAME##xx = [&]() { __VA_ARGS__ }; \
        ScopeWarden<decltype(xx##NAME##xx)> NAME(xx##NAME##xx)
    
    
    #include <iostream>  // for std::cout
    #include <map>       // for std::map
    #include <ostream>   // for std::endl
    #include <stdexcept> // for std::runtime_error
    #include <string>    // for std::string
    #include <utility>   // for std::pair and std::make_pair()
    #include <vector>    // for std::vector
    using namespace std;
    
    void foo() {
        int x = 9999;
    
        vector<pair<int, string>> v;
        v.push_back(make_pair(20, "twenty"));
        v.push_back(make_pair(50, "fifty"));
        v.push_back(make_pair(10, "ten"));
        v.push_back(make_pair(40, "forty"));
        v.push_back(make_pair(30, "thirty"));
    
        SCOPE_WARDEN(g0, cout << "cute" << endl; );
        SCOPE_WARDEN(g1, cout << "fluffy" << endl; );
        SCOPE_WARDEN(g2, cout << "kittens" << endl; );
        SCOPE_WARDEN(g3, cout << "ZOMBIES" << endl; );
        SCOPE_WARDEN(g4, cout << "g4: " << x << endl; );
        SCOPE_WARDEN(g5,
            cout << "g5: " << x << endl;
            ++x;
        );
        SCOPE_WARDEN(g6,
            map<int, string> m(v.begin(), v.end());
    
            for (auto i = m.begin(); i != m.end(); ++i) {
                cout << "(" << i->first << ", " << i->second << ")" << endl;
            }
        );
    
        g3.dismiss();
    
        x = 1729;
    
        cout << "Throwing exception." << endl;
    
        throw runtime_error("Too many puppies!");
    }
    
    int main() {
        try {
            foo();
        } catch (const runtime_error& e) {
            cout << "Caught exception: " << e.what() << endl;
        }
    }
    
    C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp
    meow.cpp
    
    C:\Temp>meow
    Throwing exception.
    (10, ten)
    (20, twenty)
    (30, thirty)
    (40, forty)
    (50, fifty)
    g5: 1729
    g4: 1730
    kittens
    fluffy
    cute
    Caught exception: Too many puppies!

    I believe that this code is free of bugs, easy to use, and hard to misuse (not impossible, of course).  In particular, because SCOPE_WARDEN doesn't throw, this sort of code is just fine:

    do_X();
    SCOPE_WARDEN(g0, undo_X(); );
    do_Y();
    g0.dismiss();
    

  • @STL: Thanks for the feedback and information.
    Sounds like that internal C++ mailing list got some juicy stuff, i wish i had read access to it Wink

    >Note that Suggestion One is more efficient than Suggestion Two, because std::function
    > implements the Small Functor Optimization 

    How do you correctly make use of make_shared, i get strange errors when trying to use it.

    Nice solution. Personally i do not fancy marcos.

    I would have preferred something like this: (pseudo code)

     auto s1 = // if you want to control it
    scoped<int>(123, [](int v){cout << v << endl; );
    scoped<int>(new int(123), [](int *v){
        cout << *v << endl;
        delete v;
    });
    s1.dismiss(); 
    //etc...
    

    Somehow it looks better.

    So it's not possible to do this without overhead ?
    Is the compiler not smart enough to see whats going on and inline it, that's sad. 

  • STLSTL

    > Sounds like that internal C++ mailing list got some juicy stuff, i wish i had read access to it

    http://careers.microsoft.com

    > How do you correctly make use of make_shared, i get strange errors when trying to use it.

    These definitions are equivalent:

    shared_ptr<T> sp(new T(zero or more args));
    auto sp = make_shared<T>(zero or more args);

    Except that make_shared is (1) significantly more efficient, (2) less verbose when T is 3+ characters, (3) invulnerable to the "unnamed shared_ptr leak".

    > Nice solution. Personally i do not fancy marcos.

    The SCOPE_WARDEN macro is for convenience, but ScopeWarden can be used directly.

    > So it's not possible to do this without overhead ?
    > Is the compiler not smart enough to see whats going on and inline it, that's sad.

    I don't know what that usage example means.

  • @STL:
    > http://careers.microsoft.com
    awwh! 

     

    > I don't know what that usage example means.

    I was trying to demonstrate how i would have liked the scoped class usage syntax to look like.
    See function "void test()" in code below 

     

    While your class ScopeWarden looks very nice can it be done i a different way with the same efficiency ?
    That is with the usage syntax i would like it to be.

    Ok lets begin from beginning take this example code:

    #include <iostream>
    
    using namespace std;
    
    class scoped_func_base {
        virtual void _Destroy() = 0;
        virtual void _Destroy_this() = 0;
    protected:
        scoped_func_base() {}
    public:
        virtual ~scoped_func_base() {} // ensure that derived classes can be destroyed properly
    
        void _Des() {
            _Destroy();
            _Destroy_this();
        }
    };
    
    template <typename Type>
    class scoped_func_std : public scoped_func_base {
        Type *m_ptr;
    
        virtual void _Destroy() {
            delete m_ptr;
        }
    
        virtual void _Destroy_this() {
            delete this;
        }
    public:
        scoped_func_std(Type *ptr) : scoped_func_base(), m_ptr(ptr) {}
    };
    
    template <typename Type, typename Func>
    class scoped_func_custom : public scoped_func_base {
        Type *m_ptr;
        Func m_func;
    
        virtual void _Destroy() {
            m_func(m_ptr);
        }
    
        virtual void _Destroy_this() {
            delete this;
        }
    public:
        scoped_func_custom(Type *ptr, Func f) : scoped_func_base(), m_ptr(ptr), m_func(f) {}
    };
    
    template <typename Type>
    class scoped_base {
        Type *m_ptr;
        scoped_func_base *m_func_base;
    public:
        scoped_base() : m_ptr(nullptr), m_func_base(nullptr) {}
    
        void reset_base(Type *ptr, scoped_func_base *other_func_base) {
            if (m_func_base != nullptr)
                m_func_base->_Des();
            m_func_base = other_func_base;
            m_ptr = ptr;
        }
    
        void _Des() {
            if (m_func_base != nullptr)
                m_func_base->_Des();
        }
    };
    
    template <typename Type>
    class scoped : scoped_base<Type> {
        template <typename SecType>
        void reset(SecType *ptr) {
            reset_common(ptr, new scoped_func_std<Type>(ptr)); // NOTE: Skipping failure code
        }
    
        template <typename SecType, typename Func>
        void reset(SecType *ptr, Func f) {
            reset_common(ptr, new scoped_func_custom<Type, Func>(ptr, f)); // NOTE: Skipping failure code
        }
    public:
        scoped() {}
    
        template <typename SecType, typename Func>
        scoped(SecType *ptr, Func f) {
            reset(ptr, f);
        }
    
        ~scoped() {
            this->_Des();
        }
    
        template <typename SecType>
        void reset_common(SecType *ptr, scoped_func_base *func_base) {
            this->reset_base(ptr, func_base);
        }
    };
    
    inline void func(int *p) {
        cout << "func: " << *p << endl;
        delete p;
    }
    
    struct functor {
        inline void operator()(int *p) const {
            cout << "functor: " << *p << endl;
            delete p;
        }
    };
    
    void test() {
        // Mmmm this is how it should look like in my opinion.
        scoped<int> s1(new int(123), &func);
        scoped<int> s2(new int(456), functor());
        scoped<int> s3(new int(789), [](int *p) {
            cout << "lambda: " << *p << endl;
            delete p;
        });
    }
    
    int main()
    {
        test();
        cout << "done" << endl;
    }
    

     

    Is there any way to remove this dynamic allocation in scoped::reset:
    "reset_common(ptr, new scoped_func_...<...>(...)); " 

    This dynamic allocation have been bugging me for some time and i can't remove it. C++ rules doesn't seem to allow me to do it Sad

    You will always use a function with 'scoped' and with that information you should be able to do some template magic without this dynamic allocation trick to store the function for later use.

     

  • STLSTL

    > I was trying to demonstrate how i would have liked the scoped class usage syntax to look like.

    It looks like you want unique_ptr.

    What scope guards (including ScopeWarden) do is remember an arbitrary action to be performed in the event of their premature destruction (and they're dismissable so they do nothing if they reach their full life expectancy). They're most useful for achieving the strong guarantee (transaction semantics) when copy-modify-swap isn't an option. As you perform actions, you create scope guards to exactly undo those actions in the event of an exception. If everything succeeds, you dismiss the scope guards, committing all of your actions.

    Scope guards can be used for resource management (I did that with Boost in Advanced Part 5, when I didn't want to write wrappers for Windows' bcrypt.h), but dedicated resource managers like unique_ptr, shared_ptr, and vector should be used whenever possible.

    > While your class ScopeWarden looks very nice can it be done i a different way with the same efficiency ?

    ScopeWarden avoids both dynamic memory allocation and virtuals. (Remember that virtuals inhibit inlining, except with very advanced compilers, and even then the stars must align perfectly.)

    > Is there any way to remove this dynamic allocation in scoped::reset:

    You can with the Small Functor Optimization (keep a local buffer, placement-new your object into it), but it's rather tricky machinery.

    > You will always use a function with 'scoped' and with that information you should be able to do some
    > template magic without this dynamic allocation trick to store the function for later use.

    If you know you're going to have a function *pointer*, then just store the function pointer. You need placement new trickery for arbitrary functors.

  • I did thought of unique_ptr but its not general enough.


    For example it can't do this:

    unique_ptr<HMODULE> lib(LoadLibrary(_T("ntdll.dll")), [](HMODULE hHandle) {    FreeLibrary(hHandle);
    });
    if (!lib)
        return <fail code>;
     

     

    Or this:

    // Clear ex. sensitive memory on scope exit
    // pseudo code
    unique_ptr secureMemRelease([](PVOID  ptr, size_t s) {
    SecureZeroMemory( ptr, s );
    delete [] ptr;
    }(some_memptr, size));
    
    // alternative way 
    unique_ptr secureMemRelease([]() {
    SecureZeroMemory( some_memptr, size );
    size = 0;
    delete [] some_memptr;
    });
    


    Yes you can enclose the ptr in a class and pass it to unique_ptr but if you're only going to use it once that extra work and messes with locality etc... 


    I did see  Advanced Part 5. But as i've said i don't like macros and the way boost does it is impossible to understand. I've tried to understand that macro but i got lost every time in the macro jungle Perplexed oh and it's ugly and sort of unsafe if you compare it to say your ScopeWarden as far as i know.

    I'm having a hard time finding information on  Small Functor Optimization. Sad 

    >If you know you're going to have a function *pointer*, then just store the function pointer.

    When i said function i meant (function, functor and lambda) We need a general group name for these :/

    > You need placement new trickery for arbitrary functors. 
    Does this include lambdas too ?

    That's sad news indeed, you would think c++0x would have fixed this issue so new trickery wasn't needed. Sad

    So now what, got any ideas or suggestions ? 

  • IvanIvan

    autoLOL, I was looking at the STL's code and I felt like an idiot, because I couldnt understand couple of lines ... then I noticed the horizontal bar. xD
    @ Charles
    One business question that you probably cant answer, but Im curious in case you can. AFAIK VS cpp regex machinery has a fair amount of bugs. Was it ever considered to buy the boost regex code(because it is so old and part of the boost that has high standards I presume it is pretty much bug free). Also that would be a huge boost for boost community IMHO. :)
    Regarding Boost would it be against the C9 rules if you would kidnap autors of some of the most used boost libs and asked them to do a couple of lectures on their library. I know boostcon has videos but they are relatively poor sound quality and relatively short.
    P.S. First going native show had some flying code that was too simple, please use some epic STL's stuff for the ep2. :D
    @ Charles && STL
    I like the new Native show(again I found the PR parts about fresh CPP a bit boring, but it was first show and a very good intro for non cpp people IMHO), but I hope that STL will continue with this series. Native show is OK as general talk about, present feature in couple of mins, but I really really like STLs "deep" lectures.

    @ STL
    1) I know that you mentioned many times that you had a bunch of free time :P , so is there any chance to that you might review (some parts ofc, not entire manual) of the:
    "Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms"
    http://www.agner.org/optimize/#manuals
    I know that it is a strange request, but manual seems very interesting and I would feel much better following if they have your stamp of approval .
    2)I dont know if you remember your FizzBuzz suggestion(do it with templates). Im not asking for a solution(please please dont post the solution, I hate when I cant solve something and then I found out solution before I had time to figure it out) but could you explain the printing part of it. I mean AFAIK you cant cout during compilation. wikibook example for prime numbers uses function that is called at runtime:
    http://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming#History_of_TMP
    3)recently I realized how my knowledge is fragile. I thought that i understand (theoretically ofc) implementation of all STL containers, but then i realized that i dont understand how dequeue is done.
    I presume that it is like a vector with half of the reserved space before begin() and half of the reserved space after the end(). Am I right?
    Regarding topics for the future shows:
    1. you could do more on TMP but please explain slowly because I presume that most people(including me) have only basic understanding of it and arent familiar with all the tricks.
    2. Ofc doing something like "Modern CPP: why very good Cpp programmer from 2001 needs to update himself". could be useful:) Just please keep it hardcore :)and specific without generic :P PR stuff.
    3. Random problem solving using modern CPP is cool.
    eg http://en.wikipedia.org/wiki/Directed_acyclic_word_graph



    P.S. sorry for the long comment

  • IvanIvan

    P.P.S
    Am I looking at the wrong place or
    #include <memory> // for std::addressof()
    is not documented at msdn
    http://msdn.microsoft.com/en-us/library/96xh3xxe.aspx

  • @Ivan: "#include <memory> // for std::addressof() is not documented at msdn"

    My guess is that addressof is a C++0x function and technically it haven't been finalized / released yet so i'm guessing that's why its not in msdn docs.

    I would suggest you use the c++ working draft for stl stuff: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf

    Even so msdn docs is infamous for its poor documentation quality and correctness. You should take what it say with a grain of salt and verify with other sources.

  • STLSTL

    Jonas_No: unique_ptr wants to store a pointer, so it can't work with things that aren't pointers (e.g. arbitrary handles), but your
    SecureZeroMemory example can easily be achieved by using custom deleters with unique_ptr.

    Jonas_No> I'm having a hard time finding information on  Small Functor Optimization.

    It's an STL implementation detail.

    Jonas_No> When i said function i meant (function, functor and lambda) We need a general group name for these :/

    Different authors use different terminology, but I use "functor" to mean "anything callable" ("arbitrary functor" if I want to be very precise), "function object" to mean "class overloading op()" ("function object of class type" to be very precise), and "function" to mean "real function".

    STL> You need placement new trickery for arbitrary functors.

    Jonas_No> Does this include lambdas too ?

    Yes. Lambdas with captures can contain an arbitrary amount of arbitrary state. Only stateless lambdas are convertible (in VC11) to function pointers.

    Jonas_No> That's sad news indeed, you would think c++0x would have fixed this issue so new trickery wasn't needed.

    There is no issue to fix, as far as I can tell.

    Jonas_No> So now what, got any ideas or suggestions ?

    Use ScopeWarden.

    Ivan> so is there any chance to that you might review

    No time, sorry.

    Ivan> could you explain the printing part of it.

    Oh, you can use cout (or printf, or puts) to print the fizzing and the buzzing. The trick is to avoid runtime testing, runtime iteration, and runtime recursion.

    Ivan> i realized that i dont understand how dequeue is done.

    deque is magic - probably the most magical STL container.

    It stores elements in contiguous blocks. Unlike vector, which is a single contiguous block of memory, deque can contain multiple blocks. (Therefore, as far as users are concerned, deque does NOT provide the contiguity guarantee that vector and string have.) There can be 1 element in each block, or more (e.g. 16). deque has a "map" of pointers to blocks, to keep track of where they all are (this is essentially a vector of pointers, not a std::map).

    When you push_front or push_back, the deque can allocate new blocks to store elements. From time to time, it has to reallocate its "map", which is why deque has the strangest invalidation guarantee in the whole STL - push_front and push_back can invalidate iterators, but they preserve pointers and references to elements (because the underlying blocks don't move around).

    deque also has some truly complicated machinery to handle paired push_backs and pop_fronts, etc. for efficiency. (So complicated, it was broken in VC10. We've fixed that in VC11.)

  • IvanIvan

    @ STL super interesting answers esp deque(except the part about being the most magical container, RB_Tree based ones are my favs <3 :))... I know, I know it is just because I ask great questions :P
    But seriously this deque really intrigues me.
    a) i dont understand the last paragraph. Can you explain it a bit. If the explanation is to complicated can you just provide a example of program that uses "paired push_backs and pop_fronts". And I dont understand how can an "old" container be broken. Did you reimplemented it in VC10?
    b) my model of the world is crumbling :)
    how can container that has RA access (AFAIK) not weaker one like BID have nonsequential implementation. I know that it can have amortized O(1) but that implementation doesnt fee like amortized O(1). I know that it doesnt have to be "one operation" to be O(1)(in fact vector implementation that takes 73 seconds to return single element for any size of the array is O(1) :)) but that vector of pointers just feels strange. :)
    And ofc I have other questions about the vector of pointers, how is dq[74656] translated to same internal block and the position in the block, but it is too long to explain I presume.

  • STLSTL

    > except the part about being the most magical container, RB_Tree based ones are my favs <3

    Red-black trees appear in textbooks, though. I can't name any other language/library that has a deque (specifically one with the trick of being random-access).

    > i dont understand the last paragraph. Can you explain it a bit.

    Imagine a program that repeatedly calls push_back(), pop_front(), push_back(), pop_front(). It would be lame if the deque had to constantly allocate new blocks (because one end of the deque is growing) and deallocate old blocks (because the other end of the deque is shrinking). Instead, the deque "wraps around", reusing its blocks. It needs to allocate new blocks only when the overall size of the deque is constantly expanding.

    > If the explanation is to complicated can you just provide a example of program that uses "paired push_backs and pop_fronts".

    Here's my regression test, which fails with VC10 SP1 and passes with VC11.

    C:\Temp>type meow.cpp
    #include <stdio.h>
    #include <deque>
    #include <vector>
    using namespace std;
    
    int main() {
        deque<int> d;
    
        for (int n = 0; n < 1000; ++n) {
            d.push_back(n);
    
            if (d.size() < 26) {
                continue;
            }
    
            vector<deque<int>::iterator> v;
    
            for (deque<int>::iterator i = d.begin() + 1; i != d.end(); ++i) {
                v.push_back(i);
            }
    
            d.pop_front();
    
            for (deque<int>::size_type i = 0; i < d.size(); ++i) {
                if (d[i] != *v[i]) {
                    puts("FAIL");
                }
            }
        }
    
        puts("PASS");
    }
    
    C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp
    meow.cpp
    
    C:\Temp>meow
    ---------------------------
    Microsoft Visual C++ Debug Library
    ---------------------------
    Debug Assertion Failed!
    
    Program: C:\Temp\meow.exe
    File: C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\deque
    Line: 338
    
    Expression: deque iterator not dereferencable
    
    For information on how your program can cause an assertion
    failure, see the Visual C++ documentation on asserts.
    
    (Press Retry to debug the application)
    ---------------------------
    Abort   Retry   Ignore
    ---------------------------
    

    > And I dont understand how can an "old" container be broken. Did you reimplemented it in VC10?

    My notes say that it was actually broken in VC8 with the addition of _HAS_ITERATOR_DEBUGGING.

    This was Dev10#860421/Connect#533131:

    http://connect.microsoft.com/VisualStudio/feedback/details/533131/bug-in-std-deque-non-conforming-invalidation-of-iterators-after-pop-front

    > how can container that has RA access (AFAIK) not weaker one like BID have nonsequential implementation.

    Loosely speaking, given an index, the deque figures out which block that index corresponds to (with a division), then which element in the block is needed (with a modulo). This is true O(1).

  • IvanIvan

    @ STL
    so if I understand correctly deque has n(variable ofc) blocks of same size(same size so that it can do division to get the block from the idx( like when finding an row in a axb matrix from 1D idx , but this is not continuous memory ofc so "map" of pointers ), and also uses modulo trick(it also (I presume) knows where in the block is the "start" )to achieve circularity (for eg(numbers are idxs): 3 4 5 ...(free space)...0("start") 1 2 )to make the full use of all but the last allocated block.
    Again this is kind of "trivia"(although I remember u saying something like "most of the time you dont need deque but when you need it, YOU NEED IT" :)) but I find it really interesting, if nothing else it made me think about the vector vs deque. Vector "cant" allocate +10 or +47 elements because of the copying(all elements must be continuous in the mem). Deque can, so it can use the trick that you mentioned.
    Again this is AFAIK from what I have understood from your comments, lets hope that I'm right. :)

  • new2STLnew2STL xkcd.com

    @Ivan: I like the definition on here and the articles about memory management here (The Visual C++ Weekly). Vector is the abstraction of an array with a plus you can grow it if needed (efficiency on only one side for insertion and removes) , the contiguous guaranty of vector make it able o use even on C function that waits pointer and size.

    Deque are good when you need insertions and removes frequently and efficiently like a vector on both ends (that article about memory management: double stack), one could use deque for jitter buffers (perhaps not the best example) with consumer and producers on a non-reliable line where you can use a reasonable 'buffer' length but cause bursts or starves the size could vary greatly.

    >Vector "cant" allocate +10 or +47 elements because of the copying

    It can, you can create a vector with a chunk increase of 10, so it will be prepared and changes bellow this threshold will be efficient, but if you insert 47 will had cost (worst if do it frequently). Even when you use a deque you need measure the correct needs of your application Wink

    @STL: this cool discussion sure are equivalent to an episode itself! We gained an extra before the next video Tongue Out

  • STLSTL

    Ivan: Yep, that's right.

    Ivan> I remember u saying something like "most of the time you dont need deque but when you need it, YOU NEED IT"

    That is something I would say!

    new2STL> It can, you can create a vector with a chunk increase of 10

    Nope, that would trigger quadratic complexity, violating vector's complexity guarantees. Calling vector::push_back() N times must be O(N), with each push_back() being amortized O(1). Only geometric/exponential reallocation (x1.5, x2, etc.) provides the necessary complexity. arithmetic/linear reallocation (+10, +1024, etc.) does not.

    new2STL> this cool discussion sure are equivalent to an episode itself! We gained an extra before the next video

    :->

    I've been busy and don't have anything prepared yet, hence the long gap. I'll do Part 7 when I think of something, or when I can show off VC11.

  • IvanIvan

    @STL
    can you tell us if this solution is the correct fizzbuzz solution
    (I took the code from http://codegolf.stackexchange.com/questions/23/fizz-buzz-in-tmp and modified it slightly when it wasnt working, probably i could make it not take 3 ints as template args, but if that is the only problem then it is not a problem xD ):

    #include <cstdio>
    #include <string>
    #include <iostream>
    using namespace std;
    template<int N, int m3, int m5>
    struct fizzbuzz_print {
    static void print() {
    cout << N << '\n';
    }
    };

    template<int N, int m5>
    struct fizzbuzz_print<N, 0, m5> {
    static void print() {
    cout << "fizz\n";
    }
    };

    template<int N, int m3>
    struct fizzbuzz_print<N, m3, 0> {
    static void print() {
    cout << "buzz\n";
    }
    };

    template<int N>
    struct fizzbuzz_print<N, 0, 0> {
    static void print() {
    cout << "fizzbuzz\n";
    }
    };

    template<int N,int m3, int m5>
    struct fizzbuzz:public fizzbuzz<N-1,(N-1)%3,(N-1)%5> {
    fizzbuzz<N,m3,m5>() {
    fizzbuzz_print<N,N%3,N%5>::print();
    }
    };

    template<>
    struct fizzbuzz<1,1,1> {
    fizzbuzz<1,1%3,1%5>() {
    fizzbuzz_print<1,1,1>::print();
    }
    };

    int main() {
    fizzbuzz<100,100%3,100%5> t;
    }


    Regarding part 7- I think that people understand that you are very busy, but if it means something(if you are thinking that nobody cares if you make video or not) please know that I(and a bunch of other people I presume) found these videos very valuable.

  • STLSTL

    > can you tell us if this solution is the correct fizzbuzz solution

    Yes, that's correct. At a minimum, I'd suggest default template arguments to make main() look nicer. Always try to make usage simple and resistant to error.

    Now, if you want to really have fun, try it with Boost.Preprocessor.

    > I(and a bunch of other people I presume) found these videos very valuable.

    Thanks. :->

  • IvanIvan

    First sorry it took me so long to say than you(I was kind of busy :)). Secondly, thank you. :)
    Regarding Boost.Peporcessor -it is out of my league. Only for now I hope.
    Also do you consider it "really useful" or "cool" or both?
    1. BTW Stephen do you have opinion about this article:
    http://cpptruths.blogspot.com/2011/07/want-speed-use-constexpr-meta.html
    Don't be scared to click, it is short one.
    1 b)do you know why it isnt possible (AFAIK) for example to calculate something during compile time using regular functions, not TMP.
    For example I want to have an vector or array of sqrts. It would be much nicer if I could write something like const vector<int> roots=sqrt({0,1,2,3,4,5,6,7,8,9,10});(sqrt is idempotent function ofc)
    and have it calculated at the compiler at the run time. Do you know why is that not possible, is it a bad idea, or just very hard to do it withing c++ syntax rules,or proving idempotence is "hard", or...

  • Brian GoadBrian Goad

    Hi. Not sure if this is the right place to ask this question, but here goes. I am using vector in C++/CLI, I have: static vector<CPerson^>^ people = gcnew vector<CPerson^>();. I am adding people to the vector at runtime to get people[0], people[1], etc. I give the user the option to delete a person (people[n]) if he/she would like. My question: How would I go about doing this? I tried people->erase(people->begin());, among other things. I appreciate your help. Thank you very much. Brian.

  • Brian GoadBrian Goad

    Nevermind, I think I found out what is wrong. When I erased people[0], I thought all the other elements "moved up" in the vector. I was trying to use people[0] elsewhere.

  • IvanIvan

    first it is not the right place, secondly for the usage you want you should learn the differences between STL containers. vector doesn't look right for this task, I think list or set is better choice.
    Again wrong place, but if you like you should check out STL's video where he mentions remove erase idiom, or just look it up on wikipedia. Please note that erase remove idiom has bad performance if you remove just one element, then again just one element, ...

  • MattMatt

    @STL - joined the party a bit late, I'm working through all of the videos now. Your style of teaching is first class as is your mastery of the subject. I hope to see more videos from you on C++.

    Some suggestions for future episodes;

    a) exceptions - when to use and when not to. also performance details
    b) design patterns - intro into modern design patterns and which to use
    c) intro into concurrency with Boost or c++11
    d) compiler optimisations, inlining, STV vectorisation etc

  • MattMatt

    ^^^^typo above^^^^

    meant to say inlining STL and STL vectorisation.

  • IvanIvan

    @STL
    VS11 preview is out, can you show us some stuff. :)
    P.S. I hope STL is fine, I presume that he was a bit sad to hear about no var templates in VS11 :)

  • STLSTL

    Ivan> Regarding Boost.Peporcessor -it is out of my league. Only for now I hope. Also do you consider it "really useful" or "cool" or both?

    It's interesting. I haven't used it in real projects yet, but there's one place (stamping out a bunch of typedefs) where I believe it would be useful.

    Matt> @STL - joined the party a bit late, I'm working through all of the videos now. Your style of teaching is first class as is your mastery of the subject. I hope to see more videos from you on C++.

    Thanks! I'm very busy with VC11 right now, but I'm definitely planning to do more videos in the future.

    Matt> a) exceptions - when to use and when not to. also performance details

    This is probably worth a video (although I view it as more Core Language than Standard Library).

    Matt> b) design patterns - intro into modern design patterns and which to use

    I am actually not a fan of Design Patterns. I've read the book, and I didn't think it was that useful. I think in terms of C++ idioms instead (e.g. iterators, functors, non-virtual interfaces).

    Matt> c) intro into concurrency with Boost or c++11

    Definitely on the agenda. First we need to squash a bunch of bugs, though.

    Matt> d) compiler optimisations, inlining, STV vectorisation etc

    I'm not really the right person for this one - the compiler back-end is mostly a black box to me. C++ goes in, assembly comes out. I know "stuff", but not at an extreme level of detail - mostly what I need to get the STL to generate reasonably performant code.

    (For example, vector's empty() is more efficient than size() == 0, so in VC11 I audited <vector> to internally call empty() whenever possible.)

    Ivan> VS11 preview is out, can you show us some stuff. Smiley

    I'd like to when I get some time. Plus I'd have to get VC11's IDE set up.

    Ivan> P.S. I hope STL is fine, I presume that he was a bit sad to hear about no var templates in VS11 Smiley

    I heard about it long ago - as the compiler's first and best customer, I hear about their feature decisions long before everyone else. Variadic templates would certainly make my life much easier, but we have a new scheme for faking them (as I alluded to in Part 6) and I believe that it is better than the old scheme and already paying dividends.

  • @STL: I understand what you mean, but I think it's a good way to communicate intent. I still think you should do some STL videos regarding generally used "Patterns", I took ages to google, and find the right wording, to find CRTP. I think those are basics that anyone writing C++ should know. I would have written my code completely differently if I had known that. Especially I use the patterns quite often (the quality of it is another thing), so I knew, I need something that does X, and remembered something regarding that, by having read the Design Patterns book. Looked it up and implemented it. Now when I see the code I know, oh yeah, that's this or that pattern and works like this or that. Just my 2 cents.

    I assume you used the patterns all before, just never thought of it as a pattern. If someone not so smart like you would look at it, I believe if they see certain constituents, they'd know what pattern you used, and if naming the methods/classes etc. in a similar way, it's even easier, like MakeXyz() or class AbcStrategy etc.

    Matt> b) design patterns - intro into modern design patterns and which to use

    I am actually not a fan of Design Patterns. I've read the book, and I didn't think it was that useful. I think in terms of C++ idioms instead (e.g. iterators, functors, non-virtual interfaces).

  • I recently stumbled across the useful pretty_printer implementation STL presents in this nice lecture. Thinking about it, I have rewritten the code a little bit to use a traits class to detect tuple types. The traits class relies on std::tuple_element<0,T>::type being valid. The code works with vc2010 and g++ 4.6.1. You can find the code here:

    https://skydrive.live.com/redir.aspx?cid=86dcd7f4133f7b94&resid=86DCD7F4133F7B94!119

    Any comments welcome!

  • DanDan

    I miss you STL !

  • CharlesCharles Welcome Change

    @Dan: We all do! He's killing bugs. He'll be back!!
    C

  • @Charles: When? My favorite series has come to a halt for a while now Tongue Out

  • *Bump*

  • *I give up*

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.