How exactly does recursion work with iterators?

Hello. So I'm working on a Hackerrank exercise: "Journey to the Moon". In which you are given a list of pairs of astronauts that are bounded and one has to traverse through the provided list and link all connected pairs of astronauts. The result is an integer number that represents all possible non-bounded pairs in a set of n astronauts given the provided list of bounded astronaut pairs.

I have completed most of the solution of the problem, and my program even works for most simple cases. However, it fails on larger cases--primarily those where the iterator reaches the end of the list but there is more than one pair remaining within the list of astronauts.

My solution to this problem involves recursion and iteration through the list of astronauts (which is a set), while its elements are simultaneously deleted. And indeed, the particular error that prompted me to make this post is an iterator invalidation error. Though, I made sure to add safeguards to make sure the iterator never points to a delete element in the list of astronauts.

I debugged my program and was able to track down what exactly was causing my solution to crash, with a particular problematic test case. In this test case of 70 pairs, around the time when 53 of those pairs were remaining in the list of astronauts and when temp_set's (a set pointer passed to my recursive function) size was 18. The most recent recursive call finished iterating through the list of astronauts when iterator it went out of bounds triggering the while condition: it != astronaut->end(), returned its result to the next most recent recursive call-- here is where the issue lies-- whose iterator value was also undefined but not equal to astronaut->end(). The returned items were inserted into temp_set and, for some reason, the while loop was also checked. This time the check it != astronaut->end() triggered the error: list iterator incompatible. But why?

I thought with sets an invalidated iterator only triggers an error when that iterator tries to access an item in a set. But, this should not be the case in it != astronaut->end().

The iterator value that triggered this error was equal to: (-572662307, -572662307) while astronaut->end() was equal to: (-842150451, -842150451)

The IDE I am using is the free version of visual studio 2015 and I am using the compiler that was included with the package.

The input that I used to debug is: https://hr-testcases-us-east-1.s3.am...e=text%2Fplain

The details on the problem can be found at: https://www.hackerrank.com/challenge.../code/73601862

Thank you in advance for your assistance! Here is my code.

Code:

---

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
#include <stack>
#include <unordered_set>




using namespace std;

vector<string> split_string(string);

template <>
struct hash<pair<int, int> > {
        size_t operator()(const pair<int, int>& x) const noexcept
        {
                return (size_t)x.first * x.second + x.first + x.second;
        }
};

struct custom_set : unordered_set<int>
{
        void pair_insert(pair<int, int> pair)
        {
                insert(pair.first);
                insert(pair.second);
        }

        void pairs_insert(std::initializer_list <pair<int, int>> pairs)
        {
                for (pair<int, int> pair : pairs)
                {
                        insert(pair.first);
                        insert(pair.second);
                }
        }
};


pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>>::iterator it);

bool do_not_repeat;

// Complete the journeyToMoon function below.

int journeyToMoon(int n, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut)
//astronaut ids numbered : [0, n-1]
{
        //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded
        //vector<int> set_of_free_astronauts;

       
        vector<unordered_set<int>> sets_of_bounded_astronauts;
        vector<int> num_bounded_astronauts_each_set;
        int num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;
       
        while (!astronaut->empty())
        {
                //*astronaut->begin()++
               
                pair<int, int> id_pair = *astronaut->begin();
                custom_set * temp_set = new custom_set;
                journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());
                sets_of_bounded_astronauts.push_back(*temp_set);
                num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size
                num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size
                delete temp_set;
        }

        num_free_astronauts = n - num_bounded_astronauts_total;

        for (int i = 0; i < num_bounded_astronauts_each_set.size() - 1; i++)
        {
                for (int j = i + 1; j < num_bounded_astronauts_each_set.size(); j++)
                        result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];
                result += num_free_astronauts * num_bounded_astronauts_each_set[i];
        }

        result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1))/2;

        return result;
}

pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int> , hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>>::iterator it)
{
       
        while (!astronaut->empty() && it != astronaut->end()) {
                // copy the current iterator then increment it
                astronaut->erase(id_pair1);
                pair<int, int> id_pair2 = *it++;
       
                if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first
                        || id_pair2.second == id_pair1.second)
                {                       
                        temp_set->pairs_insert({ id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,
                                id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin()) });
                }
        }
        astronaut->erase(id_pair1);
        temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case
        //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates

        return id_pair1;

}

int main()
{
       
        //ofstream fout(getenv("OUTPUT_PATH"));

        string np_temp;
        std::getline(std::cin, np_temp);

        vector<string> np = split_string(np_temp);

        int n = stoi(np[0]);

        int p = stoi(np[1]);

        unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut = new unordered_set<pair<int, int>, hash<pair<int, int>>>(p);
        for (int i = 0; i < p; i++) {
                int a, b;
                std::cin >> a >> b;
                astronaut->insert(pair<int, int>(a, b));
                }

        std::cin.ignore(numeric_limits<streamsize>::max(), '\n');

        int result = journeyToMoon(n, astronaut);

        //fout << result << "\n";
        std::cout << result << "\n";
        //fout.close();
        delete astronaut;

        return 0;
}

vector<string> split_string(string input_string)
{
        string::iterator new_end = unique(input_string.begin(), input_string.end(), [](const char &x, const char &y) {
                return x == y && x == ' ';
        });

        input_string.erase(new_end, input_string.end());

        while (input_string[input_string.length() - 1] == ' ') {
                input_string.pop_back();
        }

        vector<string> splits;
        char delimiter = ' ';

        size_t i = 0;
        size_t pos = input_string.find(delimiter);

        while (pos != string::npos) {
                splits.push_back(input_string.substr(i, pos - i));

                i = pos + 1;
                pos = input_string.find(delimiter, i);
        }

        splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

        return splits;
}

---

Without looking at your code, you most likely are changing a data structure while iterating over it.

This is consistent with your bug description; The code works for smaller cases because then the data structure doesn't re-organize internally but with larger cases it does and the iterator becomes invalidated.

If you used using to set up new type names for commonly used data types eg

Code:

---

using Paii = pair<int, int>;

template <>
struct hash<Paii> {
        size_t operator()(const Paii& x) const noexcept
        {
                return (size_t)x.first * x.second + x.first + x.second;
        }
};

using unsetpii = unordered_set<Paii, hash<Paii>>;
using unsetpiiIt = unsetpii::iterator;

---

and used these in the code, then your code would be much easier to read!

You have an error in the definitions of journeyToMoon() when you use an incorrect iterator type.

Code:

---

pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>>::iterator it);

---

should be

Code:

---

pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it);

---

which if the using type definitions were used would become

Code:

---

Paii journeyToMoon(Paii id_pair1, unsetpii* astronaut, custom_set* temp_set, unsetpiiIt it);

---

(and similar for the definiton).

which is much easier to understand and less likely to have a type error.

Quote:

---

Originally Posted by Kingdominth4

The details on the problem can be found at: https://www.hackerrank.com/challenge.../code/73601862

---

That link didn't work if you're not a member of hackerrank but this one seems to do,

https://www.hackerrank.com/challenge...e-moon/problem

A pair of astronauts can be viewed as a point in a 2D coordinate system. If two pairs have an astronaut in common they can be viewed as linked with a line. In graph theory one would say that all linked pairs form a connected component (which in this problem represents one country). Finding all connected components is a standard problem,

https://en.wikipedia.org/wiki/Connec...(graph_theory)

Now that it is known which astronauts belong to which country the problem reduces to a standard combinatorics problem. Let's say we have a number of urns and all astronauts from the same country are in the same urn.

We now generate all combinations of 2 urns out of all urns. From each such 2 urn combination we get the number of possible pairs of astronauts from two different countries by simply multiplying the number of astronauts in the two urns. If we repeat this for all 2 urn combinations we end up with a grand sum total that is the solution to this problem.

Hi! Thank you so much for replying to me post. I am sorry it took me so long to get back with you. I couldn't find the time 2 days ago to reply and apparently the site was down yesterday.

I apologize that my code was difficult to parse. I thank you for your suggestions on improving readability and coherent code is something I really strive to create. Though, about your suggestion. Wouldn't using "using Paii = pair<int,int>" on top of "using namespace std" cause name clash? Or are you implying that I should use "using Paii = pair<int, int>" over "using namespace std"? Couldn't I achieve the same affect of "using Paii = pair<int, int>" with a "#define" instead?

Also, fixed the method signature like you suggested (thank you) which actually worked for another test case; however, you solution still didn't work for the test case in question. I still can't understand why though.

I'm especially confused about how the iterator it value changed from (-842150451, -842150451) to (-572662307, -572662307) and why the while loop condition is even being checked between recursive calls: the while loop condition should not have to be checked to apply the returned value from the previous recursive call. Yet it does. I do not understand this also.

Although the error that you pointed out definitely contributed to the problem, perhaps there is something else going on too. The conditions that caused error are still the same as I initially specified. Thanks a bunch. My code is updated as follows:

Code:

---

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
#include <stack>
#include <unordered_set>




using namespace std;

vector<string> split_string(string);

template <>
struct hash<pair<int, int> > {
        size_t operator()(const pair<int, int>& x) const noexcept
        {
                return (size_t)x.first * x.second + x.first + x.second;
        }
};

struct custom_set : unordered_set<int>
{
        void pair_insert(pair<int, int> pair)
        {
                insert(pair.first);
                insert(pair.second);
        }

        void pairs_insert(std::initializer_list <pair<int, int>> pairs)
        {
                for (pair<int, int> pair : pairs)
                {
                        insert(pair.first);
                        insert(pair.second);
                }
        }
};


pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it);



// Complete the journeyToMoon function below.

int journeyToMoon(int n, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut)
//astronaut ids numbered : [0, n-1]
{
        //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded
        //vector<int> set_of_free_astronauts;

       
        vector<unordered_set<int>> sets_of_bounded_astronauts;
        vector<int> num_bounded_astronauts_each_set;
        int num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;
       
        while (!astronaut->empty())
        {
                //*astronaut->begin()++
               
                pair<int, int> id_pair = *astronaut->begin();
                custom_set * temp_set = new custom_set;
                journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());
                sets_of_bounded_astronauts.push_back(*temp_set);
                num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size
                num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size
                delete temp_set;
        }

        num_free_astronauts = n - num_bounded_astronauts_total;

        for (int i = 0; i < num_bounded_astronauts_each_set.size() - 1; i++)
        {
                for (int j = i + 1; j < num_bounded_astronauts_each_set.size(); j++)
                        result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];
                result += num_free_astronauts * num_bounded_astronauts_each_set[i];
        }

        result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1))/2;

        return result;
}

pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int> , hash<pair<int, int>>> * astronaut,
        custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it)
{
       
        while (it != astronaut->end()) {
                // copy the current iterator then increment it
                astronaut->erase(id_pair1);
                pair<int, int> id_pair2 = *it++;
       
                if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first
                        || id_pair2.second == id_pair1.second)
                {                       
                        temp_set->pairs_insert({ id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,
                                id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin()) });
                }
        }
        astronaut->erase(id_pair1);
        temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case
        //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates

        return id_pair1;

}

int main()
{
       
        //ofstream fout(getenv("OUTPUT_PATH"));

        string np_temp;
        std::getline(std::cin, np_temp);

        vector<string> np = split_string(np_temp);

        int n = stoi(np[0]);

        int p = stoi(np[1]);

        unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut = new unordered_set<pair<int, int>, hash<pair<int, int>>>(p);
        for (int i = 0; i < p; i++) {
                int a, b;
                std::cin >> a >> b;
                astronaut->insert(pair<int, int>(a, b));
                }

        std::cin.ignore(numeric_limits<streamsize>::max(), '\n');

        int result = journeyToMoon(n, astronaut);

        //fout << result << "\n";
        std::cout << result << "\n";
        //fout.close();
        delete astronaut;

        return 0;
}

vector<string> split_string(string input_string)
{
        string::iterator new_end = unique(input_string.begin(), input_string.end(), [](const char &x, const char &y) {
                return x == y && x == ' ';
        });

        input_string.erase(new_end, input_string.end());

        while (input_string[input_string.length() - 1] == ' ') {
                input_string.pop_back();
        }

        vector<string> splits;
        char delimiter = ' ';

        size_t i = 0;
        size_t pos = input_string.find(delimiter);

        while (pos != string::npos) {
                splits.push_back(input_string.substr(i, pos - i));

                i = pos + 1;
                pos = input_string.find(delimiter, i);
        }

        splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

        return splits;
}

---

Thank you for replying! How is this the case with unordered_set? Could you elaborate? Can reordering be avoided, and if not, does that mean unordered_set is not the appropriate data structure to be using after all? Thanks! A lot of the overhead of the problem was solved by using an unordered_set so that's why that data structure was my default, but perhaps there is a better way to: store unique elements, whose order is not important, and provide constant time access to its elements for deletion.

Really, the crux of my implementation of the problem hinges on the property of deletion that just described. Maybe there is a data structure that is more apt for that?

Thanks for summarizing the problem. I did not tackle the problem in the fashion you described. Though I wonder if your interpretation would be easier to solve.

I apologize. I now realize that I didn't provide much insight into my approach of solving this problem. I can explain. My solution involved the application of set theory. As the problem describes, two astronauts are bounded (meaning they are not available to be represented as pair in the final solution) if they directly appear as a pair within the provided list of astronauts or if they a linked transitively to one of the astronauts that directly appear in said pair. The final solution should reflect the total number astronauts that are not bounded together (or in other words "free"). That solution involves a sum of the amount of resulting pairs from the Cartesian product between every two sets of bounded astronauts, resulting pairs from the Cartesian product between the set of free astronauts and every set of bounded astronauts, and the subsets of size two within the free set itself. Such a sum represents the total amount of astronauts that can be grouped together from a list of astronauts that can't be.

Bounded astronauts can be grouped together in sets, where one such set represents all the astronauts that are prohibited from appearing together as a pair of two in the final solution. You have to correctly group all transitively linked astronauts within a given set to solve the problem. Given a pair pair1: <a1, a2>, that task entails finding all pairs that include a1, and then finding all pairs that include a2.

If there are any pairs matching the previous condition, we must then consider that pair pair2: <a3, a4> and add its astronaut (only one because by definition, one of its astronauts must be a1 or a2 and there for is already included in the set of bounded astronauts) to the set of astronauts that can't be grouped with a1 and a2. Every pair in the list of astronauts must be checked against pair1, and then against pair2, and so on, since there may be more than two pairs that include a1 or a2, a3 or a4, and so on.

Once the last transitively linked pair is checked against all the remaining astronauts in the list (the end of the astronaut list is reached), we know that there are no more bounded astronauts in the list of astronauts (at least for the current pair). We can then visit the next most current pair and continue checking it against the remaining astronauts in the list (provided that it hasn't already been checked against all the remaining astronauts). This situation occurs until pair1 has been checked against all the astronauts in the list. And once it has, the first set of bounded astronauts is made (there can be more than one set if there are pairs of astronauts in the list that are not transitively linked to pair1--in which case, the process is repeated with the first instance of said pairs).

You can see how this interpretation naturally encourages the use of recursion, which is what I used. And the only way to check a pair against all pairs in the list is to somehow iterate through the list of astronaut pairs, which is why I used the while loop. But for some reason the condition of the while loop is causing an error, when I don't think it should.

Why does "it != astronaut->end()" cause an error with the value (-572662307, -572662307)? Obviously there is a value there. And although that value is not equal to the value of astronaut->end(): (-842150451, -842150451), it should not be prompting the error "list iterators incompatible", right?

Also, sorry. I didn't realize that the link was dead. Though I can include the 70 integer pairs if that is necessary to diagnose the problem.

Quote:

---

Originally Posted by Kingdominth4

Though I wonder if your interpretation would be easier to solve.

---

So do I and that's why I'm tempted to give it a go. :)

I would appreciate if you would post the 70-pairs test case.

Quote:

---

Though, about your suggestion. Wouldn't using "using Paii = pair<int,int>" on top of "using namespace std" cause name clash?

---

I mean consider (I've done some other tidying up)

Code:

---

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
#include <unordered_set>

using namespace std;

vector<string> split_string(string);

using Paii = pair<size_t, size_t>;

template <>
struct hash<Paii> {
        size_t operator()(const Paii& x) const noexcept
        {
                return x.first * x.second + x.first + x.second;
        }
};

using Unsetpii = unordered_set<Paii, hash<Paii>>;
using UnsetpiiIt = Unsetpii::iterator;
using Unseti = unordered_set<int>;

struct custom_set : Unseti
{
        void pair_insert(Paii pair)
        {
                insert(pair.first);
                insert(pair.second);
        }

        void pairs_insert(const initializer_list<Paii>& pairs)
        {
                for (auto pair : pairs)
                        pair_insert(pair);
        }
};


Paii journeyToMoon(Paii id_pair1, Unsetpii *astronaut, custom_set *temp_set, UnsetpiiIt it);

// Complete the journeyToMoon function below.

size_t journeyToMoon(size_t n, Unsetpii *astronaut)
//astronaut ids numbered : [0, n-1]
{
        //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded
        //vector<int> set_of_free_astronauts;

        vector<Unseti> sets_of_bounded_astronauts;
        vector<size_t> num_bounded_astronauts_each_set;
        size_t num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;

        while (!astronaut->empty())
        {
                //*astronaut->begin()++

                const auto id_pair = *astronaut->begin();
                const auto temp_set = new custom_set;

                journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());
                sets_of_bounded_astronauts.push_back(*temp_set);
                num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size
                num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size

                delete temp_set;
        }

        num_free_astronauts = n - num_bounded_astronauts_total;

        for (size_t i = 0; i < num_bounded_astronauts_each_set.size() - 1; ++i)
        {
                for (size_t j = i + 1; j < num_bounded_astronauts_each_set.size(); ++j)
                        result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];

                result += num_free_astronauts * num_bounded_astronauts_each_set[i];
        }

        result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1)) / 2;

        return result;
}

Paii journeyToMoon(Paii id_pair1, Unsetpii *astronaut, custom_set *temp_set, UnsetpiiIt it)
{
        while (it != astronaut->end()) {
                // copy the current iterator then increment it
                astronaut->erase(id_pair1);
                const auto id_pair2 = *it++;

                if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first
                        || id_pair2.second == id_pair1.second)
                                temp_set->pairs_insert({id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,
                                        id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin())});
        }

        astronaut->erase(id_pair1);
        temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case
                                                                        //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates

        return id_pair1;
}

int main()
{
        //ofstream fout(getenv("OUTPUT_PATH"));

        string np_temp;
        getline(cin, np_temp);

        const auto np = split_string(np_temp);

        const auto n = stoul(np[0]);
        const auto p = stoul(np[1]);

        const auto astronaut = new Unsetpii(p);

        for (size_t i = 0; i < p; ++i) {
                size_t a, b;
                cin >> a >> b;
                astronaut->emplace(a, b);
                //astronaut->insert(Paii(a, b));
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        const auto result = journeyToMoon(n, astronaut);

        //fout << result << "\n";
        cout << result << "\n";
        //fout.close();
        delete astronaut;

        return 0;
}

vector<string> split_string(string input_string)
{
        const char delimiter = ' ';

        // Remove duplicate spaces
        const auto new_end = unique(input_string.begin(), input_string.end(), [&](const char &x, const char &y) {
                return x == y && x == delimiter;
        });

        // Remove left-overs from duplicate at end
        input_string.erase(new_end, input_string.end());

        // Make sure ends with a delimiter
        if (input_string.back() != delimiter)
                input_string.push_back(delimiter);

        vector<string> splits;

        // Split string on space
        for (size_t i = (input_string.front() == delimiter), pos = 0; (pos = input_string.find(delimiter, i)) != string::npos; i = pos + 1)
                splits.push_back(input_string.substr(i, pos - i));

        return splits;
}

---

using has different meanings depending upon how its used. In the case of

Code:

---

using Paii = pair<size_t, size_t>;

---

its the modern equivalent of

Code:

---

typedef pair<size_t, size_t> Paii;

---

I've come up with a solution now according to the strategy in my post #4. The test cases from the problem description work but I would need more to be sure.

The first part of the algorithm (the graph theory) is linear in the number of pairs and the second part (the conbinatorics) is linear in the number countries, so it should be O(N) altogether.

Code:

---

#include <vector>
#include <utility>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <stack>

using Astro = int;
using Pair = std::pair<Astro, Astro>;
using PairList = std::vector<Pair>;

int journeyToMoon2(const int n, const PairList& pairs) {

        // definitions

        const int ASTROS = n; // number of astronauts

        const auto equal = [] (Pair l, Pair r) {return l.first == r.first;};
        const auto hash = [] (Pair p) {return std::hash<Astro>{}(p.first);};
        using PairSet = std::unordered_multiset<Pair, decltype(hash), decltype(equal)>; // hash table for pairs, equal relation is on first astronaut in a pair
       
        PairSet straight(10, hash, equal); // pairs are stored as is
        PairSet reversed(10, hash, equal); // pairs are reversed and stored

        const auto reverse_pair = [](Pair p) {
                return Pair(p.second, p.first);
        };

        const auto add_pair = [&] (Pair p) { // add pait to both hash tables
                straight.emplace(p); // straight
                reversed.emplace(reverse_pair(p)); // reverse
        };

        const auto remove_pair = [&] (Pair p) { // remove certain pair from both hashtable
                const auto range1 = straight.equal_range(p);
                const auto iterator1 = std::find(range1.first, range1.second, p);
                if (iterator1 != range1.second) straight.erase(iterator1);

                const Pair r = reverse_pair(p);
                const auto range2 = reversed.equal_range(r);
                const auto iterator2 = std::find(range2.first, range2.second, r);
                if (iterator2 != range2.second) reversed.erase(iterator2);
        };

        const auto any_pair = [&] () { // pick any pair
                return *straight.begin();
        };

        const auto no_pairs = [&] () { // no more pairs
                return straight.empty();
        };

// setup

        using Urn = std::vector<Astro>;
        using Urns = std::vector<Urn>;
        Urns urns;        // the urns

        using AstroSet = std::unordered_set<Astro>;
        AstroSet astrosInPairs; // stores all astronauts that are present in the list of pairs

        for (Pair p : pairs) {
                add_pair(p); // add pairs to hash tables
                astrosInPairs.insert(p.first);
                astrosInPairs.insert(p.second);
        }

        for (Astro i=0; i<ASTROS; ++i) { // astronauts that are not in the pair list get one urn each
                if (astrosInPairs.count(i) == 0) {
                        Urn urn;
                        urn.push_back(i);
                        urn.shrink_to_fit();
                        urns.push_back(urn);
                }
        }
        astrosInPairs.clear();


        // Part 1 - generating all urns with austronauts from the same country

        while (!no_pairs()) { // as long as there are pairs
                std::stack<Pair> stack;
                const auto push_stack = [&] (Pair p) {
                        stack.push(p);
                };
                const auto pop_stack = [&] () {
                        Pair p = stack.top();
                        stack.pop();
                        return p;
                };

                AstroSet set; // tempporary storage for astrounauts the will go into one urn

                push_stack(any_pair()); // push any pair
                while (!stack.empty()) { // when empty all astronouts from a common country have been identified
                        const Pair p = pop_stack(); // pop a pair

                        remove_pair(p); // remove it from both hash tables

                        set.insert(p.first); // store both astronauts of the pair
                        set.insert(p.second);

                                // identify all other pairs that share an astronout with this pair
                        const auto range1 = straight.equal_range(p);
                        std::for_each(range1.first, range1.second, push_stack);
                        const auto range2 = reversed.equal_range(p);
                        std::for_each(range2.first, range2.second, push_stack);

                        const Pair r = reverse_pair(p);
                        const auto range3 = straight.equal_range(r);
                        std::for_each(range3.first, range3.second, push_stack);
                        const auto range4 = reversed.equal_range(r);
                        std::for_each(range4.first, range4.second, push_stack);
                }

                Urn urn(set.begin(), set.end()); // load urn with astronauts
                urn.shrink_to_fit();
                urns.push_back(urn); // store urn
        }

        { // print urns
                std::cout << "The urns ="  << std::endl;
                int i=0;
                for (Urn urn : urns) {
                        std::cout << (i++) << ": " ;
                        for (Astro a : urn) {
                                std::cout << a << " " ;
                        }
                        std::cout << std::endl;
                }
        }

       
        // Part 2 - generate all combination of 2 urns and sum up all possible pairs of astronouts from different countries.
/*
        int sum = 0;
        const int URNS = int(urns.size());
        for (int i=0; i<URNS; ++i) { // first urns
                const int ni = int(urns[i].size());
                for (int j=i+1; j<URNS; ++j) { // second urns
                        const int nj = int(urns[j].size());
                        sum += ni*nj; // multiply the number of astronauts of urn 1 and 2 and add to sum
                }
        }
*/
                // the above nested loops can be optimized to no nesting
                // with the use of an array of accumulated sums like
/*        const int URNS = int(urns.size());
        std::vector<int> accSum;
        for (int i=0; i<URNS; ++i) accSum.push_back(int(urns[i].size())); // copy urn sizes
        for (int i=URNS-1; i>0; --i) accSum[i-1] += accSum[i]; // calculate accumulated sums
        int sum=0;
        for (int i=0; i<URNS-1; ++i) sum += int(urns[i].size())*accSum[i+1]; // perform summing
*/

                // and the above 3 loops merged into one
        int sum = 0;
        {
                int accSum = 0;
                for (int i=int(urns.size())-1; i>0; --i) {
                        accSum += int(urns[i].size());
                        sum += accSum * int(urns[i-1].size());
                }
        }

        return sum;
}

void test() {

                // sample 0 from problem description
        PairList pairs_sample_0 = {
//                {5, 3}, // not a pair, 5 astronauts
                {0, 1},
                {2, 3},
                {0, 4}
        };
        int result_0 = journeyToMoon2(5, pairs_sample_0);
        std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should

                // sample 1 from problem description
        PairList pairs_sample_1 = {
//                {4, 1}, // not a pair, 4 astronauts
                {0, 2}
        };
        int result_1 = journeyToMoon2(4, pairs_sample_1);
        std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should

}

---

100 70
0 11
2 4
2 95
3 48
4 85
4 95
5 67
5 83
5 42
6 76
9 31
9 22
9 55
10 61
10 38
11 96
11 41
12 60
12 69
14 80
14 99
14 46
15 42
15 75
16 87
16 71
18 99
18 44
19 26
19 59
19 60
20 89
21 69
22 96
22 60
23 88
24 73
27 29
30 32
31 62
32 71
33 43
33 47
35 51
35 75
37 89
37 95
38 83
39 53
41 84
42 76
44 85
45 47
46 65
47 49
47 94
50 55
51 99
53 99
56 78
66 99
71 78
73 98
76 88
78 97
80 90
83 95
85 92
88 99
88 94

Thanks, I wasn't aware that using could be used like that. And thank you for polishing up the code. I agree, it looks a lot more legible.

And a few more:

10 7
0 2
1 8
1 4
2 8
2 6
3 5
6 9


10 20
0 1
0 3
0 4
1 2
1 3
1 5
1 7
1 8
1 9
2 8
2 7
3 5
3 8
3 7
4 9
4 5
4 6
4 7
6 8
6 7

10000 2
1 2
3 4

Wow, your program looks impressive. It seems you also used a while loop to iterate through the list. What is the benefit of using a lambda expression that returns "straight.empty()" as the while condition rather than just using "straight.empty()" directly as the while condition? Does that somehow circumvent errors or something? Should I use a lambda expression instead of using "it->astronaut.end()" directly in my program?

Quote:

---

Originally Posted by Kingdominth4

What is the benefit of using a lambda expression that returns "straight.empty()" as the while condition rather than just using "straight.empty()" directly as the while condition? Does that somehow circumvent errors or something? Should I use a lambda expression instead of using "it->astronaut.end()" directly in my program?

---

Several of my lambdas aren't strictly necessary. For example also pop_stack() and remove_pair() are both called from one place only. I do this for the reason of abstraction. If I were to tidy up the code (which I certainly would if it was for production) I probably would introduce a couple of classes to hide certain data structures and these functions would then most likely appear as methods of those classes. There's no reason to refrain from "unnecessary" lambdas for performance reasons, the compiler will see to that. I'm also quite fond of using the using keyword for the same purpose, namely abstraction.

Anyway I got these results,

(100 70) = 3984
(10 7) = 23
(10 20) = 0
(10000 2) = 49994998

Are they correct?

For the (10000 2) case I had to comment out the printing of the urns because the list became too long to fit in my output window. Here's the test program I used,

Code:

---

void test() {

                // sample 0 from problem description
        PairList pairs_sample_0 = {
//                {5, 3}, // not a pair, 5 astronauts
                {0, 1},
                {2, 3},
                {0, 4}
        };
        int result_0 = journeyToMoon2(5, pairs_sample_0);
        std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should
        std::cout << "----------" << std::endl; // 5 as it should

                // sample 1 from problem description
        PairList pairs_sample_1 = {
//                {4, 1}, // not a pair, 4 astronauts
                {0, 2}
        };
        int result_1 = journeyToMoon2(4, pairs_sample_1);
        std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should
        std::cout << "----------" << std::endl; // 5 as it should

        PairList pairs_sample_2 = {
//                {100, 70},
                {0, 11},
                {2, 4},
                {2, 95},
                {3, 48},
                {4, 85},
                {4, 95},
                {5, 67},
                {5, 83},
                {5, 42},
                {6, 76},
                {9, 31},
                {9, 22},
                {9, 55},
                {10, 61},
                {10, 38},
                {11, 96},
                {11, 41},
                {12, 60},
                {12, 69},
                {14, 80},
                {14, 99},
                {14, 46},
                {15, 42},
                {15, 75},
                {16, 87},
                {16, 71},
                {18, 99},
                {18, 44},
                {19, 26},
                {19, 59},
                {19, 60},
                {20, 89},
                {21, 69},
                {22, 96},
                {22, 60},
                {23, 88},
                {24, 73},
                {27, 29},
                {30, 32},
                {31, 62},
                {32, 71},
                {33, 43},
                {33, 47},
                {35, 51},
                {35, 75},
                {37, 89},
                {37, 95},
                {38, 83},
                {39, 53},
                {41, 84},
                {42, 76},
                {44, 85},
                {45, 47},
                {46, 65},
                {47, 49},
                {47, 94},
                {50, 55},
                {51, 99},
                {53, 99},
                {56, 78},
                {66, 99},
                {71, 78},
                {73, 98},
                {76, 88},
                {78, 97},
                {80, 90},
                {83, 95},
                {85, 92},
                {88, 99},
                {88, 94}
        };
        int result_2 = journeyToMoon2(100, pairs_sample_2);
        std::cout << "Result 2 = " << result_2 << std::endl;
        std::cout << "----------" << std::endl;

        PairList pairs_sample_3 = {
                //{10, 7},
                {0, 2},
                {1, 8},
                {1, 4},
                {2, 8},
                {2, 6},
                {3, 5},
                {6, 9}
        };
        int result_3 = journeyToMoon2(10, pairs_sample_3);
        std::cout << "Result 3 = " << result_3 << std::endl;
        std::cout << "----------" << std::endl;


        PairList pairs_sample_4 = {
//                {10, 20},
                {0, 1},
                {0, 3},
                {0, 4},
                {1, 2},
                {1, 3},
                {1, 5},
                {1, 7},
                {1, 8},
                {1, 9},
                {2, 8},
                {2, 7},
                {3, 5},
                {3, 8},
                {3, 7},
                {4, 9},
                {4, 5},
                {4, 6},
                {4, 7},
                {6, 8},
                {6, 7}
        };
        int result_4 = journeyToMoon2(10, pairs_sample_4);
        std::cout << "Result 4 = " << result_4 << std::endl;
        std::cout << "----------" << std::endl;

        PairList pairs_sample_5 = {
//                {10000, 2},
                {1, 2},
                {3, 4}
        };
        int result_5 = journeyToMoon2(10000, pairs_sample_5);
        std::cout << "Result 5 = " << result_5 << std::endl;
        std::cout << "----------" << std::endl;
}

---

Quote:

---

Originally Posted by wolle

I've come up with a solution now according to the strategy in my post #4.

---

I've cleaned up my solution in #10. It turns out that the second part of the solution strategy isn't necessary. Once it's known how many astronauts there are in an urn it's possible to calculate how much they contribute to the total pairs of astronauts from different countries. The contribution from astronauts that aren't in any urn can be calculated once the total number of astronauts that are in urns is known. This observation greatly simplifies the code.

Code:

---

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <stack>

namespace tomoon {

        using Astro = int;
        using Pair = std::pair<Astro,Astro>;
        using PairList = std::vector<Pair>;

        class PairBase { // pair storage
        public:

                PairBase(const PairList& pairs) {
                        for (Pair p : pairs) {
                                storage.emplace(p); // store all pairs
                                storage.emplace(reverse_pair(p)); // and reversed pairs
                        }
                }

                void remove_pair(Pair p) { // remove pair
                        const auto rem = [&] (const Pair p) {
                                const auto range = storage.equal_range(p); // here equal is on first of pair (as defined for Pairs in the storage hashtable)
                                const auto iterator = std::find(range.first, range.second, p); // here equal is on both first and second (standard for an std::pair)
                                if (iterator != range.second) storage.erase(iterator);
                        };
                        rem(p);
                        rem(reverse_pair(p));
                };

                Pair any_pair() const { // pick any pair (for example the first)
                        return *storage.begin();
                };

                bool no_pairs() const { // no more pairs ?
                        return storage.empty();
                };

                PairList linked_pairs(Pair p) const {        // identify all pairs that are linked (share an astronout) with this pair
                        PairList pairList;
                        const auto add = [&] (const Pair p) {
                                const auto range = storage.equal_range(p);
                                pairList.insert(pairList.end(), range.first, range.second);
                        };
                        add(p);
                        add(reverse_pair(p));
                        return pairList;
                }

        private:
                struct Hash {
                        std::size_t operator() (Pair p) const { return std::hash<Astro>{}(p.first); }
                };
                struct Equal {
                        bool operator() (Pair l,Pair r) const { return l.first == r.first; };
                };
                    // hash table for pairs, equal relation and hashing is on first astronaut of a pair
                std::unordered_multiset<Pair,Hash,Equal> storage; // pair storage

                Pair reverse_pair(Pair p) const { // switch first with second in pair
                        return Pair(p.second,p.first);
                };
        }; // PairBase


        inline int journey(const int astros,const PairList& pairs) {
                PairBase pairBase(pairs); // pair storage

                int comb_sum = 0; // total sum of astronaut not from same country combinations
                int urn_sum = 0; // sum of austronauts in urns

                while (!pairBase.no_pairs()) { // as long as there are pairs
                        std::stack<Pair> stack; // stack of pairs
                        std::unordered_set<Astro> urn; // urn of austronauts

                        stack.push(pairBase.any_pair()); // push any pair
                        while (!stack.empty()) { // when empty all astronouts from a common country have been identified
                                const Pair p = stack.top(); // pop a pair
                                stack.pop();
                                pairBase.remove_pair(p); // remove pair
                                urn.insert({p.first,p.second}); // store both astronauts of pair
                                for(const Pair q : pairBase.linked_pairs(p)) stack.push(q); // push all linked pairs on stack
                        }

                        const int n = int(urn.size()); // number of astros in this urn
                        urn_sum += n; // add to total urn sum
                        comb_sum += n * (astros - n); // multiply astros inside this urn with all other astros and add up total sum
                }
                comb_sum += (astros - urn_sum) * (astros - 1); // consider astros outside any urn
                comb_sum /= 2; // all combinations have been counted twice

                return comb_sum; //comb_sum;
        }

} // tomoon

void test() {

        // sample 0 from problem description
        tomoon::PairList pairs_sample_0 ={
                //                {5, 3}, // not a pair, 5 astronauts
                                {0,1},
                                {2,3},
                                {0,4}
        };
        int result_0 = tomoon::journey(5,pairs_sample_0);
        std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should
        std::cout << "----------" << std::endl; // 5 as it should

                                                                                        // sample 1 from problem description
        tomoon::PairList pairs_sample_1 ={
                //                {4, 1}, // not a pair, 4 astronauts
                                {0,2}
        };
        int result_1 = tomoon::journey(4,pairs_sample_1);
        std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should
        std::cout << "----------" << std::endl; // 5 as it should

        tomoon::PairList pairs_sample_2 ={
                //                {100, 70},
                                {0,11},
                                {2,4},
                                {2,95},
                                {3,48},
                                {4,85},
                                {4,95},
                                {5,67},
                                {5,83},
                                {5,42},
                                {6,76},
                                {9,31},
                                {9,22},
                                {9,55},
                                {10,61},
                                {10,38},
                                {11,96},
                                {11,41},
                                {12,60},
                                {12,69},
                                {14,80},
                                {14,99},
                                {14,46},
                                {15,42},
                                {15,75},
                                {16,87},
                                {16,71},
                                {18,99},
                                {18,44},
                                {19,26},
                                {19,59},
                                {19,60},
                                {20,89},
                                {21,69},
                                {22,96},
                                {22,60},
                                {23,88},
                                {24,73},
                                {27,29},
                                {30,32},
                                {31,62},
                                {32,71},
                                {33,43},
                                {33,47},
                                {35,51},
                                {35,75},
                                {37,89},
                                {37,95},
                                {38,83},
                                {39,53},
                                {41,84},
                                {42,76},
                                {44,85},
                                {45,47},
                                {46,65},
                                {47,49},
                                {47,94},
                                {50,55},
                                {51,99},
                                {53,99},
                                {56,78},
                                {66,99},
                                {71,78},
                                {73,98},
                                {76,88},
                                {78,97},
                                {80,90},
                                {83,95},
                                {85,92},
                                {88,99},
                                {88,94}
        };
        int result_2 = tomoon::journey(100,pairs_sample_2);
        std::cout << "Result 2 = " << result_2 << std::endl;
        std::cout << "----------" << std::endl;

        tomoon::PairList pairs_sample_3 ={
                //{10, 7},
                {0,2},
                {1,8},
                {1,4},
                {2,8},
                {2,6},
                {3,5},
                {6,9}
        };
        int result_3 = tomoon::journey(10,pairs_sample_3);
        std::cout << "Result 3 = " << result_3 << std::endl;
        std::cout << "----------" << std::endl;


        tomoon::PairList pairs_sample_4 ={
                //                {10, 20},
                {0,1},
                {0,3},
                {0,4},
                {1,2},
                {1,3},
                {1,5},
                {1,7},
                {1,8},
                {1,9},
                {2,8},
                {2,7},
                {3,5},
                {3,8},
                {3,7},
                {4,9},
                {4,5},
                {4,6},
                {4,7},
                {6,8},
                {6,7}
        };
        int result_4 = tomoon::journey(10,pairs_sample_4);
        std::cout << "Result 4 = " << result_4 << std::endl;
        std::cout << "----------" << std::endl;

        tomoon::PairList pairs_sample_5 ={
                //                {10000, 2},
                {1,2},
                {3,4}
        };
        int result_5 = tomoon::journey(10000,pairs_sample_5);
        std::cout << "Result 5 = " << result_5 << std::endl;
        std::cout << "----------" << std::endl;
}

---

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.

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.

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.

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.

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!

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.