Stephan T. Lavavej - Core C++, 7 of n

Sign in to queue

Description

In Part 7, STL teaches us about Usual Arithmetic Conversions, Template Metaprogramming, and shares some of the STL internal implementation ( some of it not yet released Smiley ). Many of you have asked for some treatment of TMP and STL delivers! Merry Christmas. Here's hoping you all have a wonderful 2013.

 

See part 1: Name Lookup
See part 2: Template Argument Deduction
See part 3: Overload Resolution
See part 4: Virtual Functions
See part 5: Explicit and Partial Specialization

See part 6: New C++11 features added to the Visual C++ 2012 compiler (CTP)

Embed

Download

Download this episode

The Discussion

  • User profile image
    tomkirbygre​en

    And a very Happy Chridtmas to you too Stephan! Here's hoping we'll get to see a lot more of you on Chnnel 9 in 2013. Major kudos for all your efforts this year mate.

  • User profile image
    Tominator20​05

    Happy Christmas to you Stephen,
    Bring on more C++ videos.
    Keep up the good work, an excellent Christmas present from C9 team.
    Thanks again Big Smile

  • User profile image
    Matt_PD

    Thank you for all your work, Stephen! Merry Christmas & Happy New Year! Smiley

  • User profile image
    Aeon

    Merry Christmas, great effort once again. Channel9 is  my one stop destination to listen and watch this and all the other videos on C++/STL/Haskell and so on and so forth. Thank you Mr. Stephan T. Lavavej, Charles and all the other nice people at Channel9.

  • User profile image
    Spetum

    Thank you Stephan and others. Merry Christmas and Happy new year.

  • User profile image
    abigagli

    Thank you Stephen, and Merry Christmas.

    A great video as usual, and this time for a too often ignored subject that I care very much about.

    Just to be sure I'm on the right path: in your example about the case of a "-2 billion" signed long to be added to a "-7 billion" signed long long (@ around 30:20 in the video), the conversion of the "-2 billion" should be to a LL not a ULL, right?

  • User profile image
    yanshuai

    Thank you Stephan for all you brought to us. 

    Look forward to seeing you often on Channel9. 

    Merry Christmas and Happy New Year! 

  • User profile image
    bkircher

    Just wanted to join in the chorus. Thanks so much for all the hard work. I really enjoy these lectures. They taught me a lot about the core language and the Standard Template Library and Visual Studio's implementation there of. They gave me lots of insights I'm really using in my day-to-day work. Stephan, you are my hero!

    So thanks Stephan, Charles, and the invisible team behind the camera.

  • User profile image
    Philhippus

    I would be of the opinion that a programmer trying to pass a value outside of a type's range deserves the spanking that the compiler would hand out.

    Well it seems now at least the STL will give those (us?) bad programmers a pass due to its use of template metaprogramming. Talking of which, I would like to see more lectures about/including the arcane and mysterious world of template metaprogramming.

    Keep up the awesome work!


  • User profile image
    STL

    Thanks everyone!

    abigagli> in your example about the case of a "-2 billion" signed long to be added to a "-7 billion" signed long long (@ around 30:20 in the video), the conversion of the "-2 billion" should be to a LL not a ULL, right?

    Argh, I simultaneously misspoke and scribbled the wrong thing on the whiteboard. (I might have been distracted by correcting myself from saying "promoted" to saying "converted" earlier.) You're absolutely correct - the signed long is widened to signed long long. I should have said "signed long long" and scribbled "sll" on the whiteboard at that moment. I correctly said "value preserving" and "negative 9 billion" immediately afterwards.

    I apologize for the confusion, and thank you for the valuable correction.

    Philhippus> I would be of the opinion that a programmer trying to pass a value outside of a type's range deserves the spanking that the compiler would hand out. Well it seems now at least the STL will give those (us?) bad programmers a pass due to its use of template metaprogramming.

    The Standard says that comparing a signed char to an unsigned long long must compile (although the compiler can warn about anything if it wants to). Similarly, passing a range of signed char and a value of unsigned long long to std::find() must compile.

    I would characterize this as "squirrelly", but the rules are the rules, and the STL has to follow them.

    > Talking of which, I would like to see more lectures about/including the arcane and mysterious world of template metaprogramming.

    I'll look for more places to mention it. I really don't like presenting template metaprogramming in the absence of realistic context, because that makes it seem bizarre and pointless. find() is a great example because we have good reasons to do lots of template metaprogramming:

    * We need to determine when the stars align for the memchr() optimization, which requires detecting when the iterator (after "unwrapping") is a pointer to a possibly-const byte, and the value is integral.

    * Then we need a 4-way test for all combinations of signed/unsigned ranges and signed/unsigned values.

    * Plus a fifth case for when a small negative element could be equal to a huge unsigned value.

    * Plus a special case for bool (mostly to avoid compiler warnings but also to avoid programmer headaches - there's enough going on here already).

  • User profile image
    Johnaton

    Excellent presentation, Thank you for all your efforts on Channel 9.

    Hope you and everyone at Microsoft, and Channel 9, had a wonderful Christmas, and has a Happy New Year!

  • User profile image
    Alex

    Hi STL,
    very cool lecture!! thank you! is there any approx info about STL update? we want initializer lists!! :)

  • User profile image
    Johannes Schaub

    Reminds me of my silly safe_cast answer on StackOverflow :) http://stackoverflow.com/a/998982/34509

  • User profile image
    soc

    I understand why you have the fifth and sixth overloads, but is there a reason you didn't just define the first four as one function using std::numeric_limits' ::lowest and ::max?

  • User profile image
    Fredrik

    I was recently interested in allocators while fighting the horribly outdated CRT that prevents you from using your own much faster allocator.

    I discovered Mr Lavavej's mallocator.

    I was going to update it when I discovered an old bug that I assumed would have been fixed in Visual Studio 2012.

    Why haven't this bug been fixed yet?!
    Is this what microsoft calls C++ Renaissance and GoingNative?
    Very disappointing. Makes me sad and angry to be lied to my face with false advertisement.

    Why am I worried about a warning?
    Because the compiler could silently do the wrong thing in the background.

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

    The still-alive bug:
    C4100 // unreferenced formal parameter

    Caused by this code:
    template <typename T> void Mallocator<T>::destroy(T * const p) const {
    p->~T();
    }

    I checked STL allocator and in xmemory header they are disabling that warning there too.

    I'm asking this here because I assume Mr Lavavej would know the answer to this question.
    To be honest the msdn forums are useless and a wast of time.

  • User profile image
    Fredrik

    Got very ugly with all the special treatment of the crappy c++ compiler from microsoft but here it is.

    Tear it to pieces, please.

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

    // The following headers are required for all allocators.
    #include <stddef.h> // Required for size_t and ptrdiff_t
    #include <new> // Required for placement new and std::bad_alloc
    #include <stdexcept> // Required for std::length_error

    // The following headers contain stuff that Mallocator uses.
    #include <stdlib.h> // For malloc() and free()
    #include <iostream> // For std::cout
    #include <ostream> // For std::endl

    // The following headers contain stuff that main() uses.
    #include <list> // For std::list
    #include <memory> // For std::addressof

    // Visual Studio 2012
    #define INFERIOR_COMPILER_VER 1700511061 // 17.00.51106.1

    #if _MSC_FULL_VER <= INFERIOR_COMPILER_VER
    #define NOEXCEPT
    #else
    #define NOEXCEPT noexcept
    #endif

    template <typename T> class Mallocator;

    // specialize for void:
    template <>
    class Mallocator<void> {
    public:
    typedef void* pointer;
    typedef const void* const_pointer;
    // reference-to-void members are impossible.
    //typedef void& reference;
    //typedef const void& const_reference;
    typedef void value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    template <typename U> struct rebind {
    typedef Mallocator<U> other;
    };
    };

    template <typename T>
    class Mallocator {
    public:
    // The following will be the same for virtually all allocators.
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    // The following must be the same for all allocators.
    template <typename U> struct rebind {
    typedef Mallocator<U> other;
    };

    // Default constructor, copy constructor, rebinding constructor, and destructor.
    // Empty for stateless allocators.
    Mallocator() NOEXCEPT { }
    Mallocator(const Mallocator&) NOEXCEPT { }
    template <typename U> Mallocator(const Mallocator<U>&) NOEXCEPT { }
    ~Mallocator() { }

    pointer address(reference r) const NOEXCEPT {
    return std::addressof(r);
    }

    const_pointer address(const_reference r) const NOEXCEPT {
    return std::addressof(r);
    }

    size_type max_size() const NOEXCEPT {
    // The following has been carefully written to be independent of
    // the definition of size_t and to avoid signed/unsigned warnings.
    return (static_cast<size_type>(0) - static_cast<size_type>(1)) / sizeof(T);
    }

    // The following will be different for each allocator.
    pointer allocate(size_type n, Mallocator<void>::const_pointer /*hint*/ = 0) const {
    // Mallocator prints a diagnostic message to demonstrate
    // what it's doing. Real allocators won't do this.
    std::cout << "Allocating " << n << (n == 1 ? " object" : "objects")
    << " of size " << sizeof(T) << "." << std::endl;

    // The return value of allocate(0) is unspecified.
    // Mallocator returns NULL in order to avoid depending
    // on malloc(0)'s implementation-defined behavior
    // (the implementation can define malloc(0) to return NULL,
    // in which case the bad_alloc check below would fire).
    // All allocators can return NULL in this case.
    if (n == 0) {
    return nullptr;
    }

    // All allocators should contain an integer overflow check.
    // The Standardization Committee recommends that std::length_error
    // be thrown in the case of integer overflow.
    if (n > max_size()) {
    throw std::length_error("Mallocator<T>::allocate() - Integer overflow.");
    }

    // Mallocator wraps malloc().
    void* const pv = malloc(n * sizeof(T));

    // Allocators should throw std::bad_alloc in the case of memory allocation failure.
    if (pv == nullptr) {
    throw std::bad_alloc();
    }

    return static_cast<pointer>(pv);
    }

    void deallocate(pointer p, size_type n) const {
    // Mallocator prints a diagnostic message to demonstrate
    // what it's doing. Real allocators won't do this.
    std::cout << "Deallocating " << n << (n == 1 ? " object" : "objects")
    << " of size " << sizeof(T) << "." << std::endl;

    // Mallocator wraps free().
    free(p);
    }

    #if _MSC_FULL_VER <= INFERIOR_COMPILER_VER
    void construct(pointer p) const {
    void* const pv = static_cast<void* const>(p);
    ::new (pv) T();
    }

    void construct(pointer p, const_reference t) const {
    void* const pv = static_cast<void* const>(p);
    ::new (pv) T(t);
    }

    void construct(pointer p, value_type&& t) const {
    void* const pv = static_cast<void* const>(p);
    ::new (pv) T(std::forward<value_type>(t)); // Still confused about move vs forward, not sure which one to use
    }

    void destroy(pointer p) const; // Defined below.
    #else
    template<class U, class... Args>
    void construct(U* p, Args&&... args) {
    void* const pv = static_cast<void* const>(p);
    ::new (pv) U(std::forward<Args>(args)...);
    }

    template <class U>
    void destroy(U* p) {
    p->~U();
    }
    #endif

    // Note: The standard say these should be globals
    // not sure if it matter they are inside the class or not.

    // Returns true if and only if storage allocated from *this
    // can be deallocated from other, and vice versa.
    // Always returns true for stateless allocators.
    bool operator==(const Mallocator& other) const NOEXCEPT {
    return true;
    }

    bool operator!=(const Mallocator& other) const NOEXCEPT {
    return !(*this == other);
    }

    // Allocators are not required to be assignable, so
    // all allocators should have a private unimplemented
    // assignment operator. Note that this will trigger the
    // off-by-default (enabled under /Wall) warning C4626
    // "assignment operator could not be generated because a
    // base class assignment operator is inaccessible" within
    // the STL headers, but that warning is useless.
    private:
    Mallocator& operator=(const Mallocator&);
    };

    // A compiler bug causes it to believe that p->~T() doesn't reference p.
    // Note: Disabling a warning doesn't work inside a class which is why the function is here.
    #if _MSC_FULL_VER <= INFERIOR_COMPILER_VER
    #pragma warning(push)
    #pragma warning(disable: 4100) // unreferenced formal parameter
    #endif

    // The definition of destroy() must be the same for all allocators.
    template <typename T> void Mallocator<T>::destroy(pointer p) const {
    p->~T();
    }

    #if _MSC_FULL_VER <= INFERIOR_COMPILER_VER
    #pragma warning(pop)
    #endif

    int main() {
    using namespace std;

    cout << "Constructing l:" << endl;

    list<int, Mallocator<int> > l;

    cout << endl << "l.push_back(1729):" << endl;

    l.push_back(1729);

    cout << endl << "l.push_back(2161):" << endl;

    l.push_back(2161);

    cout << endl;

    for (auto i = l.cbegin(); i != l.cend(); ++i) {
    cout << "Element: " << *i << endl;
    }

    cout << endl << "Destroying l:" << endl;
    }

    /*
    Using Visual Studio 2012 (fully updated as of 2013-01-05)

    ->Release x64:
    Constructing l:
    Allocating 1 object of size 24.

    l.push_back(1729):
    Allocating 1 object of size 24.

    l.push_back(2161):
    Allocating 1 object of size 24.

    Element: 1729
    Element: 2161

    Destroying l:
    Deallocating 1 object of size 24.
    Deallocating 1 object of size 24.
    Deallocating 1 object of size 24.

    ->Debug x64:
    Constructing l:
    Allocating 1 object of size 24.
    Allocating 1 object of size 16.

    l.push_back(1729):
    Allocating 1 object of size 24.

    l.push_back(2161):
    Allocating 1 object of size 24.

    Element: 1729
    Element: 2161

    Destroying l:
    Deallocating 1 object of size 24.
    Deallocating 1 object of size 24.
    Deallocating 1 object of size 24.
    Deallocating 1 object of size 16.
    */

  • User profile image
    STL

    Alex> is there any approx info about STL update? we want initializer lists!! Smiley

    I can't talk about release dates, sorry.

    soc> I understand why you have the fifth and sixth overloads, but is there a reason you didn't just define the first four as one function using std::numeric_limits' ::lowest and ::max?

    We define find() in our internal header <xutility>, which is included by almost everything and doesn't drag in <limits>.

    Fredrik> Because the compiler could silently do the wrong thing in the background.

    It's a spurious warning. It doesn't lead to silent bad codegen. Nowadays I'd just suppress it with a (void) cast. (I did report it to the compiler team.)

    C++11's minimal allocator interface doesn't require destroy() anymore, which is nice.

  • User profile image
    STL

Add Your 2 Cents