dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 21 of 21

Thread: How exactly does recursion work with iterators?

  1. #16
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,115

    Re: How exactly does recursion work with iterators?

    Few small remarks.
    When you write the following:
    Code:
    for (Pair p : pairs) {
    You are creating a copy of each pair in the vector. In your case, those copies are not that expensive, but it's good to get into the habit of avoiding unnecessary copies.
    For example, the following uses const references to avoid any copies:
    Code:
    for (const Pair& p : pairs) {
    Similarly, your remove_pair() method can be changed as follows:
    Code:
    void remove_pair(const Pair& p)
    And your 'rem' lambda as well:
    Code:
    const auto rem = [&] (const Pair& p)
    Similar for the 'add' lambda.

    The any_pair() method returns the first pair in the storage as a copy. Is this what you want?

    The operator() in your Hash can also accept its parameter as const reference.
    Same for the l and r parameters for operator() of Equal.

    And same for reverse_pair(), its parameter can be a const reference.
    Marc Gregoire - NuonSoft (http://www.nuonsoft.com)
    My Blog
    Wallpaper Cycler 3.5.0.97

    Author of Professional C++, 4th Edition by Wiley/Wrox (includes C++17 features)
    ISBN: 978-1-119-42130-6
    [ http://www.facebook.com/professionalcpp ]

  2. #17
    Join Date
    Jun 2018
    Posts
    8

    Re: How exactly does recursion work with iterators?

    Great! Good job. Also, I didn't see your previous reply. You were right by the way in all cases.

    I think, what you are addressing here, is something I figured out to. The number of free astronauts can be calculated from the total number of bounded astronauts and the total number of astronauts. And in fact, trying to generate a list of all free astronauts ends up slowing the program down. That was a problem for me for the test case 10000 astronauts and 2 bounded pairs.

    When you talk about "urns", what's the story behind your naming convention? Is there a kind of general or abstract way of tackling this problem that I can read up about. I also what was your approach to error checking you program? Or were you able to write a functional program on your first try? Is there a way I can minimize the amount and complexity of errors in my programs? Your solution is impressive, to me. The way you use hashing and lambda expressions seems pretty advanced (though I am a novice programmer). Thanks for showing me a way to solve the problem. I couldn't get my way to work, and I still don't know why so I'll try to learn off of your approach.

    Thanks.
    Last edited by Kingdominth4; June 30th, 2018 at 05:33 PM.

  3. #18
    Join Date
    Feb 2017
    Posts
    344

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by Marc G View Post
    You are creating a copy of each pair in the vector. In your case, those copies are not that expensive, but it's good to get into the habit of avoiding unnecessary copies.
    To pass pair<int> by value throughout the code was an active choice (but maybe I should've motivated it).

    I use this rule of thumb: Pass primitives by value (including anything that doesn't cost more to pass than the largest primitive), pass everything else by const reference.

    To pass a pair<int> should cost the same as a double or a long long int so I decided to pass it by value. Larger data structures are passed by const reference or reference (for example the vector in the PairBase constructor and the unordered_multiset in the capture lists of the lambda expressions in PairBase.)

    Since the introduction of move semantics in C++ 11 my rule of thumb isn't as clear-cut as it used to be but I stick to it as a matter of routine and because it still is a reasonable guide. I know there are situation where it probably would make sense to break it but I'm not there quite yet.
    Last edited by wolle; July 1st, 2018 at 03:34 PM.

  4. #19
    Join Date
    Feb 2017
    Posts
    344

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by Kingdominth4 View Post
    When you talk about "urns", what's the story behind your naming convention?
    I used the term "urn" because this problem reminded me of the so called Urn problems I struggled with when studying basic probability theory a long time ago,

    https://en.wikipedia.org/wiki/Urn_problem

    The first version in my post #10 is a straightforward implementation of my solution strategy from #4. I always try to get something up and working as quickly as possible and then usually spend quite some time refining that solution so it becomes as simple and fast as possible. The result this time is in #15. It's nothing special but a fairly typical example of modern C++, at least that's what I hope. And I'm glad to hear it seems to be working correctly.

    Is there a kind of general or abstract way of tackling this problem that I can read up about.
    I always go about problem solving in the same manner. First I try to reduce the problem to a standard problem because then there's often a known best solution (algorithm) available. In this case there were two standard problems "finding all connected components of a graph" and "generating all 2-subsets of an n-set".

    Second I try to implement the solution using features at the highest abstraction level available in the language. In C++ it means selecting data structures and algorithms from the standard library but also using things like lambda expressions, foreach loops and smart pointers.

    When it comes to large scale organization of programs I apply object orientation and increasingly functional programming concepts (like say preferring immutability).

    I think problem solving on a computer is very fun and that's why I stole your problem instead of helping you. But maybe it turned out right because now you have a working solution to look at.
    Last edited by wolle; July 2nd, 2018 at 02:34 AM.

  5. #20
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,416

    Re: How exactly does recursion work with iterators?

    Pass primitives by value (including anything that doesn't cost more to pass than the largest primitive), pass everything else by const reference.
    Yes. Passing by reference usually just has an overhead of copying a pointer by value (either 32 or 64 bits). So anything passed which has a higher performance copying cost then this should be passed by ref.

    I consider the choice between pass by value and pass by const reference a premature optimization because they are logically equivalent.
    Only if the cost of a copy by value doesn't exceed the cost of a pass by const reference. Passing a 500MB vector by value and by const reference will have a huge difference in performance. Don't pass by value anything that uses dynamic memory unless you really mean a copy to be made.

    Finally, I have great faith in today's optimizing compilers. With full optimization enabled I expect compilers to not generate unnecessary code.
    They're not there yet re parameter passing. They don't optimise a by value to a const reference (but there are certainly cases where the compiler could make such an optimization but don't currently) - but they are there for function return (in C++17 with Guaranteed copy elision). Where ever possible a function return value is now not by value (ie is not copied) so it is safe performance wise to return dynamic data structures. So we can finally return vectors etc OK without having to have them as reference params!
    Last edited by 2kaud; July 1st, 2018 at 12:03 PM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.8.4)

  6. #21
    Join Date
    Feb 2017
    Posts
    344

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by 2kaud View Post
    Only if the cost of a copy by value doesn't exceed the cost of a pass by const reference. Passing a 500MB vector by value and by const reference will have a huge difference in performance. Don't pass by value anything that uses dynamic memory unless you really mean a copy to be made.
    My point was that even if it doesn't make any difference for the logic of my code whether I pass by value or by const reference, C++ still forces me to make a performance consideration when deciding which one of these passing mechanisms to use, and that's an optimization. I accept that this is how C++ works and thanks to my rule of thumb I don't have to dwell on the decision. It's not that important so I remove that comment from my post #18.

    I also remove the section on my faith in optimizing compilers. I still have it but who cares . I know that if I don't apply my rule of thumb and make the wrong choice the compiler won't save the day. I think it maybe should but at this point it doesn't as you state.
    Last edited by wolle; July 2nd, 2018 at 01:40 AM.

Page 2 of 2 FirstFirst 12

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)