STL Veri Yapısı - unordered_set - HashSet

Giriş
Bu sınıfı kullanmak için şu satırı dahil etmek gerekir.

#include <unordered_set>

Tanımı

Polymorphic allocator kullanan tanımı şöyledir

using unordered_set = std::unordered_set<Key, Hash, Pred,
                                         std::pmr::polymorphic_allocator<Key>>

Rehash 
Mark Weiss'ın "Data Structures and Algorithm Analysis in C++" kitabında şöyle bir örnek var. Gerçek veri yapısı da buna benzer bir şekilde çalışıyor.

/**
* Rehashing for quadratic probing hash table.
*/
void rehash( )
{
    vector<HashEntry> oldArray = array;

    // Create new double-sized, empty table
    array.resize( nextPrime( 2 * oldArray.size( ) ) );
    for( auto & entry : array )
        entry.info = EMPTY;

    // Copy table over
    currentSize = 0;
    for( auto & entry : oldArray )
        if( entry.info == ACTIVE )
            insert( std::move( entry.element ) );
}

Tanımlama
Elimizde şöyle bir sınıf olsun.

struct Link
{
  
  uint32_t param1; // ..... and more

  bool operator==(Link const& rhs)
  {
    return param1 == rhs.param1;
  }
}

Bu sınıfı set içinde kullanıbilmek için bir hash metodu yazmamız gerekir. Hash metodunu std isim alanı içine alabiliriz.

namespace std
{
  template<> struct hash<Link>
  {
    size_t operator()(Link const& link) const
    {
      return  hash<uint32_t>()(link.param1) ^ hash<uint32_t>()(link.param2);     }
  };    
}

Veri yapısını şöyle tanımlarız.

std::unordered_set<Link> link;

begin metodu - bucket index
Belirtilen bucket index'teki listeye erişim sağlar. Şöyle yaparız.

for (size_t index = 0; index < set.bucket_count(); ++index) {
  
  for (auto bit = set.begin(index); bit != set.end(index); ++bit) {
    cout << " " << *bit;
  }
  
}

bucket_count metodu
Her bucket içindeki listeye erişilebilir. Şöyle yaparız.

for (size_t index = 0; index < set.bucket_count(); ++index) {
  
  for (auto bit = set.begin(bidx); bit != set.end(bidx); ++bit) {
    cout << " " << *bit;
  }
  
}

erase metodu

Örnek
Elimizde şöyle bir kod olsun.

std::unordered_set<int> foo{1,2,3};

Bir değer varsa silip yeni bir değer eklemek için şöyle yaparız.

if (foo.erase(1)) {
    foo.insert(4);
}

operator ==
Örnek
Elimizde şöyle bir kod olsun

struct Foo {
};

struct FooHasher {
  size_t operator()(const Foo&) const {
    return ...;
  }
};

struct FooEqual {
  bool operator()(const Foo& lhs, const Foo& rhs) const {
    return true;
  }
};

std::unordered_set<Foo, FooHasher, FooEqual> s1;
std::unordered_set<Foo, FooHasher, FooEqual> s2;
(void)(s1 == s2);

İki set'in eişitliğini kontrol etmek için Foo nesnesinin "operator ==" metodunu olması gerekir. Açıklaması şöyle

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent=key group [Ea1,Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1,Eb2) obtained from b.equal_range(Ea1), such that distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1) returns true.