Is an unordered_set an appropriate data structure for storing vector elements? And if so how would I go about implementing the hash function?

Question

so this question is prompted by a HackerRank practice exercise that I am currently attempting. The exercise "Journey to the Moon", takes a given list of pairs of astronauts that are prevented from being grouped together in the final result.

The original container for the list of astronauts was vector<vector<int>> astronaut, but in my implementation I changed this list (after researching) to be an unordered_set<vector<int>> astronauts because I found that a lot of the overhead of this problem was satisfied by this data structure. The problem is that I now don't know how I should go about hashing each element of astronaut. I understand that standard C++ does not provide a default implementation for hashing vector values, and that I must provide my own implementation for the hashing to the vector template. But just how do I do that (I don't understand much about hashing). However, I also read that one should avoid using containers as keys for unordered_sets; hence I am stuck.

Is an unordered_set really that best data structure for what I am trying to do: store unique pairs of integers within a set where the order of the pairs doesn't particularly matter, and provide constant-time access to the elements or is there a better container for what I am trying to do. Here is my code prior to attempting to implement hashing. main() and split_string() were pre-defined. Thanks in advance for the help!

HackerRank Link: https://www.hackerrank.com/challenges/journey-to-the-moon/problem

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);


int journeyToMoon(int n, unordered_set<pair<int, int>, hash<pair<int, int>>> *     astronaut)
//astronaut ids numbered : [0, n-1]
{



    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())
    {


        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()); 
        num_bounded_astronauts_total += sets_of_bounded_astronauts.back().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()
{



    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);


    std::cout << result << "\n";

    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;
}

Answer 1

In general, unordered_set is NOT an appropriate data structure for storing elements in a vector, because doing so destroys, by definition, the ordering of the original elements, which is a key feature of the vector.

In your case, however, it appears the ordering of the list of astronaut pairs doesn't matter (as long as the exclusion of all pairs are satisfied). So in this particular case, you probably could use unordered_set instead of vector to store the list.

In fact, instead of vector<int>, you should use pair<int, int> to store a pair of astronauts, and then implement the hash function as follows:

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;
  }
};

EDIT: The choice of the simple hashing "algorithm" may not be perfect -- you could certainly improve on it. Note that it makes Hash(a,b) == Hash(b,a), which might be a property that suits the application here. You may wish to implement your own unordered_pair and use it instead of std::pair.

The unordered set of astronaut pairs could then be defined as

unordered_set<pair<int, int> > astronaut_pairs;

See also: https://stackoverflow.com/a/18098536/4509057