unordered_set是否适合存储矢量<int>元素的数据结构？如果是这样，我将如何实现哈希函数？

Question

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

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

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

黑客排名链接：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