避免在 map/unordered_map 中进行多次查找
Avoiding multiple lookups in map/unordered_map
假设我们有一个昂贵的函数映射 string
到 int
并且想要在映射中缓存结果。
最简单的代码是
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
if (cache.count(s) > 0) return cache[s];
else return cache[s] = myExpensiveFunction(s);
}
但这有 2 次查找。
所以我倾向于写这个
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
size_t sizeBefore = cache.size();
int& val = cache[s];
if (cache.size() > sizeBefore) val = myExpensiveFunction(s);
return val;
}
这只有一次查找,但看起来有点笨拙。有没有更好的方法?
只需使用std::map::emplace()
方法:
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
auto pair = cache.emplace( s, 0 );
if( pair.second )
pair.first->second = myExpensiveFunction(s);
return pair.first->second;
}
@Slava 的回答只是一个注释:如果你通过 const 左值引用传递参数,那么如果它是右值,你就不能从这个参数中移动:
int i = mapStringToIntWithCache("rvalue argument here");
临时 std::string
参数将在此处 复制 如果插入到 cache
。
您可以使用 完美转发 ,但是,如果您希望将参数保持为仅 std::string
类型(例如,对于从字符串文字的隐式转换),那么你需要一些 wrapper-helper 函数 解决方案:
template <typename T>
int mapStringToIntWithCacheHelper(T&& s) {
static std::unordered_map<std::string, int> cache;
auto pair = cache.emplace( std::forward<T>(s), 0 );
if( pair.second )
pair.first->second = myExpensiveFunction(pair.first->first); // can't use s here !!!
return pair.first->second;
}
int mapStringToIntWithCache(const std::string & s) {
mapStringToIntWithCacheHelper(s);
}
int mapStringToIntWithCache(std::string && s) {
mapStringToIntWithCacheHelper(std::move(s));
}
假设我们有一个昂贵的函数映射 string
到 int
并且想要在映射中缓存结果。
最简单的代码是
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
if (cache.count(s) > 0) return cache[s];
else return cache[s] = myExpensiveFunction(s);
}
但这有 2 次查找。
所以我倾向于写这个
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
size_t sizeBefore = cache.size();
int& val = cache[s];
if (cache.size() > sizeBefore) val = myExpensiveFunction(s);
return val;
}
这只有一次查找,但看起来有点笨拙。有没有更好的方法?
只需使用std::map::emplace()
方法:
int mapStringToIntWithCache(std::string const& s) {
static std::unordered_map<std::string, int> cache;
auto pair = cache.emplace( s, 0 );
if( pair.second )
pair.first->second = myExpensiveFunction(s);
return pair.first->second;
}
@Slava 的回答只是一个注释:如果你通过 const 左值引用传递参数,那么如果它是右值,你就不能从这个参数中移动:
int i = mapStringToIntWithCache("rvalue argument here");
临时 std::string
参数将在此处 复制 如果插入到 cache
。
您可以使用 完美转发 ,但是,如果您希望将参数保持为仅 std::string
类型(例如,对于从字符串文字的隐式转换),那么你需要一些 wrapper-helper 函数 解决方案:
template <typename T>
int mapStringToIntWithCacheHelper(T&& s) {
static std::unordered_map<std::string, int> cache;
auto pair = cache.emplace( std::forward<T>(s), 0 );
if( pair.second )
pair.first->second = myExpensiveFunction(pair.first->first); // can't use s here !!!
return pair.first->second;
}
int mapStringToIntWithCache(const std::string & s) {
mapStringToIntWithCacheHelper(s);
}
int mapStringToIntWithCache(std::string && s) {
mapStringToIntWithCacheHelper(std::move(s));
}