Modify

Ticket #2841 (assigned Feature Requests)

Opened 5 years ago

Last modified 8 weeks ago

boost::hash to support boost::dynamic_bitset

Reported by: astukalov@… Owned by: acharles
Milestone: Boost 1.56.0 Component: dynamic_bitset
Version: Boost 1.38.0 Severity: Optimization
Keywords: Cc: daniel_james@…

Description

IIUC, there's no out-of-box support for hashing of dynamic_bitset.

Could something as simple as

    template <typename B, typename A>
    friend std::size_t hash_value(const dynamic_bitset<B, A>& v) {
        return hash_value( v.m_bits );
    }

be added to boost::dynamic_bitset class?

Attachments

Change History

comment:1 follow-up: ↓ 2 Changed 5 years ago by danieljames

  • Cc daniel_james@… added
  • Owner changed from danieljames to gennaro_prota
  • Component changed from hash to dynamic_bitset

I don't know anything about dynamic_bitset, but I suspect the hash function will also need to include the length of the bitset so that '1', '10' and '01' all have different hash values.

Anyway, this needs to be implemented as part of dynamic_bitset so I'm passing it to it's maintainer. But I'm adding myself as a CC, so he can ask for assistance if needed.

comment:2 in reply to: ↑ 1 Changed 5 years ago by anonymous

Replying to danieljames:

I don't know anything about dynamic_bitset, but I suspect the hash function will also need to include the length of the bitset so that '1', '10' and '01' all have different hash values.

Well, yes, adding length may improve hashing quality. On the other hand, the length of m_bits array directly correlates with the length of bitset, so it's (kind of) already included.

comment:3 follow-up: ↓ 4 Changed 5 years ago by danieljames

'0', '00', '000' and '0000' should have different hash values, but unless I've misunderstood dynamic_bitset m_bits will be the same for all of them.

comment:4 in reply to: ↑ 3 Changed 5 years ago by astukalov@…

Replying to danieljames:

'0', '00', '000' and '0000' should have different hash values, but unless I've misunderstood dynamic_bitset m_bits will be the same for all of them.

I think so too. It should be true for all zero bitsets with lengths <= bits per bitset block. For bigger lengths - two and more values would be hash_combined, resulting in different hash key.

Anyway, not including bitset length into hashing directly would have so small performance improvement, that I withdraw my previous comment. :)

comment:5 Changed 5 years ago by cheapest Cialis next day delivery

"Cogito ergo I'm right and you're wrong."

-- Blair Houghton

 viagra prezzo online  purchase fioricet  buy order cialis online BgnAuHX  tramadol buy cheap

comment:6 Changed 8 months ago by jim@…

It would also be great if dynamic_bitset supported std::hash, which exists beginning with C++11.

comment:7 Changed 8 weeks ago by acharles

  • Owner changed from gennaro_prota to acharles
  • Status changed from new to assigned

comment:8 Changed 8 weeks ago by acharles

  • Milestone changed from Boost 1.39.0 to Boost 1.56.0
View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as assigned
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.