[multi_index] problem with hashed index

newer
[Date_Time] undefined reference to...

Boris

21 Mar 2007 21 Mar '07

7:05 p.m.

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 > >

...

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?!

Show replies by date

"JOAQUIN LOPEZ MU?Z"

21 Mar 21 Mar

7:32 p.m.

Hi Boris, ----- Mensaje original ----- De: Boris 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 > >

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 > Good luck, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Boris

7:39 p.m.

On Wed, 21 Mar 2007 21:32:38 +0200, JOAQUIN LOPEZ MU?Z 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 > >

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 >

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

"JOAQUIN LOPEZ MU?Z"

7:40 p.m.

----- Mensaje original ----- De: "JOAQUIN LOPEZ MU?Z" 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 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 > >

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 >

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, which compares pointers, not foo objects. Hence the problem. Rather than overloading std::equal_to, which breaks the natural equality semantics of shared_ptr, my advice is that you change the key of the hashed index to: indexed_by > 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

Boris

11:43 p.m.

On Wed, 21 Mar 2007 21:40:54 +0200, JOAQUIN LOPEZ MU?Z 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,

which compares pointers, not foo objects. Hence the problem. Rather than overloading std::equal_to, which breaks the natural equality semantics of shared_ptr, my advice is that you change the key of the hashed index to:

indexed_by >

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

6463

Age (days ago)

6463

Last active (days ago)

List overview

Download

4 comments

2 participants

participants (2)

"JOAQUIN LOPEZ MU?Z"
Boris