text: ﻿#ifndef DEALII_UNORDERED_SET_H_
  #define DEALII_UNORDERED_SET_H_
  
  // 这个头文件包含两个模板类 unordered_set 和 unordered_multiset
  // 功能与用法与 set 和 multiset 类似，不同的是使用 hashtable
  // 作为底层实现机制，容器中的元素不会自动排序
  
  // notes:
  //
  // 异常保证：
  // mystl::unordered_set<Key> / mystl::unordered_multiset<Key>
  // 满足基本异常保证，对以下等函数做强异常安全保证：
  //   * emplace
  //   * emplace_hint
  //   * insert
  
  #include "hashtable.h"
  
  namespace mystl
  {
    // 模板类 unordered_set，键值不允许重复
    // 参数一代表键值类型，参数二代表哈希函数，缺省使用 mystl::hash，
    // 参数三代表键值比较方式，缺省使用 mystl::equal_to
    template <class Key,
              class Hash     = mystl::hash<Key>,
              class KeyEqual = mystl::equal_to<Key>>
    class unordered_set
    {
    private:
      // 使用 hashtable 作为底层机制
      typedef hashtable<Key, Hash, KeyEqual> base_type;
      base_type                              ht_;
  
    public:
      // 使用 hashtable 的型别
      typedef typename base_type::allocator_type allocator_type;
      typedef typename base_type::key_type       key_type;
      typedef typename base_type::value_type     value_type;
      typedef typename base_type::hasher         hasher;
      typedef typename base_type::key_equal      key_equal;
  
      typedef typename base_type::size_type       size_type;
      typedef typename base_type::difference_type difference_type;
      typedef typename base_type::pointer         pointer;
      typedef typename base_type::const_pointer   const_pointer;
      typedef typename base_type::reference       reference;
      typedef typename base_type::const_reference const_reference;
  
      typedef typename base_type::const_iterator       iterator;
      typedef typename base_type::const_iterator       const_iterator;
      typedef typename base_type::const_local_iterator local_iterator;
      typedef typename base_type::const_local_iterator const_local_iterator;
  
      allocator_type
      get_allocator() const
      {
        return ht_.get_allocator();
      }
  
    public:
      // 构造、复制、移动函数
  
      unordered_set()
        : ht_(100, Hash(), KeyEqual())
      {}
  
      explicit unordered_set(size_type       bucket_count,
                             const Hash &    hash  = Hash(),
                             const KeyEqual &equal = KeyEqual())
        : ht_(bucket_count, hash, equal)
      {}
  
      template <class InputIterator>
      unordered_set(InputIterator   first,
                    InputIterator   last,
                    const size_type bucket_count = 100,
                    const Hash &    hash         = Hash(),
                    const KeyEqual &equal        = KeyEqual())
        : ht_(mystl::max(bucket_count,
                         static_cast<size_type>(mystl::distance(first, last))),
              hash,
              equal)
      {
        for (; first != last; ++first)
          ht_.insert_unique_noresize(*first);
      }
  
      unordered_set(std::initializer_list<value_type> ilist,
                    const size_type                   bucket_count = 100,
                    const Hash &                      hash         = Hash(),
                    const KeyEqual &                  equal        = KeyEqual())
        : ht_(mystl::max(bucket_count, static_cast<size_type>(ilist.size())),
              hash,
              equal)
      {
        for (auto first = ilist.begin(), last = ilist.end(); first != last;
             ++first)
          ht_.insert_unique_noresize(*first);
      }
  
      unordered_set(const unordered_set &rhs)
        : ht_(rhs.ht_)
      {}
      unordered_set(unordered_set &&rhs) noexcept
        : ht_(mystl::move(rhs.ht_))
      {}
  
      unordered_set &
      operator=(const unordered_set &rhs)
      {
        ht_ = rhs.ht_;
        return *this;
      }
      unordered_set &
      operator=(unordered_set &&rhs)
      {
        ht_ = mystl::move(rhs.ht_);
        return *this;
      }
  
      unordered_set &
      operator=(std::initializer_list<value_type> ilist)
      {
        ht_.clear();
        ht_.reserve(ilist.size());
        for (auto first = ilist.begin(), last = ilist.end(); first != last;
             ++first)
          ht_.insert_unique_noresize(*first);
        return *this;
      }
  
      ~unordered_set() = default;
  
      // 迭代器相关
  
      iterator
      begin() noexcept
      {
        return ht_.begin();
      }
      const_iterator
      begin() const noexcept
      {
        return ht_.begin();
      }
      iterator
      end() noexcept
      {
        return ht_.end();
      }
      const_iterator
      end() const noexcept
      {
        return ht_.end();
      }
  
      const_iterator
      cbegin() const noexcept
      {
        return ht_.cbegin();
      }
      const_iterator
      cend() const noexcept
      {
        return ht_.cend();
      }
  
      // 容量相关
  
      bool
      empty() const noexcept
      {
        return ht_.empty();
      }
      size_type
      size() const noexcept
      {
        return ht_.size();
      }
      size_type
      max_size() const noexcept
      {
        return ht_.max_size();
      }
  
      // 修改容器操作
  
      // empalce / empalce_hint
  
      template <class... Args>
      pair<iterator, bool>
      emplace(Args &&...args)
      {
        return ht_.emplace_unique(mystl::forward<Args>(args)...);
      }
  
      template <class... Args>
      iterator
      emplace_hint(const_iterator hint, Args &&...args)
      {
        return ht_.emplace_unique_use_hint(hint, mystl::forward<Args>(args)...);
      }
  
      // insert
  
      pair<iterator, bool>
      insert(const value_type &value)
      {
        return ht_.insert_unique(value);
      }
      pair<iterator, bool>
      insert(value_type &&value)
      {
        return ht_.emplace_unique(mystl::move(value));
      }
  
      iterator
      insert(const_iterator hint, const value_type &value)
      {
        return ht_.insert_unique_use_hint(hint, value);
      }
      iterator
      insert(const_iterator hint, value_type &&value)
      {
        return ht_.emplace_unique_use_hint(hint, mystl::move(value));
      }
  
      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last)
      {
        ht_.insert_unique(first, last);
      }
  
      // erase / clear
  
      void
      erase(iterator it)
      {
        ht_.erase(it);
      }
      void
      erase(iterator first, iterator last)
      {
        ht_.erase(first, last);
      }
  
      size_type
      erase(const key_type &key)
      {
        return ht_.erase_unique(key);
      }
  
      void
      clear()
      {
        ht_.clear();
      }
  
      void
      swap(unordered_set &other) noexcept
      {
        ht_.swap(other.ht_);
      }
  
      // 查找相关
  
      size_type
      count(const key_type &key) const
      {
        return ht_.count(key);
      }
  
      iterator
      find(const key_type &key)
      {
        return ht_.find(key);
      }
      const_iterator
      find(const key_type &key) const
      {
        return ht_.find(key);
      }
  
      pair<iterator, iterator>
      equal_range(const key_type &key)
      {
        return ht_.equal_range_unique(key);
      }
      pair<const_iterator, const_iterator>
      equal_range(const key_type &key) const
      {
        return ht_.equal_range_unique(key);
      }
  
      // bucket interface
  
      local_iterator
      begin(size_type n) noexcept
      {
        return ht_.begin(n);
      }
      const_local_iterator
      begin(size_type n) const noexcept
      {
        return ht_.begin(n);
      }
      const_local_iterator
      cbegin(size_type n) const noexcept
      {
        return ht_.cbegin(n);
      }
  
      local_iterator
      end(size_type n) noexcept
      {
        return ht_.end(n);
      }
      const_local_iterator
      end(size_type n) const noexcept
      {
        return ht_.end(n);
      }
      const_local_iterator
      cend(size_type n) const noexcept
      {
        return ht_.cend(n);
      }
  
      size_type
      bucket_count() const noexcept
      {
        return ht_.bucket_count();
      }
      size_type
      max_bucket_count() const noexcept
      {
        return ht_.max_bucket_count();
      }
  
      size_type
      bucket_size(size_type n) const noexcept
      {
        return ht_.bucket_size(n);
      }
      size_type
      bucket(const key_type &key) const
      {
        return ht_.bucket(key);
      }
  
      // hash policy
  
      float
      load_factor() const noexcept
      {
        return ht_.load_factor();
      }
  
      float
      max_load_factor() const noexcept
      {
        return ht_.max_load_factor();
      }
      void
      max_load_factor(float ml)
      {
        ht_.max_load_factor(ml);
      }
  
      void
      rehash(size_type count)
      {
        ht_.rehash(count);
      }
      void
      reserve(size_type count)
      {
        ht_.reserve(count);
      }
  
      hasher
      hash_fcn() const
      {
        return ht_.hash_fcn();
      }
      key_equal
      key_eq() const
      {
        return ht_.key_eq();
      }
  
    public:
      friend bool
      operator==(const unordered_set &lhs, const unordered_set &rhs)
      {
        return lhs.ht_.equal_range_unique(rhs.ht_);
      }
      friend bool
      operator!=(const unordered_set &lhs, const unordered_set &rhs)
      {
        return !lhs.ht_.equal_range_unique(rhs.ht_);
      }
    };
  
    // 重载比较操作符
    template <class Key, class Hash, class KeyEqual, class Alloc>
    bool
    operator==(const unordered_set<Key, Hash, KeyEqual> &lhs,
               const unordered_set<Key, Hash, KeyEqual> &rhs)
    {
      return lhs == rhs;
    }
  
    template <class Key, class Hash, class KeyEqual, class Alloc>
    bool
    operator!=(const unordered_set<Key, Hash, KeyEqual> &lhs,
               const unordered_set<Key, Hash, KeyEqual> &rhs)
    {
      return lhs != rhs;
    }
  
    // 重载 mystl 的 swap
    template <class Key, class Hash, class KeyEqual, class Alloc>
    void
    swap(unordered_set<Key, Hash, KeyEqual> &lhs,
         unordered_set<Key, Hash, KeyEqual> &rhs)
    {
      lhs.swap(rhs);
    }
  
    /*****************************************************************************************/
  
    // 模板类 unordered_multiset，键值允许重复
    // 参数一代表键值类型，参数二代表哈希函数，缺省使用 mystl::hash，
    // 参数三代表键值比较方式，缺省使用 mystl::equal_to
    template <class Key,
              class Hash     = mystl::hash<Key>,
              class KeyEqual = mystl::equal_to<Key>>
    class unordered_multiset
    {
    private:
      // 使用 hashtable 作为底层机制
      typedef hashtable<Key, Hash, KeyEqual> base_type;
      base_type                              ht_;
  
    public:
      // 使用 hashtable 的型别
      typedef typename base_type::allocator_type allocator_type;
      typedef typename base_type::key_type       key_type;
      typedef typename base_type::value_type     value_type;
      typedef typename base_type::hasher         hasher;
      typedef typename base_type::key_equal      key_equal;
  
      typedef typename base_type::size_type       size_type;
      typedef typename base_type::difference_type difference_type;
      typedef typename base_type::pointer         pointer;
      typedef typename base_type::const_pointer   const_pointer;
      typedef typename base_type::reference       reference;
      typedef typename base_type::const_reference const_reference;
  
      typedef typename base_type::const_iterator       iterator;
      typedef typename base_type::const_iterator       const_iterator;
      typedef typename base_type::const_local_iterator local_iterator;
      typedef typename base_type::const_local_iterator const_local_iterator;
  
      allocator_type
      get_allocator() const
      {
        return ht_.get_allocator();
      }
  
    public:
      // 构造、复制、移动函数
  
      unordered_multiset()
        : ht_(100, Hash(), KeyEqual())
      {}
  
      explicit unordered_multiset(size_type       bucket_count,
                                  const Hash &    hash  = Hash(),
                                  const KeyEqual &equal = KeyEqual())
        : ht_(bucket_count, hash, equal)
      {}
  
      template <class InputIterator>
      unordered_multiset(InputIterator   first,
                         InputIterator   last,
                         const size_type bucket_count = 100,
                         const Hash &    hash         = Hash(),
                         const KeyEqual &equal        = KeyEqual())
        : ht_(mystl::max(bucket_count,
                         static_cast<size_type>(mystl::distance(first, last))),
              hash,
              equal)
      {
        for (; first != last; ++first)
          ht_.insert_multi_noresize(*first);
      }
  
      unordered_multiset(std::initializer_list<value_type> ilist,
                         const size_type                   bucket_count = 100,
                         const Hash &                      hash         = Hash(),
                         const KeyEqual &                  equal = KeyEqual())
        : ht_(mystl::max(bucket_count, static_cast<size_type>(ilist.size())),
              hash,
              equal)
      {
        for (auto first = ilist.begin(), last = ilist.end(); first != last;
             ++first)
          ht_.insert_multi_noresize(*first);
      }
  
      unordered_multiset(const unordered_multiset &rhs)
        : ht_(rhs.ht_)
      {}
      unordered_multiset(unordered_multiset &&rhs) noexcept
        : ht_(mystl::move(rhs.ht_))
      {}
  
      unordered_multiset &
      operator=(const unordered_multiset &rhs)
      {
        ht_ = rhs.ht_;
        return *this;
      }
      unordered_multiset &
      operator=(unordered_multiset &&rhs)
      {
        ht_ = mystl::move(rhs.ht_);
        return *this;
      }
  
      unordered_multiset &
      operator=(std::initializer_list<value_type> ilist)
      {
        ht_.clear();
        ht_.reserve(ilist.size());
        for (auto first = ilist.begin(), last = ilist.end(); first != last;
             ++first)
          ht_.insert_multi_noresize(*first);
        return *this;
      }
  
      ~unordered_multiset() = default;
  
      // 迭代器相关
  
      iterator
      begin() noexcept
      {
        return ht_.begin();
      }
      const_iterator
      begin() const noexcept
      {
        return ht_.begin();
      }
      iterator
      end() noexcept
      {
        return ht_.end();
      }
      const_iterator
      end() const noexcept
      {
        return ht_.end();
      }
  
      const_iterator
      cbegin() const noexcept
      {
        return ht_.cbegin();
      }
      const_iterator
      cend() const noexcept
      {
        return ht_.cend();
      }
  
      // 容量相关
  
      bool
      empty() const noexcept
      {
        return ht_.empty();
      }
      size_type
      size() const noexcept
      {
        return ht_.size();
      }
      size_type
      max_size() const noexcept
      {
        return ht_.max_size();
      }
  
      // 修改容器相关
  
      // emplace / emplace_hint
  
      template <class... Args>
      iterator
      emplace(Args &&...args)
      {
        return ht_.emplace_multi(mystl::forward<Args>(args)...);
      }
  
      template <class... Args>
      iterator
      emplace_hint(const_iterator hint, Args &&...args)
      {
        return ht_.emplace_multi_use_hint(hint, mystl::forward<Args>(args)...);
      }
  
      // insert
  
      iterator
      insert(const value_type &value)
      {
        return ht_.insert_multi(value);
      }
      iterator
      insert(value_type &&value)
      {
        return ht_.emplace_multi(mystl::move(value));
      }
  
      iterator
      insert(const_iterator hint, const value_type &value)
      {
        return ht_.insert_multi_use_hint(hint, value);
      }
      iterator
      insert(const_iterator hint, value_type &&value)
      {
        return ht_.emplace_multi_use_hint(hint, mystl::move(value));
      }
  
      template <class InputIterator>
      void
      insert(InputIterator first, InputIterator last)
      {
        ht_.insert_multi(first, last);
      }
  
      // erase / clear
  
      void
      erase(iterator it)
      {
        ht_.erase(it);
      }
      void
      erase(iterator first, iterator last)
      {
        ht_.erase(first, last);
      }
  
      size_type
      erase(const key_type &key)
      {
        return ht_.erase_multi(key);
      }
  
      void
      clear()
      {
        ht_.clear();
      }
  
      void
      swap(unordered_multiset &other) noexcept
      {
        ht_.swap(other.ht_);
      }
  
      // 查找相关
  
      size_type
      count(const key_type &key) const
      {
        return ht_.count(key);
      }
  
      iterator
      find(const key_type &key)
      {
        return ht_.find(key);
      }
      const_iterator
      find(const key_type &key) const
      {
        return ht_.find(key);
      }
  
      pair<iterator, iterator>
      equal_range(const key_type &key)
      {
        return ht_.equal_range_multi(key);
      }
      pair<const_iterator, const_iterator>
      equal_range(const key_type &key) const
      {
        return ht_.equal_range_multi(key);
      }
  
      // bucket interface
  
      local_iterator
      begin(size_type n) noexcept
      {
        return ht_.begin(n);
      }
      const_local_iterator
      begin(size_type n) const noexcept
      {
        return ht_.begin(n);
      }
      const_local_iterator
      cbegin(size_type n) const noexcept
      {
        return ht_.cbegin(n);
      }
  
      local_iterator
      end(size_type n) noexcept
      {
        return ht_.end(n);
      }
      const_local_iterator
      end(size_type n) const noexcept
      {
        return ht_.end(n);
      }
      const_local_iterator
      cend(size_type n) const noexcept
      {
        return ht_.cend(n);
      }
  
      size_type
      bucket_count() const noexcept
      {
        return ht_.bucket_count();
      }
      size_type
      max_bucket_count() const noexcept
      {
        return ht_.max_bucket_count();
      }
  
      size_type
      bucket_size(size_type n) const noexcept
      {
        return ht_.bucket_size(n);
      }
      size_type
      bucket(const key_type &key) const
      {
        return ht_.bucket(key);
      }
  
      // hash policy
  
      float
      load_factor() const noexcept
      {
        return ht_.load_factor();
      }
  
      float
      max_load_factor() const noexcept
      {
        return ht_.max_load_factor();
      }
      void
      max_load_factor(float ml)
      {
        ht_.max_load_factor(ml);
      }
  
      void
      rehash(size_type count)
      {
        ht_.rehash(count);
      }
      void
      reserve(size_type count)
      {
        ht_.reserve(count);
      }
  
      hasher
      hash_fcn() const
      {
        return ht_.hash_fcn();
      }
      key_equal
      key_eq() const
      {
        return ht_.key_eq();
      }
  
    public:
      friend bool
      operator==(const unordered_multiset &lhs, const unordered_multiset &rhs)
      {
        return lhs.ht_.equal_range_multi(rhs.ht_);
      }
      friend bool
      operator!=(const unordered_multiset &lhs, const unordered_multiset &rhs)
      {
        return !lhs.ht_.equal_range_multi(rhs.ht_);
      }
    };
  
    // 重载比较操作符
    template <class Key, class Hash, class KeyEqual, class Alloc>
    bool
    operator==(const unordered_multiset<Key, Hash, KeyEqual> &lhs,
               const unordered_multiset<Key, Hash, KeyEqual> &rhs)
    {
      return lhs == rhs;
    }
  
    template <class Key, class Hash, class KeyEqual, class Alloc>
    bool
    operator!=(const unordered_multiset<Key, Hash, KeyEqual> &lhs,
               const unordered_multiset<Key, Hash, KeyEqual> &rhs)
    {
      return lhs != rhs;
    }
  
    // 重载 mystl 的 swap
    template <class Key, class Hash, class KeyEqual, class Alloc>
    void
    swap(unordered_multiset<Key, Hash, KeyEqual> &lhs,
         unordered_multiset<Key, Hash, KeyEqual> &rhs)
    {
      lhs.swap(rhs);
    }
  
  } // namespace mystl
  #endif // !DEALII_UNORDERED_SET_H_
  