Является ли unordered_set подходящей структурой данных для хранения векторных<int> элементов? И если так, как бы я пошел о реализации хэш-функции?

Question

Поэтому этот вопрос вызван практическим упражнением 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;
}

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;

Смотрите также: /questions/15407998/kak-ispolzovat-unorderedset/15408010#15408010