散列和访问

我想为我的对象使用散列存储。这真的比std::map<std::string, Object>更快吗？我的意思是搜索。据我所知，助推过程进行了很多优化。散列和访问

而且我不确定我的代码是否正确。搜索/插入时是否真的使用散列键？

using boost::multi_index_container; 
using namespace boost::multi_index; 

struct Object 
{ 
    std::string name; 

    Object(std::string name_): name(name_) {} 
}; 

typedef multi_index_container< 
    Object, 
    indexed_by< 
    hashed_unique< 
     BOOST_MULTI_INDEX_MEMBER(Object, std::string, name) 
    > 
    > 
> ObjectSet; 

ObjectSet objects; 
objects.insert(Object("test1")); 
objects.insert(Object("test2")); 
objects.insert(Object("test3")); 

// And testing: 
objects.find("test2");

来源

2011-04-10 Ockonal

为什么当你只有一个键时使用Boost Multi-Index Container？如果您不打算快速添加更多密钥，则应使用std::unordered_map或std::map。

至于哈希表与树：

unordered_map的GCC实现例如永远不会收缩其表，因此，如果您添加了很多元素，然后删除其中大部分，你留下的东西，有非常可怕的数据位置（因此性能较差）。在算法上哈希表可能很有吸引力，但在实际运行的系统中，它们可能表现出比树更糟的性能，尤其是当元素数量在数百个或更少时。

来源

2011-04-10 14:35:44

钥匙数量：这只是一个例子。实际情况下有3个键。地图中的对象数量：接近500-1000。 – Ockonal 2011-04-10 14:39:33

然后我会使用多索引容器，但使用普通地图（树）而不是散列。 – 2011-04-10 15:00:11

感谢您的提示。 – Ockonal 2011-04-10 15:03:57

精确匹配的发现是，在任何但最极其简并的情况下，更快使用比标准::地图底层红黑树在unordered_map（的hash_map）散列密钥。

是的，你的代码应该是正确的，假设有一个散列函数需要std :: string并返回其内容的散列。

来源

2011-04-10 13:53:47

回答

相关问题