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), 4 of n

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.

In part 4, Stephan explains his solution to writing a solver for the Nurikabe puzzle using the STL (of course...). You will be introduced to some new concepts as well as use some of the things you have already learned. 

Get the output and source code (v1) for Stephan's Nurikabe solver.

Get the optimized output and source code(v1.2) for Stephan's Nurikabe solver. 1.2 adds new test cases, improves the output, and significantly speeds up certain test cases. 1.2 is a better foundation for the performance exploration that Stephan suggested for the homework assignment. You're doing your homework, right? Smiley

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

  • Another awesome video from Stephen Big Smile

    I'm still quite new to the STL, though I do like C++.

    I was wondering if theres a C++ class that handles HTTPRequest without using .NET.

    I was thinking about a writing a RSS Reader that checks a RSS feed every few hours/days/minutes whatever,

    and if it finds what I'm looking for, it notifies me using a notifer icon.

     

     

     

  • So, I opened the source file, saw a nearly 400 line solve function with minimal "island" comments and pretty much lost all interest in what the program does. Just my two cents worth... Does it really have to be this unstructured to perform? Can it be any less structured and still be instructive (/sarcasm)? Was it necessary to cram it all into one .cpp file, given that it was part of a zip archive?

     

    Just my 2 cents...

     

     

  • CharlesCharles Welcome Change

    The commentary is in the video. Play the video, listen, watch, open the sources (v1) and follow along Smiley Yes, the time algorithm isn't as efficient as you'd like, but knowledge requires real time. There is no getting around it. Well, there's virtual time, but what's the delivery vehicle, exactly? Better would be synching viewers' VS editors with Stephan's presentation.

     

    Hmm.

     

    C

  • Well, he does state that the solve function, the meat of this application, will be covered in the next video, so I suppose we can take a wait and see approach. However, basic OO/structured programming tenets do not condone the use of 400 line "super-do-everything" functions, of which solve() is one. Bottom line is that we'll have to give Stephan the benefit of the doubt and let him elaborate in the next episode...

     

     

  • STLSTL

    [Tominator2005]
    > I was wondering if theres a C++ class that handles HTTPRequest without using .NET.

    If you want to do anything with networking, I suggest looking at Boost.Asio, documented at http://www.boost.org/doc/libs/1_44_0/doc/html/boost_asio.html . (Asio stands for Asynchronous I/O.) In particular, their examples at http://www.boost.org/doc/libs/1_44_0/doc/html/boost_asio/examples.html demonstrate HTTP. I have not yet used Asio myself, but I was extremely impressed with it at BoostCon 2010.

    [Corrector2]
    > So, I opened the source file, saw a nearly 400 line solve function with
    > minimal "island" comments and pretty much lost all interest in what the program does.

    My apologies. Please give it a second chance - it is not nearly as complicated as its length suggests.

    I'm not sure what you mean by "island comments". I assume you're referring to big comment blocks. I carefully commented most of the file, especially the data structures, with short comments. As I mentioned in either Part 4 or 5, typically I let my code speak for itself, and I reserve comments for inherently complicated code (for example, I usually don't include comments like "Validate width and height." or "Parse the string."). In this case, though, I included almost as many comments as possible without overcommenting ("++i; // Increment i" being an obvious example of a comment that should not exist). The short comments do tend to thin out in the complicated functions like unreachable(), which assume an increasing level of familiarity with the STL, the problem domain, and the algorithm. However, I did include two gigantic comment blocks, for the complicated analysis steps. There's a big one explaining confinement that begins with "A region would be "confined" if it could not be completed.", with a diagram (!) for the most subtle part, and another big one explaining unreachability that begins with "The cell at (x_root, y_root) is unreachable if". Instead of explaining individual implementation steps, these big comment blocks explain concepts that are absolutely critical to understanding the following code.

    Do you really want a big comment block for the step "Look for complete islands."? The single-line comment explains what's going on, and the code explains how it's finding complete islands (it looks for numbered regions with sizes equal to their numbers - and the "class Region" comments explain how that's tracked). This is a perfect example of code that should NOT have a gigantic comment.

    I did consider breaking solve() up into smaller member functions, which I mentioned in either Part 4 or 5 (they were filmed back-to-back; I suspect it was Part 5). I decided against it, because solve() simply performs one step after another, and the steps are essentially independent. Introducing smaller member functions would have increased the total amount of code, and I didn't feel that it would improve clarity. Perhaps this judgment was incorrect.

    > Does it really have to be this unstructured to perform?

    No - solve()'s length is unrelated to its performance.

    > Was it necessary to cram it all into one .cpp file, given that it was part of a zip archive?

    It's a single class, with a small nested class, and a main() function. Unlike solve(), which I thought about breaking up, I felt no urge to break this up into multiple headers and source files. It's a large and realistic example, but not production code. If it were production code, Grid's class definition would certainly appear in a header, with member function implementations in source files, and it might even be pimpled to reduce compile-time dependencies (observe that its public interface is extremely small, while its private interface is large and refers to many things - in this case all of those things are from the Standard Library, but when they're from other code that's actively changing, that's a motivation to pimpl).

    I'll see about breaking up solve() in version 1.3. Although I don't think it's the end of the world, your points are valid, and I'm probably desensitized to long functions.

    > However, basic OO/structured programming tenets do not condone the
    > use of 400 line "super-do-everything" functions, of which solve() is one.

    The most important lessons from structured programming are that complex behavior should be encapsulated in simple functions, and that for/while loops are the antidote to poisonous gotos. solve() encapsulates very complex behavior - it performs a step of grid analysis - in a very simple interface. (It has to be told whether to be verbose and whether guessing is permitted - both of which have defaults - and it returns whether more analysis is required, or if not, why not.) As far as the outside world is concerned, solve() is perfectly structured. Internally, you may argue that solve() could be further structured, by independently encapsulating its steps of analysis. That is reasonable, although my first reaction was that it would simply move blocks of code around, not make those blocks easier to understand, or avoid duplication. (unreachable(), confined(), and other helpers are called more than once, which is why they're separate member functions.) Hopefully you can agree that my original point of view was at least somewhat reasonable.

    As for object-oriented programming, its most important lesson is that state and behavior should be encapsulated in classes. Grid perfectly satisifes that and there are absolutely no problems there. Region is not especially encapsulated, but as I explained in either Part 4 or 5, that's because it's internal to Grid, and Grid is ultimately responsible for maintaining Region's invariants.

    (Some people think that "object-oriented programming" means that everything should live in inheritance hierarchies. I disagree extremely strongly. Fortunately, that doesn't appear to be an issue here.)

  • Since most of the issues revolved around solve, let me be more clear in my argument:

     

    - A complex function, even if it is mostly one containing linear flow can be broken down into several simple functions in order to become more hierarchical and less linear. Let me give a simple example to elucidate my point:

     

    Instead of a long function such as:

     

    void Car::Build()

    {
       // Build the frame

       ... build the frame code

     

       // Add doors

       ... add doors code

     

       // Insert engine

       ... insert engine code

     

       // Insert transmission

       ... insert transmission code

     

       // Insert upholstery

       ... insert upholstery code

     

       // Paint the car

       ... paint the car code

     

       // Whatever else needs to be done

       ... whatever else needs to be done

    }

     

    It is much easier to see (the comments are not part of the code, I am just adding them to show what the functions being called do for the purpose of explaining my point):

     

    void Car::Build()

    {
       BuildFrame(...); // Calls AddDoors()

       AddInternalParts(...); // Calls AddEngine(), AddTransmission(), AddUphostery()?, etc...

       AddBodyParts(...); // Calls AddDoors()

       Paint(...);

    }

     

    Now the Build function is easy to eye over and comprehend. If the programmer wishes to look into detail and see how each step is actually implemented, he can go into each of the functions being called and examine them (or look at call graphs, etc...).

     

    By creating a deeper (rather than shallower) Build() function, it is much easier to comprehend in a top down (rather than bottom up) fashion. This is how most people solve and analyze problems - from an abstract problem statement to analyzing (i.e., "sweating") the details.

     

    If you:

     

    1. Break up your solve function into sub-tasks (functions)
    2. Give them meaningful names
    3. Only call these sub-tasks from within solve

    Then, it would be much easier to see what solve does as a whole and there would be no performance penalty in doing this, to boot, because these sub-tasks would probably still be gross tasks. If any of the sub-tasks are still complex, you can further decompose them into more sub-tasks.

     

    A developer reading solve would drill down to the level of interest to him, while seeing the big picture all along the way. Compare this to having to gloss over 400 lines of code, even if only looking for comments, in order to try to figure out what solve does.

     

    My two cents...

  • Download:[Pending]

    [Tominator2005]
    > I was wondering if theres a C++ class that handles HTTPRequest without using .NET.

    If you want to do anything with networking, I suggest looking at Boost.Asio, documented at http://www.boost.org/doc/libs/1_44_0/doc/html/boost_asio.html . (Asio stands for Asynchronous I/O.) In particular, their examples at http://www.boost.org/doc/libs/1_44_0/doc/html/boost_asio/examples.html demonstrate HTTP. I have not yet used Asio myself, but I was extremely impressed with it at BoostCon 2010.

     

    Thanks I'll take a look at that.

     

    Charles,

    Any idea when's the next video will be uploaded?

  • CharlesCharles Welcome Change

    Yes. Next week.

    C

  • One other niggle, Stephen.

    When is it best to use helper methods?

    I've heard a lot of people say they're bad.

    Tom

  • STLSTL

    Check out version 1.3 at http://cid-e66e02dc83efb165.office.live.com/browse.aspx/nurikabe

    // 1.3 (9/8/2010) - Reorganized Grid::solve() into smaller member functions.

    Thank you, Corrector2, for helping me to improve my code.

    [Tominator2005]
    > When is it best to use helper methods?
    > I've heard a lot of people say they're bad.

    Nonsense. (I've never even heard that before.) Helper functions (both free and member) are wonderful. They are absolutely necessary when called more than once, and as Corrector2 patiently explained, they are useful even when called exactly once.

    If you look at my Grid, its public member functions are supported by its private member functions. This is how basically every well-designed class works. Whether you refer to the private member functions as "helpers" doesn't change the fact that you need them.

    When I wrote my solver, I planned from the beginning to have Regions, and I knew that I'd need add_region(), fuse_region(), and so forth. As I wrote more code, I noticed that I was repeatedly looking at a cell, figuring out which of its neighbors were within the bounds of the grid, and doing something for each neighbor. I lifted that out into for_valid_neighbors(), and as I noticed common operations, I created insert_valid_neighbors() and insert_valid_unknown_neighbors() to remove code duplication.

  • Looking much better in 1.3! I'd still do more refactoring on unreachable(), but it's a whole world better than before...

  • C64C64

    I noted in case of errors exceptions are thrown in your code (e.g. throw runtime_error, throw logic_error...) with a proper error message.

    The error message is an English string stored in a char-based string. In case of production-quality code there would be a need to localize error messages. But std::exception class seems to support only char* strings. How could this localization problem be solved? Should a new class be derived from std::exception, adding Unicode string supports or some form of string table? Should every library define its own custom localizable std::exception class?

    Thanks.

     

  • STLSTL

    [C64]
    > In case of production-quality code there would be a need to localize error messages.

    Yep!

    > But std::exception class seems to support only char* strings.

    Correct. std::exception::what() is intended to be seen by developers and not by end users. You could put UTF-8 in there, but you only get one what().

    > How could this localization problem be solved?

    Derive from std::exception (at a minimum; deriving from the <stdexcept> classes would be better), and tag your exceptions with string resource identifiers. Then you can load the appropriate string at runtime based on the user's language.

    Also, see Boost.Exception: http://www.boost.org/doc/libs/1_44_0/libs/exception/doc/boost-exception.html The Standard Library's exceptions are just a starting point.

  • Thanks STL,

     

    Ok, my bad. It wasn't helper functions but Helper Classes, as in classes with static functions,

    it just came up on a Google Search for Helper functions, and I saw the word Helper and Evil,

    and totally misread and misconceived that the idea of helper functions were evil.

     

    Looking good btw. I might try Boost ASIO, but its not as simple as creating a instance

    of HTTPRequest to get html from a web page or xml from a RSS feed.

  • I do enjoy watching these STL videos and request a lot more please  Angel

     

    But why does it take so long to release them ?

     

    Also i must ask: how blood hard is it to make videos without black stripes ?!

    To me this is a very obvious sloppy mistake (there are other mistakes too but you get the point). The noob editing this video needs a go-back-to-school slap.

    Seems to me that the stl videos get low priority, how come ? You (Charles) did say more C++ videos are coming and that they were important to you and the community so was the 'important' part yet another microsoft PR lie ?

    What is your time table with the other C++ videos, i'm craving C++ videos and my patience is running low after a few weeks..month of waiting.

     

    I'm trying to express my worry and concern here.

     

    Charles, give that sloppy noob video editor a friendly slap from me. 

     

  • wow, Part 5 you managed to mess-up even more (out of sync, black stripes, etc), do you get paid to do it wrong ?!

  • CharlesCharles Welcome Change

    What's wrong with these videos, exactly?  Parts 4 and 5 were encoded by somebody who is far from a noob... That said, I will pass along your feedback to him. Would be nice if you could remove your harshness and replace with useful feedback. Please do provide it.

     

    These release as soon as we can make them. Stephan has a very busy day job, so we get him into the studio when it's convenient for him. There is a lot of C++content on C9 (and there has been for a long time....). New content in on the horizon including more lectures.

     

    Re: Part 5: this is being corrected. My apologies.
    C

  • STLSTL

    [Tominator2005]
    > It wasn't helper functions but Helper Classes, as in classes with static functions,

    Writing a class that contains only static member functions is usually silly. (Non-member functions in namespaces would be a better idea.) However, there's at least one case where such classes are definitely useful. Function templates cannot be partially specialized; they can be overloaded, which has the same effect 98% of the time. The rest of the time, when you really do need partial specialization, you can partially specialize a class with static member functions, and that'll get the job done.

    [Mr Crash]
    > I do enjoy watching these STL videos and request a lot more please
    > But why does it take so long to release them ?

    Glad you like them. Editing is a black box to me, but I know what determines my frequency of filming. As you're aware, I work with Dinkumware to maintain VC's implementation of the C++ Standard Library. Because this implementation is inherently very complex, and the C++0x Working Paper has been a fast-moving target for the last several years, this is a lot of work! I try to write blog posts and film videos whenever I can, but this competes for time with my development work (i.e. making VC11's STL even more awesome than VC10's), so I have to balance them.

    In terms of time, Parts 4 and 5 were even more expensive than 1, 2, and 3, because I wrote a large example program. I almost never get the chance to do that. Part 6 (which will cover algorithms and customizing them with functors, unless I think of a better idea) will go back to my (organized) stream of consciousness, which requires little advance preparation, but I'm on vacation this week, so I won't be able to film it immediately.

  • @STL:

    > But why does it take so long to release them ?

    I was unclear here, sorry. I meant the time between filming and release video to public

    Does the video editing/encoding take that long ? Do you use some kind of queue system?

  • @Charles:ok, i guess i could help with translating my feedback  Wink
    Do you have an e-mail address i can send the feedback to (i plan to include some pictures to better show what i mean)

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    Mr_Crash!  Have you ever used Windows Media Encoder?  Do try, and in the meantime go visit your family in another state Tongue Out

    Vector of vectors is appropriate for a text editor, less appropriate for relational data where you want to do things to rows, and totally inappropriate for a matrix, unless the matrix is so huge that you cannot keep it all in RAM --- but then, please explain the options for low RAM environments because STL is not an option for various reasons.  And, even if you insist, the interface class should be called Matrix (or, in fact, Grid proper) and use a vector of vectors as an implementation detail.

    And I do not think that explaining the viewers that the numbers count the fields in contiguous white areas would be such a waste of time.  I am watching your videos in circumstances where I cannot type.

  • STLSTL

    [giecrilj71pl]
    > Vector of vectors is appropriate for a text editor, less appropriate for relational data where you want to do things to rows, and totally inappropriate for a matrix

    It works fine for Nurikabe. (I agree with you that solutions should be chosen so that they're appropriate for the problem domain - and the problem domain in this example is Nurikabe.)

    One of my todos is to investigate storing the cells in a 1D vector. I actually did that during my development (it makes parsing somewhat easier, as cells can be stored in input order), but I never thought about using 1D coordinates everywhere as well. I suspect that my reliance on pair<int, int> may affect performance.

    > but then, please explain the options for low RAM environments because STL is not an option for various reasons.

    Actually, the STL is extremely good at conserving space.

    > And, even if you insist, the interface class should be called Matrix (or, in fact, Grid proper) and use a vector of vectors as an implementation detail.

    My Nurikabe Grid class uses a vector of vectors as an implementation detail. It is strongly encapsulated and nobody outside of the Grid is aware of its presence. I saw, and continue to see, no reason to further encapsulate the Grid's storage. (On the other hand, Region is a nontrivial data structure, which benefits greatly from the partial encapsulation that I gave to it.)

    > And I do not think that explaining the viewers that the numbers
    > count the fields in contiguous white areas would be such a waste
    > of time.  I am watching your videos in circumstances where I cannot type.

    I'm sorry, I don't understand. Are you saying that I should have explained the meaning of the numbers in a Nurikabe grid? As I recall, I clearly stated in the video that Wikipedia's Nurikabe page was required reading. I also linked to it in the source code.

  • Scott CScott C

    Thanks for your great lectures, I appreciate how you got into the scaling factors of the STL containers.  The O factors have never been explained in plain english before!
    vector::reserve() can make populating a big list 100x faster! You should mention the performance improvement in future lectures. I use the following function, same as mentioned to check the time:
    #include <windows.h> double CurrentTime (){ LARGE_INTEGER freq; LARGE_INTEGER time; QueryPerformanceFrequency( &freq) ;   QueryPerformanceCounter(&time);   double ct = (double)time.QuadPart / (double)freq.QuadPart;   return ct;}
    I am a Java programmer, using shared_ptr and STL containers, as well at std::string, the programming style has become intuitively very similar!
    The nurikabe program is quite verbose for a puzzle that only needs to follow 8 simple rules. Can someone try to code this in F# and see how it compares?
     

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    , STL wrote


    > but then, please explain the options for low RAM environments because STL is not an option for various reasons.

    Actually, the STL is extremely good at conserving space.

    Your correctly observed in Installment 1 how the triple A-I-C saves us from having A*C implementations.  However, this only applies to source code, because the object code will contain (up to) A*C implementations (actually A*C*T).  Of course, most code sets do not use all pairs; however, depending on the domain, the object size can skyrocket.  This is not a big problem for algorithms like find, and any algorithms you would type inline off your head, but complex and long template algorithms do exist, e.g. sort.  That was a significant problem for Adobe when they created their image manipulation library.

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    , STL wrote

    [giecrilj71pl]
    > And, even if you insist, the interface class should be called Matrix (or, in fact, Grid proper) and use a vector of vectors as an implementation detail.

    My Nurikabe Grid class uses a vector of vectors as an implementation detail. It is strongly encapsulated and nobody outside of the Grid is aware of its presence. I saw, and continue to see, no reason to further encapsulate the Grid's storage. (On the other hand, Region is a nontrivial data structure, which benefits greatly from the partial encapsulation that I gave to it.)

    On the other hand, a Matrix is a fairly general data structure, and if you promoted your implementation to a separate component, you could use it elsewhere.  But then my criticism at your implementation choice would be much more valid, so it was actually clever to hide it Angel

  • STLSTL

    [Scott C]
    > Thanks for your great lectures, I appreciate how you got into the scaling factors of the STL containers.
    > The O factors have never been explained in plain english before!

     

    I'm glad to be of service.

     

    > vector::reserve() can make populating a big list 100x faster!
    > You should mention the performance improvement in future lectures.

     

    Actually, this is not true. Understanding why is enlightening.

     

    Imagine that you're using an STL implementation with a 2x growth factor for vector. Then you push_back() N = 2^20 + 1 = 1048577 elements. (This is not a rigorous mathematical proof because I am not a mathematician, but the logic is sound, and insensitive
    to my example N.) How many element copies during reallocation have been performed? (I have sneakily chosen N to maximize the number of element copies relative to the number of final elements; i.e. the worst-case ratio.) Well, look at the vector's capacity()
    as it underwent reallocation. It was 0, 1, 2, 4, 8, 16, 32, ..., 1048576 (the capacity before pushing back the last element), 2097152 (the final capacity). The number of element copies performed was 1 + 2 + 4 + 8 + ... + 1048576 = 2097151. So, with N elements,
    the worst-case number of element copies during reallocation is almost exactly 2N. (This is what "linear time" means, and we've just discovered the constant factor associated with it.)

     

    Because reserve() eliminates unnecessary element copies during reallocation, when you use it, you'll construct exactly N elements. So, with a 2x growth factor STL (like GCC's libstdc++), calling reserve() will improve your performance by at most 2x, ignoring
    other factors (like the cost of an allocation itself). Not 100x.

     

    With a 1.5x growth factor STL, like VC's, the numbers change but the principles stay the same. Suppose you push_back() N elements, where N is just over a capacity boundary. (Because of the 1.5x growth factor and integer arithmetic, these boundaries aren't
    convenient to exactly calculate, but 1049869 is the first boundary over a million, so you could use N = 1049870 as a concrete example.)

     

    The last reallocation copied N - 1 elements, and then pushed back 1 more. I'm going to call that approximately N copies (ignoring the "- 1" is okay). The reallocation before that copied N / 1.5 = (2/3) * N elements. The one before that copied (2/3)^2 * N
    elements, and so forth. The total number of copies is approximately (ignoring the integer arithmetic is also okay)

     

    N + (2/3) * N + (2/3)^2 * N + (2/3)^3 * N + ...

     

    http://en.wikipedia.org/wiki/Geometric_series#Sum explains that 1 + r + r^2 + r^3 + ... = 1 / (1 - r), so we've performed N * 1 / (1 - (2/3)) = N * 1 / (1/3) = 3N copies.

     

    So with VC's implementation, calling reserve() will improve your performance by at most 3x. Let's test this experimentally:

     

    C:\Temp>type meow.cpp
    #include <iostream>
    #include <ostream>
    #include <vector>
    #include <windows.h>
    using namespace std;
    
    long long counter() {
        LARGE_INTEGER li;
        QueryPerformanceCounter(&li);
        return li.QuadPart;
    }
    
    long long frequency() {
        LARGE_INTEGER li;
        QueryPerformanceFrequency(&li);
        return li.QuadPart;
    }
    
    void print_time(const long long start, const long long finish, const char * const s) {
        cout << s << ": " << (finish - start) * 1000.0 / frequency() << " ms" << endl;
    }
    
    int main() {
        const int N = 60540697 + 1;
    
        for (int k = 0; k < 5; ++k) {
            {
                const long long start = counter();
    
                vector<int> v;
    
                for (int i = 0; i < N; ++i) {
                    v.push_back(1729);
                }
    
                const long long finish = counter();
    
                print_time(start, finish, "Normal");
            }
    
            {
                const long long start = counter();
    
                vector<int> v;
    
                v.reserve(N);
    
                for (int i = 0; i < N; ++i) {
                    v.push_back(1729);
                }
    
                const long long finish = counter();
    
                print_time(start, finish, "Reserve");
            }
        }
    }
    
    C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL meow.cpp
    meow.cpp
    Generating code
    Finished generating code
    
    C:\Temp>meow
    Normal: 1012.54 ms
    Reserve: 311.053 ms
    Normal: 908.927 ms
    Reserve: 294.182 ms
    Normal: 909.3 ms
    Reserve: 316.129 ms
    Normal: 890.19 ms
    Reserve: 313.943 ms
    Normal: 889.658 ms
    Reserve: 314.778 ms

     

    After the numbers stop bouncing around, the observed speedup is roughly 889.658/314.778 = 2.83x, which agrees with the theoretical calculation above.

     

    > The nurikabe program is quite verbose for a puzzle that only needs to follow 8 simple rules.

     

    Simple rules don't imply simple solvers.

     

    [giecrilj71pl]
    > That was a significant problem for Adobe when they created their image manipulation library.

     

    "Template code bloat" can be an issue for other libraries, but it isn't a major problem for the STL itself, which has few truly large algorithms, and doesn't actually have that many containers.

     

    I'll also point out that /OPT:REF,ICF discards unreferenced functions and folds binary-identical functions, so binary-identical template instantiations (like for A *, B *, C *) are harmless. Binary-different template instantiations are maximizing runtime
    perf at the (typically minor) cost of executable size. If you want to reduce the amount of generated code, you'll typically need something like type erasure, which has runtime costs.

     

    > On the other hand, a Matrix is a fairly general data structure, and if you promoted your implementation to a separate component, you could use it elsewhere.

     

    The Nurikabe grid isn't a mathematical matrix.

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    ,STL wrote

    > On the other hand, a Matrix is a fairly general data structure, and if you promoted your implementation to a separate component, you could use it elsewhere.

     

    The Nurikabe grid isn't a mathematical matrix.

    Why not?  It is rectangular and it contains numbers and symbols in the cells.

  • STLSTL

    Mathematical matrices undergo operations like addition, multiplication, and so forth. Nurikabe isn't linear algebra.

  • Scott CScott C

    I stand corrected, yes I understand and have retested that using vector.reserve() only increases performance by at best 3x, and actually become close to 1:1 at larger sizes.
    Also, a few authors have mentioned its best to keep objects in STL containers for safer memory management, rather than using STL to hold pointers to object in the heap.  Any suggestions how one can push objects into an STL container and use them efficiently?  Most of the STL documentation deals with data structures rather than class objects with behaviour.  I've found the following function calls the destructor 3 times for my class.
    MyFunction() {
    vector<GameEntity>.push_back(GameEntity())
    GameEntity gameEntity = vector.back();
    gameEntity .start();
    }
     

  • STLSTL

    > Also, a few authors have mentioned its best to keep objects in STL containers for safer memory management, rather than using STL to hold pointers to object in the heap.

    Correct.  vector<T>, vector<shared_ptr<T>>, and vector<unique_ptr<T>> are all good. vector<T *> where the pointers have been newed and must be deleted is bad. It's virtually guaranteed to leak memory; this was covered in Part 3.

    (vector<T *> where the pointers point to objects that will outlive the vector is fine, and can occasionally be useful.)

    > Any suggestions how one can push objects into an STL container and use them efficiently?

    Give your classes move constructors and move assignment operators. Then using them with the STL will generate maximally efficient code. (STL objects already have move constructors and move assignment operators, so things like vector<string> and vector<vector<int>> are already efficient.)

    I'll describe what happens with this if GameEntity is copyable but not movable (or if you're using VC9, which you shouldn't be - please, please upgrade to VC10):

    vector<GameEntity> v;

    v.push_back(GameEntity());

    This constructs a temporary GameEntity (that's the GameEntity() expression).  Then, a vector element GameEntity is copy-constructed from the temporary.  Then the temporary is destroyed (temporaries are destroyed "at the semicolon").

    If the vector undergoes reallocation, you'll see copy constructors being invoked for elements in the new memory block, and destructors being invoked for elements in the old memory block.

    GameEntity gameEntity = v.back();

    v.back() returns a reference to the last element in the vector.  Then you copy-construct the local variable gameEntity from this vector element.

    gameEntity.start();

    You call the start() member function on this local variable, not the vector element (or the original temporary, which is long gone).

    If you wanted to call start() on the vector element, you'd say either v.back().start(), or:

    GameEntity& r = v.back();

    r.start();

    This binds a reference r to the last element of the vector, then invokes start() through the reference.

  • Chtistopher Yeleightongiecrilj71pl turtlethere

    ,STL wrote

    vector<GameEntity> v;

    v.push_back(GameEntity());

    This constructs a temporary GameEntity (that's the GameEntity() expression).  Then, a vector element GameEntity is copy-constructed from the temporary.  Then the temporary is destroyed (temporaries are destroyed "at the semicolon").

    If GameEntity‘s copy constructor has trivial path, there is a workaround, although contrived and against the bitzkrieg convention that objects in C++ should not have an error state: push back a temporary constructed to follow that trivial path and do serious things to v.back() afterwards.

  • JohnJohn

    This is a great example of c++ and STL. However, the implementation itself is not able to fully explore puzzles where multiple solutions exist.  I want to emphasize that the scope of the solver was never to determine all possible solutions for a puzzle so I am not criticizing here, just observing.
    Consider this puzzle, which has 212 solutions: 
    "big5", 5, 5, "     \n" "    7\n" "     \n" "8    \n" "     \n"
    The solver yields "I'm Stumped!" at the second step.
    Now this puzzle, which has 2 solutions:
    "hasTwo", 5, 5, " 7   \n" "     \n" "    4\n" "     \n" " 2  2\n"
    The solver yields only the first solution, presumably because of the deterministic solving techniques.  
    I'm not a c++ programmer, but I did write a solver in F# that does find all solutions for a given puzzle using a technique called "recursively expanding neighborhoods" (source: http://www.liacs.nl/assets/Bachelorscripties/18-JohanGroenen.pdf , page 7).  I would be interested to see if anyone has explored this further in c++.

  • JohnJohn

    @John:
    Sorry for the poor formatting.  Not sure what happened there.

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.