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

## The Discussion

• Yay, the wait is finally over! Awesome!

• The IDE fullscreen is going out of sync starting at 20:15

• Bummer. Sorry about that. We will fix.

C

• I saw this earlier before it disappeared, now its back up cos I thought I triggered some undefined behavior.

What makes this lecture fantastic is the speaker's passion on the subject. (Just like Erik's)

You can clearly tell that Stephan knews his stuff.

Charles I look forward more video of this quality

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).

• Yeah, I took it down and our wizard in the studio, Michael O'Neill,, fixed the audio timing glitches reported by NotFredSafe yesterday. Thank you, Fred! Thank you, Michael!
C

PS: This is part 1 of n lectures on the subject by Stephen, so there will be more Stephan in the future!

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

I would love to see some homework at the end. The following lesson could start by discussing solutions to the homework. Here are three tasks I have come up with based on the video:

---

Task: Sort the strings in a vector.

Goal: Learn to iterate over a vector and do something with isolated elements.

Example: Given {cat, dog, bear}, the program should produce {act, dgo, aber}.

Hint: string can be thought of as a sequence of characters, it has begin and end methods.

---

Task: Check if a vector of ints contains duplicates.

Goal: Learn to do something interesting with multiple elements.

Example: Given {3, 7, 1, 3}, the program should print "found duplicate". Given {2, 4, 3, 1}, the program should print "found no duplicate".

Hint: This is a lot easier if the elements are stored in order. Why?

---

Task: Sort a vector of strings by length. If the length of two strings is equal, they shall be sorted lexicographically.

Goal: Learn to write sorting predicates via lambdas.

Example: Given {"dog", "bark", "cat", "meow"}, the program should produce {"cat", "dog", "bark", "meow"} -- that is, the short words come first, and equally long words are sorted by alphabet.

Hint: You can solve this problem in two different ways:
a) By executing two sorts with different sorting predicates. Think about the order of the sorts and remember the importance of stable sorting.
b) By executing a single sort with a slightly more complicated predicate.

> 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.

> 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

• From the top of my head, I would love to see the following things in the next video(s):

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.

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.)

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

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

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

• 1 of n, you mean * v.begin() or v.front() right ?

• "... It could send an email to your boss that you quit.  It could format your harddrive! Anything could happen!"

Best part of the movie!

• Wow. What a fantastic reply. Thank you, Stephan. Looking forward to the next lecture. You are something else, man.

C

• Thanks for a nice lecture.

I once read thru Stephen Prata's "C++ Primer Plus 5th ed."

This lecture must be a nice review of the chapter 16 for me!

iStation

• [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

• Hi Stephen!

As to people not using lambdas in the C++, many embedded systems don't yet have any compilers that support C++0x features. Some people don't want to use lambdas until they become part of standard C++. Additionally, I think that lambdas require allocation from the heap, causing cache misses and memory fragmentation (although that might only be true when passing the lambda above the current scope).

• Wow, this is awesome!

No book can explain it that kind a detail. I really like the answers of the "why" of some of the decisions.

• [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 https://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

• Stephan,

Just wanted to let you know how much I enjoy your lectures.  They are very informative and easy to watch.  Keep up the good work!

Edit: I removed my incorrect advisement about "&arr[1]+5" being wrong.  It is indeed correct since &arr[1] is an "int *" pointer, the compiler will automatically multiply the addend by the sizeof(int) ... Oops!  Yet another reason why STL is nice

• Great to finally see an introduction post on STL from Stephan himself! Other videos I would love to see from him are:

* Associative containers intro: sets, hash tables, priority queues

* 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?

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

• [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

• Great subject for a video series. STL is fantastic & powerful but also daunting at first (most documentation reads like a degree-level maths textbook), so anything which makes STL more accessible to more programmers gets my thumbs up.

Re error messages, the LLVM project seems to be doing some good things in that space, though I don't know if its "working out what the programmer intended" feats extend to templates. Definitely some good ideas there, either way.

Re "upgrade or die" for VS, I agree to some degree but I think it's too early to expect people to move to VS2010. It's a big task to move large/complex projects to VS2010.

(And, to be blunt, it feels unfinished; we're sticking with VS2008 for the time being, even though we've got our stuff building in VS2010 and though I'd love to start using some of the new C++0x features today. Don't know if others feel that way -- perhaps we just happened to run into several bugs/annoyances/missing features that are atypical -- but it added up to "let's wait for an update" for us. Shipping the IDE minus a proper help browser (when there were apparently two in development but unfinished) was a big indicator. Plug-ins seem to be appearing which fill the holes, though.)

It's fine for a series like this to use VS2010 features, though. They are interesting and even if you don't yet use VS2010 as your day-to-day IDE you can still watch the video and can also have VS2010 installed (as I do) if you want to try things out. Plus this video series will remain relevant long after everyone (except those die-hards who will never leave VC6 ) is using VS versions that support the new features.

• Thanks! Where can one find the C++ draft document (PDF) online, that you keep around for reference in the video?

• > I actually don't use the IDE for development,

What do you use ? notepad  ?
Also why don't you use the IDE ?

• Hey Stephen!

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!

Thanks for the info!

• [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

• Stephen,

Wow, the committee really factored the lambda specification beautifully!

Succinct, efficient higher order programming in C++... Brings a tear to my eye

Fight on!

• Hey Stephen,

Thank you very much for the great lecture. I would like to have some home work so that beginners gets used to them. Also I would like to know whether hash table and hash map are added to the new upcoming standard

• Everybody,

Stephan's name is StephAn!!  I know, I get it wrong too, sometimes... Stephan, Stephan, Stephan.

Stephan Lavavej. That's him.

C

• 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.

• Great video, STL!

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

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").

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++?

Thanks much for your time and knowledge sharing skills!

• 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. 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).

Thanks.

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

> 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 https://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

Thanks.

• Thank you very much for the reply. Awaiting for the next lecture in the series.. 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.

• Hi Stephan,

thanks a lot for this excellent introduction to STL. I can't wait to see more. I also very much appreciate how much progress C++ made in VS 2010.

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? I am working on our coding guidelines and I would be interested what those gotchas are and what you recommend instead. BOOST_FOREACH? Waiting for C++0x's for (int i : v)?

I am well aware of the STL for_each or transform algorithms, but in my eyes it is much clearer to write e.g.

std::vector<int> v;

v.push_back(1);

v.push_back(2);

BOOST_FOREACH(auto& i, v)

++i;

std::transform(v.begin(), v.end(), v.begin(), [](int i) { return ++i; });

Regards,

Bernd

• [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

• Thank you for sharing your expertise on STL.  I really enjoyned this and hope you will continue to make these videos.

• The text size of the cpp file was great.  The console app and the Adobe pdf were harder to make out.  Are there any adjustments you can make so that the text is larger, such as editing the CMD prompt font size, or zooming the PDF to margin, rather than to page width ?

seebrisket_eatbrisket

• 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

• Thanks for the fantastic video, Stephan  - the material is presented very clearly making it easy to follow along.

I'm looking forward to more videos in the series.

• Look for part 2 on Wednesday, July 21, 2010.

C

• Great!

And, if possible, please prepare a part 3 on C++ exceptions, exception-safety, etc.

Thanks much!

• EXCELLENT VIDEO - would really like to see more of these!

• Comment removed at user's request.

• This is a really great lecture.  This is the kind of stuff that gets me excited and motivates me to push the limit of my programming skills.  I'm moving into the .NET framework out of necessity but there is no replacement for low-level native coding.  Thanks a lot guys.  Oh, by the way, in response to the error reporting: 2010 really is an improvement.  Error reporting is something that can always be improved upon though.

• Interesting and very well presented.

1. Please do not encourage listeners to std:: sort anything but numbers and iterators.  Once you have anything more complicated, like std:: string, you should really build an index instead.
2. Wrt sorting strings by length, my approach is to write a perspective (query) iterator that returns the length as value, and index that iterator. (That would not work for the "length or otherwise lexi" case, of course).
3. You explain that the STL optimizes for speed; what library would you recommend for environments that need to optimize for memory?  Because the M*N problem still remains in the memory footprint, and it is really M*N*X, which is clearly visible from the way my laptop grinds under Windows XP SP3 while it used to run quite smoothly under original Windows XP (it cannot get any more memory because of the motherboard).  So in this case it would be actually better to use those shunned virtual functions.
4. Following, the problem with the latest tools is that they require the latest hardware to run, which is obvious for professionals but painful for students/hobbyists.
5. I do not believe your dedication to quality as you advertise it.  For example, Visual C++ is still unable to digest
`class X; X &foo (class X &p) { return p; }`
— reported back in 2006, postponed, forgotten, reported in 2009 and postponed.  Ugh.

• Very informative, well organized, thanks! Good work Channel 9, looking forward to similar lectures.

• Great lecture on the subject.Thank you!

• awesome presentation

• 中文可以留言吗？

• 中国字当然可以

• Very informative! Thank you

• Great lecture, thank you.

Todd

STL is what...
a) function oriented programming
b) object oriented programming

other options were there but quite invalid

• Great informative video. I would like to improve  my skills in this language, and i think that the only real way to do in deep is to get involve in some project. Because c++ can be use to do a lot of things, what do you think, would be a nice project ? maybe:

1.games

2.simulations of algorithms

3. windows applications (a gui with forms)

4. telecomunications apps (play with sockets and somethings like that)

....

what do yo think?

• [quote]
Jun 29, 2010 at 12:56 PM, NotFredSafe wrote
The IDE fullscreen is going out of sync starting at 20:15
[/quote]

• Great introduction. I look forward to the other installments.
Thanks!

• Great lecture. Learned a Lot thanks..
Can we have a next link posted to it, so that it is easy to navigate to next lecture(s) of the series. That will be good for all the series of blogs here.

• May I speak in Chinese? Have to say tonight is fantastic. Merry Christmas Eve, everyone.

• Very nice and useful lecture. It is not only for the beginner but refreshing for experienced developers. I think a little formal structured approach to the topic would help the beginners to get the clear understanding of the features of the STL. Indeed this lecture has done its intent very nicely. Thanks to Stephan T. Lavajev.

• Associative data structures would be a nice topic for future presentations. Especially attendant with how they can be maintained with sorts.

• [STL]Caltech

• [quote]
Jun 29, 2010 at 11:57 AM, NotFredSafe wrote
Yay, the wait is finally over! Awesome!
[/quote]

• he's awesome

• Great video series!

Stephan is great at explaining complicated things very clearly.

• Great videos. Microsoft is doing a good job by picking on stl. C++ is language that requires strong tutorial methodologies. Stephan, may god bless you for this good karma!
• Thank you for the fantastic videos, I am really in awe of Stephan's knowledge and passion.

I was about to ask a question regarding allocating new blocks of memory for a vector's contents when I solved it, It's probably common knowledge, but I thought I'd post it here for anyone else that may be curious or not fully understand it.

When a vector has to add an additional element, but doesn't have space for it, as STL said (using VS 2010) the next block of memory will increase by 1.5~ (can't remember the value). I originally was confused as to why the vector's address would not change; This is because the vector is not really 'containing' the data, it is pointing to it.

This brief snippet should elaborate things:

vector<int> v;
for (int i = 0; i < 50000; ++i) {
v.push_back(i);
if (i % 5000 == 0) {
cout << v.size() << ' ' << &v << endl;
cout << "vector v index 0 addr: " << &v[0];
}
}

Thanks again for the fantastic videos STL, I really appreciate your expertise, and also to the Microsoft team producing this, the quality is fantastic.

• true

• Nice overview of STL!
Thanks a lot for your effort

• Hi Stephen

Can you please tell me where i am going wrong.

1. Can we send the function values by call by values or we can use only const ref ?
Actually i wanna to change the value in vector then get it sorted.
like dividing each value by 10 then sort. How can i do it in better way.

This is not working why so,
std::sort(data.begin(), data.end(),
[](const double& left, const double& right){
return left == right;
});

This is also not working why so,
std::stable_sort(data.begin(), data.end(),
[](const double& left, const double& right){
return left == right;
});

This Works fine
std::sort(data.begin(), data.end(),
[](const double& left, const double& right){
return left > right;
});

Thanks
Ankur Shah