1

我想为我的对象使用散列存储。这真的比 快std::map<std::string, Object>吗？我的意思是搜索。据我所知，boost 过程有很多优化。

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

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");
4

2 回答 2

2

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

至于哈希表与树：

例如，unordered_map 的 GCC 实现从不缩小其表，因此如果您添加大量元素，然后删除其中大部分，您将得到一些具有非常可怕的数据局部性的东西（因此缓存性能很差）。算法上的哈希表可能很吸引人，但在实际运行的系统中，它们的性能可能比树差，尤其是当元素的数量在数百个或更少时。

于 2011-04-10T14:35:44.117 回答
1

在任何情况下，除了最极端退化的情况外，精确匹配查找在 unordered_map (hash_map) 中使用散列键比 std::map 的底层红黑树更快。

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

于 2011-04-10T13:53:47.633 回答