代码之家 › 专栏 › 技术社区 › bradgonesurfing

如何避免在std::unordered_映射上进行双重搜索,以及在实现缓存时避免在不需要时调用工厂函数

unordered-map c++17 c++

bradgonesurfing · 技术社区 · 4 年前

我一直在基于std::unordered_map实现一个缓存。如果值已经存储,我希望避免调用生成该值的工厂函数,但我也希望避免在地图上运行两次搜索。

#include <unordered_map>

struct Value {
    int x;
    Value & operator=(Value const &) = delete;
};

using Cache = std::unordered_map<int, Value>;

Value make_value(int i){
    // Imagine that this takes a time ok!
    i = i + 1;
    return Value{i};
}

// This has double search
template <typename F>
Value & insert_a(Cache & cache, int key, F factory)
{
    auto i = cache.find(key);
    if(i==cache.end()){
        auto r = cache.try_emplace(key,factory(key));
        return r.first->second;
    }
    return i->second;
}

// This runs the factory even if it is not required
template <typename F>
Value & insert_b(Cache & cache, int key, F factory)
{
    auto r = cache.try_emplace(key,factory(key));
    return r.first->second;
}

int main(){
    std::unordered_map<int,Value> map;

    insert_a(map,10,make_value);

    insert_b(map,10,make_value);

    return 0;

}

我有两个简化的插入演示如何构建缓存。

这个 插入_a 使用find first来检测项目是否存在,并且仅当它没有调用工厂来获取值时。在容器上执行两次搜索。

这个插入电话 试一试 只返回存储的值。这显然很糟糕,因为即使值已经存在,也会调用工厂。

似乎我想要一个中间地带,在那里我直接传递工厂函数来尝试部署,并且只有在需要时才在内部调用它。有没有办法来模拟这种情况?

这不是一个关于如何构建缓存的一般问题。我知道多线程问题、常量正确性和可变关键字。我特别想问的是如何做到这两个

对容器进行一次搜索
仅在需要时致电工厂

请注意,我故意删除了复制分配运算符,以便价值班一个显而易见的答案是先插入一个默认值,然后覆盖它。并不是所有的类都是可复制分配的,我想支持这些。

有一个沙箱可以玩 https://godbolt.org/z/Gja3MaGWf

1 回复 | 直到 4 年前

463035818_is_not_an_ai 4 年前

你可以使用懒惰的工厂。也就是说,只有在需要时才给实际工厂打电话:

#include <unordered_map>
#include <iostream>
struct Value {
    int x;
    Value & operator=(Value const &) = delete;
};

using Cache = std::unordered_map<int, Value>;

Value make_value(int i){
    // Imagine that this takes a time ok!
    i = i + 1;
    return Value{i};
}

template <typename F>
Value & insert_b(Cache & cache, int key)
{
    auto r = cache.try_emplace(key,F{key});
    return r.first->second;
}

// call the factory when needed    
struct ValueMaker {
    int value;
    operator Value() {
        std::cout << "called\n";
        return make_value(value);
    }
};

int main(){
    std::unordered_map<int,Value> map;
    insert_b<ValueMaker>(map,10);
    insert_b<ValueMaker>(map,10);
    return 0;

}

输出为

called

因为 ValueMaker::operator Value 仅在将元素插入贴图时调用一次。在第二个调用中,值生成器(只是一个细长的包装器)不会转换为 Value 因为 key 已经在地图上了。

我试着尽可能少地修改你的代码。对于您的实际代码,您可能希望去掉这两个工厂( make_value 和 ValueMaker )只使用一个。关键的一点是把一些薄薄的包装纸递给他们 try_emplace 这只会在转换为时触发实际值的构造 价值 .