, поэтому этот вопрос вызван практическим упражнением HackerRank, которое я сейчас пытаюсь выполнить.В упражнении «Путешествие на Луну» приводится заданный список пар космонавтов, которые не могут быть сгруппированы вместе в конечном результате.
Первоначальным контейнером для списка астронавтов был vector<vector<int>> астронавт, но в своей реализации я изменил этот список (после исследования), чтобы он был unordered_set<vector<int>> астронавтами, потому что я обнаружил, что большая часть этих издержекпроблема была удовлетворена этой структурой данных.Проблема в том, что я сейчас не знаю, как мне следует хэшировать каждый элемент астронавта.Я понимаю, что стандартный C ++ не предоставляет реализацию по умолчанию для хэширования векторных значений, и что я должен предоставить свою собственную реализацию для хэширования в векторный шаблон.Но как мне это сделать (я не очень разбираюсь в хешировании).Однако я также читал, что следует избегать использования контейнеров в качестве ключей для 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;
}