unordered_set.hh

Go to the documentation of this file.

#ifndef VCSN_MISC_UNORDERED_SET_HH
# define VCSN_MISC_UNORDERED_SET_HH

# include <unordered_set>

# include <vcsn/misc/hash.hh>

namespace std
{

  /*-------------------------.
  | hash(unordered_set<T>).  |
  `-------------------------*/

  template <typename Key, typename Hash, typename KeyEqual, typename Alloc>
  struct hash<unordered_set<Key, Hash, KeyEqual, Alloc>>
  {
    using type = unordered_set<Key, Hash, KeyEqual, Alloc>;
    size_t operator()(const type& ss) const
    {
      // Compute the sum of the hashes.  Beware that we must be
      // independant of the order, since this is an unordered_set.
      Hash hasher;
      size_t res = 0;
      for (auto s: ss)
        res += hasher(s);
      return res;
    }
  };
}

namespace vcsn
{

  template <typename Key, typename Hash, typename KeyEqual, typename Alloc>
  bool
  has(const std::unordered_set<Key, Hash, KeyEqual, Alloc>& s, const Key& k)
  {
    return s.find(k) != std::end(s);
  }

  template <typename Key, typename Hash, typename KeyEqual, typename Alloc>
  std::unordered_set<Key, Hash, KeyEqual, Alloc>
  intersection(const std::unordered_set<Key, Hash, KeyEqual, Alloc>& s1,
               const std::unordered_set<Key, Hash, KeyEqual, Alloc>& s2)
  {
    if (s2.size() < s1.size())
      return intersection(s2, s1);
    else
      {
        std::unordered_set<Key, Hash, KeyEqual, Alloc> res;
        for (const auto& e : s1)
          if (has(s2, e))
            res.emplace(e);
        return res;
      }
  }

}

#endif // !VCSN_MISC_UNORDERED_SET_HH