Making sense of STL <utility>

The code starts harmlessly enough with a bunch of boilerplate:

// utility standard header
#pragma once
#ifndef _UTILITY_
#define _UTILITY_
#ifndef RC_INVOKED
#include <xstddef>
#include <iosfwd>
#include <type_traits>

#pragma pack(push,_CRT_PACKING)
#pragma warning(push,3)
#pragma push_macro("new")
#undef new

#pragma warning(disable: 4180 4512)

_STD_BEGIN

But let's not start sloppy, let's look at it in some detail:

So let's dive into each template as it comes along:

		// TEMPLATE FUNCTION iter_swap (from <xutility>)
template<class _Ty> inline
	void swap(_Ty&, _Ty&)
		_NOEXCEPT_OP(is_nothrow_move_constructible<_Ty>::value
			&& is_nothrow_move_assignable<_Ty>::value);

My powers of psychic debugging tell me that the author of the STL files - unlike me - is a TAB fan (not a blanks guy), and that her default indent is probably not mine (aka 4).

Note: Because of this, for the rest of the header I will take the liberty of reformatting the code to make it more readable (I think). I will not change any text: I will just change indentation and newlines. Any other change is off-limits.

So, let's start again, this time with the "beautified" version:

template
    <class _Ty>
    inline
    void swap(_Ty&, _Ty&)
        _NOEXCEPT_OP(
                is_nothrow_move_constructible<_Ty>::value && 
                is_nothrow_move_assignable<_Ty>::value);

Actually, we can see that this is not a template, it is a template forward declaration. For now, we will ignore it because everything that makes this template look strange (the _NOEXCEPT_OP, the type traits and so on) is explained better in actual templates as we go along.

Swaping iterators

template
    <class _FwdIt1, class _FwdIt2>
    inline
    void iter_swap(_FwdIt1 _Left, _FwdIt2 _Right)
    {
        // swap *_Left and *_Right
        swap(*_Left, *_Right);
    }

OK, our first template! Let's see how far we can dissect this:

One question should be: why not declare it like this:

template
    <class _FwdIt1, class _FwdIt2>
    inline
    void iter_swap_bad_idea(<font color="#FF0000">_FwdIt1*</font> _Left, <font color="#FF0000">_FwdIt2*</font> _Right)
    {
        // swap *_Left and *_Right
        swap(*_Left, *_Right);
    }

Can you see the problem? It will fail for anything that behaves like a pointer, but is not a pointer. Case in point:

    std::shared_ptr<int> a;
    std::shared_ptr<int> b;

    std::iter_swap(a, b); // works perfectly
    iter_swap_bad_idea(a, b); // fails

works with the above (correct) implemenation, but not with the faulty one: because a is a pointer-like object, but not a pointer.

The above (correct) template implementation assumes the minimal requirement for the caller: the caller only has to support the * dereferencing operator, nothing else. Templates really are a way to support duck-typing in C++.

At this point in life one can safely assume that the authors of the STL knew what they were doing, so let's also spend a moment on thinking about why they wrote:

template<<font color="#FF0000">class</font> _FwdIt1, <font color="#FF0000">class</font> _FwdIt2> inline

and not

template<<font color="#FF0000">typename</font> _FwdIt1, <font color="#FF0000">typename</font> _FwdIt2> inline

It turns out there is an actual reason: class is preferable if you could have template-template parameters. So, you do need to know arcane implementation details even notable C++ guru Stan Lippman isn't 100% sure of (read both links in sequence to see what I mean) when you want to become a STL author later in life.

You can see something else from all of this: A style guide for C++ templates must of essence be different than a style guide for C++ classes

OK, on to the next one!

Swaping stuff

// TEMPLATE FUNCTION swap
template
    <class _Ty, size_t _Size>
    inline
    void swap(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size])
        _NOEXCEPT_OP(_NOEXCEPT_OP(swap(*_Left, *_Right)))
    {
        // exchange arrays stored at _Left and _Right
        if (&_Left != &_Right)
        {
            // worth swapping, swap ranges
            _Ty *_First1 = _Left;
            _Ty *_Last1 = _First1 + _Size;
            _Ty *_First2 = _Right;
            for (; _First1 != _Last1; ++_First1, ++_First2)
            {
                _STD iter_swap(_First1, _First2);
            }
        }
    }

First of, let's remove _NOEXCEPT_OP. This is defined in yvals.h like this:

#define _NOEXCEPT_OP(x)

We can safely remove it, right? Well, yes and no. Yes, if you assume the above macro definition. But really the problem is that Visual Studio 2013 does not support conditional noexcept specifications, as documented, but presumably the next version will. And when it (finally) does, I assume the macro will be redefined thus:

#define _NOEXCEPT_OP(x) noexcept(x)

And suddenly, it will have an impact: so No, we cannot completely remove it.

Also, you should stop and wonder why they essentially write

    noexcept(noexcept(x))

when one would think that a single noexcept would have done just as well. But alas: one would be wrong: noexcept really is two quite different things with the same name:

So the inner noexcept is an operator, and the outer one is a specifier.

Note: We are only few lines into utility and already I feel Linus has been right once again.

But OK, I've started this article (and some hours ago I was foolish enough to think I can do this for more than one header! we shall see!), so let's keep on doing this. Since VS2013 doesn't support noexcept, we'll remove it and look at it again:

template
    <class _Ty, size_t _Size>
    inline
    void swap(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size])
    {
        // exchange arrays stored at _Left and _Right
        if (&_Left != &_Right)
        {
            // worth swapping, swap ranges
            _Ty *_First1 = _Left;
            _Ty *_Last1 = _First1 + _Size;
            _Ty *_First2 = _Right;
            for (; _First1 != _Last1; ++_First1, ++_First2)
            {
                _STD iter_swap(_First1, _First2);
            }
        }
    }

Again, it should be immediately obvious that _STD is a helpful macro expanding to std::. Actually, upon checking it it expands to ::std::, so this is a way of

  1. saving two keystrokes (because you need a blank after _STD its actual keystroke-size is 5, not 4 :)), and
  2. a paranoid way of stating that you're doing something in the std namespace. The crazy thing is: iter_swap is declared right above this template. I know, stupid me, but I cannot think of a way how you could fool the compiler into not using your iter_swap here.

One other thing: the author is declaring an explicit array size, here:

void swap(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size])

But at least the Visual Studio 2013 compiler (with all warnings enabled) happily ignores this spec. You can do this without any problem:

void xtest(int a[20])
{
...
}
...
int a[3];
xtest(a);

and it won't so much as emit a beep. This also was my understanding based on discussions of array decaying. But OK, maybe this is meant as a hint to those unfortunate souls that try to understand the template headers.

The rest of the macro is pretty standard: if the two array pointers (really: pointers only!) are different, then there is a loop: enumerate the array using pointers, and swap the contents of the array (using iter_swap from above). One should mention a couple of potential issues with this function:

OK, the next template is really a variation on the swap theme, so let's look at it:

template
    <class _Ty>
    inline
    void swap(_Ty& _Left, _Ty& _Right)
        _NOEXCEPT_OP(
            is_nothrow_move_constructible<_Ty>::value && 
            is_nothrow_move_assignable<_Ty>::value)
    {
        // exchange values stored at _Left and _Right
        _Ty _Tmp = _Move(_Left);
        _Left = _Move(_Right);
        _Right = _Move(_Tmp);
    }

Let's look at the _NOEXCEPT bits first. It is supposed to say the following (even though we know it doesn't with Visual Studio 2013):

    noexcept(
        is_nothrow_move_constructible<_Ty>::value
            && 
        is_nothrow_move_assignable<_Ty>::value
    )

It is easy to understand the intent of this specification:

So let's look at the body of the function:

        // exchange values stored at _Left and _Right
        _Ty _Tmp = _Move(_Left);
        _Left = _Move(_Right);
        _Right = _Move(_Tmp);

Aha! This is probably a C++11-style "moving-swap". But what is this _Move? Well, if you try the Visual Studio browse information, you'll end up nowhere fast: it'll misleadingly point you to xutility, but what you're looking for really is defined in type_traits:

// TEMPLATE FUNCTION _Move
template
    <class _Ty>
    inline
    typename remove_reference<_Ty>::type&& _Move(_Ty&& _Arg) 
        _NOEXCEPT
    {
        // forward _Arg as movable
        return ((typename remove_reference<_Ty>::type&&)_Arg);
    }

OK, this is definitely a C++11 beast. First of, look at this:

#define _NOEXCEPT   throw ()

Basically this tells us that the Microsoft compiler doesn't really support noexcept and instead falls back to the throw () hack.

Second, going back to the template, the sole input parameter is _Ty&&, which (kudos to Effective Modern C++) is actually a universal reference. There is a nice discussion of this code on stackoverflow.com that explains how it works - probably better than I ever could. So take a minute and read the comment.

Having understood that we can see that the swap template above was basically a swap using C++11-style move operations (if possible), or copy operations (if necessary). Good! Next one:

template
    <class _Ty>
    inline
    void _Swap_adl(_Ty& _Left, _Ty& _Right)
    {
        // exchange values stored at _Left and _Right, using ADL
        swap(_Left, _Right);
    }

Phew! We are few lines in a first simple STL header and already we've seen the std::move magic, and now this awe inspiring comment:

// exchange values stored at _Left and _Right, using ADL

ADL is Argument Dependant Lookup and a description about it can be read here.

The executive summary here would be this: The compiler will choose the best fit among different overloaded swap implementations based on the arguments passed at runtime.

The obvious question here should be: why? Why on earth do I need this template? Wouldn't it be better to use plain and simple swap rather than the ugly-duckling _Swap_adl?

The above disussion on ADL notes something that could have an impact here; let me quote it:

ADL is the reason behind the established idiom for swapping two objects in generic code: 
using std::swap;
swap(obj1, obj2);
because calling std::swap(obj1, obj2) directly would not consider the user-defined swap() functions that could be defined in the same namespace as the types of obj1 or obj2, and just calling the unqualified swap(obj1, obj2) would call nothing if no user-defined overload was provided. In particular, std::iter_swap and all other standard library algorithms use this approach when dealing with Swappable types.

OK, so I see why you wouldn't want to write std::swap, but a) you didn't, and b) shouldn't plain old swap be OK?

I admit I don't know a convincing reason. Normally, I would argue this is just bad code, but we have already seen that the STL authors know their shit, so presumably there is a reason. If you, dear reader, happen to have a good idea, please contact me...

Piecewise construction and you

Next up: another mystery:

// STRUCT piecewise_construct_t
struct piecewise_construct_t
{
    // tag type for pair tuple arguments
};

const piecewise_construct_t piecewise_construct = piecewise_construct_t();

OK, this looks fairly stupid. But apparently piecewise_construct is an actual, official thing used to do, guess what, piecewise construction. I am glad that other people question the use-case behind this as well, so I am not alone.

Actually, what we're seeing here is a typical template programming pattern:

Trouble comes in pairs

OK, so far we've fooled around with the easy bits, but slowly but surely we're working our way up to std::pair. We start with a template forward declaration for tuple

// TEMPLATE STRUCT pair
template
    <class...>
    class tuple;

So far, so good. Next one:

template
    <class _Ty1, class _Ty2>
    struct pair
    {   
        // store a pair of values
        typedef pair<_Ty1, _Ty2> _Myt;
        typedef _Ty1 first_type;
        typedef _Ty2 second_type;

OK, the template starts harmlessly enough, with a couple of typedefs. Interestingly enough, std::pair is a template struct, not a class, and the only reason I can guess for this is that it makes everything public: by default. Also, my guess would be that _Myt is there only to safe a few keystrokes; first_type and second_type are standard defines that exist there as standard names.

    pair()
        : first(), second()
    {
        // default construct
    }

The default constructor initializes the two values to their defaults. Actually, let's discuss this a bit. Let's look at a simple class:

class foo
{
public:
    foo()
    {}
    
    int this_is_the_name_of_a_variable_NOT_its_type;
};

If you want to initialize this_is_the_name_of_a_variable_NOT_its_type to its default value, you can of course use this:

...
    foo() : this_is_the_name_of_a_variable_NOT_its_type(0)
    {}
..

But (and I admit I didn't know this before), you can also do this:

...
    foo() : this_is_the_name_of_a_variable_NOT_its_type()
    {}
..

This will initialize this_is_the_name_of_a_variable_NOT_its_type to its default value - which, for int, happens to be 0, but for other objects might be something else. The really strange thing here is we are using the variable name as a type, something that I was not aware you could do anywhere else. Really, it's like using the default constructor: but normally to specify that we would use the type, not the name...right?

There is a third way that I did know (and use): you can use the type and specify the default value for the type explicitly, like this:

...
    foo() : this_is_the_name_of_a_variable_NOT_its_type(int())
    {}
..

So now we have three methods of setting an int to zero. Note that this is a special treatment of the constructor: in normal code, you can use both of these:

    this_is_the_name_of_a_variable_NOT_its_type = 0;
    this_is_the_name_of_a_variable_NOT_its_type = int();

but you cannot use this:

    this_is_the_name_of_a_variable_NOT_its_type = this_is_the_name_of_a_variable_NOT_its_type();

Because, duh, this_is_the_name_of_a_variable_NOT_its_type is the name of a variable, NOT its type

Back to std::pair. Here is our next constructor:

    pair(const _Ty1& _Val1, const _Ty2& _Val2)
        : first(_Val1), second(_Val2)
    {
        // construct from specified values
    }

This looks like a pretty harmless constructor that uses two lvalue references to initialize both values. In a way, it is like two copy-constructors in a row.

    template
        <class _Other1,
            class _Other2,
            class = typename enable_if<is_convertible<const _Other1&, _Ty1>::value &&
                                          is_convertible<const _Other2&, _Ty2>::value,
                                          void>::type>
        pair(const pair<_Other1, _Other2>& _Right)
            : first(_Right.first), second(_Right.second)
        {
            // construct from compatible pair
        }

The intent of this constructor is pretty obvious: if _Other1 is convertible to _Ty1, and _Other2 is convertible to _Ty2, then this constructor applies. But let's check how that actually works. We start with this expression:

    class = typename enable_if<
        is_convertible<const _Other1&, _Ty1>::value && 
        is_convertible<const _Other2&, _Ty2>::value, void>::type

First of all, this is an unnamed template parameter. That means, the code doesn't actually use it. The expression after the = assigns a default value to that parameter, so nobody has to specify it either. Sounds strange? It gets better:

The enable_if code (actually, it is a template of sorts, but I would be hard pressed to find the exact name: is it a function? a method? a template? a struct? But I digress) What happens here is that the compiler either generates a valid type, or it fails to do so:

  1. If it generates a valid type, then this template has a default value, so only the first two parameters are considered when resolving the correct constructor overload.
  2. If it fails to do so, the third template parameter is undefined, so for those types the constructor will not be considered.

The definition of enable_if is in xtr1common, and with a little bit of reformatting it looks like this:

template
    <bool _Test, class _Ty = void>
    struct enable_if
    {
        // type is undefined for assumed !_Test
    };

So the core template does not define enable_if::type (which is another way of saying: if the compiler resolves the default template, it will not see the expression enable_if::type, so there won't be a valid default value for the above constructor, so it won't be a candidate for name resolution). But there is more, a template specialisation for true:

template
    <class _Ty>
    struct enable_if<true, _Ty>
    {
        // type is _Ty for _Test
        typedef _Ty type;
    };

This is template metaprogramming indeed, and it is worth doing a short recap because it is another one of those standard patterns for templates:

I have to admit: there is one thing I don't understand about this: why the default parameter type void, when the user of the macro also passes void? I am talking about this:

template
    <bool _Test<font color="#FF0000">, class _Ty = void</font>>
    struct enable_if
and
    class = typename enable_if<
        is_convertible<const _Other1&, _Ty1>::value && 
        is_convertible<const _Other2&, _Ty2>::value<font color="#FF0000">, void</font>>::type

If you happen to know a good answer, again, please contact me.

But we're not done yet. Looking back at our expression we see that we haven't looked at is_convertible yet, and this is defined in type_traits like this:

template
    <class _From, class _To>
    struct is_convertible _IS_CONVERTIBLE(_From, _To)
    {
        // determine whether _From is convertible to _To
    };

This doesn't tell us a lot. In particular, about the only thing one could infer from looking at this is that _IS_CONVERTIBLE is probably a macro, and it probably specifies a base-class for this struct. Let's look it up:

#define _IS_CONVERTIBLE(_From, _To) \
    : _Cat_base<__is_convertible_to(_From, _To)>

OK, what is this? The header comment tells us:

// COMPILER SUPPORT MACROS
// VC++ V14 SUPPORT

and indeed, Google is our friend: This is one of many Microsoft compiler extension for Type Traits: and it does what the name indicates: tells us if _From is convertible to _To.

So now let's go back to the template in all its beauty:

    template
        <class _Other1,
            class _Other2,
            class = typename enable_if<is_convertible<const _Other1&, _Ty1>::value &&
                                          is_convertible<const _Other2&, _Ty2>::value,
                                          void>::type>
        pair(const pair<_Other1, _Other2>& _Right)
            : first(_Right.first), second(_Right.second)
        {
            // construct from compatible pair
        }

We can summarize now how this works: If both template arguments are convertible to the base types of the tuple, then this constructor is a possible match. And in essence it is very similar to the 'copy-constructor-like' constructor we saw before. The only bit of magic really is using type traits to determine at compile time if this is a potential match.

Next up is the assignment operator, and that is pretty basic:

template
    <class _Other1, class _Other2>
    _Myt& operator=(const pair<_Other1, _Other2>& _Right)
    {
        // assign from compatible pair
        first = _Right.first;
        second = _Right.second;
        return (*this);
    }

This looks pretty boring by now. I want to point out one particular thing anyway: often, you are instructed to do a self-assignment test before doing the actual copy, somewhat like this:

template
    <class _Other1, class _Other2>
    pair& operator=(const pair<_Other1, _Other2>& _Right)
    {
        <font color="#FF0000">if( this != &_Right )
        {</font>
            // assign from compatible pair
            first = _Right.first;
            second = _Right.second;
            return (*this);
        <font color="#FF0000">}</font>
    }

But, this code more-or-less assumes that child values are safe with regards of self-assignment (as they always should) and therefor skips this as unnecessary.

Next up: our first variadic template:

    template<class _Tuple1,
        class _Tuple2,
        size_t... _Indexes1,
        size_t... _Indexes2> inline
        pair(_Tuple1& _Val1,
            _Tuple2& _Val2,
            _Arg_idx<_Indexes1...>,
            _Arg_idx<_Indexes2...>);

But it turns out to be an enormous anti-climax: this isn't really a template, it is another template forward declaration. So we'll dissect it when we find it in another header. Basically the same thing applies to the next template:

    template<class... _Types1,
        class... _Types2> inline
        pair(piecewise_construct_t,
            tuple<_Types1...> _Val1,
            tuple<_Types2...> _Val2)
            _NOEXCEPT_OP((is_nothrow_constructible<_Ty1, _Types1&&...>::value
                && is_nothrow_constructible<_Ty2, _Types2&&...>::value));

Again, this is only a forward declaration, not the actual fun part. OK, let's look at the next one:

template
    <class _Other1,
        class _Other2,
        class = typename enable_if<
            is_convertible<_Other1, _Ty1>::value && 
            is_convertible<_Other2, _Ty2>::value, void>::type>
    pair(_Other1&& _Val1, _Other2&& _Val2)
        _NOEXCEPT_OP((
            is_nothrow_constructible<_Ty1, _Other1&&>::value&& 
            is_nothrow_constructible<_Ty2, _Other2&&>::value))
        :   first(_STD forward<_Other1>(_Val1)),
            second(_STD forward<_Other2>(_Val2))
    {
        // construct from moved values
    }

OK, this is a template, but most of it should come in pretty natural by now.

        class = typename enable_if<
            is_convertible<_Other1, _Ty1>::value && 
            is_convertible<_Other2, _Ty2>::value, void>::type>

This is once again the template-overloading magic of enable_if, just like with the extended copy-constructor from above.

        _NOEXCEPT_OP((
            is_nothrow_constructible<_Ty1, _Other1&&>::value&& 
            is_nothrow_constructible<_Ty2, _Other2&&>::value))

by now poses only a very small mystery: what is is_nothrow_constructible<_Ty1, _Other1&&>::value: it is another one of the many Microsoft compiler extension for Type Traits that basically says: return a valid (true) type if _Ty1 can be constructed from a universal _Other1 reference.

But here is something new:

        :   first(_STD forward<_Other1>(_Val1)),
            second(_STD forward<_Other2>(_Val2))

This is a use of the C++11 std::forward: "perfectly forwarding" of _Val1 to the constructor of first. What it effectivelymeans is this:

Mysteries solved, on to the next one:

    template
        <class _Other1,
            class _Other2,
            class = typename enable_if<
                is_convertible<_Other1, _Ty1>::value && 
                is_convertible<_Other2, _Ty2>::value, void>::type>
        pair(pair<_Other1, _Other2>&& _Right)
            _NOEXCEPT_OP((is_nothrow_constructible<_Ty1, _Other1&&>::value && 
                          is_nothrow_constructible<_Ty2, _Other2&&>::value))
        :   first(_STD forward<_Other1>(_Right.first)),
            second(_STD forward<_Other2>(_Right.second))
        {
            // construct from moved compatible pair
        }

This is basically the same as the previous constructor, with a small exception: the previous one had this parameter list:

        pair(pair<_Other1, _Other2>&& _Right)

so you basically call it with two arguments, one for first and one for right, whereas this constructor is called for a std::pair instance:

        pair(pair<_Other1, _Other2>&& _Right)

I think you'll probably agree that having come so far the code in utility has lost lots of its threat-potential... But ok, there are more templates to come, let's check them:

    template
        <class _Other1, class _Other2>
        _Myt& operator=(pair<_Other1, _Other2>&& _Right)
            _NOEXCEPT_OP((is_nothrow_assignable<_Ty1, _Other1&&>::value &&
                          is_nothrow_assignable<_Ty2, _Other2&&>::value))
        {
            // assign from moved compatible pair
            first = _STD forward<_Other1>(_Right.first);
            second = _STD forward<_Other2>(_Right.second);
            return (*this);
        }

This is a move-assigment operator. It doesn't throw if moving the callers types doesn't throw. The only thing causing a slight unease while reading this code should be this: it uses std::forward rather than std::move to move the parameters. Once again this is a question I was unable to answer to my own satisfaction: if you know the answer, please contact me.

    _Myt& operator=(_Myt&& _Right)
        _NOEXCEPT_OP((is_nothrow_move_assignable<_Ty1>::value && 
                      is_nothrow_move_assignable<_Ty2>::value))
        {
            // assign from moved pair
            first = _STD forward<_Ty1>(_Right.first);
            second = _STD forward<_Ty2>(_Right.second);
            return (*this);
        }

Hm. Reading this one questions why this exists at all. Personally I think the template code would have sufficed, and just when I thought I had finally understood a bit of templates, the STL authors repeat the code for no reason I can discern. How is this different from the move-assignment operator template immediately before it?. You know the drill: if you know the answer, please contact me.

    void swap(_Myt& _Right)
        _NOEXCEPT_OP( _NOEXCEPT_OP(_Swap_adl(this->first, _Right.first)) && 
                      _NOEXCEPT_OP(_Swap_adl(this->second, _Right.second)))
        {
            // exchange contents with _Right
            if (this != &_Right)
            {
                // different, worth swapping
                _Swap_adl(first, _Right.first);
                _Swap_adl(second, _Right.second);
            }
        }

So we meet again, strange _Swap_adl friend. First, let's see what we can easily know about this function, and then look at its mysteries.

But none of this provides an obvious motivation for _Swap_adl over plain old swap, so I will keep this point open as well.

        _Myt& operator=(const _Myt& _Right)
        {
            // assign from copied pair
            first = _Right.first;
            second = _Right.second;
            return (*this);
        }

This is an assignment operator. Again, like we've seen with the assignment operator template earlier, there is no checking for self-assignment. But this also brings up the question we've already seen with the template move-assignment and the explicit move assignment: why have both, when they do precisely the same?

The class ends with some rather boring bits:

    _Ty1 first;     // the first stored value
    _Ty2 second;    // the second stored value
    };

Pair template functions

template
    <class _Ty1, class _Ty2>
    inline
    void swap(pair<_Ty1, _Ty2>& _Left, pair<_Ty1, _Ty2>& _Right)
        _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right)))
    {
        // swap _Left and _Right pairs
        _Left.swap(_Right);
    }

I mentioned it above already, this is duck typing: you can think of this as a specialisation of the std::swap template: for any two std::pairs, call the swap() member function to swap the contents.

template
    <class _Ty1, class _Ty2> 
    inline
    bool operator==(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test for pair equality
        return (_Left.first == _Right.first && _Left.second == _Right.second);
    }

This is an overloaded == operator that, given two pairs, will test whether they are equal: they are equal if both first and second members are equal

template
    <class _Ty1, class _Ty2>
    inline
    bool operator!=(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test for pair inequality
        return (!(_Left == _Right));
    }

Duh. Two std::pairs are not equal if they are ... surprise, surprise: not equals.

template
    <class _Ty1, class _Ty2>
    inline
    bool operator<(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test if _Left < _Right for pairs
        return (_Left.first < _Right.first ||
              (!(_Right.first < _Left.first) && _Left.second < _Right.second));
    }

This is the < operator.

template
    <class _Ty1, class _Ty2>
    inline
    bool operator>(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test if _Left > _Right for pairs
        return (_Right < _Left);
    }

This is another one of those less-is-more tricks: the > operator is implemented by swapping argument order and doing <.

template
    <class _Ty1, class _Ty2> 
    inline
    bool operator<=(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test if _Left <= _Right for pairs
        return (!(_Right < _Left));
    }

Rather obviously, <= can be expressed as !>, or as !< with swapped argument order...

template
    <class _Ty1, class _Ty2>
    inline
    bool operator>=(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right)
    {
        // test if _Left >= _Right for pairs
        return (!(_Left < _Right));
    }

The >= operator is ... !<

// TEMPLATE FUNCTION make_pair
template
    <class _Ty1, class _Ty2>
    inline
    pair<
        typename _Unrefwrap<_Ty1>::type,
        typename _Unrefwrap<_Ty2>::type>
        make_pair(_Ty1&& _Val1, _Ty2&& _Val2)
    {
        // return pair composed from arguments
        typedef pair<typename _Unrefwrap<_Ty1>::type, typename _Unrefwrap<_Ty2>::type> _Mypair;
        return (_Mypair(_STD forward<_Ty1>(_Val1), _STD forward<_Ty2>(_Val2)));
    }

Just when you thought things were getting too easy the STL comes up with another tricky one.

OK, let's start with the known unknowns: what is _Unrefwrap? Well, it is defined in type_traits like this:

// CLASS _Unrefwrap
template <class _Ty> class reference_wrapper;

template <class _Ty> struct _Unrefwrap_helper
    {
        // leave unchanged if not a reference_wrapper
        typedef _Ty type;
    };

template <class _Ty> struct _Unrefwrap_helper<reference_wrapper<_Ty>>
    {
        // make a reference from a reference_wrapper
        typedef _Ty& type;
    };

template <class _Ty> struct _Unrefwrap
    {   
        // decay, then unwrap a reference_wrapper
        typedef typename decay<_Ty>::type _Ty1;
        typedef typename _Unrefwrap_helper<_Ty1>::type type;
    };

Let me take a moment to assure you, dear reader, that while writing this page I often wanted to wring my hands in despair, and this is one of those moments where you think: may god punish the inventors of templates.

But let's do it in slo-mo

template <class _Ty> class reference_wrapper;

Another forward declaration. It is time to fire up the trusty documentation: quote: "std::reference_wrapper is a class template that wraps a reference in a copyable, assignable object", defined in xrefwarp and we're going to cross that bridge when we reach it. For now, we only know what it does and that it actually exists.

template <class _Ty> struct _Unrefwrap_helper
    {
        // leave unchanged if not a reference_wrapper
        typedef _Ty type;
    };

This template defines a new type _Unrefwrap_helper::type that is really an alias for _Ty. So when the compiler calls _Unrefwrap_helper<FOO>::type, it actually sees the type FOO. OK. Why bother?

template <class _Ty> struct _Unrefwrap_helper<reference_wrapper<_Ty>>
    {
        // make a reference from a reference_wrapper
        typedef _Ty& type;
    };

So now we have a specialisation: if you call _Unrefwrap_helper with a reference_wrapper for a type, you get the underlying type. And the final bit was this:

template <class _Ty> struct _Unrefwrap
    {   
        // decay, then unwrap a reference_wrapper
        typedef typename decay<_Ty>::type _Ty1;
        typedef typename _Unrefwrap_helper<_Ty1>::type type;
    };

So it decays the template parameter, and then it even removes the reference if someone is foolish enough to provide a reference_wrapper rather than an actual, honest-to-god, reference. It is like more decaying that std::decay.

But now that we know this, how does it help us with this:

// TEMPLATE FUNCTION make_pair
template
    <class _Ty1, class _Ty2>
    inline
    pair<
        typename _Unrefwrap<_Ty1>::type,
        typename _Unrefwrap<_Ty2>::type>
        make_pair(_Ty1&& _Val1, _Ty2&& _Val2)
    {
        // return pair composed from arguments
        typedef pair<typename _Unrefwrap<_Ty1>::type, typename _Unrefwrap<_Ty2>::type> _Mypair;
        return (_Mypair(_STD forward<_Ty1>(_Val1), _STD forward<_Ty2>(_Val2)));
    }

Well, let's look at this with examples:

  1. If the template arguments are plain types, then the result is a tuple of plain types as well. Example: 
                int a, b;
            puts(typeid(std::make_pair(a, b)).name()); 
            // -> prints 'struct std::pair<int,int>'
  2. If the template arguments are references to plain types, the result still is a tuple of plain types. Example: 
                int& c = a;
            int& d = b;
            puts(typeid(std::make_pair(c, d)).name());
            // -> prints 'struct std::pair<int,int>'
    This is true even if you explicitly specify the template arguments are references: 
                puts(typeid(std::make_pair&Lt;int&, int&>(c, d)).name());
            // -> prints 'struct std::pair<int,int>'
  3. Only if you are a smart-arse and pass a std::reference_wrapper, you get a pair of references: 
                std::reference_wrapper<int> wc(c);
            std::reference_wrapper<int> wd(d);
            puts(typeid(std::make_pair(wc, wd)).name());
            // -> prints 'struct std::pair<int &,int &>'

The funny thing is this: looking at _Unrefwrap above, one would have thought that even std::reference_wrapper should by law be decayed: but it isn't. Let's investigate this:

    puts(typeid(std::_Unrefwrap<std::reference_wrapper<int>>::type).name());
    // -> prints 'int'

Going back to the actual std::make_pair macro, it seems that this 

    typedef pair<typename _Unrefwrap<_Ty1>::type, typename _Unrefwrap<_Ty2>::type> _Mypair;

should, by law and custom, return a std::pair<int,int>, and the fact that it doesn't looks like a bug to me. Once again I am stumped: if you, dear reader, know a convincing reason why this is so please... contact me.

Rel-ops land

// TEMPLATE OPERATORS
namespace rel_ops
{
    // nested namespace to hide relational operators from std
    template
        <class _Ty>
        inline
        bool operator!=(const _Ty& _Left, const _Ty& _Right)
        {
            // test for inequality, in terms of equality
            return (!(_Left == _Right));
        }

Ok, now we're in rel_ops land. This namespace is used to define standard relational operations like != and > in terms of only two operators: == and <.

We have seen the logic behind this at work already above. What I find funny is that before, we had an explicit specification of these for std::pair, and now we define the very same things again, but in a different namespace, as templates. It is hard to see the logic behind all of this: shouldn't these overloads simply be compiler defaults? why define them in a super-special namespace std::rel_ops? I guess this has something to do with history, backward-compatibility and the general tendency of the C++ team to prefer complicated hacks to sweeping core changes...

But anyway, if you've come so far the following templates should pose no questions at all:

template
    <class _Ty>
    inline
    bool operator>(const _Ty& _Left, const _Ty& _Right)
    {
        // test if _Left > _Right, in terms of operator<
        return (_Right < _Left);
    }

template
    <class _Ty>
    inline
    bool operator<=(const _Ty& _Left, const _Ty& _Right)
    {
        // test if _Left <= _Right, in terms of operator<
        return (!(_Right < _Left));
    }

template
    <class _Ty>
    inline
    bool operator>=(const _Ty& _Left, const _Ty& _Right)
    {
        // test if _Left >= _Right, in terms of operator<
        return (!(_Left < _Right));
    }
}
_STD_END

Sizing up tuples

Tuples are really declared in tuple and not in utility, but since this header is a mixed bag anyway, somebody thought it a brilliant idea to include tuple sizes not alongside the actual tuple declaration, but somewhere else entirely, namely here: 

_STD_BEGIN
    // TEMPLATE STRUCT tuple_size
    template
        <class _Tuple>
        struct tuple_size
        {
            // size of non-tuple
            static_assert(_Always_false<_Tuple>::value, "The C++ Standard doesn't define tuple_size for this type.");
        };

OK, hold it right there. I can see what this is supposed to do, but let's check if we really get all of it.

One can immediately see that the static_assert will always be raised by this template. But why does it say 

    static_assert(_Always_false<_Tuple>::value, ...
and not simply 
    static_assert(false, ...

Well, looking at the definition of _Always_false in xstddef, one sees this:

template
    <class _Ty>
    struct _Always_false
    {
        // false value that probably won't be optimized away
        static const bool value = false;
    };

Hm. The comment seems to say that this is somehow better than plain-old false because it won't be optimized away. But how can that ever occur for a static_assert? You guessed right: if you, dear reader, have a convincing idea: please contact me.

But back to the actual template: what the default, unspecialized template says is basically this: "sorry, caller, I have no idea what size this tuple is". We'll see if things get more helpful as we get along...

template
    <class _Ty1, class _Ty2>
    struct tuple_size<pair<_Ty1, _Ty2>>
        : integral_constant<size_t, 2>
    {
        // size of pair
    };

OK, what is an integral_constant? Let's look in xtr1common, to find this:

// TEMPLATE CLASS integral_constant
template
    <class _Ty, _Ty _Val>
    struct integral_constant
    {
        // convenient template for integral constant types
        static const _Ty value = _Val;
        
        typedef _Ty value_type;
        
        typedef integral_constant<_Ty, _Val> type;
        
        operator value_type() const
        {
            // return stored value
            return (value);
        }
    };

I think I'll talk more about this once I get around to the header, but for now one thing should be obvious: by inheriting from integral_constant<size_t, 2>, tuple_size<pair<_Ty1, _Ty2>> inherits a member value that is 2. In other words, if you ask for the tuple_size of a pair, you get 2: pairs are tuples of 2.

template
    <class... _Types>
    struct tuple_size<tuple<_Types...> >
        : integral_constant<size_t, sizeof...(_Types)>
    {
        // size of tuple
    };

The first new thing I learnt reading this was that among the many changes brought by the introduction of variadic templates was also the introduction of the the new sizeof... operator, which unsurprisingly returns the sizeof a variadic items list.

Given that, the rest of the template becomes pretty obvious: really all the hard work resides in sizeof....

Now for some more fun definitions:

template
    <class _Tuple>
    struct tuple_size<const _Tuple>
        : tuple_size<_Tuple>
    {
        // size of const tuple
    };

template
    <class _Tuple>
    struct tuple_size<volatile _Tuple>
        : tuple_size<_Tuple>
    {
        // size of volatile tuple
    };

template
    <class _Tuple>
    struct tuple_size<const volatile _Tuple>
        : tuple_size<_Tuple>
    {
        // size of const volatile tuple
    };

All of this says that if you have const, volatile or const volatile tuples, the tuple_size is equal to the one of the plain vanilla object. Duh!

// TUPLE INTERFACE TO pair
template
    <size_t _Idx, class _Tuple>
    struct tuple_element;

template
    <int _Idx, class _Ty>
    struct _Pair_data;

OK, so tuple_element is a forward declaration, but _Pair_data is a lot more mysterious. It is a forward declaration alright, but it is also deliberately not defined. Really, I am not kidding you, the general template is not defined, so if you try to use it with just any old class, you'll get a compile time error:

std::_Pair_data<0, int> test;
// -> fails with error C2079: 'test' uses undefined struct 'std::_Pair_data<0,int>

Worry, not, here are the specialisations that make this undefined template actually useful:

template
    <class _Ty1, class _Ty2>
    struct _Pair_data<0, pair<_Ty1, _Ty2>>
    {
        // struct to pick out argument type and value at index 0
        typedef typename add_lvalue_reference<const _Ty1>::type _Ctype;
        typedef typename add_lvalue_reference<_Ty1>::type _Rtype;
        typedef typename add_rvalue_reference<_Ty1>::type _RRtype;

    static _Rtype _Val(pair<_Ty1, _Ty2>& _Pr)
    {
        // return value
        return (_Pr.first);
    }

    static _Ctype _Val(const pair<_Ty1, _Ty2>& _Pr)
    {
        // return value
        return (_Pr.first);
    }

    static _RRtype _Val(pair<_Ty1, _Ty2>&& _Pr)
    {
        // return value
        return (_STD forward<_Ty1>(_Pr.first));
    }
};

So the difference between _Rtype and _RRtype is not actually in the type, but in the fact that the compiler will move std::pair.first if a rvalue std::pair is passed to the _Val static method, and copy the lvalue otherwise. (And a const lvalue, if the input is const to begin with).

But what does it all mean? Well, this is obviously a helper class. It basically defines a set of overloaded functions

std::_Pair_data<0, std::pair<int, int>>::_Val(...)

that always return the first item of a std::pair. Given that, understanding the next template is a piece of cake: 

template
    <class _Ty1, class _Ty2>
    struct _Pair_data<<font color="#FF0000">1</font>, pair<_Ty1, _Ty2> >
    {
        // struct to pick out argument type and value at index 1
        typedef typename add_lvalue_reference<const _Ty2>::type _Ctype;
        typedef typename add_lvalue_reference<_Ty2>::type _Rtype;
        typedef typename add_rvalue_reference<_Ty2>::type _RRtype;

        static _Rtype _Val(pair<_Ty1, _Ty2>& _Pr)
        {
            // return value
            return (_Pr.second);
        }

        static _Ctype _Val(const pair<_Ty1, _Ty2>& _Pr)
        {
            // return value
            return (_Pr.second);
        }

        static _RRtype _Val(pair<_Ty1, _Ty2>&& _Pr)
        {
            // return value
            return (_STD forward<_Ty2>(_Pr.second));
        }
    };

Really this is more of the same: only if you pass the constant index 1 you'll get the second item of a std::pair.

template
    <class _Ty1, class _Ty2>
    struct tuple_element<0, pair<_Ty1, _Ty2> >
    {
        // struct to determine type of element 0 in pair
        typedef _Ty1 type;
    };

    template
    <class _Ty1, class _Ty2>
    struct tuple_element<1, pair<_Ty1, _Ty2> >
    {
        // struct to determine type of element 1 in pair
        typedef _Ty2 type;
    };

So this is the actual tuple_element definition. Actually, it is two specialisations of the template: if you use the index 0, you'll get the type of std::pair.first, and for 1 you'll get unsurprisingly std::pair.right. But note that these two functions do not refer to _Pair_data, so why was it defined at all?

template
    <int _Idx, class _Ty1, class _Ty2>
    inline
    typename _Pair_data<_Idx, pair<_Ty1, _Ty2> >::_Rtype
        get(pair<_Ty1, _Ty2>& _Pr) _NOEXCEPT
    {
        // get reference to element at _Idx in pair _Pr
        return (_Pair_data<_Idx, pair<_Ty1, _Ty2> >::_Val(_Pr));
    }

Aha! If you call std::get on a std::pair, the compiler will find this specialisation, and it will use the _Pair_data::_Val() method to find the actual element. Note: in a code review you would consider it bad style to not define this helper struct where you need it, but alas, STL writers have certain freedoms we don't. Also note that there are two more specialisations coming up

template
    <int _Idx, class _Ty1, class _Ty2>
    inline
    typename _Pair_data<_Idx, pair<_Ty1, _Ty2> >::_Ctype
        get(const pair<_Ty1, _Ty2>& _Pr) _NOEXCEPT
    {
        // get const reference to element at _Idx in pair _Pr
        return (_Pair_data<_Idx, pair<_Ty1, _Ty2> >::_Val(_Pr));
    }

The use of _Ctype gives it away: this is the specialisation if you pass in a const pair: you'll get const members back.

template
    <int _Idx, class _Ty1, class _Ty2>
    inline
    typename _Pair_data<_Idx, pair<_Ty1, _Ty2> >::_RRtype
        get(pair<_Ty1, _Ty2>&& _Pr) _NOEXCEPT
    {
        // get rvalue reference to element at _Idx in pair _Pr
        typedef typename _Pair_data<_Idx, pair<_Ty1, _Ty2> >::_RRtype _RRtype;
        return (_STD forward<_RRtype>(_Pair_data<_Idx, pair<_Ty1, _Ty2> >::_Val(_Pr)));
    }

And finally: this is the specialisation for rvalues: if you pass them in, you'll get the rvalue of the member back.

Summary

We have almost reached the end of utility, only a few lines remain:

_STD_END
_STD_BEGIN
namespace tr1 { // TR1 additions
using _STD get;
using _STD tuple_element;
using _STD tuple_size;
} // namespace tr1
_STD_END

Really just a couple of template forwards back from TR1-stuff which we'll elect not to discuss at this point. The standard end-of-header boilerplate follows:

 #pragma pop_macro("new")
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _UTILITY_ */

And finally, a few words for our friends, the lawyers:

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2012 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V6.00:0009 */

OK, so this was it: our very first STL header dissected. At this point I am fairly confident that it is indeed possible to read the STL code, if one is dedicated enough. But we have noted a couple of loose ends: things I couldn't quite resolve, and open questions. So let's see what the story will be for our next header... I can barely await it :)

->Back to the STL overview