c++ - unordered_set 是用于存储 vector 元素的适当数据结构吗？如果是这样，我将如何着手实现哈希函数？

Question

所以这个问题是由我目前正在尝试的 HackerRank 练习提示的。 “月球之旅”练习采用给定的成对宇航员列表，这些宇航员在最终结果中被阻止组合在一起。

宇航员名单的原始容器是vector<vector<int>>宇航员，但在我的实现中，我将此列表(经过研究)更改为 unordered_set<vector<int>>宇航员，因为我发现这个问题的很多开销都被这个数据结构满足了。问题是我现在不知道应该如何散列宇航员的每个元素。我知道标准 C++ 不提供散列 vector 值的默认实现，我必须提供自己的散列实现到 vector 模板。但是我该怎么做(我对散列不太了解)。但是，我还读到应该避免使用容器作为 unordered_sets 的键；因此我被困住了。

unordered_set 真的是我正在尝试做的最好的数据结构吗:在一个集合中存储唯一的整数对，其中对的顺序并不特别重要，并提供对元素的恒定时间访问或者是有一个更好的容器来容纳我正在尝试做的事情。这是我在尝试实现散列之前的代码。 main() 和 split_string() 是预定义的。在此先感谢您的帮助!

HackerRank 链接: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

一般来说，unordered_set不是用于在 vector 中存储元素的适当数据结构，因为根据定义，这样做会破坏原始元素的顺序，这是 vector 的一个关键特征.

但是，在您的情况下，宇航员对列表的顺序似乎无关紧要(只要满足所有对的排除)。所以在这种特殊情况下，您可能使用unordered_set而不是 vector存储列表。

事实上，而不是vector<int> , 你应该使用 pair<int, int>存储一对宇航员，然后实现哈希函数如下:

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

编辑:简单散列“算法”的选择可能并不完美——您当然可以对其进行改进。请注意，它使 Hash(a,b) == Hash(b,a)，这可能是适合此处应用的属性。您可能希望实现自己的 unordered_pair并使用它代替 std::pair .

然后可以将无序的宇航员对集定义为

unordered_set<pair<int, int> > astronaut_pairs;

另请参阅:https://stackoverflow.com/a/18098536/4509057