如何减少C++ map/unordered_map容器中的查找分配？

假设我在我的代码中使用了std::unordered_map<std::string, Foo>。这很好，很方便，但不幸的是，每次我想在这张地图上进行查找（find()）时，我都得出一个std::string的实例。如何减少C++ map/unordered_map容器中的查找分配？

例如，假设我正在标记其他字符串并且想要在每个标记上调用find()。这迫使我在查看每个标记前围绕std::string构建一个std::string，这需要一个分配器（std::allocator，相当于CRT malloc()）。这很容易比实际的查找本身慢。它也与其他线程竞争，因为堆管理需要某种形式的同步。

几年前我找到了Boost.intrusive库;当时它只是一个测试版。有趣的是它有一个名为boost::intrusive::iunordered_set的容器，它允许代码使用任何用户提供的类型执行查找。

我会解释它，我想它是如何工作的：

struct immutable_string 
{ 
    const char *pf, *pl; 
    struct equals 
    { 
     bool operator()(const string& left, immutable_string& right) const 
     { 
      if (left.length() != right.pl - right.pf) 
       return false; 

      return std::equals(right.pf, right.pl, left.begin()); 
     } 
    }; 

    struct hasher 
    { 
     size_t operator()(const immutable_string& s) const 
     { 
      return boost::hash_range(s.pf, s.pl); 
     } 
    }; 

}; 

struct string_hasher 
{ 
    size_t operator()(const std::string& s) const 
    { 
     return boost::hash_range(s.begin(), s.end()); 
    } 
}; 

std::unordered_map<std::string, Foo, string_hasher> m; 
m["abc"] = Foo(123); 

immutable_string token; // token refers to a substring inside some other string 

auto it = m.find(token, immutable_string::equals(), immutable_string::hasher());

另一件事是加快“查找和插入，如果没有找到”用例的伎俩与lower_bound()只有作品对于有序的容器。侵入式容器具有称为insert_check()和insert_commit()的方法，但这是针对我猜测的单独主题。

来源

2013-02-23 yonil

使用更好的库实现？有可能实现'std :: string'，使得小字符串不会使用任何动态内存分配... – 2013-02-23 13:48:31

如果'std :: string'太昂贵，请将自己的对象包装在令牌中并避免堆分配。侵入式与非侵入式容器是一个正交的问题。 – 2013-02-23 13:52:29

这是一个过早的悲观。许多'std :: string'实现通过将字符串直接存储到自身中来避免分配小字符串。看到[这个答案]（http://stackoverflow.com/a/11639305/597607）的例子，根本没有任何分配构造和复制一个字符串。 – 2013-02-23 14:21:42

当谈到乐星，我个人使用两个简单的技巧：

我用StringRef（类似于LLVM的），它只是包装一个char const*和size_t，并提供串类的操作（只有常量的操作，显然）
我集中使用了凸点分配器（使用的肿块遇到弦说4K）

两个组合是非常有效的，但一个需要了解所有StringRef当池被销毁时，进入池的点显然无效。

来源

2013-02-23 14:51:14

从Boost 1.53开始，你可以使用'#include ' – 2013-02-23 15:36:36

@MarshallClow：很高兴知道！ – 2013-02-23 15:39:26

非常好，谢谢。我目前的工作无法升级到Boost 1.53。无论如何，我正在使用'unordered_map '。从本质上讲，它是唯一不需要修改容器接口的现实选择。我的'immutable_string'真的和'StringRef'完全一样。 – yonil 2013-02-23 17:17:33

原来boost::unordered_map（截至1.42）具有find重载需要CompatibleKey，CompatibleHash，CompatiblePredicate类型，所以它可以做什么我问这里。

来源

2013-03-11 11:02:00 yonil

如何减少C++ map/unordered_map容器中的查找分配？

回答

相关问题