[multi_index] problem with hashed index
I've been using Boost Multiindex quite a lot but don't understand why the code below inserts two items. The container has a unique hash index and the two items return the same hash value. Is this is a bug in the library or in my code? Boris -- struct foo { int i, j; foo(int i, int j) : i(i), j(j) { } }; std::size_t hash_value(const shared_ptr<foo> &f) { std::size_t seed = 0; boost::hash_combine(seed, f->i); boost::hash_combine(seed, f->j); return seed; } typedef multi_index_container< shared_ptr<foo>, indexed_by<hashed_unique<identity<shared_ptr<foo> > > >
mi_t;
shared_ptr<foo> f1(new foo(0, 0)); shared_ptr<foo> f2(new foo(0, 0)); mi_t mi; cout << mi.insert(f1).second << endl; // Returns 1. cout << mi.insert(f2).second << endl; // Returns again 1?! cout << mi.size() << endl; // Returns 2?!
Hi Boris, ----- Mensaje original ----- De: Boris <boriss@web.de> Fecha: Miércoles, Marzo 21, 2007 8:19 pm Asunto: [Boost-users] [multi_index] problem with hashed index Para: boost-users@lists.boost.org
I've been using Boost Multiindex quite a lot but don't understand why the code below inserts two items. The container has a unique hash index and the two items return the same hash value. Is this is a bug in the library or in my code? [...] indexed_by<hashed_unique<identity<shared_ptr<foo> > > >
Here's the problem: your key is shared_ptr<foo>, i.e., you compare *the pointers* rather than the pointed to foo objects. What you want is this instead: indexed_by<hashed_unique<identity<foo > > > Good luck, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Wed, 21 Mar 2007 21:32:38 +0200, JOAQUIN LOPEZ MU?Z <joaquin@tid.es> wrote: Hi Joaquín,
I've been using Boost Multiindex quite a lot but don't understand why the code below inserts two items. The container has a unique hash index and the two items return the same hash value. Is this is a bug in the library or in my code? [...] indexed_by<hashed_unique<identity<shared_ptr<foo> > > >
Here's the problem: your key is shared_ptr<foo>, i.e., you compare *the pointers* rather than the pointed to foo objects. What you want is this instead:
indexed_by<hashed_unique<identity<foo > > >
thanks for your fast answer! But the hash function is still hash_value(const shared_ptr<foo> &f) or hash_value(const foo &f)? Boris
----- Mensaje original ----- De: "JOAQUIN LOPEZ MU?Z" <joaquin@tid.es> Fecha: Miércoles, Marzo 21, 2007 8:33 pm Asunto: Re: [Boost-users] [multi_index] problem with hashed index Para: boost-users@lists.boost.org
Hi Boris,
----- Mensaje original ----- De: Boris <boriss@web.de> Fecha: Miércoles, Marzo 21, 2007 8:19 pm Asunto: [Boost-users] [multi_index] problem with hashed index Para: boost-users@lists.boost.org
I've been using Boost Multiindex quite a lot but don't understand why the code below inserts two items. The container has a unique hash index and the two items return the same hash value. Is this is a bug in the library or in my code? [...] indexed_by<hashed_unique<identity<shared_ptr<foo> > > >
Here's the problem: your key is shared_ptr<foo>, i.e., you compare *the pointers* rather than the pointed to foo objects. What you want is this instead:
indexed_by<hashed_unique<identity<foo > > >
Hi again, I answered too fast, the answer above is more or less correct but there's more to it: you have overloaded hash_value for shared_ptr<foo>s so as to use the pointed to foo objects: std::size_t hash_value(const shared_ptr<foo> &f) { std::size_t seed = 0; boost::hash_combine(seed, f->i); boost::hash_combine(seed, f->j); return seed; } So far so good; but the hashed index depends not only on the hash functor, but also on an equality predicate, which is by default (in this case) std::equal_to<shared_ptr<foo> >, which compares pointers, not foo objects. Hence the problem. Rather than overloading std::equal_to<shared_ptr<foo> >, which breaks the natural equality semantics of shared_ptr, my advice is that you change the key of the hashed index to: indexed_by<hashed_unique<identity<foo > > > as suggested in my previous post, and write the overload of hash_value for foo, not for shared_ptr<foo>: std::size_t hash_value(const foo &f) { std::size_t seed = 0; boost::hash_combine(seed, f.i); boost::hash_combine(seed, f.j); return seed; } Does this work? Please report back, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Wed, 21 Mar 2007 21:40:54 +0200, JOAQUIN LOPEZ MU?Z <joaquin@tid.es> wrote:
[...]Hi again, I answered too fast, the answer above is more or less correct but there's more to it: you have overloaded hash_value for shared_ptr<foo>s so as to use the pointed to foo objects:
std::size_t hash_value(const shared_ptr<foo> &f) { std::size_t seed = 0; boost::hash_combine(seed, f->i); boost::hash_combine(seed, f->j); return seed; }
So far so good; but the hashed index depends not only on the hash functor, but also on an equality predicate, which is by default (in this case)
std::equal_to<shared_ptr<foo> >,
which compares pointers, not foo objects. Hence the problem. Rather than overloading std::equal_to<shared_ptr<foo> >, which breaks the natural equality semantics of shared_ptr, my advice is that you change the key of the hashed index to:
indexed_by<hashed_unique<identity<foo > > >
as suggested in my previous post, and write the overload of hash_value for foo, not for shared_ptr<foo>:
std::size_t hash_value(const foo &f) { std::size_t seed = 0; boost::hash_combine(seed, f.i); boost::hash_combine(seed, f.j); return seed; }
Does this work? Please report back,
Thanks, it worked. I also had to define the comparison operator == for foo though. Boris
participants (2)
-
"JOAQUIN LOPEZ MU?Z"
-
Boris