2

我正在实现一个像这样的开放地址哈希表：

template <typename  K, typename V> 
class open_addressing_map
{
public:
    using key_type = K;
    using mapped_type = V;
    using value_type = std::pair<const key_type, mapped_type>;
    using hasher = std::hash<K>;
    using hash_code = std::size_t;
    using allocator_type = std::allocator<value_type>;

    value_type* buckets; //array of value, allocate at constructor
    std::size_t capacity; //capacity buckets
    hasher hash_func;
    allocator_type allocator;

private:
    std::pair<std::size_t, bool> find_internal(hash_code hash, const key_type& key);
    std::size_t find_free_bucket(hash_code hash);

public:
    template<typename ...Args>
    std::pair<iterator, bool> emplace(Args&& ...args) {
        //I need to construct a key_type in stack here to pass into find() and find_free_bucket
        //I don't want to construct a value_type because it can be expensive.
        key_type key = ...?; //how can I do this

        hash_code hash;
        hash = hash_func(key); 

        auto res = find(hash, key);
        //if not found
        if (!res.second) {
            std::size_t free_idx = find_free_bucket(hash);
            if (hash == capacity)
                return {iterator(capacity), false};
            else {
                //need to rehash then insert a gain.
            }
            //construct value
            allocator.construct(std::forward<Args&&>(args)...);
        }
    }

};

问题是我使用了在构造函数中预先分配的容量来减少分配开销。在emplace函数中，我需要找到正确的位置来构造值，但需要key才能得到这个位置。

我可以在value_type这里构造一个来获得，key但后来，我必须将它移动到buckets数组中的正确位置。

这个想法是只构建key堆栈，但我不知道该怎么做？

4

0 回答 0