How exactly does recursion work with iterators?

[kingdominth4]

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 was 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.amazonaws.com/784/input02.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1528593910&Signature=Jp3C5%2ByQi1l7QaC35jnKgWBAfbs%3D&response-content-type=text%2Fplain

The details on the problem can be found at: https://www.hackerrank.com/challenges/journey-to-the-moon/submissions/code/73601862

Thank you in advance for your assistance! Here is my 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;
}