Как инициализировать unordered_set unordered_set? [Дубликат]

std::unordered_set<unsigned int>> не соответствует требованию быть элементом из std::unordered_set, поскольку не существует хэш-функции по умолчанию (т. е. std::hash<> не специализируется на std::unordered_set<unsigned int>>).

вы можете (он должен быть быстрым и избегать столкновений как можно больше):

class MyHash
{
public:
    std::size_t operator()(const std::unordered_set<unsigned int>& s) const 
    {
        return ... // return some meaningful hash of the et elements
    }
};

int main() {

    std::unordered_set<std::unordered_set<unsigned int>, MyHash> u;

}

Вы можете увидеть очень хорошие примеры хеш-функций в этом ответе .

Вы действительно должны предоставить как функцию Хэша и Равенства, удовлетворяющую стандартным требованиям неупорядоченного ассоциативного контейнера.

Hash () функция по умолчанию для создания хэшей элементов вашего набора не знает, как обращаться со всем набором как с элементом. Создайте хеш-функцию, которая создает уникальное значение для каждого уникального набора, и вам хорошо идти.

Это конструктор для unordered_set

explicit unordered_set( size_type bucket_count = /*implementation-defined*/, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); http: //en.cppreference.com/w/cpp/container/unordered_set/unordered_set

Возможно, самая простая вещь для вас - создать хеш-функцию для вашего unordered_set<unsigned int>

unsigned int my_hash(std::unordered_set<unsigned int>& element)
{
  for( e : element )
  {
     some sort of math to create a unique hash for every unique set
  }
}

edit: как видно из другого ответа, который я полностью забыл, функция хэширования должна находиться внутри объекта Hash. По крайней мере, согласно конструктору, который я вставил в свой ответ.

Есть причина, по которой хеш отсутствует unordered_set. По умолчанию unordered_set является изменчивой последовательностью. Хэш должен иметь такое же значение, пока объект находится в unordered_set. Таким образом, ваши элементы должны быть неизменными. Это не гарантируется с помощью модификатора const&, так как это только гарантирует, что только основной unordered_set и его методы не изменят sub- unordered_set. Не использовать ссылку может быть безопасное решение (вам все равно придется писать хеш-функцию), но действительно ли вам нужны накладные расходы на перемещение / копирование unordered_set s?

Вместо этого вы можете использовать какой-то вид указателя. Это отлично; указатель - это только адрес памяти, и ваш unordered_set сам не перемещается (он может перераспределить свой пул элементов, но кому это нужно?). Поэтому ваш указатель является постоянным, и он может удерживать один и тот же хэш для своего времени жизни в unordered_set. ( EDIT : как указал Говард, вы должны убедиться, что любой элемент вашего заказа хранится для вашего набора, если два набора имеют одинаковые элементы, они считаются равными. Выполняя заказ в том, как вы храните свой целые числа, вы легко получаете, что два набора соответствуют двум равным векторам.)

В качестве бонуса теперь вы можете использовать интеллектуальный указатель внутри самого основного набора для управления памятью sub- unordered_set, если вы

Обратите внимание, что это еще не самая эффективная реализация, чтобы получить набор наборов int. Чтобы сделать вас подмножествами, вы можете написать краткую обертку вокруг std::vector, которая хранит int, упорядоченную по значению. int int являются малыми и дешевыми для сравнения, а использование дихотомического поиска является только O(log n) по сложности. A std::unordered_set - это тяжелая структура и то, что вы теряете, перейдя от O(1) до O(log n), вы получите его обратно, имея компактную память для каждого набора. Это не должно быть слишком сложно реализовать, но почти гарантированно будет лучше в производительности.

Более сложное решение будет включать в себя trie .

Вы можете сделать это, но, как и каждый тип элемента unsorted_set/map, внутренняя unsorted_set теперь нуждается в определении функции Хэша. По умолчанию он не имеет его, но вы можете написать его самостоятельно.

Что вам нужно сделать, так это определить соответствующий хеш для ключей типа std::unordered_set<unsigned int> (поскольку operator== уже уже определен для этого ключа, вам не нужно будет также предоставлять EqualKey для параметра std::unordered_set<std::unordered_set<unsigned int>, Hash, EqualKey>.

Один простой (хотя и неэффективный) вариант - это хеш на общую сумму всех элементов набора. Это будет выглядеть примерно так:

template<typename T>
struct hash_on_sum
: private std::hash<typename T::element_type>
{
  typedef T::element_type count_type;
  typedef std::hash<count_type> base;
  std::size_t operator()(T const&obj) const
  {
    return base::operator()(std::accumulate(obj.begin(),obj.end(),count_type()));
  }
};

typedef std::unordered_set<unsigned int> inner_type;
typedef std::unordered_set<inner_type, hash_on_sum<inner_type>> set_of_unique_sets;

Однако, хотя это просто, это не хорошо, поскольку это не гарантирует следующее требование. Для двух разных параметров k1 и k2, которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должна быть очень малой, приближается к 1.0/std::numeric_limits<size_t>::max().