CODEWITHSUNDEEP
c++boosthashtablemulti-index
Max Frai
Max Frai

Reputation: 64266

Hashing and access

I want to use hashed storage for my objects. Is this really faster, than std::map<std::string, Object>? I mean searching. As I know, boost process a lot of optimizing.

And I'm not sure my code is right. Does it really use hashed keys when searching/inserting, etc?

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

Upvotes: 1

Views: 249

Answers (2)

John Zwinck
John Zwinck

Reputation: 249133

Why are you using Boost Multi-Index Container when you only have a single key? If you don't plan to add more keys soon, you should just use std::unordered_map, or std::map.

As for hash tables vs. trees:

The GCC implementation of unordered_map for example never shrinks its table, so if you add a lot of elements, then delete most of them, you are left with something that has pretty horrible data locality (and therefore poor performance w.r.t. caching). Algorithmically hash tables may be appealing, but in real, running systems they can exhibit worse performance than trees, especially when the number of elements is in the hundreds or less.

Upvotes: 2

Andy Finkenstadt
Andy Finkenstadt

Reputation: 3587

Exact-match finding is, under any but the most extremely degenerate circumstances, faster using a hashed key in an unordered_map (hash_map) than the underlying red-black tree of std::map.

And yes, your code should be right, assuming that there is a hash function that takes std::string and returns a hash of its contents.

Upvotes: 1

Related Questions