Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

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

Download

Right click “Save as…”

Welcome to another installment of C9 Lectures covering the powerful general C++ library, STL. Joining us once again is the great Stephan T. Lavavej, Microsoft's keeper of the STL cloth (this means he manages the partnership between the owners of STL (dinkumware) and Microsoft, including, of course, bug fixes and enhancements to the STL that ships as part of Visual C++). Simply, Stephan is a C++ library developer.

As is Stephan's nature, he elaborates on technical details in very substantive way. The Standard Template Library, orSTL, is a C++ library of container classes, algorithms, and iterators. STL provides many fundamental algorithms and data structures. Furthermore, the STL is a general-purpose library: its components are heavily parameterized, such that almost every component in the STL is a template.

Merry Christmas to all Niners who celebrate it! This is the last episode of STL's intro to STL series. A great way to end the year and a nice gift for all of you out there who are interested in and/or practice the art of native programming with C++. Enjoy. Learn.

In part 10, the final chapter in this magnificent introductory series covering the STL, Stephan introduces us to type traits.

Stephan (I guess we can just call him STL now, eh?) will be back!! Look for a new series on advanced C++ topics and deeper dives into the implementation details of the STL. Yes, Advanced STL with STL is on the horizon. Much thanks and praise for Stephan's exemplary lectures!

Enjoy! Learn!

Books mentioned by Stephen:

The C++ Standard Library: A Tutorial And Reference by Nicolai M. Josuttis
Effective STL by Scott Meyers

[STL Introduction lecture links]

Part 1 (sequence containers)

Part 2 (associative containers)

Part 3 (smart pointers)

Part 4 (Nurikabe solver) - see Wikipedia's article and Stephan's updated source code

Part 5 (Nurikabe solver, continued)

Part 6 (algorithms and functors)

Part 7 (algorithms and functors, continued)

Part 8 (regular expressions)

Part 9 (rvalue references)

Part 10 (type traits)

Tags:

Follow the Discussion

  • felix9felix9 the cat that walked by itself

    AH, so nice ! A holidy gift !

  • Oh Oh Good!

    But,  this episode is too hard. Crying

    Happy new year to everyone!!

    Thanks STL.

     

  • new2stlnew2stl

    Very nice. I have to say it end with gold key.
    Thank you.
    Happy new year!

  • This was good stuff as always with one small yet annoying thing, 1.5 gigs for 44 minutes of video goodness, Charles, really ?!  Expressionless


    is it just me or doesn't that seem oddly high for just 44 minutes ?  Perplexed

    is this yet another example of why wmv is bad or is it that editor again i've been hearing so much about ?

  • CharlesCharles Welcome Change

    , Mr Crash wrote

    This was good stuff as always with one small yet annoying thing, 1.5 gigs for 44 minutes of video goodness, Charles, really ?!  Expressionless


    is it just me or doesn't that seem oddly high for just 44 minutes ?  Perplexed

    is this yet another example of why wmv is bad or is it that editor again i've been hearing so much about ?

    You can blame me. I wont be able to fix it until sometime in early '11, though. Sorry.

    C

  • These vids are really good. But, I am sad that they have ended Sad

    Have they?

  • STLSTL

    [Spetum]
    > But, this episode is too hard.

    At what point do you start to get confused?

    [srikalyan]
    > These vids are really good. But, I am sad that they have ended
    > Have they?

    This is the end of the introductory series, where I assumed viewers were familiar with C++ but not the STL's interface. Shortly after I return from vacation I'll begin filming the advanced series, where I will assume familiarity with the STL's interface but not its implementation.

  • petkepetke

    Just wanted to say: Good job, and please keep these videos coming. I look forward to the second series. The meta-programming and functional programming style in C++ would be cool to learn more about. And I expect there is lots of that in your implementation of the STL. 
    Oh and Happy Yule Goat Day!

  • GordonGordon

    @STL: Here's a slightly off-topic question: Can GCC be made usb-thumb drive portable ? Would be nice to have a compiler handy everywhere you go. Bloaty-slow vs2010 should have a portability feature...

  • Evgeniy++Evgeniy++

    Great stuff, Stephen! Thank you very much! And Happy new Year! :-D

  • HMHM

    Thank alot Stephen. The whole series is very valuable to me.
    Wishing you a New New Year.

  • C64C64

    Thank you very much Stephan (and Charles) for this interesting series introducing STL!

    Happy New Year!

     

  • STLSTL

    Thanks for the kind words, everyone.

    Gordon: Yes, that's possible. I learned how to do that in college.

  • KimKim

    @STL:
    Why not just do:
    template <typename T> void foo(T t){    if(std::is_integral<T>::value)        std::cout << "integral";    else        std::cout << "not integral";}vs your introductory piece?

  • felix9felix9 the cat that walked by itself

    compile-time vs runtime ?

  • STLSTL

    Kim: That's a good question, and it's sometimes convenient to do so. (The optimizer can trivially see through this, so performance is not an issue. It triggers "conditional expression is constant" warnings, but I find those to be of dubious value in the first place.) However, it's not always possible. Consider what happens when code for the "true" case won't compile for the "false" case or vice-versa.

    As a general rule, in the STL's implementation we rely on overload resolution instead of if-statements so we can avoid having to determine whether both branches will compile for all possible cases.

  • KimKim

    @STL: Ah, I see. The overload resolution bit makes good sense. Could you provide a trivial example that would fail a specific branch, just for completeness?
    Thank you for your lectures!

  • STLSTL

    Here's an example from the STL. If you're given two forward-or-better iterators first and last, you can determine the distance between them by counting how many invocations of ++first it takes to make first == last. If they're really random-access iterators, the expression "last - first" is much more efficient (O(1) versus O(N)), but that won't compile for bidirectional-or-weaker iterators.

  • DeepDeep

    Stephen your videos are fantastic!
    Is it just me or is this happening to all of us. The file
    C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 10 of 10
     
    is does not play properly. It gets stuck in the first minute and jumps 15 minutes and then 10 minutes.... 
     
     

  • CharlesCharles Welcome Change

    @Deep: I'm not experiencing this behavior. Is there a particular file (format) where you're seeing this?

    C

  • DeepDeep

    @Charles: Yes. It is the  High Quality WMV format file. I am playing it in VLC media player version 1.1.5 under Windows Vista Home Premium with 4 GB of RAM.

  • The hand gesture in the screen shot looks like Stephan is performing in a rap video. "Yo mother******, check these type traits out..."

    Again, superb video. Keep the stuff coming!

  • CharlesCharles Welcome Change

    @Deep: Thanks for the details. Are you streaming the file or did you download it first? When "streaming" (which is really just downloading the file and playing chunks of it in this case...), buffering will cause many pauses on slower connections. Also, this file is huge so it's extra annoying. I suggest you right-click the WMV High link and wath after the download completes.

    C

     

  • KimKim

    @STL: That solidifies my understanding, thank you very much! When you say "don't use type_traits indiscriminately" do you mean in relation to SFINAE or just type_traits in general?
    Again, thanks for these lectures, they're excellent.

  • This has been a wonderful series of C++ lectures and I'm really looking forward the advanced series in 2011. A big tip of the hat goes out to Stephan, Charles and the whole C9 crew.

  • STLSTL

    [Kim]
    > When you say "don't use type_traits indiscriminately" do you mean in relation to SFINAE or just type_traits in general?

    I recall saying in the video that SFINAE should be used rarely and carefully. If I misspoke and said type traits instead of SFINAE, I apologize for the error. (SFINAE is just one of the things that you can do with type traits; I haven't seen people go nuts with type traits in general, although like everything there are probably ways to abuse them.)

    SFINAE is dangerously powerful because it silently removes overloads from the set of candidates. It's really a tool for experts; even the Standardization Committee has been learning how to use it effectively.

  • @Gordon: MinGW (Minimalist GNU for Windows) can provide gcc and g++ for use off of a portable device (i.e. usb thumb-drive).  Additionally, MinGW ... and MSYS (the MinGW Shell) ... can be "installed" with non-admin rights ... the MinGW installer just needs a folder with no spaces in its path to which it will download all the relevent files and subfolders.

    Previous MinGW installers were worthless; however, the current MinGW installer is outstanding (in comparison).  MinGW can be downloaded here:  http://sourceforge.net/projects/mingw/

    At the time that I'm writing this, "mingw-get-inst-20101030.exe" is the current installer and that installer downloads and installs gcc and g++ version 4.5.0.  The installer can also be used to install MSYS, so ensure that you also install the MSYS Basic System ... this will give you a shell that includes make for makefiles and a number of other utilities.

    Here are step-by-step screen captures of what you should see during the install process:  http://www.joshuaburkholder.com/glut/step_1/

    After the install is complete, just copy and paste the MinGW folder to your portable device ... and ensure that there are no spaces in MinGW's new path.  For ease of access to MSYS ... and therefore to the versions of gcc and g++ in MinGW, create a link to "C:\MinGW\msys\1.0\msys.bat" (or the msys.bat file wherever you installed MinGW) and change the link's "Start in:" path to "C:\MinGW\msys\1.0\bin" (or similar).

    Hope This Helps,
    Joshua Burkholder

    NOTE:  By default, executables built with MinGW's g++ dynamically link to the following DLLs: "C:\MinGW\bin\libgcc_s_dw2-1.dll" and "C:\MinGW\bin\libstdc++-6.dll" ... hence, you should use the

    -enable-auto-import
    flag with g++ when building executables in this default setting.  The current installer does not pollute your PATH environment variable, so you may want to add C:\MinGW\bin (or similar) to your System or User PATH environment variable so that your g++ produced EXEs can find those DLLs ... esp. if you are going to launch those EXEs by double-clicking on them.  MSYS temporarily prepends C:\MinGW\msys\1.0\local\bin (if it exists), C:\MinGW\bin, and C:\MinGW\msys\1.0\bin to the PATH environment variable ... so if you run your EXEs from MSYS, your executables will find the needed DLLs.  Or, you can make copies of these two DLLs and place them next to your EXE.  Alternatively, you can just statically link those libraries to your EXE by using the
    -static
    flag with g++ ... which adds about 1 MB to your executable ... and allows double-click execution of your EXE without having to pollute your PATH environment variable or without having to place DLLs next to your EXE.

    NOTE:  To change the /mingw alias from C:\MinGW to whatever the portable device path is, edit C:\MinGW\msys\1.0\etc\fstab.

  • @Charles:  I'm trying to downlead the high quality WMV file.  Each of my several attempts failed with this Download Error: "C9LecturesSTLonSTLp10_2MB_ch9.wmv could not be saved, because the source file could not be read.  Try again later, or contact the server administrator."   Is the file itself OK, or is it my connection?  Thanks!

  • CharlesCharles Welcome Change

    @Magentus: Could be your connection. We've received no other reports on this matter. Are you on a high speed line?

    C

  • PhilhippusPhilhippus

    I have watched all the episodes and each one is a wealth of knowledge. To be getting this quality of lectures for free is kind of mind boggling; the perks of our time.
    I have recently finished reading "C++ for Programmers" and I noticed STL (the man) is in the credits for having contributed to its publication. I found the book to be very thorough - almost too much so in its delivery to the point of repetition, making some parts monotonous reading, but top quality nevertheless.
    There is a short section in the book on 'Overloading Function Templates' (pg 586) which I assume is what Stephan discussed in the video, though it doesn't go into the same amount of detail. I feel there is more to be said about template metaprogramming and we have seen only a small part here (I don't mean going through every function). Am I right?
    Looking forward to the next series, keep it up!
    P.

  • @Philhippus:Yes, Stephan has only scratched the surface of template metaprogramming (i.e. using C++ templates to create/modify C++ code at compile-time).  Here are a few good references that go into greater detail:

    These books are outstanding ... esp. C++ Templates - The Complete Guide.  Alexandrescu's book is about more than just template metaprogramming ... however, it applies template metaprogramming throughout the text and is an excellent book for showing what can be done with template metaprogramming.  Ensure that you look at the correction to Typelists (i.e. use templates, not #defines, to create lists of types) that Alexandrescu made here: http://www.drdobbs.com/cpp/184403813

    NOTE:  There is also a horribly written book called "C++ Template Metaprogramming - Concepts, Tools, and Techniques from Boost and Beyond".  If you can get through this book ... with its coverage of template metaprogramming for seemingly template metaprogramming's sake and its occasional lack of structure & direction, then you will pick up some template metaprogramming techniques ... and (most importantly) be introduced to the template metaprogramming library called MPL from boost.org:  http://www.boost.org/doc/libs/1_45_0/libs/mpl/doc/index.html  . However, the documentation for Boost's MPL is about as good as the book, so I would go to the documentation first ( http://www.boost.org/doc/libs/1_45_0/libs/mpl/doc/tutorial/tutorial_toc.html  ) ... and then take a look at that book at a library or a bookstore (rather than wasting your money on it ... like I did).

    Hope This Helps,
    Joshua Burkholder

  • HansHans

    Not properly playing epsiode 10 with VLC:
    @Charles: Have same issue with hq WMV episode 10 on VLC 1.1.5.  Have Win7-64 and downloaded the file completely before playing.
    Windows Media Player has no problems to play it so it seems to be a VLC problem.

  • Stephan, any news on the upcoming advanced STL series? Really looking forward to watching it Smiley

  • PhilhippusPhilhippus

    @Burkholder: Thanks for the tips. That adds to my reading list. As with any subject, it's harder to find material once you get off the elementary stuff, so hopefully there's a worthwhile audience for Stephan to get into more advanced programming!

  • STLSTL

    NotFredSafe: Charles will be back next week, and we'll schedule a filming session soon afterwards (hopefully they're done remodeling the usual studio).

  • maikmaik

    Nice video. You explain very well.

  • Thanks for the great presentation! Please let me know if the source code you've discussed, especially for the game in the 3&4th epicsode is available for download.

    Thanks!

  • STLSTL

    My Nurikabe source code is at http://cid-e66e02dc83efb165.office.live.com/browse.aspx/nurikabe and a table explaining the performance improvements I've made is at http://blogs.msdn.com/b/vcblog/archive/2010/10/25/video-introduction-to-the-stl-parts-6-and-7.aspx .

  • MichaelMichael

    Are you planning on releasing the hi-res mp4? Please...?
    I've only seen #9 so far, but brilliant work Stephan, thanks very much.

  • STL said

    Today I only have my laptop to show you code. You'll be spared my horrible scribblings on the whiteboard this time.

    I miss your "horrible scribblings" Wink When will the new series start? Can't wait!

  • STLSTL

    Filming is scheduled for Friday, Feb 4.

  • devcodexdevcodex SWGANH.com

    Hi STL,

    This was another great episode and I'm looking forward to the new series! I've learned a great deal from the whole series and it's had a significant impact on the code I write. Thanks for all the effort you put into this!

    I was just working on a bit of code necessary for converting endianness when dealing with integer types in network code. Having recently watched this episode and remembering your solution presented in episode 3 for containers I put together this solution, I'm sure it's not perfect but thanks to these shows I feel it's a much more robust and flexible solution than what I would have come up with in the past.

    #include <cstdint>
    #include <algorithm>
    #include <iostream>
    #include <limits>
    
    namespace anh {
    
        namespace detail {
            /// @TODO Remove quotes from around constexpr when visual studio begins
            /// supporting that c++0x feature.
            /*constexpr*/ bool inline is_big_endian() {
                uint16_t x = 1;
                return !(*reinterpret_cast<char*>(&x));
            }
    
            struct bit8_tag{};
            struct bit16_tag{};
            struct bit32_tag{};
            struct bit64_tag{};
    
            template<typename T> struct integer_traits;
            
            template<>
            struct integer_traits<int8_t> {
                typedef bit8_tag category;
            };
            
            template<>
            struct integer_traits<uint8_t> {
                typedef bit8_tag category;
            };
            
            template<>
            struct integer_traits<int16_t> {
                typedef bit16_tag category;
            };
            
            template<>
            struct integer_traits<uint16_t> {
                typedef bit16_tag category;
            };
            
            template<>
            struct integer_traits<int32_t> {
                typedef bit32_tag category;
            };
            
            template<>
            struct integer_traits<uint32_t> {
                typedef bit32_tag category;
            };
            
            template<>
            struct integer_traits<int64_t> {
                typedef bit64_tag category;
            };
            
            template<>
            struct integer_traits<uint64_t> {
                typedef bit64_tag category;
            };
            
            template<typename T>
            T swap_endian_(T value, bit8_tag) {
                return value;
            }
    
            template<typename T>
            T swap_endian_(T value, bit16_tag) {
                return (value >> 8) | (value << 8);
            }
            
            template<typename T>
            T swap_endian_(T value, bit32_tag) {
                return (value >> 24) |
                    ((value & 0x00FF0000) >> 8) | ((value & 0x0000FF00) << 8) |
                    (value << 24);
            }
            
            template<typename T>
            T swap_endian_(T value, bit64_tag) {
                return (value  >> 56) |
                #ifdef _WIN32
                    ((value & 0x00FF000000000000) >> 40) |
                    ((value & 0x0000FF0000000000) >> 24) |
                    ((value & 0x000000FF00000000) >> 8)  |
                    ((value & 0x00000000FF000000) << 8)  |
                    ((value & 0x0000000000FF0000) << 24) |
                    ((value & 0x000000000000FF00) << 40) |
                #else
                    ((value & 0x00FF000000000000LLU) >> 40) |
                    ((value & 0x0000FF0000000000LLU) >> 24) |
                    ((value & 0x000000FF00000000LLU) >> 8)  |
                    ((value & 0x00000000FF000000LLU) << 8)  |
                    ((value & 0x0000000000FF0000LLU) << 24) |
                    ((value & 0x000000000000FF00LLU) << 40) |
                #endif
                (value  << 56);
            }
        }
    
        /*! Swaps the endianness of the passed in value and returns the results.
        *
        * For standard integer types (any of the intX_t/uintX_t types)
        * specializations exist to ensure the fastest performance. All other types
        * are treated as char* and reversed.
        */
        template<typename T> 
        T swap_endian(T value) {
            if (std::numeric_limits<T>::is_integer) {
                return detail::swap_endian_<T>(value, detail::integer_traits<T>::category());
            }
    
            unsigned char* tmp = reinterpret_cast<unsigned char*>(&value);
            std::reverse(tmp, tmp + sizeof(T));
            return value;
        }
    
        /*! Converts a value from host-byte order to little endian.
        *
        * Only works with integer types.
        *
        * \param value The value to convert to little endian
        * \return The value converted to endian order.
        */
        template<typename T>
        T host_to_little(T value) {
            static_assert(std::numeric_limits<T>::is_integer);
            return detail::is_big_endian() ? swap_endian(value) : value;
        }
        
        /*! Converts a value from host-byte order to big endian.
        *
        * Only works with integer types.
        *
        * \param value The value to convert to big endian
        * \return The value converted to endian order.
        */
        template<typename T>
        T host_to_big(T value) {
            static_assert(std::numeric_limits<T>::is_integer);
            return detail::is_big_endian() ? value : swap_endian(value);
        }
        
        /*! Converts a value from big endian to host-byte order.
        *
        * Only works with integer types.
        *
        * \param value The value to convert to host-byte order.
        * \return The value converted to host-byte order.
        */
        template<typename T>
        T big_to_host(T value) {
            static_assert(std::numeric_limits<T>::is_integer);
            return detail::is_big_endian() ? value : swap_endian(value);
        }
        
        /*! Converts a value from little endian to host-byte order.
        *
        * Only works with integer types.
        *
        * \param value The value to convert to host-byte order.
        * \return The value converted to host-byte order.
        */
        template<typename T>
        T little_to_host(T value) {
            static_assert(std::numeric_limits<T>::is_integer);
            return detail::is_big_endian() ? swap_endian(value) : value;
        }
            
    }  // namespace anh
    
    
    using namespace std;
    
    int main() {   
        uint32_t test_int_hostbyte = 0x00000002;
        uint32_t test_int_netbyte = 0x02000000;
    
        uint32_t tmp_int = anh::swap_endian(test_int_hostbyte);
    
        if (tmp_int == test_int_netbyte) {
            cout << "Hurray, swapping works!\n";
        } else {
            cout << "Sorry, try again!\n";
        }
    
        return 0;
    }

  • STLSTL

    devcodex: I'm very glad to hear that.

    > I was just working on a bit of code necessary for converting endianness when dealing with integer types in network code.

    Are Winsock's htonl()/etc. functions insufficient? (They probably don't benefit from inlining.)

    Suggestions:

    1. VC supports the ULL suffix just fine.

    2. Your code special-cases [u]int32_t, but there are two 32-bit types on our LLP64 platform: [unsigned] int and [unsigned] long. Whichever one [u]int32_t happens to be, your code won't detect the other one.

    3. You can use <type_traits> to eliminate your own integer_traits machinery. I suggest std::integral_constant<size_t, sizeof(T)> after you've verified std::is_integral<T>::value. That'll solve issue #2 for free.

    4. Also, mixing signed integers and bitwise manipulation is on my list of Scary Things (in particular, right-shifting negative numbers is implementation-defined). Fortunately, on two's complement machines, casting between signed and unsigned is bit-preserving.

  • Hugh.

    I finished watching this episode from start to end just now.

    It's very hard to watch it on mobile device.

    Next time I will download those and then watch.

    Charles! Thanks alot.

    STL! Thank you very much.

  • devcodexdevcodex SWGANH.com

    @STL

    Thank you for the excellent feedback. In this particular case the Winsock htonl and similar functions to my knowledge don't work directly on 64-bit types, which is a need for several of the proprietary data packet formats that the project I'm currently working on deals with.

    I am humbled again by just how much there is already provided with the STL and how much I still have to learn Smiley Thanks again!

  • devcodexdevcodex SWGANH.com

    I watched through this episode again and felt like I came away with much more this time around. After taking another stab at this I think I have an improved solution that addresses each of the suggestion points you provided. I wasn't certain how to handle the conversion of signed to unsigned while in a template scenario like this, but with a little digging I found the STL has something for that too. Thanks again!

    #include <cstdint>
    #include <iostream>
    #include <type_traits>
    
    namespace anh {
    
        namespace detail {
    
            template<typename T>
            T swap_endian_(T value, std::integral_constant<size_t, 1>) {
                return value;
            }
    
            template<typename T>
            T swap_endian_(T value, std::integral_constant<size_t, 2>) {
                std::make_unsigned<T>::type& tmp = static_cast<std::make_unsigned<T>::type&>(value);
                tmp = (tmp >> 8) | (tmp << 8);
    
                return value;
            }
            
            template<typename T>
            T swap_endian_(T value, std::integral_constant<size_t, 4>) {
                std::make_unsigned<T>::type& tmp = static_cast<std::make_unsigned<T>::type&>(value);
                tmp = (tmp >> 24) |
                       ((tmp & 0x00FF0000) >> 8) | ((tmp & 0x0000FF00) << 8) |
                       (tmp << 24);
    
                return value;
            }
            
            template<typename T>
            T swap_endian_(T value, std::integral_constant<size_t, 8>) {
                std::make_unsigned<T>::type& tmp = static_cast<std::make_unsigned<T>::type&>(value);
                tmp = (tmp >> 56) |
                    ((tmp & 0x00FF000000000000ULL) >> 40) |
                    ((tmp & 0x0000FF0000000000ULL) >> 24) |
                    ((tmp & 0x000000FF00000000ULL) >> 8)  |
                    ((tmp & 0x00000000FF000000ULL) << 8)  |
                    ((tmp & 0x0000000000FF0000ULL) << 24) |
                    ((tmp & 0x000000000000FF00ULL) << 40) |
                    (tmp  << 56);
    
                return value;
            }
        }
    
        /*! Swaps the endianness of integral values and returns the results.
        *
        * \param value An integral value for which to swap the endianness.
        * \return A copy of the input parameter with its endianness swapped.
        */
        template<typename T>
        T swap_endian(T value) {
            static_assert(std::is_integral<int>::value, "swap_endian<T> requires T to be an integral type.");
            return detail::swap_endian_<T>(value, std::integral_constant<size_t, sizeof(T)>());
        }
    
    }  // namespace anh
    
    using namespace std;
    
    int main() {
        uint32_t test_uint_hostbyte = 0x00000002;
        uint32_t test_uint_netbyte = 0x02000000;
    
        uint32_t tmp_uint = anh::swap_endian(test_uint_hostbyte);
    
        if (tmp_uint == test_uint_netbyte) {
            cout << "Can swap 32-bit unsigned types\n";
        } else {
            cout << "Swapping 32-bit unsigned types failed\n";
        }
    
        int32_t test_int_hostbyte = 0xfffffff5;  // -11 on two's complement machines
        int32_t test_int_netbyte = 0xf5ffffff;
    
        if (tmp_uint == test_uint_netbyte) {
            cout << "Can swap 32-bit signed types\n";
        } else {
            cout << "Swapping 32-bit signed types failed\n";
        }
    
        return 0;
    }

     

  • Any news on the next series? Did you record your next video?

  • SuperlexxSuperlexx

    Hello Stephen,
    I'm watching the highres WMA video (1,5GB) and the Windows part is noisy (i.e. around 10:00). I see fast horizontal shifts like it was recorded through a bad analog cable. I suppose that's why the file is so big this time.

  • STLSTL

    Deraynger: I filmed Advanced Part 1 today, covering shared_ptr's implementation (mostly focusing on type erasure).

    Superlexx: Hopefully that was due to the temporary setup we had during the studio remodeling. If you keep seeing it in future parts, please mention so in the comments.

  • puzzleslogicpuzzleslogic

    Just few days ago I was looking for nurikabe solver to solve about 4000 nurikabe puzzles for my new nurikabe related web page http://www.puzzleslogic.com
    However I didn't found your solver but other one available at http://sourceforge.net/projects/nurikabedotnet/
    It did the job on all 4k puzzles except on about 20 where it didn't found solutions.
    But what I am searching now is some better nurikabe generator. Which is quite hard especialy with rule that there has to be only one possible solution. Is your solver finding all solutions (if there are more then one) or just first it finds?

  • @devcodex:That's a whole lot of specific code for a very simple and general idea.  I'm not really sure that a destructive endian swap is the way to go; however, try this code out:

    typedef unsigned int SIZE;
    typedef unsigned char BYTE;
    
    template < typename T >
    inline T & swap_endian ( T & t ) {
        static_assert( std::is_integral< T >::value, "swap_endian<T> requires T to be an integral type." );
        SIZE const number_of_bytes = sizeof( t );
        SIZE const middle = number_of_bytes / 2; // integer division
        BYTE * bytes = reinterpret_cast< BYTE * >( &t );
        for ( SIZE i = 0, j = number_of_bytes - 1; i < middle; ++i, --j ) {
            bytes[ i ] ^= bytes[ j ];
            bytes[ j ] ^= bytes[ i ];
            bytes[ i ] ^= bytes[ j ];
        }
        return t;
    }
    Two of these swap_endian's in a row gets you back where you started from ... without having to use temporaries ... ; however, this code can easily be modified to be non-destructive and use the more traditional buffer.  Does this code meet your needs?

    The code above can be used in the following manner:

    #include <iostream>
    #include <iomanip>
    #include <type_traits>
    
    typedef unsigned int SIZE;
    typedef unsigned char BYTE;
    
    template < typename T >
    void print_byte_info ( T const & t ) {
        std::ostream & os = std::cout;
        SIZE const number_of_bytes = sizeof( t );
        SIZE const number_of_bits = 8;
        SIZE const width = 4;
        BYTE const * bytes = reinterpret_cast< BYTE const * >( &t );
        for ( SIZE i = 0, j; i < number_of_bytes; ++i ) {
            os << "byte ( " << std::setw( width ) << ( i + 1 ) << " ): ( address: "
                << std::setw( width ) << static_cast< void const * >( &bytes[ i ] )
                << ", value: " << std::setw( width ) << 
                static_cast< unsigned int >( bytes[ i ] ) << ", binary value: ";
            j = number_of_bits;
            do {
                --j;
                os << ( bytes[ i ] & ( 1 << j ) ? '1' : '0' );
            } while ( j > 0 );
            os << " )\n";
        }
        os << std::endl;
    }
    
    template < typename T >
    inline T & swap_endian ( T & t ) {
        static_assert( std::is_integral< T >::value, "swap_endian<T> requires T to be an integral type." );
        SIZE const number_of_bytes = sizeof( t );
        SIZE const middle = number_of_bytes / 2; // integer division
        BYTE * bytes = reinterpret_cast< BYTE * >( &t );
        for ( SIZE i = 0, j = number_of_bytes - 1; i < middle; ++i, --j ) {
            bytes[ i ] ^= bytes[ j ];
            bytes[ j ] ^= bytes[ i ];
            bytes[ i ] ^= bytes[ j ];
        }
        return t;
    }
    
    int main () {
        unsigned long long x = 0x0102030405060708ULL;
        std::cout << "x ( unsigned long long ): " << x << std::endl;
        std::cout << "x ( unsigned long long | hex ): " << std::hex << x << std::endl;
        std::cout << std::dec;
        print_byte_info( x );
        swap_endian( x );
        std::cout << "swapped x ( unsigned long long ): " << x << std::endl;
        std::cout << "swapped x ( unsigned long long | hex ): " << std::hex << x << std::endl;
        std::cout << std::dec;
        print_byte_info( x );
    
        signed long long y = 0xF7F8F9FAFBFCFDFELL;
        std::cout << "y ( signed long long ): " << y << std::endl;
        std::cout << "y ( signed long long | hex ): " << std::hex << y << std::endl;
        std::cout << std::dec;
        print_byte_info( y );
        swap_endian( y );
        std::cout << "swapped y ( signed long long ): " << y << std::endl;
        std::cout << "swapped y ( signed long long | hex ): " << std::hex << y << std::endl;
        std::cout << std::dec;
        print_byte_info( y );
        
        return 0;
    }
    
    This code will compile using Warning Level 4 in VS2010 or in g++ 4.5.2 using the following command ( assuming the code is in main.cpp ):
    g++ -o main.exe main.cpp -std=c++0x -O3 -Wall -Wextra -Werror
    Here's an example of the output from this code:
    x ( unsigned long long ): 72623859790382856
    x ( unsigned long long | hex ): 102030405060708
    byte (    1 ): ( address: 0044F89C, value:    8, binary value: 00001000 )
    byte (    2 ): ( address: 0044F89D, value:    7, binary value: 00000111 )
    byte (    3 ): ( address: 0044F89E, value:    6, binary value: 00000110 )
    byte (    4 ): ( address: 0044F89F, value:    5, binary value: 00000101 )
    byte (    5 ): ( address: 0044F8A0, value:    4, binary value: 00000100 )
    byte (    6 ): ( address: 0044F8A1, value:    3, binary value: 00000011 )
    byte (    7 ): ( address: 0044F8A2, value:    2, binary value: 00000010 )
    byte (    8 ): ( address: 0044F8A3, value:    1, binary value: 00000001 )
    
    swapped x ( unsigned long long ): 578437695752307201
    swapped x ( unsigned long long | hex ): 807060504030201
    byte (    1 ): ( address: 0044F89C, value:    1, binary value: 00000001 )
    byte (    2 ): ( address: 0044F89D, value:    2, binary value: 00000010 )
    byte (    3 ): ( address: 0044F89E, value:    3, binary value: 00000011 )
    byte (    4 ): ( address: 0044F89F, value:    4, binary value: 00000100 )
    byte (    5 ): ( address: 0044F8A0, value:    5, binary value: 00000101 )
    byte (    6 ): ( address: 0044F8A1, value:    6, binary value: 00000110 )
    byte (    7 ): ( address: 0044F8A2, value:    7, binary value: 00000111 )
    byte (    8 ): ( address: 0044F8A3, value:    8, binary value: 00001000 )
    
    y ( signed long long ): -578437695752307202
    y ( signed long long | hex ): f7f8f9fafbfcfdfe
    byte (    1 ): ( address: 0044F88C, value:  254, binary value: 11111110 )
    byte (    2 ): ( address: 0044F88D, value:  253, binary value: 11111101 )
    byte (    3 ): ( address: 0044F88E, value:  252, binary value: 11111100 )
    byte (    4 ): ( address: 0044F88F, value:  251, binary value: 11111011 )
    byte (    5 ): ( address: 0044F890, value:  250, binary value: 11111010 )
    byte (    6 ): ( address: 0044F891, value:  249, binary value: 11111001 )
    byte (    7 ): ( address: 0044F892, value:  248, binary value: 11111000 )
    byte (    8 ): ( address: 0044F893, value:  247, binary value: 11110111 )
    
    swapped y ( signed long long ): -72623859790382857
    swapped y ( signed long long | hex ): fefdfcfbfaf9f8f7
    byte (    1 ): ( address: 0044F88C, value:  247, binary value: 11110111 )
    byte (    2 ): ( address: 0044F88D, value:  248, binary value: 11111000 )
    byte (    3 ): ( address: 0044F88E, value:  249, binary value: 11111001 )
    byte (    4 ): ( address: 0044F88F, value:  250, binary value: 11111010 )
    byte (    5 ): ( address: 0044F890, value:  251, binary value: 11111011 )
    byte (    6 ): ( address: 0044F891, value:  252, binary value: 11111100 )
    byte (    7 ): ( address: 0044F892, value:  253, binary value: 11111101 )
    byte (    8 ): ( address: 0044F893, value:  254, binary value: 11111110 )

    Hope This Helps,
    Joshua Burkholder

  • STLSTL

    [puzzleslogic]
    > However I didn't found your solver

    I don't understand - it's available at http://cid-e66e02dc83efb165.office.live.com/browse.aspx/nurikabe , which I've linked repeatedly.

    > [Another solver] did the job on all 4k puzzles except on about 20 where it didn't found solutions.

    How well does my solver do? Are there any that it can't solve, or that are harder than nikoli_9? I'm interested in realistic but monstrously difficult puzzles.

    > But what I am searching now is some better nurikabe generator.

    Generating is the flip side of solving - I've thought about generating, but haven't explored it. If I were trying to write a generator, I'd start by generating a valid solution of white and black cells (which should be pretty easy), then randomly select cells to number and see if the solver finds a single valid solution.

    > Is your solver finding all solutions (if there are more then one) or just first it finds?

    It assumes that there's exactly one, so it doesn't attempt to find more. However, it could be changed to find all solutions, and I believe that would be quite easy - it's almost entirely powered by finding contradictions which are paths that lead to no valid solution. If it guesses a cell and that leads to a solution, it'll declare victory early, but it could be told to keep going. Also, it would have to be changed to be fully recursive instead of one-guess recursive.

    By the way, Advanced STL Part 1 is out: http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Stephan-T-Lavavej-Advanced-STL-1-of-n .

    I don't have time to monitor every single video part for new comments, so you should add comments to the latest part (or if you really want to get my attention, E-mail me at stl@microsoft.com).

  • AbeAbe

    Is it at all possible to get all STL (basic and advanced) videos via torrent, i've been having heaps of issues downloading these to watch offline (slow download rate, download dying mid way etc).

  • Hi.

    I've tried to watch that chapter for several days but all the links seem to be broken.

    Is it just a temporary glitch?

  • Can watch all chapters except Part 10 of 10 (also not downloadable)

  • The video and files are not working!

  • MattMatt

    Can't get part 10 to work

  • Oh! It's back!

    Thanks a ton Smiley

  • JavierJavier

    Hi, thank you for uploading again the video. In my case I'm having problems with High Quality WMV video. I have downloaded it twice and the video as a bad encoding. First 10 minutes fail (I'm using VLC). With Medium Quality WMV it works perfect so I suppose that the problem is with just that High Quality video.

    Can you encode and upload that video again please?

  • The power! the power! muHahaHaHahaha

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.