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

Stephan T. Lavavej: Core C++, 3 of n

Download

Right click “Save as…”

In Part 3, STL digs into Overload Resolution. A function template can overload non-template functions of the same name. In this scenario, function calls are resolved by first using template argument deduction to instantiate the function template with a unique specialization (STL taught us all about TAD in Part 2). If template argument deduction fails, the other function overloads are considered to resolve the call. These other overloads, also known as the candidate set, include nontemplate functions and other instantiated function templates. If template argument deduction succeeds, then the generated function is compared with the other functions to determine the best match, following the rules for overload resolution. [source]

As STL says: "I walk through why foo(const T&) beats foo(const T *), when given int *. The reason is surprisingly subtle."

Tune in.

Tags:

Follow the Discussion

  • Awesome, that's put the cat amongst the pigeons when it comes to my next study item! Thank you Stephan! Here's hoping that 'n' turns out to be a large number Smiley

  • AnujAnuj

    Good lecture. It would be extremely helpful, if you can give some lecture on bind, lambdas and related gotchas.

  • AnujAnuj

    Also, Advanced STL series stopped abruptly. Please resume that as well.

  • Thank you, Stephan.

    more or less difficult to understand this subject.

    Both this lecture and last one(TAD; Template Argument Deduction) are very helpful for me.

  • IvanIvan

    @ STL
    to me passing shared_ptr by ref is abomination(if I MUST use it without atomic costs i prefer to use raw ptr as func param). Am I wrong ?

  • When I play this video in VLC, the title says "Dina Dublon". Why is that? Smiley

  • @NotFredSafe: This was the next video on the Channel 9 homepage ticker http://channel9.msdn.com/posts/Dina-Dublon

  • I love these indepth studies.  I don't care what your next subject is, just keep them coming.

  • static_assert(sizeof("peppermint") == 11, "6 + 4 + 1 == 11");

  • BekennBekenn

    @Ivan: Nope, you're not wrong. In this example, the correct thing to do is to prototype foo on the raw pointer type (since the function is merely observing the value). If the function needs to take shared ownership, it should accept a shared_ptr by value (and then use std::move to set its internal shared_ptr instance). Similarly, for unique ownership, it should accept a unique_ptr by value.

  • STLSTL

    dot_tom: I'll keep going until I run out of ideas or time.

    Anuj: I'll probably cover lambdas in this series (maybe soon). bind() is STL tech, so it'd be off topic for this series. The good news is that lambdas supersede bind() in 99% of cases (and the remaining 1% should be dealt with by writing traditional functors). I stopped filming Advanced STL primarily because I ran out of time (VC11 was running really hot). You can think of my GoingNative 2012 presentation as Advanced STL, Part Infinity though.

    Ivan, Bekenn: I disagree. Consider a set<shared_ptr<X>, Comparator>. The Comparator will be given shared_ptr<X>, so it should take (const shared_ptr<X>&, const shared_ptr<X>&).

    NotFredSafe: Heh. I try to avoid performing such calculations on the fly, mostly because if I get them wrong, I'll look like an idiot. (It's already bad enough that I forgot that whether conversions are even possible is determined during the "viable function" and not the "best viable function" part of overload resolution - I regenerated that knowledge on screen as I was talking, but it would have been less confusing to avoid that thinko in the first place.)

  • Xeoc9xeo Sanity is just a mask

    I think you can just use std::is_pointer() as the tag "value" for dispatching, as all UnaryTypeTraits are required to derive from either true_type or false_type (which is incidentially where the nested type typedef comes from).

    Other than that, another great video, thanks.

  • STLSTL

    Yes, that's right. I knew I had forgotten something.

  • KennyKenny

    Thank you STL for the great lecture, and I like the ‘is_pointer’ part more. But as your most examples were based on one argument function overloads it made me some questions about overloading functions with more than one arguments and considering each argument alone, in which they matche different ranks based on Standard conversion sequences table.
    e.g. : what if I had two overloads with following matches rank:
    foo(Identity, Identity);
    foo(Identity, Qualification Adjustment);
    or a bit more complicated issue:
    foo(identity, conversion);
    foo(promotion, promotion);
    And if the bigger rank in the argument list is considered for the whole function then for the second example the second foo should be chosen and this indicates that the in the first example the first function should be chosen but I think for the first example the compiler would result in ambiguity .
    And would you mind please update your post in msdn http://blogs.msdn.com/b/vcblog/archive/2011/09/12/10209291.aspx about c++11 features in VC11 for upcoming visual studio 2012 final release. You know as gcc 4.7 supports most of the new features (but unfortunately not the concurrency part) http://gcc.gnu.org/gcc-4.7/cxx0x_status.html multi-platform programmers of c++ like to take the advantage of new c++11, but they are not sure about some features support in VC11 and if the VC11 releases with some missing parts would they be ready until next general release or they will ship with sp1 updates or sth like that.
    Thanks.

  • STLSTL

    I didn't have time to cover the multi-arg rules, but they're a "natural" extension of the single-arg rules. The Standardese here isn't *too* frightening, so I'll just quote it (trimming some bulky and less-important sections):

    N3376 13.3.3 "Best viable function" [over.match.best]/1: "Define ICSi(F) as follows: [...]

    — let ICSi(F) denote the implicit conversion sequence that converts the i-th argument in the list to the type of the i-th parameter of viable function F. 13.3.3.1 defines the implicit conversion sequences and 13.3.3.2 defines what it means for one implicit conversion sequence to be a better conversion sequence or worse conversion sequence than another.

    Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICSi(F1) is not a worse conversion sequence than ICSi(F2), and then

    — for some argument j, ICSj(F1) is a better conversion sequence than ICSj(F2), or, if not that, [...]

    — F1 is a non-template function and F2 is a function template specialization, or, if not that,

    — F1 and F2 are function template specializations, and the function template for F1 is more specialized than the template for F2 according to the partial ordering rules described in 14.5.6.2."

    The main rule is, F1 is better than F2 if none of F1's conversions are worse, and at least one of F1's conversions is better. (Then there are tiebreakers for templates.)

    /2 then says: "If there is exactly one viable function that is a better function than all other viable functions, then it is the one selected by overload resolution; otherwise the call is ill-formed."

    > And would you mind please update your post in msdn

    That's already accurate for VC11 RTM.

  • AndrewAndrew

    Thanks for the wonderful lecture, which helps me clarify some fundamental concepts.
    Below is a problem that I cannot figure out, which is modified from C++ Primer 4ed Sec. 16.7, and it seems similar to the problem presented in the video.

    template <typename T> void foo(const T&, const T&) {};
    void foo(const char*, const char*) {};

    int main() {
    char c1 [] = “meow”;
    char c2 [] = “cat”;
    const char const_c1 [] = “meow”;
    const char const_c2 [] = “cat”;
    foo(c1, c2); // non-template
    foo(c1, const_c1); // template
    foo(c1, const_c2); // non template
    }

    It seems to me in foo(c1, c2),
    c1 and c2 first do array-to-pointer conversion, and follow by qualification conversion (char* to const char*?) to match the non-template version; Similar to the lecture, we need only array-to-pointer conversion (a proper subsequence of the non-template conversion?) to match the template version. But the non-template version still wins.

    For foo(c1, const_c1) and foo(c1, const_c2) I need some help for more explanations.

    Thanks for your help and thanks again for the great lecture.

  • STLSTL

    Given foo(c1, c2), template argument deduction fails for foo(const T&, const T&). That's because c1 is char[5] ("array of 5 characters") and c2 is char[4], so the first argument and the second argument don't result in identical T's being deduced. (foo(10, 3.14) would similarly cause template argument deduction to fail, because T can't be int and double simultaneously. Remember from part 2, template argument deduction plays a type matching game and has almost no wiggle room for conversions.) Therefore foo(const T&, const T&) is not instantiated and added to the overload set. foo(const char *, const char *) then wins by default (it is viable, and the only competitor, so as long as the conversions are possible it doesn't matter how "bad" they are).

    (Note! Because the parameters are const T&, array-to-pointer decay is not performed during template argument deduction.)

    foo(c1, const _c2) behaves identically, because the types are char[5] and const char[4]. The sizes are part of the array types, so the mismatch ensures that no consistent T can be deduced.

    foo(c1, const_c1) is the trickiest. Template argument deduction succeeds, resulting in the signature foo(const char (&)[5], const char (&)[5]). This competes against the non-template foo(const char *, const char *). At this point I grumble and actually look at clause 13. For the template, const char (&)[5] binds directly to c1 and const_c1, as we saw in this video. Direct reference binding (which happens whenever a temporary is not introduced; adding constness does not affect directness) is considered the identity conversion, which is best of all. So now we need to look at how good the non-template is. It requires array-to-pointer conversions, which have a category of Lvalue Transformation and a rank of Exact Match. Again as we saw in the video, although this is an Exact Match, the Identity conversion is better because it is a strict subsequence. Therefore, the template wins.

    (Note: If there were a non-template with the signature foo(const char (&)[5], const char (&)[5], then the conversions would be Identity, and the tie-breaker that non-templates beat templates when they are equally good would be invoked. Without such a signature, the template is simply better, and the tiebreaker is not invoked.)

    TLDR: Templates are greedy! Don't overload them unless you're absolutely sure what will happen.

  • kennykenny

    Thank you STL for a such brief and complete answer. but it seems the background standard rules of this answer too freighting to me. I will take a look at those sections of the working draft n3376 but considering all these rules in developing libraries must not be easy. and about the second answer I want to ask if there is any way to make a code which is developed for gcc using new features like 'Initializer lists' or 'Unicode string literals' portable to vc11 or not. I mean some thing like macros, ....
    Thanks

  • IvanIvan

    @STL
    (now its no longer working week I have time ) for longer comment.
    First tnx for explaining the question I posted in comments in this video.
    1) Regarding that example did I get it correctly that template stamping makes 2 signatures:
    void f(const int* p)
    void f(int*& const p)
    (when you were writing on a board you inverted the order so I got confused)
    2) Regarding boostcon -
    a) if you had a 3 copies of yourself and they had a lot of free time... is there a lib that you would like to write and submit to boost?
    b) regarding Bartosz TMP-Haskell lectures... did you ever tried Haskell, do you like it, do you feel it is useful(I mean ofc it is useful, I mean significantly) for C++ programmers in general and/or C++ TMP programmers? And Im not talking about lambdas, tbh I consider them just a sint sugar, and ofc like you said perf opportunity because for some reason they are more easily inlined.

    3) regarding templates are greedy - this lectures are really great but like Scott Myers said of his book programmers like do, dont do rules. So maybe in the next lectures you can go a bit deeper for rules you use, beside generic templates are greedy.

    4) Your compiler friend Jonathan that worked on implementing for each in his free time... is there any chance that we might get him to do some lectures? There are 2 things Im really interested in, both performance related:
    -lockfree programming with <atomic>
    - in general how to write code that doesnt prevent some optimizations
    Ofc any topic would be cool. From common boring but useful how to speed up builds to really academic stuff(that I like unlike most ppl) about general compiler architecture.
    5) do you have any list of "approved by STL" C++ links, on MS or personal web because I know you dont have time to write all the things you like but maybe you know some really good resources beside generic classics from Sutter, Alexandrescu and Meyers.

  • Made an account just to say thanks for taking the time to do this. I have watched all your other videos here and they have been very informative. 

  • gayagaya

    I just want to thank You for a great job

  • STLSTL

    kenny> it seems the background standard rules of this answer too freighting to me.

    Here's an analogy that might help.

    Let's play an ultra-simple mutated version of chess. Chess pieces are conventionally ranked in strength as Pawn < Knight < Bishop < Rook < Queen, with Pawns being the weakest and Queens being the strongest. (Fellow chess nerds, please hold your objections.) In Single-Piece Mutant Chess, I secretly choose a chess piece, and so do you, and then we reveal our chosen pieces simultaneously. Whoever chooses the stronger piece wins. For example, if I choose a Rook, and you choose a Knight, my Rook beats your Knight and I win. If we choose equally strong pieces, then we are tied. This is an incredibly simple (and boring) game!

    Now let's add pieces. In Multi-Piece Mutant Chess, we agree on a particular N before we start playing: for example, 4. Then I secretly choose a sequence of N chess pieces. (Because this is an analogy, let's say I've bought a bunch of chess sets, so nothing is stopping me from choosing many copies of a particular piece.) The important thing that that this sequence is ordered, so I have to choose a particular "first piece", then a second, and so forth, and I can't go rearrange them later. So I could choose Bishop, Pawn, Pawn, Queen in that order. After you also choose a sequence of pieces, we reveal and compare them.

    Multi-Piece Mutant Chess's rules say that our pieces pair up in order (my first piece with your first piece, my second with your second, etc.) and they each fight a Single-Piece battle. So if you've chosen Bishop, Pawn, Pawn, Rook, then the results are Tied, Tied, Tied, STL-Better (because Queen beats Rook). Finally, Multi-Piece Mutant Chess decides an overall winner:

    * If every Single-Piece battle is tied, the Multi-Piece war is tied.

    * Otherwise, 1 or more (perhaps all) Single-Piece battles ended with a winner. Ignoring the tied battles, if Player A consistently won all of the non-tied battles, Player A wins the whole Multi-Piece war. (So if I tie 3 battles and win 1 battle, I win the whole war.)

    * Otherwise, we've got a case where Player A won at least 1 battle and Player B won at least 1 (different) battle. In this case, the overall Multi-Piece war is tied. (It doesn't matter if A won 50 battles, 47 were tied, and B won 1.)

    I had to explain that with words and bullet points (actually sequenced bullet points), but the effects are simple and very intuitive:

    Knight, Pawn, Queen, Bishop TIES Knight, Pawn, Queen, Bishop. (4 ties.)

    Bishop, Pawn, Pawn, Queen BEATS Bishop, Pawn, Pawn, Rook. (3 ties, A wins 1.)

    Rook, Bishop, Knight, Pawn LOSES TO Queen, Rook, Bishop, Knight. (B wins 4.)

    Queen, Queen, Pawn, Pawn TIES Pawn, Pawn, Pawn, Knight. (A wins 2, 1 is tied, B wins 1.)

    Those are the rules for 2-player Multi-Piece Mutant Chess. We can also hold an entire tournament of Multi-Piece Mutant Chess, where K competitors each bring a sequence of N pieces, and either one competitor wins the whole tournament and everyone else loses, or nobody wins. The tournament rules are very simple: all competitors play 2-player Multi-Piece Mutant Chess with all other competitors. If one competitor wins *every* 2-player Multi-Piece game against all other competitors, that player wins the whole tournament. In all other cases, the tournament ends in failure and nobody wins (this includes the case where two competitors beat everyone else, but tie each other).

    At this point, it should be obvious that the rules for the Multi-Piece Mutant Chess tournament are the same as for C++'s overload resolution. (Mutant Chess piece strength is analogous to argument-parameter conversion rank; a Queen is like an Exact Match while a Pawn is like a user-defined conversion, roughly.) C++ is of course trickier than Mutant Chess, mostly because it has lots of conversions instead of 5 simple pieces (and also because it needs a few tiebreakers for templates and so forth) but the basic structure is the same.

    > considering all these rules in developing libraries must not be easy.

    Because overload resolution (and template argument deduction, and name lookup, etc.) works hard to produce intuitive, expected results, many programmers can go their whole careers without understanding all of the little details. However, library programmers walk a harder path. Library code typically wants to do tricky things while implementing a simple interface, and it has to deal with a wide range of inputs from "users", who are simultaneously the library's customers and tormentors (because users will inevitably pass the craziest possible inputs, and then some). This is especially true for C++, where user input (and I am referring to programmer-users here, not end users) includes the types that are given to a library. So generic library programmers usually end up learning most of the Core Language's rules, especially in areas that have the potential to burn them. And that is certainly true of overload resolution.

    > if there is any way to make a code which is developed for gcc using new features like 'Initializer lists' or 'Unicode string literals' portable to vc11 or not.

    Some things can be faked (e.g. variadic templates, explicit operator bool()) with great difficulty. Others cannot (e.g. initializer lists, raw string literals).

    Ivan> Regarding that example did I get it correctly that template stamping makes 2 signatures:

    > void f(const int* p)

    > void f(int*& const p)

    Not quite. foo(const T *) produces foo(const int *) and foo(const T&) produces foo(int * const &). The latter (reading backwards) is "reference to const pointer to modifiable int". You wrote "const reference to modifiable pointer to modifiable int" which is incorrect - references cannot be const themselves (N3376 8.3.2 [dcl.ref]/1 "Cv-qualified references are ill-formed except when the cv-qualifiers are introduced through the use of a typedef (7.1.3) or of a template type argument (14.3), in which case the cv-qualifiers are ignored."). Informally, "const reference to T" is always interpreted as "reference to const T" precisely because const references are impossible. However, when dealing with anything tricky (and references to pointers certainly qualify as they are "multi-level"), using the formally correct wording helps to avoid confusion.

    > if you had a 3 copies of yourself and they had a lot of free time... is there a lib that you would like to write and submit to boost?

    I'd choose either Iostreams Done Right (not because I like I/O but because I hate iostreams so very much) or 2D graphics. (I am intermittently working on the latter at home, but not in library form.)

    > did you ever tried Haskell

    Nope.

    > regarding templates are greedy - this lectures are really great but like Scott Myers said of his book programmers like do, dont do rules.

    I don't usually think in terms of hard and fast rules. I have some, of course, where I've noticed them myself or learned them from others (e.g. never return by const value, never return by rvalue reference) where they can be stated simply and where they apply so broadly that even beginning programmers can follow them without getting into trouble (experts, as usual, will know about the very rare exceptions where they shouldn't follow the rules).

    What I think about are the underlying principles. "Templates (especially perfect forwarders) are greedy" is a good example. It is a high-level statement about how C++ works, a consequence of the Core Language's rules. But it is not a rule itself. It suggests various things - for example, template overloading should be avoided proportionally to how new you are to working with templates. No ironclad rule is possible here, simply because some overload sets will work as intended and some won't, and recognizing the difference requires experience.

    > Your compiler friend Jonathan that worked on implementing for each in his free time... is there any chance that we might get him to do some lectures?

    Magic 8 Ball says: Very doubtful. He's a more powerful programmer than I am, but I suspect that no amount of pleading could get him in front of a camera.

    > lockfree programming with <atomic>

    To paraphrase a famous quote - The first rule of lock-free programming is: Don't do it. The second rule, for experts only, is: Don't do it yet.

    When I start doing episodes about the STL again, I'll get VC11 RTM on my laptop and show how threads/futures/etc. work. I may do an episode about atomics, but I think it might be better to avoid encouraging people to use them. They are incredibly dangerous, exceeded only by weaker-than-sequential-consistency atomics (so dangerous we got burned by them in an obscure way in VC11, *after* having a team of experts review the code), and by attempting such programming without encapsulated atomics (psychotically dangerous *and* platform-dependent).

    > in general how to write code that doesnt prevent some optimizations

    Most recently, I learned from Howard Hinnant at C++Now! 2012 that redundantly saying "return move(local);" instead of "return local;" is actually a pessimization - it inhibits the NRVO. I already avoided writing such code (following my general principle to avoid saying redundant things, with a very limited number of exceptions), and it was obvious in hindsight, but I didn't see the consequence ahead of time.

    > maybe you know some really good resources beside generic classics from Sutter, Alexandrescu and Meyers.

    C++ Templates: The Complete Guide is really good. More readable than the Standard, but very precise (this is a difficult combination to achieve).

    snyzel, gaya: Thanks for watching. I'm glad you've found my videos to be useful.

  • KennyKenny

    Thank you STL, I was a university student for 7 years and I never had a such complete answers for my questions. Your comments are as good as your lectures and The helped me a lot. I really mean it. Thanks again.

  • PeterPeter

    @STL
    I have developed a technique to speed up range based insertation to any autobalanced tree, however when I use it on the standard library's set, I get much worse results, because the hint based insertation is still doing lot of extra calculations.
    Is there any documentation on how can I insert a node with full trust implementation specific way(I know the color, parent and childs of the node)? Maybe you could create a video from the red-balck tree implementation?
    I get more comparisons with std::sort, then inserting all elements to a std::set. How can that be? :S

    here is my benchmark code: http://pastebin.com/RyZr5GCq
    benchmark output: http://pastebin.com/E9pG2TkB

  • IvanIvan

    @STL tnx for the answers, it is getting old saying that but seriously for academic(in a sense slower than a quick course but with more understanding) learning I really think this is the best content available.
    1. that thing that I wrote "void f(int*& const p"
    compiles in VS11 and VS10.
    2. Your compiler friend Jonathan sounds like yours Tyler Durden. :)
    3. burned in obscure way by nonseqconst atomics - interesting story. Out of academic curiosity do you know are there any formal verifiers for lock free code?
    BTW It would be nice if certain company that shipped lockfree containers for .Net("ConcurrentQueue<T> and ConcurrentStack<T> are completely lock-free in this way.", http://blogs.msdn.com/b/pfxteam/archive/2010/01/26/9953725.aspx) would submit them to std for C++17.



    @Peter - STL did a video in his advanced STL series where he talks about RB trees, you might wanna check that out. Dont know which video but I distinctly remember him talking about RB trees and how one doesnt wanna be a person to reimplement it or something like that. Im sure you can find it.

  • STLSTL

    Peter> the hint based insertation is still doing lot of extra calculations.

    One of the things about hint-insert is that it doesn't rely on the hint for correctness (the complexity is "logarithmic in general, but amortized constant if t is inserted right before p"). Things would be different if hint-insert was specified as "fast for good hints, boom for bad hints".

    > Is there any documentation on how can I insert a node with full trust implementation specific way(I know the color, parent and childs of the node)?

    STL containers don't grant outsiders access to their implementation guts.

    > I get more comparisons with std::sort, then inserting all elements to a std::set. How can that be?

    I'm not sure what you're saying here, but in general for sorting N elements I would expect sort() on a vector to significantly outperform inserting the elements into a set, because of the vector's greater locality. set is necessary when insertions are interleaved with lookups and especially erasures.

    Ivan> 1. that thing that I wrote "void f(int*& const p" compiles in VS11 and VS10.

    Emitting "warning C4227: anachronism used : qualifiers on reference are ignored". Always compile at /W4.

    > Out of academic curiosity do you know are there any formal verifiers for lock free code?

    I don't know - formal verification is very far removed from what I do for a living.

    > lockfree containers for .Net

    PPL has concurrent_vector, etc. for C++. They're pretty cool.

    > Dont know which video but I distinctly remember him talking about RB trees and how one doesnt wanna be a person to reimplement it or something like that.

    Specifically, I mentioned that I have never implemented a red-black tree.

  • Shantanu IndeShantanu Inde

    nice.....!!!!!

  • STLSTL

    Part 4: http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavavej-Core-C-/Stephan-T-Lavavej-Core-C-4-of-n

  • ricodericode

    Thank you for all the videos, looking forward to see more of them.

    Would be also nice to see extra series dedicated to Boost only.

  • bobobobobobobobo

    When using a technique of dispatching on std::is_pointer one has to take nullptr into account. Because according to is_pointer<> nullptr is not a pointer, therefore variant for non pointer types will be called. That might be a bit surprising to the user, so when using this technique one should consider adding an overload for nullptr_t (possibly deleted).

  • Johannes SchaubJohannes Schaub

    For an interesting ambiguity problem with multi-arg functions and operators, consider http://stackoverflow.com/questions/3519282/why-is-this-ambiguity-here and the explanation.

  • thanks Stephan, your lessons are great!

     

    just a simple note, in part 2 you are mentioning that developers use 'instantiation' and not 'specialization'

    this may come from the fact compilers say: "no instance of function template ...."

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.