# How exactly does recursion work with iterators?

Show 50 post(s) from this thread on one page
Page 2 of 2 First 12
• June 30th, 2018, 01:56 PM
Marc G
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)`

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.
• June 30th, 2018, 03:44 PM
Kingdominth4
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.
• June 30th, 2018, 06:29 PM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by Marc G
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.
• July 1st, 2018, 10:54 AM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by Kingdominth4
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.

Quote:

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.
• July 1st, 2018, 11:20 AM
2kaud
Re: How exactly does recursion work with iterators?
Quote:

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.

Quote:

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.

Quote:

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!
• July 1st, 2018, 03:16 PM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by 2kaud
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.
Show 50 post(s) from this thread on one page
Page 2 of 2 First 12