从零开始的 STL 实现记录：Container-9

前言

前面用四节的内容分析了 STL-hashtable，本节将会分析基于 hashtable 的四种容器：unordered_set、unordered_map、unordered_multiset、unordered_multimap。这四种容器并未在 STL 的标准规格内，是 SGI-STL 额外提供的。

这四种容器以 hashtable 为底层机制，使用方法与 set、map 等完全相同。不同之处在于，使用红黑树实现的容器都会自动排序而使用 hashtable 的容器不会自动排序。

这四种容器所做的事情也几乎都只是转调用了 hashtable 的接口而已，没有什么复杂的地方。

unordered_set

/// @brief  模板类 unordered_set，键值不允许重复
/// @tparam Key  键值类型
/// @tparam Hash  哈希函数对象类型
/// @tparam KeyEqual  判断键值相等的函数对象类型，缺省使用 equal_to
template <class Key, class Hash = tinystl::hash<Key>, class KeyEqual = tinystl::equal_to<Key>>
class unordered_set {

private:  // 以 tinystl::hashtable 作为底层机制
    typedef tinystl::hashtable<Key, Hash, KeyEqual> base_type;
    base_type ht_;

public:   // 使用 hashtable 的型别定义


public:  // 构造、复制、移动、析构函数
    // 缺省使用 100 个桶，会被 hashtable 自动调整为最接近且较大的质数
    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_(tinystl::max(bucket_count, static_cast<size_type>(tinystl::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_(tinystl::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_(tinystl::move(rhs.ht_)) {}

    unordered_set& operator=(const unordered_set& rhs) {
        ht_ = rhs.ht_;
        return *this;
    }

    unordered_set& operator=(unordered_set&& rhs) noexcept {
        ht_ = tinystl::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;

public:  // 迭代器相关操作
    iterator        begin()         noexcept { return ht_.begin(); }
    const_iterator  begin()  const  noexcept { return ht_.begin(); }
    const_iterator  cbegin() const  noexcept { return ht_.cbegin(); }

    iterator        end()           noexcept { return ht_.end(); }
    const_iterator  end()    const  noexcept { return ht_.end(); }
    const_iterator  cend()   const  noexcept { return ht_.cend(); }

public:  // 容量相关
    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(); }

public:  // 修改容器相关
    // 插入操作全部使用 unique 操作，键值不允许重复
    template <class... Args>
    tinystl::pair<iterator, bool> emplace(Args&&... args) {
        return ht_.emplace_unique(tinystl::forward<Args>(args)...);
    }

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&&... args) {
        return ht_.emplace_unique_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    tinystl::pair<iterator, bool> insert(const value_type& value) {
        return ht_.insert_unique(value);
    }

    tinystl::pair<iterator, bool> insert(value_type&& value) {
        return ht_.insert_unique(tinystl::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_.insert_unique_use_hint(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        ht_.insert_unique(first, last);
    }

    void erase(iterator pos) {
        ht_.erase(pos);
    }
    
    void erase(iterator first, iterator last) {
        ht_.erase(first, last);
    }

    size_type erase(const key_type& key) {
        return ht_.erase_unique(key);
    }

    void clear() noexcept {
        ht_.clear();
    }

    void swap(unordered_set& rhs) noexcept {
        ht_.swap(rhs.ht_);
    }

public:  // 查找相关
    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);
    }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return ht_.equal_range_unique(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return ht_.equal_range_unique(key);
    }

public:  // 桶相关操作
    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); }

public:  // 哈希函数相关
    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) noexcept { ht_.max_load_factor(ml); }
    void      rehash(size_type count)            { ht_.rehash(count); }
    void      reserve(size_type count)            { ht_.reserve(count); }
    hasher    hash_function()   const            { return ht_.hash_function(); }
    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>
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>
bool operator!=(const unordered_set<Key, Hash, KeyEqual>& lhs,
                const unordered_set<Key, Hash, KeyEqual>& rhs) {
    return !(lhs == rhs);
}

// ====================== 重载 swap ====================== //

template <class Key, class Hash, class KeyEqual>
void swap(unordered_set<Key, Hash, KeyEqual>& lhs,
          unordered_set<Key, Hash, KeyEqual>& rhs) noexcept {
    lhs.swap(rhs);
}

unordered_set 的大部分操作都只是简单地调用 hashtable 的接口，需要注意的是所有的插入操作使用的都是 insert_unqiue 以满足键值不允许重复的要求。

同时，由于 TinySTL 中的 hashtable 没有提供 Extract_Key 参数，而是在类的内部自行制定了提取普通元素与 pair 元素的 key 的方式，因此无法处理像 array 或 C风格字符串这样的数据，因为这些数据都是一个指针指向一片区域，必须逐位地进行比较（如使用 strcmp 等）。

如果是 STL 的哈希表，可以自定义一个仿函数，如下面这个例子就通过自定义一个 Extract_Key 仿函数的形式，定义了一个可以存储 C 风格字符串为键值的哈希表。

struct eqstr
{
    bool operator() (const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) == 0;
    }
}

unordered_set<const char*, hash<const char*>, eqstr> Set;

unordered_multiset

unordered_multiset 与 unordered_set 实现上唯一的区别就是前者使用 hashtable 的 insert_multi 插入元素，后者使用 insert_unique，下面只列出不同的部分。

/// @brief 模板类 unordered_multiset，键值允许重复
/// @tparam Key  键值类型
/// @tparam Hash  哈希函数对象类型
/// @tparam KeyEqual  判断键值相等的函数对象类型，缺省使用 equal_to
template <class Key, class Hash = tinystl::hash<Key>, class KeyEqual = tinystl::equal_to<Key>>
class unordered_multiset {

private:  // 以 tinystl::hashtable 作为底层机制
    typedef tinystl::hashtable<Key, Hash, KeyEqual> base_type;
    base_type ht_;

public:   // 使用 hashtable 的型别定义

public:   // 构造、复制、移动、析构函数

public:  // 迭代器相关

public:  // 修改容器相关
    template <class... Args>
    iterator emplace(Args&&... args) {
        return ht_.emplace_multi(tinystl::forward<Args>(args)...);
    }

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&&... args) {
        return ht_.emplace_multi_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    iterator insert(const value_type& value) {
        return ht_.insert_multi(value);
    }

    iterator insert(value_type&& value) {
        return ht_.insert_multi(tinystl::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_.insert_multi_use_hint(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        ht_.insert_multi(first, last);
    }


public:  // 查找相关
    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);
    }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return ht_.equal_range_multi(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return ht_.equal_range_multi(key);
    }

public:  // 桶相关操作

public:  // 哈希函数相关

};

unordered_map

与 map 类似，unordered_map 插入的也是 pair 类型的元素，由于这里的 hashtable 内已经实现了对于 pair 的键值提取，因此这里使用的底层 hashtable 与 unordered_set 中的没有任何区别，但 STL 中会指定 _ExtractKey = __detail::_Select1st 实现同样的效果。

由于不允许键值重复，因此插入元素使用的也都是 insert_unique。

/// @brief 模板类 unordered_map，键值不允许重复
/// @tparam Key  键值类型
/// @tparam T  数据类型
/// @tparam Hash  哈希函数对象类型
/// @tparam KeyEqual  判断键值相等的函数对象类型, 默认使用 tinystl::equal_to
template <class Key, class T, class Hash = tinystl::hash<Key>, class KeyEqual = tinystl::equal_to<Key>>
class unordered_map {

private:  // 使用 hashtable 作为底层机制
    typedef tinystl::hashtable<tinystl::pair<const Key, T>, 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::mapped_type          mapped_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::iterator             iterator;
    typedef typename base_type::const_iterator       const_iterator;
    typedef typename base_type::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_map() : ht_(100, hasher(), key_equal()) {}

    explicit unordered_map(size_type bucket_count, const hasher& hash = hasher(),
                           const key_equal& equal = key_equal())
        : ht_(bucket_count, hash, equal) {}

    template <class InputIterator>
    unordered_map(InputIterator first, InputIterator last,
                  const size_type bucket_count = 100, 
                  const hasher& hash = hasher(),
                  const key_equal& equal = key_equal())
        : ht_(tinystl::max(bucket_count, static_cast<size_type>(tinystl::distance(first, last))), hash, equal) {
        for (; first != last; ++first)
            ht_.insert_unique_noresize(*first);
    }

    unordered_map(std::initializer_list<value_type> ilist,
                  const size_type bucket_count = 100,
                  const hasher& hash = hasher(),
                  const key_equal& equal = key_equal())
        : ht_(tinystl::max(bucket_count, static_cast<size_type>(ilist.size())), hash, equal) {
        for (auto first = ilist.begin(); first != ilist.end(); ++first)
            ht_.insert_unique_noresize(*first);
    }

    unordered_map(const unordered_map& rhs) : ht_(rhs.ht_) {}

    unordered_map(unordered_map&& rhs) noexcept : ht_(tinystl::move(rhs.ht_)) {}

    unordered_map& operator=(const unordered_map& rhs) {
        ht_ = rhs.ht_;
        return *this;
    }

    unordered_map& operator=(unordered_map&& rhs) noexcept {
        ht_ = tinystl::move(rhs.ht_);
        return *this;
    }

    unordered_map& operator=(std::initializer_list<value_type> ilist) {
        ht_.clear();
        ht_.reserve(ilist.size());
        for (auto first = ilist.begin(); first != ilist.end(); ++first)
            ht_.insert_unique_noresize(*first);
        return *this;
    }

    ~unordered_map() = default;

public:  // 迭代器相关操作
    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(); }

public:  // 容量相关操作
    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(); }

public:  // 修改容器相关操作
    template <class... Args>
    tinystl::pair<iterator, bool> emplace(Args&&... args) {
        return ht_.emplace_unique(tinystl::forward<Args>(args)...);
    }

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&&... args) {
        return ht_.emplace_unique_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    tinystl::pair<iterator, bool> insert(const value_type& value) {
        return ht_.insert_unique(value);
    }

    tinystl::pair<iterator, bool> insert(value_type&& value) {
        return ht_.insert_unique(tinystl::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_.insert_unique_use_hint(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        ht_.insert_unique(first, last);
    }

    void erase(iterator position) { ht_.erase(position); }

    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_map& rhs) noexcept { ht_.swap(rhs.ht_); }

public:  // 查找相关
    mapped_type& at(const key_type key) {
        auto it = ht_.find(key);
        THROW_OUT_OF_RANGE_IF(it.node == nullptr, "unordered_map<Key, T> no such element exists");
        return it->second;
    }

    const mapped_type& at(const key_type key) const {
        auto it = ht_.find(key);
        THROW_OUT_OF_RANGE_IF(it.node == nullptr, "unordered_map<Key, T> no such element exists");
        return it->second;
    }

    mapped_type& operator[](const key_type& key) {
        iterator it = ht_.find(key);
        if (it.node == nullptr) {
            // 在 map 中插入一个 键为 key，值为 mapped_type() 的键值对
            // 这里的 mapped_type() 即为 T()，即调用 T 的默认构造函数
            it = ht_.emplace_unique(key, mapped_type()).first;
        }
        return it->second;
    }

    mapped_type& operator[](key_type&& key) {
        iterator it = ht_.find(key);
        if (it.node == nullptr) {
            it = ht_.emplace_unique(tinystl::move(key), mapped_type()).first;
        }
        return it->second;
    }

    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); }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return ht_.equal_range_unique(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return ht_.equal_range_unique(key);
    }

public:  // bucket 相关操作
    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); }

public:  // hash 相关
    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_function()         const           { return ht_.hash_function(); }
    key_equal   key_eq()                const           { return ht_.key_eq(); }

public:
    friend bool operator==(const unordered_map& lhs, const unordered_map& rhs) {
        return lhs.ht_.equal_range_unique(rhs.ht_);
    }

    friend bool operator!=(const unordered_map& lhs, const unordered_map& rhs) {
        return !lhs.ht_.equal_range_unique(rhs.ht_);
    }
};

// ============================== 重载比较操作符 ============================== //
template <class Key, class T, class Hash, class KeyEqual>
bool operator==(const unordered_map<Key, T, Hash, KeyEqual>& lhs,
                const unordered_map<Key, T, Hash, KeyEqual>& rhs) {
    return lhs != rhs;
}

template <class Key, class T, class Hash, class KeyEqual>
bool operator!=(const unordered_map<Key, T, Hash, KeyEqual>& lhs,
                const unordered_map<Key, T, Hash, KeyEqual>& rhs) {
    return lhs != rhs;
}

// =========================== 重载 swap =========================== //
template <class Key, class T, class Hash, class KeyEqual>
void swap(unordered_map<Key, T, Hash, KeyEqual>& lhs,
          unordered_map<Key, T, Hash, KeyEqual>& rhs) noexcept {
    lhs.swap(rhs);
}

unordered_multimap

unordered_multimap 与 unordered_map 实现上的区别也仅在于插入元素时使用的是 insert_multi，以下仅列出与 unordered_map 不相同的部分。

/// @brief 模板类 unordered_multimap，键值允许重复
/// @tparam Key  键值类型
/// @tparam T  数据类型
/// @tparam Hash  哈希函数对象类型
/// @tparam KeyEqual  判断键值相等的函数对象类型, 默认使用 tinystl::equal_to
template <class Key, class T, class Hash = tinystl::hash<Key>, class KeyEqual = tinystl::equal_to<Key>>
class unordered_multimap {

private:  // 使用 hashtable 作为底层机制
    typedef tinystl::hashtable<tinystl::pair<const Key, T>, Hash, KeyEqual> base_type;
    base_type ht_;

public:   // 使用 hashtable 的型别定义

public:  // 构造、复制、移动、析构函数

public:  // 迭代器相关操作

public:  // 容量相关

public:  // 修改容器相关
    template <class... Args>
    iterator emplace(Args&&... args) {
        return ht_.emplace_multi(tinystl::forward<Args>(args)...);
    }

    template <class... Args>
    iterator emplace_hint(const_iterator hint, Args&&... args) {
        return ht_.emplace_multi_use_hint(hint, tinystl::forward<Args>(args)...);
    }

    iterator insert(const value_type& value) {
        return ht_.insert_multi(value);
    }

    iterator insert(value_type&& value) {
        return ht_.insert_multi(tinystl::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_.insert_multi_use_hint(hint, tinystl::move(value));
    }

    template <class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        ht_.insert_multi(first, last);
    }

public:  // 查找相关
    iterator find(const key_type& key) { return ht_.find(key); }
    const_iterator find(const key_type& key) const { return ht_.find(key); }

    size_type count(const key_type& key) const { return ht_.count(key); }

    tinystl::pair<iterator, iterator> equal_range(const key_type& key) {
        return ht_.equal_range_multi(key);
    }

    tinystl::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return ht_.equal_range_multi(key);
    }

public:  // bucket 相关

public:  // hash 相关

};

总结

本节简要分析了基于 hashtable 实现的四种容器：unordered_set、unordered_map、unordered_multiset、unordered_multimap。到这里，关联式容器也就全部介绍完毕了。这也就意味着 STL 六大组件中的 “容器（container）” 也已经被我们实现完毕。

回顾一下迄今为止的历程，我们已经实现了 Allocator、Iterator、Container，剩下的就只有 Algorithm、Functor、Adaptor 部分的内容了，胜利就在前方！