3 ms·
The thing is, it’s not actually effortless in many situations to switch from one map to the other. In C++, if you switch to an unordered map, you now have to co
by jb1991 4y ago
The thing is, it’s not actually effortless in many situations to switch from one map to the other. In C++, if you switch to an unordered map, you now have to contend with the annoying boilerplate of implementing a hash function for many key types. Using an ordered map may sometimes give you a slight hit in performance, but it offers significant benefits in developer convenience, and for small maps, the binary tree could actually be faster anyway.
- benreesman 4y agoIn fairness the tree still needs operator<() which sometimes less but not always easier to figure out than std::hash<>. I’d make a polite observation that in practice the GNU std::map is a red-black tree and that terminology mixup (which the author makes) might confuse folks.
- jb1991 4y agoIt’s not unusual for the operator to be automatically available while the hashing function is not, however.
- benreesman 4y agoYeah that’s fair and not a bad point.
- MauranKilom 4y agoAlso, for some reason the C++ standard library does not provide a simple hash_combine or similar that would allow composing hashes of sub-objects of your custom type in a straightforward manner.
- sicp-enjoyer 4y agoCan many hashes be combined quickly in a uniform way? This is another benefit of `<`, it composes.
- masklinn 4y ago> Can many hashes be combined quickly in a uniform way? The XOR operator?
- sicp-enjoyer 4y agoIf you do that 10 times for all members of your struct, do you get good uniformly distributed keys? This post doesn't think so: https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes https://stackoverflow.com/questions/5889238/why-is-xor-the-d...
- int_19h 4y agoXOR is a bad way to do it, but there are ones that work much better that are described in answers to that post, and it's what other languages use in similar situations (e.g. tuples in Python and C#): https://github.com/python/cpython/blob/71db5dbcd714b2e1297c43538188dd69715feb9a/Objects/tupleobject.c#L318-L342 https://github.com/python/cpython/blob/71db5dbcd714b2e1297c4...
- sicp-enjoyer 4y agoYes, and eventually you start computing another hash of the buffer of the concatenated members. I'm not saying it can't be done, I'm just comparing it with recursive memberwise comparison.
- gpderetta 4y agoAll pairs of {x,y} with x==y or hash(x)==hash(y) would hash to the same value (0). That's seems suboptimal.
- 112233 4y agoJust wait until you accidentaly hash your key struct invisible padding between data members (that are not there on you arch, because different alignment), and get irreproducible heisenbugs.