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

前言

上一节介绍了 hashtable 的构造等功能的实现，本节将会介绍 hashtable 最重要的增删查改功能（与基于红黑树的 set 和 map 相同，hashtable 实现的 unordered_set 与 unordered_map 也不允许修改键值，仅允许修改 pair 类型元素的实值）。

增删元素

与 RB-tree 相同，由于需要同时支持 multiset 与 set 等容器，因此 hashtable 内部要提供两套不同的插入与删除元素的逻辑。

public:  // 修改容器相关操作
    template <class ...Args>
    iterator emplace_multi(Args&&... args);

    template <class ...Args>
    tinystl::pair<iterator, bool> emplace_unique(Args&&... args);


    iterator insert_multi_noresize(const value_type& value);
    pair<iterator, bool> insert_unique_noresize(const value_type& value);

    iterator insert_multi(const value_type& value) {
        rehash_if_need(1);
        return insert_multi_noresize(value);
    }

    iterator insert_multi(value_type&& value) {
        return emplace_multi(tinystl::move(value));
    }

    pair<iterator, bool> insert_unique(const value_type& value) {
        rehash_if_need(1);
        return insert_unique_noresize(value);
    }

    pair<iterator, bool> insert_unique(value_type&& value) {
        return emplace_unique(tinystl::move(value));
    }

    template <class InputIterator>
    void insert_multi(InputIterator first, InputIterator last) {
        copy_insert_multi(first, last, tinystl::iterator_category(first));
    }

    template <class InputIterator>
    void insert_unique(InputIterator first, InputIterator last) {
        copy_insert_unique(first, last, tinystl::iterator_category(first));
    }

    void erase(const_iterator pos);
    void erase(const_iterator first, const_iterator last);

    size_type erase_multi(const key_type& key);
    size_type erase_unique(const key_type& key);

emplace

/// @brief 就地构造元素，键值允许重复，强异常安全保证
template <class T, class Hash, class KeyEqual>
template <class ...Args>
typename hashtable<T, Hash, KeyEqual>::iterator
hashtable<T, Hash, KeyEqual>::emplace_multi(Args&&... args) {
    auto np = create_node(tinystl::forward<Args>(args)...);
    try {
        if (static_cast<float>(size_ + 1) > static_cast<float>(bucket_size_) * max_load_factor()) {
            rehash(size_ + 1);
        }
    }
    catch (...) {
        destroy_node(np); 
        throw;
    }
    return insert_node_multi(np);
}

/// @brief 就地构造元素，键值不允许重复，强异常安全保证
template <class T, class Hash, class KeyEqual>
template <class ...Args>
tinystl::pair<typename hashtable<T, Hash, KeyEqual>::iterator, bool>
hashtable<T, Hash, KeyEqual>::emplace_unique(Args&&... args) {
    auto np = create_node(tinystl::forward<Args>(args)...);
    try {
        if (static_cast<float>(size_ + 1) > static_cast<float>(bucket_size_) * max_load_factor()) {
            rehash(size_ + 1);
        }
    }
    catch (...) {
        destroy_node(np);
        throw;
    }
    return insert_node_unique(np);
}

emplace 会使用传入的参数原地构造一个 node，并判断当插入这个节点后需不需要重新哈希一次，rehash 会在下一小节进行说明，emplace 最终会调用 insert_node 将创建的节点插入哈希表，下面来看 insert_node 的实现。

/// @brief 在 hashtable 中插入一个节点，键值允许重复
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::iterator
hashtable<T, Hash, KeyEqual>::insert_node_multi(node_ptr node) {
    const auto n = hash(value_traits::get_key(node->value));
    auto cur = buckets_[n];
    if (cur == nullptr) {
        buckets_[n] = node;
        ++size_;
        return iterator(node, this);
    }
    for (; cur->next; cur = cur->next) {
        // 如果链表中存在相同键值的节点就马上插入，然后返回
        // 相同键值的节点放在一起，方便查找
        if (is_equal(value_traits::get_key(cur->value), value_traits::get_key(node->value))) {
            node->next = cur->next;
            cur->next = node;
            ++size_;
            return iterator(node, this);
        }
    }
    // 否则插入在链表头部
    node->next = buckets_[n];  // 将新节点插入到链表头部
    buckets_[n] = node;        // 更新 bucket[n] 的头部
    ++size_;
    return iterator(node, this);
}

insert_node_multi 会先计算元素键值的哈希值，作为存放 node 的 bucket 的索引。如果该 bucket 为空则直接放在头部位置，否则会遍历 bucket，若有键值相同的节点会放在一起，方便查找；否则会放在 bucket 头部。该函数会返回插入位置的迭代器。

/// @brief 在 hashtable 中插入一个节点，键值不允许重复
template <class T, class Hash, class KeyEqual>
pair<typename hashtable<T, Hash, KeyEqual>::iterator, bool>
hashtable<T, Hash, KeyEqual>::insert_node_unique(node_ptr node) {
    const auto n = hash(value_traits::get_key(node->value));
    auto cur = buckets_[n];
    if (cur == nullptr) {
        buckets_[n] = node;
        ++size_;
        return tinystl::make_pair(iterator(node, this), true);
    }
    for (; cur; cur = cur->next) {
        // 如果链表中存在相同键值的节点就马上返回
        // 相同键值的节点放在一起，方便查找
        if (is_equal(value_traits::get_key(cur->value), value_traits::get_key(node->value))) {
            return tinystl::make_pair(iterator(cur, this), false);
        }
    }
    // 否则插入在链表头部
    node->next = buckets_[n];  // 将新节点插入到链表头部
    buckets_[n] = node;        // 更新 bucket[n] 的头部
    ++size_;
    return tinystl::make_pair(iterator(node, this), true);
}

insert_node_unique 的流程也是先计算哈希值，再遍历对应的 bucket；不同之处在于不允许有重复节点，因此如果找到了相同值的节点就直接返回，否则也是插在 bucket 的头部。

该函数会返回一个 pair<iterator, bool>，其中第一个值是插入位置的迭代器，第二个值代表是否插入成功。

insert

insert 的逻辑与 emplace 类似，这里就不再赘述，实际上这里功能的分割是有些不合理的，但是无伤大雅。

/// @brief 在不需要重新分配桶的情况下插入新节点，键值允许重复
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::iterator
hashtable<T, Hash, KeyEqual>::insert_multi_noresize(const value_type& value) {
    const auto n = hash(value_traits::get_key(value));
    auto first = buckets_[n];
    auto tmp = create_node(value);
    for (auto cur = first; cur; cur = cur->next) {
        // 如果链表中存在相同键值的节点就马上插入，然后返回
        if (is_equal(value_traits::get_key(cur->value), value_traits::get_key(value))) {
            tmp->next = cur->next;
            cur->next = tmp;
            ++size_;
            return iterator(tmp, this);
        }
    }
    // 否则插入在链表头部
    tmp->next = first;  // 将新节点插入到链表头部
    buckets_[n] = tmp;  // 更新 bucket[n] 的头部
    ++size_;
    return iterator(tmp, this);
}

template <class T, class Hash, class KeyEqual>
tinystl::pair<typename hashtable<T, Hash, KeyEqual>::iterator, bool>
hashtable<T, Hash, KeyEqual>::insert_unique_noresize(const value_type& value) {
    const auto n = hash(value_traits::get_key(value));
    auto first = buckets_[n];
    for (auto cur = first; cur; cur = cur->next) {
        // 如果链表中存在相同键值的节点就马上返回
        if (is_equal(value_traits::get_key(cur->value), value_traits::get_key(value))) {
            return tinystl::make_pair(iterator(cur, this), false);
        }
    }
    // 否则插入在链表头部
    auto tmp = create_node(value);
    tmp->next = first;  // 将新节点插入到链表头部
    buckets_[n] = tmp;  // 更新 bucket[n] 的头部
    ++size_;
    return tinystl::make_pair(iterator(tmp, this), true);
}

erase

erase 函数负责删除某个迭代器位置处或某个迭代器区间内的元素，是 erase_unique 与 erase_multi 的基础。

/// @brief 删除迭代器所指向的节点
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::erase(const_iterator pos) {
    auto p = pos.node;
    if (p) {
        const auto n = hash(value_traits::get_key(p->value));  // 计算 bucket 的位置
        auto cur = buckets_[n];
        // p 位于链表的头部
        if (cur == p) {
            buckets_[n] = cur->next;
            destroy_node(cur);
            --size_;
        }
        // 否则在链表中查找 p
        else {
            auto next = cur->next;
            while (next) {
                if (next == p) {
                    cur->next = next->next;
                    destroy_node(next);
                    --size_;
                    break;
                }
                else {
                    cur = next;
                    next = cur->next;
                }
            }
        }
    }
}

该函数的逻辑也很好理解，先计算 pos 迭代器对应的 node 中元素的哈希值，确定 bucket 的位置后就进行遍历，删除节点。当节点位于 bucket 头部时需要特殊处理。

/// @brief 删除 [first, last) 内的节点
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::erase(const_iterator first, const_iterator last) {
    if (first.node == last.node) return;
    auto first_bucket = first.node
        ? hash(value_traits::get_key(first.node->value))
        : bucket_size_;
    auto last_bucket = last.node
        ? hash(value_traits::get_key(last.node->value))
        : bucket_size_;
    if (first_bucket == last_bucket) {
        erase_bucket(first_bucket, first.node, last.node);
    }
    else {
        erase_bucket(first_bucket, first.node, nullptr);
        for (size_type n = first_bucket + 1; n < last_bucket; ++n) {
            if (buckets_[n] != nullptr) erase_bucket(n, nullptr);
        }
        if (last_bucket != bucket_size_) {
            erase_bucket(last_bucket, last.node);
        }
    }
}

/// @brief 在第 n 个 bucket 内，删除 [first, last) 内的节点
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::erase_bucket(size_type n, node_ptr first, node_ptr last) {
    auto cur = buckets_[n];
    if (cur == first) {
        erase_bucket(n, last);
    }
    else {
        auto next = cur->next;
        for (; next != first; cur = next, next = cur->next) {}
        while (next != last) {
            cur->next = next->next;
            destroy_node(next);
            next = cur->next;
            --size_;
        }
    }
}

/// @brief 在第 n 个 bucket 内，删除 [buckets_[n], last) 内的节点
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::erase_bucket(size_type n, node_ptr last) {
    auto cur = buckets_[n];
    while (cur != last) {
        auto next = cur->next;
        destroy_node(cur);
        cur = next;
        --size_;
    }
    buckets_[n] = last;
}

区间删除的逻辑要复杂一些，因为要区分 first 与 last 在同一个 bucket 与不同 bucket 的情况，为此分别提供了两个不同的 erase_bucket 函数用于辅助。

不过博主始终没能理解 auto first_bucket = first.node ? hash(value_traits::get_key(first.node->value)): bucket_size_; 这句代码的作用…

/// @brief 删除键值为 key 的节点，返回删除的节点个数
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::erase_multi(const key_type& key) {
    auto p = equal_range_multi(key);
    if (p.first.node != nullptr) {
        erase(p.first, p.second);
        return tinystl::distance(p.first, p.second);
    }
    return 0;
}

template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::erase_unique(const key_type& key) {
    const auto n = hash(key);
    auto first = buckets_[n];
    if (first) {
        if (is_equal(value_traits::get_key(first->value), key)) {
            buckets_[n] = first->next;
            destroy_node(first);
            --size_;
            return 1;
        }
        else {
            auto next = first->next;
            while (next) {
                if (is_equal(value_traits::get_key(next->value), key)) {
                    first->next = next->next;
                    destroy_node(next);
                    --size_;
                    return 1;
                }
                first = next;
                next = first->next;
            }
        }
    }
    return 0;
}

erase_multi 内部调用 erase(first, last) 进行元素的删除，但是 erase_unique 却几乎重复了一遍 erase(pos)，因为要在不同的地方 return，逻辑略有不同。

查找元素

/// @brief 查找键值为 key 的节点，返回迭代器
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::iterator
hashtable<T, Hash, KeyEqual>::find(const key_type& key) {
    const auto n = hash(key);
    node_ptr first = buckets_[n];
    for (; first && !is_equal(value_traits::get_key(first->value), key); first = first->next) {}
    return iterator(first, this);
}

template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::count(const key_type& key) const {
    const auto n = hash(key);
    size_type result = 0;
    // 相同的值一定在同一个哈希桶里，所以只需要遍历 bucket[n] 即可
    for (node_ptr cur = buckets_[n]; cur; cur = cur->next) {
        if (is_equal(value_traits::get_key(cur->value), key)) ++result;
    }
    return result;
}

查找指定元素分为 find() 与 count() 两个函数，find() 用于查找是否有该元素，返回一个迭代器，如果没有的话，迭代器内的 node 将会是 nullptr；count()用于统计有多少个该元素，返回一个 size_type 类型的元素个数。

/// @brief 查找与键值 key 相等的区间，返回一个 pair，指向区间的首尾
template <class T, class Hash, class KeyEqual>
tinystl::pair<typename hashtable<T, Hash, KeyEqual>::iterator, 
    typename hashtable<T, Hash, KeyEqual>::iterator>
hashtable<T, Hash, KeyEqual>::equal_range_multi(const key_type& key) {
    const auto n = hash(key);
    for (node_ptr first = buckets_[n]; first; first = first->next) {
        if (is_equal(value_traits::get_key(first->value), key)) {
            for (node_ptr cur = first->next; cur; cur = cur->next) {
                // 相等的区间在当前的桶范围之内
                if (!is_equal(value_traits::get_key(cur->value), key)) {
                    return tinystl::make_pair(iterator(first, this), iterator(cur, this));
                }
            }
            // 当前桶直到最后一个元素都相等，返回的区间的尾部指向下一个不为空的桶
            for (size_type m = n + 1; m < bucket_size_; ++m) {
                if (buckets_[m]) {
                    return tinystl::make_pair(iterator(first, this), iterator(buckets_[m], this));
                }
            }
            return tinystl::make_pair(iterator(first, this), end());
        }
    }
    return tinystl::make_pair(end(), end());
}

/// @brief 查找与键值 key 相等的区间，返回一个 pair，指向区间的首尾
template <class T, class Hash, class KeyEqual>
tinystl::pair<typename hashtable<T, Hash, KeyEqual>::iterator, 
    typename hashtable<T, Hash, KeyEqual>::iterator>
hashtable<T, Hash, KeyEqual>::equal_range_unique(const key_type& key) {
    const auto n = hash(key);
    for (node_ptr first = buckets_[n]; first; first = first->next) {
        if (is_equal(value_traits::get_key(first->value), key)) {
            if (first->next) {
                return tinystl::make_pair(iterator(first, this), iterator(first->next, this));
            }
            for (auto m = n + 1; m < bucket_size_; ++m) {
                if (buckets_[m]) {
                    return tinystl::make_pair(iterator(first, this), iterator(buckets_[m], this));
                }
            }
            return tinystl::make_pair(iterator(first, this), end());
        }
    }
    return tinystl::make_pair(end(), end());
}

equal_range_multi 与 equal_range_unique 查找与键值与 key 相等的区间并返回，如果直到当前 bucket 的最后一个节点依然相等，区间的末尾将会返回下一个 bucket 的头部（如果有），或 end()，即一个空指针。

总结

本节简要分析了 hashtable 的增删查操作，关于哈希表的内容也差不多该结束了，下一节将会分析基于 hashtable 实现的 unordered_set 与 unordered_map 容器。