1

From the boost documentation:

 It also implements the extension proposed by Peter Dimov in issue 6.18 of the Library Extension Technical Report Issues List (page 63), this adds support for:
...
**the standard containers**
...

However, when looking at the implementation (boost version 1.71) in extension.hpp I can see that there is a specialization only for array, vector, list, deque, set, multiset, map, multimap. The other containers forward_list, unordered_set, unordered_multiset, unordered_map and unordered_multimap are missing, as well as the container adaptors stack, queue and priority_queue. While the latter seem more or less plausible (as the container behind is another one, just the interface changed), I'm at least wondering about the other containers. Are simply not yet integrated, did they get forgotten, is it because the draft does not name them as well (why?) or is there some special reason behind?

Notes:
I'm aware of this question on SO
Why doesn't boost::hash_value support boost::unordered_set by default?
but I think this question is mainly asking about a set inside a set and additionally the question is 6 year old (which may lead to a different answer today), that why I'm asking this question.

I'm also aware that building a hash over a complete container is neither constant access nor performant, We don't need to discuss this. Sometimes you have to change memory consumption against runtime (in this case by using boost::flyweight but this requires a hash). And if class has a container as a member, well, you're there (if you're not allowed to change the class itself).

Don Pedro
  • 335
  • 3
  • 7

1 Answers1

1

Unordered containers will largely have irrelevant, non-repeatable hashes.

This is because hash(a,b,c) is not the same as hash(b,a,c) or hash(c, a, b) etc.

Since the ordering cannot be depended and only implicitly controlled, you will never know what it means to have "identical hash". The main rule of hashes for lookup is that equivalent values should hash to the same value, but since different sets {a,b,c} as an unordered container might hash to different values while being equivalent this would break the semantics.

Of course, you can make an ordered view of the set and then hash that, but it would appear to be prohibitively costly - a good reason to not provide it by default.

As to why forward_list is excluded, I'm not so sure. This looks like simple oversight.

sehe
  • 374,641
  • 47
  • 450
  • 633
  • This is a plausible answer, THX for it! – Don Pedro Sep 10 '20 at 08:23
  • If the "only" purpose is memory saving this might be not optimal (as two identical map might compare unequal nevertheless, leading to keeping the "same" unordered container in memory twice), but nertheless it should be usable for this special purpose, shouldn't it? I might just try and give the results as a comment on this question, the performance as well as the feasibility of this approach. – Don Pedro Sep 10 '20 at 08:30
  • An addition to the container adapters: - It is not (easily) feasible for them, as the public begin() and end() functions are missing. - There is a way to access the underlying type (see e. g. https://stackoverflow.com/questions/424104/can-i-access-private-members-from-outside-the-class-without-using-friends), but this of course is non-portable and not recommended because the implementation can change even when you stick to a specific compiler! – Don Pedro Sep 14 '20 at 09:37
  • @DonPedro yeah. Adaptors are not always general purpose containers. I didn't consider that part of your question - I saw your mention of it but considered it an adjacent example for context. Also, as you've found the answer is trivial. Note that some standard container adapters allow protected access to the the underlying container – sehe Sep 14 '20 at 09:41
  • A very simple way of getting a consistent hash value for an unordered container is to sum the hash values of its elements. I wonder why this approach has not been taken. – Joaquín M López Muñoz Nov 18 '20 at 08:43
  • @JoaquínMLópezMuñoz Consistency is only small part of the desired properties for a hash. This recipe runs into the basic flaws mentioned: You want `{A,B,C}` to hash differently than `{C,B,A}` and `{B,A,C}`. Proper hash combining is pretty sensitive and subject of modern specification (e.g. NIST's descriptions for Blake3 contains specifications for it IIRC). See also https://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/, many implementation+backgrounds [here](https://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-overriding-gethashcode) – sehe Nov 18 '20 at 15:38
  • @sehe thanks for the reference. Let me insist, in the case of unordered containers you do *not* want `{A,B,C}` to hash differently than `{C,B,A}`. – Joaquín M López Muñoz Nov 18 '20 at 17:20