c++ - 散列和访问

Question

我想为我的对象使用散列存储。这真的比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");

Answer 1

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

至于哈希表与树:

例如 unordered_map 的 GCC 实现从不缩小它的表，所以如果你添加了很多元素，然后删除了其中的大部分，你会留下一些数据局部性非常糟糕的东西(因此性能很差 w.r.t. 缓存)。在算法上哈希表可能很有吸引力，但在实际运行的系统中，它们可能表现出比树更差的性能，尤其是当元素数量为数百或更少时。