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

[AdamSpeight2008]
> Question for Stephan, why can't Microsoft's IDE Experience of the C++0X,
> included more detailed / specific error messages. Eg Template Error Messages,
> You keep the Error Messages from Standard (If they are specified?) but include
> some extra information, the cause of the error was triggered by this line
> (further up the stack).

This is a good question, because decoding compiler errors (and the same thing applies to compiler warnings) can be one of the most difficult tasks that C++ programmers are faced with. It's great that C++ can move both computation and error checking to compile time (earlier is definitely better than later), but as templates can perform more advanced computations (e.g. examining types and dispatching to different implementations for built-in types), they also generate significantly more complicated errors.

First, compiler errors are emitted from the compiler front-end. VC10 actually has two: C1XX, which is the "real" front-end, and EDG, which is the Intellisense front-end. The IDE simply invokes C1XX or EDG, and then displays the error messages that they emit. This is why the build system (which invokes C1XX) displays different errors from the tooltips on Intellisense red squiggles (which invokes EDG). So, the IDE can be involved here, but it's really just a bystander.

Second, the content of compiler errors isn't specified by the Standard. The Standard requires errors to be emitted in certain cases, and permits them (without requiring them) in other cases, but the compiler authors get to design the error messages themselves. As a result, compilers vary widely in the quality and detail of their error messages. Our compiler front-end team works on generating good error messages, but there's room to significantly improve. (One of the reasons that we replaced FEACP, the mutant build of C1XX that powered Intellisense in VC9 and earlier, with EDG in VC10 is that EDG generates really good error messages.)

Third, C1XX's template error messages already include extra information, which we call the "instantiation context". If you're building with the IDE, you should look at the Output window, instead of the Error List window. Lines such as "see reference to function template instantiation" are explaining the instantiation context. You can also look at the build log.

Finally, sometimes compiler errors (especially template errors) are just extremely confusing, even when you've got the instantiation context. Concepts, a feature proposed for C++0x but removed at the last minute by the Standardization Committee, would have significantly improved template error messages (if concepts worked properly, and the Committee was not sufficiently confident that they would). In the absence of concepts, misusing libraries like the STL can thoroughly confuse compilers, when explosions happen deep within template instantiation. The fundamental problem is that the compiler sees what went wrong at the very lowest level, but doesn't understand the high level of what you're trying to do (this problem is especially severe for templates, but occurs everywhere). Here's an example. You can't call std::sort() on a std::list, because std::sort() requires random-access iterators but std::list provides only bidirectional iterators. The compiler error you get for this is particularly horrible:

C:\Temp>type meow.cpp
#include <algorithm>
#include <list>
using namespace std;

void meow() {
    list<int> lst;

    sort(lst.begin(), lst.end());
}

C:\Temp>cl /EHsc /nologo /W4 meow.cpp
meow.cpp
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\algorithm(3642) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_List_iterator<_Mylist>'
        with
        [
            _Mylist=std::_List_val<int,std::allocator<int>>
        ]
        C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\xutility(1332) : see declaration of 'std::operator -'
        meow.cpp(8) : see reference to function template instantiation 'void std::sort<std::_List_iterator<_Mylist>>(_RanIt,_RanIt)' being compiled
        with
        [
            _Mylist=std::_List_val<int,std::allocator<int>>,
            _RanIt=std::_List_iterator<std::_List_val<int,std::allocator<int>>>
        ]
[...more errors...]

The compiler's complaining about reverse_iterator, which isn't even mentioned by the code. Now, there's a reason for this, and if you have sufficient experience with decoding compiler errors you can figure it out, but it's obnoxious and there's no easy solution other than "be an expert or ask an expert". Until you learn how to interpret the green streams of code falling down your screen, you can usually muddle your way through by looking at all of the lines that the compiler error is complaining about, starting with the lines in your code, and looking very carefully to see if anything's wrong. Experts basically do two things here: first, pattern matching on their memory of compiler errors (compiler complaining about X maps to Y actually being wrong), which requires having seen lots of compiler errors and figured out their underlying causes, and second, compiling the code in their head and figuring out where it goes wrong, which requires detailed knowledge of the C++ core language and the libraries involved. Unlike runtime failures, there's no easy way to "step through" compiletime failures (unless you can debug the compiler itself, which is reserved for the most powerful wizards).

In this case, std::sort() is eventually saying last - first for two list iterators. Because list iterators aren't random-access, they can't be subtracted. However, the compiler is complaining about that in a very weird way. It's considering all of the operator-() overloads that it sees, and figuring out which one of them to call. None of them can be called, because the right one doesn't exist. Here, the compiler is looking at reverse_iterator's operator-() (which has been dragged in because std::list provides rbegin() and rend()), and it's saying that template argument deduction isn't succeeding. That's correct, and sometimes the message that template argument deduction isn't succeeding is exactly what you want to hear, but in this case this overload of operator-() is completely irrelevant to what we're trying to do.

It so happens that one of the following errors is:

C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\algorithm(3642) : error C2676: binary '-' : 'std::_List_iterator<_Mylist>' does not define this operator or a conversion to a type acceptable to the predefined operator
        with
        [
            _Mylist=std::_List_val<int,std::allocator<int>>
        ]

That's actually much closer to an ideal error message - it's complaining about std::list<int>::iterator (which happens to be a typedef for our internal type, whose name is mentioned), and that operator-() doesn't exist for it. However, it wasn't the first error message, and I almost didn't look at it because the golden rule is to always look at the first error message. (Regardless of templates, looking at the first error message is almost always an extremely good idea, because the compiler can get confused and generate totally bogus error messages afterwards.)

The STL is super wonderful, but its biggest headache is definitely decoding its compiler errors.

[NotFredSafe]
> Really awesome video! The only minor complaint is the tiny console font, maybe that could be changed for part two.

Glad you liked it. I'll make the console font bigger - I hadn't thought about that ahead of time.

> I would love to see some homework at the end.

Excellent suggestion, I'll think of something.

We're planning to film Part 2 on Tuesday, July 13. If anyone posts questions or comments before then, I'll be able to address them in the video (or answer them directly here, in the case of very detailed questions or answers - one of the things that I've been discovering is that the human voice is very slow, so I have to plan for that when filming something. In the case of presentations, I was already familiar with PowerPoint slides being very small.)

Stephan T. Lavavej, Visual C++ Libraries Developer

Cool interview, I really like this format, it has 0 distractions and just flows naturally

[NotFredSafe]
> Not everyone has a compiler that supports lambdas. Maybe show short examples of
> how to write and use good-old C++98 functors? First stateless, then stateful?
> Maybe it will become more clear why lambdas are useful.

My answer is always: Upgrade! I have roughly zero sympathy for people using old compilers and libraries - just about the only good excuse is that you're N months away from shipping your next release, at which point you should immediately upgrade for your next development cycle.

Still, I'll keep this in mind. Understanding what lambdas are doing, and how to write functors when necessary (it's still necessary when you want to do anything fancy like recursion or templated function call operators) is definitely important.

> Designing custom algorithms as function templates. Maybe start with a very specific
> algorithm that only works for vectors of strings and then generalize that step by
> step so in the end, it works with any kind of forward iterator. (Explain the iterator categories.)

I like demonstrating how to write algorithm wrappers - my usual example is erase-remove. I view writing iterator-based algorithms from scratch as a relatively advanced topic, simply because the STL's algorithms cover so many scenarios.

> Use some example where a typename in the body of a function template is necessary
> and explain why it must be there, for example "typedef typename
> std::iterator_traits<Iter>::value_type vt;". Oh, maybe you can show how one
> doesn't need than in C++0x anymore because of auto and/or decltype

Good idea - and yes, auto removes most of this obnoxiousness.

> Use "less common" data structures like priority_queue. Maybe implement
> Dijkstra's algorithm or something? Or leave that as homework?

Part 2 will cover map and set, which will probably give me a chance to mention priority_queue, an auto-sorting container adapter.

[felix9]
> 1 of n, you mean * v.begin() or v.front() right ?

Heh heh.

Stephan T. Lavavej, Visual C++ Libraries Developer

[bryanedds]
> As to people not using lambdas in the C++, many embedded systems don't yet have any compilers that support C++0x features.

Fair enough.

> Some people don't want to use lambdas until they become part of standard C++.

They're in the C++0x Final Committee Draft, which is basically a Release Candidate for an International Standard.

VC10 supports an earlier draft of lambdas, which I refer to as "lambdas v1.0", but they're basically the same as the FCD's "lambdas v1.1" except for name lookup subtleties.

> Additionally, I think that lambdas require allocation from the heap, causing cache misses and memory fragmentation

This is actually NOT the case. As I explained in http://blogs.msdn.com/b/vcblog/archive/2008/10/28/lambdas-auto-and-static-assert-c-0x-features-in-vc10-part-1.aspx , lambdas are directly translated into function objects, optionally with value or reference data members. They live on the stack, they don't perform dynamic memory allocation, and they receive all of the benefits of inlining.

There's one exception to this, and that's when you capture by value an object whose copy constructor dynamically allocates memory (e.g. capturing a std::vector or std::string by value). In that case, the lambda itself still lives on the stack, but it contains a value data member with a pointer to dynamically allocated memory, because you told it to. Again, this is exactly what a handwritten function object would do.

> (although that might only be true when passing the lambda above the current scope).

Because lambdas have unspeakable types, you can't get a function to directly return a lambda that has been constructed in the function's body. You couldn't declare the function's return type properly. (I'm deliberately ignoring some of the crazier stuff that you can do with auto, decltype, and non-local variables.)

However, you can wrap a lambda in a std::function and return that. std::function performs "type erasure" in order to forget a function object's type while remembering its signature. For function objects of arbitrarily large size, std::function has no choice but to dynamically allocate memory, but for sufficiently small function objects, std::function is allowed to implement the Small Functor Optimization and avoid the dynamic memory allocation. VC10 implements the Small Functor Optimization, and it is currently applied to functors that are 12 bytes or less on x86, and 16 bytes or less on x64. Therefore, stateless lambdas and lambdas with a small number of captures will benefit.

In any event, even when std::function dynamically allocates memory, that's the Standard Library's doing, not the Core Language feature of lambdas.

Stephan T. Lavavej, Visual C++ Libraries Developer

[jduck]
> That said, I thought I would give you a heads up that your "&arr[1] + 5;" (around 34:30) is incorrect and could confuse students.
> I suspect what you meant was "&arr[1 + 5];" or "&arr[1] + (sizeof(int)*5)".

First, it's &arr[0] + 5. Second, it's correct. &arr[5] is technically incorrect, because accessing the nonexistent past-the-end element of an array (which I depicted with a dotted border) is forbidden by the Standard even if all you do with it is immediately take its address. In practice, compilers will let you get away with &arr[5], but static analysis could complain. This is even more important when dealing with the STL, because our std::vector implementation will trigger a debug assert if you say &v[v.size()].

Third, &arr[0] + sizeof(int) * 5 is completely incorrect. That's trying to perform pointer arithmetic manually, when the compiler is already doing it for you. (This is elementary C, by the way.) The type of &arr[0] is int *, pointing to the beginning of the array (the element at index 0, which is 11). Suppose that its address is 0x1000. If you say &arr[0] + 2, this is a pointer to the element at index 2, which is 33. The C or C++ compiler performs "pointer arithmetic" to do this. Your expressions are in terms of elements, but the code actually being generated is in terms of bytes, and you get address 0x1008 (when sizeof(int) is 4, which is the case for VC on both x86 and x64). Pointer arithmetic happens invisibly.

I hope that clears things up for you.

[ashwinn]
> * Associative containers intro: sets, hash tables, priority queues

Part 2 will definitely cover associative containers.

> * High level overview of the C++0X and other new STL features that are simple
> and give the most bang for the time spent. Fantastic example is the auto,
> how many C++ programmers know that?

I'll try to mix this in as I go along.

> * How to make the best use of Visual Studio features to write and debug STL code.

I actually don't use the IDE for development, so I'm not familiar with most of its features. I use it for debugging occasionally, so I'm reasonably familiar with that, and I maintain its visualizers for STL objects (which I think I mentioned in Part 1).

Stephan T. Lavavej, Visual C++ Libraries Developer

[LeoDavidson]
> perhaps we just happened to run into several bugs/annoyances/missing features that are atypical

It's our responsibility to ship products that are perfect in every way. However, you can help us by using betas and reporting bugs/annoyances/missing features through Microsoft Connect. (With emphasis on the word "beta"; by the time that we're calling it a "release candidate", it's too late to fix anything other than bugs that turn your hard drive into a solid state drive, and I mean by melting it instead of replacing it with flash chips. For example, we fixed exactly one bug in the compiler, linker, and standard library between VC10 RC and RTM - I'm very aggressive about fixing bugs, and our Xbox team reported a particularly nasty one in shared_ptr/weak_ptr.)

[Mr Crash]
> What do you use ? notepad  ?

I use a Notepad clone that wraps a rich edit control and is therefore somewhat more powerful than Notepad itself.

> Also why don't you use the IDE ?

Lots of reasons, primarily inertia. I personally don't need the editor's features, and I personally consider the build system to be too complicated, like all build systems except my preferred one (handwritten makefiles). But since basically everyone else uses the IDE, I used it in the video so that people would see something familiar.

[bryanedds]
> I last heard they were considering making lambdas arbitrarily passable,
> and I'm glad to hear they've decided not to. Hitting the allocator
> everytime you invoke a lambda would be really suboptimal. It had me
> worried that I couldn't use them in many cases!

Oh, and I forgot to mention something even better. Recently, the Standardization Committee granted stateless lambdas the ability to be implicitly converted to function pointers, allowing them to be passed to old style functions taking "callback" function pointers. This was added too late for it to be implemented in VC10 RTM, but you'll see it in a future release.

Stephan T. Lavavej, Visual C++ Libraries Developer

Heh. The easy way to remember is that it's spelled and pronounced like Stephanie without the "ie".

[brett01]
> Also I would like to know whether hash table and hash map are added to the new upcoming standard

They are! They're called unordered_map and unordered_set (also unordered_multimap and unordered_multiset), and they're implemented in VC9 SP1 and VC10 RTM.

I'll cover them briefly in Part 2, although I'll focus on plain map and set, which I view as easier to use.

[Sys64738]
> As a suggestion, I'd like a lesson (or a part of it...) on implementing custom allocators.

See http://blogs.msdn.com/b/vcblog/archive/2008/08/28/the-mallocator.aspx .

> In particular, it would be very interesting if you could show how to implement a ".NET-like"
> allocator which consists in preallocating a big chunk of memory and then just increase a
> pointer when a (small) amount is requested (so: allocating memory == pointer increase, very
> fast - and cleanup of the whole preallocated block is done at the end of the processing,
> kind of a very primitive "garbage collector").

That's referred to as a "memory pool". See http://www.boost.org/doc/libs/1_43_0/libs/pool/doc/index.html . Also see the non-Standard Dinkum Allocators Library, documented at http://www.dinkumware.com/manuals/?manual=compleat&page=index_alloc.html , which was incorporated into VC10 RTM, documented at http://msdn.microsoft.com/en-us/library/ee292134.aspx .

> Moreover, kind of OT... but I'd appreciate if you could spend some minutes sharing with us
> some insights on when to use exceptions vs. normal error codes in C++ code. Do you use
> exceptions only for exceptionally bad error conditions? Should exceptions be used
> instead of error codes in modern C++?

Actually, that's completely on topic. I don't know if I'll have time to get to this in Part 2, and there are many subtleties involved here, but the very short answer is:

* Exceptions are for recovery. Unrecoverable errors should terminate the program.

* Exceptions have many advantages over error codes (for example, they automate recovery, and they can capture arbitrarily detailed information), so it's easier to keep track of situations where exceptions are inappropriate. Exceptions should not be used for control flow (that is, they should not be used as uber gotos), and they should not be used when something is an obvious source of failure that can be dealt with locally. For example, validating user input is an obvious source of failure (users type in garbage all the time), and can be dealt with locally (reject the input, ask again). This is a design flaw in the otherwise excellent boost::lexical_cast<Dest>(src), which throws exceptions but probably shouldn't.

You've probably given me the topic for Part 3, thanks.

> Another question: if my understanding is correct, you said that STL can smartly use memcpy/memmove
> to quickly copy raw POD data, and instead it uses proper copy constructor for non-PODs.

Yes, the Standard permits STL implementations to perform this optimization, and we do. (This is permitted by the As If Rule: compiler and Standard Library implementations are permitted to do whatever they want, as long as their observable behavior, where the Standard defines what's observable and what's not, appears As If the implementation followed the Standard directly.)

> My question is: how can you (the implementer of STL) discriminate between POD and non-POD data?
> In other words, how can you ask a C++ class: "Are you a POD or are you a non-POD?"
> (such that you then could use memcpy/memmove optimization for PODs).

That's a good question. std::is_pod<T> from <type_traits> reports whether a type is Plain Old Data, and template machinery can be used to activate optimizations depending on the answer. Like some other type traits (but not all), is_pod is powered by "compiler magic", because a library-only implementation couldn't answer this correctly for arbitrary types.

(Currently, we use a slightly less aggressive optimization, that we activate for built-ins like int and double, but not for arbitrary structs that happen to be POD. Extending this optimization is on my todo list, although it's far from the first thing.)

Stephan T. Lavavej, Visual C++ Libraries Developer

[brett01]
> Also I would like to know some implementation details of unordered_set and unordered_map.
> Some thing like how load factor and no of buckets affects the performance of these two containers.

This is actually a question that I can't easily answer (except with "magic"). It falls into one of my blind spots because I didn't write their implementations, haven't investigated them thoroughly, and haven't used them extensively (as I mentioned, I strongly prefer the ordered containers).

Most of what I know about the unordered containers comes from their interface. If you look at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3092.pdf 23.2.5 [unord.req] and 23.5 [unord], you'll see that they have "bucket interface" and "hash policy" member functions. They automatically rebucketize themselves, and you have limited control over how this happens. The idea is that they "just work" and only specialized applications need to play around with this.

I can also tell you that we're still working on unordered container performance - we believe that further improvements are possible here.

[rab36]
> I also very much appreciate how much progress C++ made in VS 2010.

Excellent. The VC team (including myself) and Dinkumware worked really hard on it, so hearing that it makes customers happy is especially satisfying.

> I have a question: you briefly mentioned some gotchas when using for each.
> Did you mean the C++/CLI for each (int i in v), that is also available in unmanaged code?

Yes, that non-Standard extension. (Also, "native" please, not "unmanaged".)

> I am working on our coding guidelines and I would be interested what those gotchas are

It doesn't permit in-place modification (through modifiable references). The code that the compiler generates for "for each" contains a static_cast and some other weirdness in it, and I'm not sure exactly what it's doing. That's why I strongly recommend against using it. It's just not worth it.

> and what you recommend instead.

Anything else. Handwritten iterator loops (now with auto), STL algorithms (now with lambdas), BOOST_FOREACH, whatever.

for_each() is kind of the least useful STL algorithm (its main virtue is that it says what it does, whereas all handwritten iterator loops have to be inspected to see what they're doing). transform() is most useful for transforming one sequence into another, instead of doing in-place transformations (which it's certainly capable of).

The ultimate solution will be C++0x's range-based for-loop, when it's implemented.

Stephan T. Lavavej, Visual C++ Libraries Developer

In Part 2, which I filmed on Tuesday, I massively increased the Command Prompt's font size, to match the IDE's 200% zoomed text size.  (I believe I used Consolas 36 in the Command Prompt.)  I didn't open any PDFs in Part 2, but I'll keep that in mind for the future.  Thanks!

Stephan T. Lavavej, Visual C++ Libraries Developer