4 ms·

C++11 only requires that "A Hash is a function object for which the output depends only on the input and has a very low probability of yielding the same output

by tlb 8y ago

C++11 only requires that "A Hash is a function object for which the output depends only on the input and has a very low probability of yielding the same output given different input values" and that "the probability of h(a)==h(b) for a!=b should approach 1.0/std::numeric_limits<std::size_t>::max()." This allows a pointer to be larger than size_t, which might be the case on some system with tagged pointers.

RcouF1uZ4gsC 8y ago
This is the case with hashing algorithms in general. The important part is "For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2)." This is what allows hash maps to work.
saagarjha 8y ago
Wait, so std::hash::operator() doesn't have to return a size_t, or are you just saying that pointers can have values "greater" than size_t and need to be "trimmed" down to size?
- gumby 8y ago
  std::hash::operator() is indeed required by the standard to return a size_t, but the standard puts few constraints on a size_t. It's certainly reasonable for an architecture with boxed numbers to make a size_t too small to hold a bona fide pointer. BTW the boxed environment could be a hardware platform (e.g. some of the Risc-V variants these days) or a software architecture -- imagine a C++ variant that generated code to run inside such an environment even if the hardware it's hosted on has a flat address space).
- asveikau 8y ago
  There are lots of places where size_t can't fit a full address. That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) By the way, intptr_t is relatively recent (C99).
  - saagarjha 8y ago
    > That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) I thought it was a stylistic choice: size_t for lengths and sizes, and intptr_t for, well, an integer holding a pointer value.
    - int_19h 8y ago
      size_t only has to be large enough to accommodate the size of the largest object possible in a given implementation. It has no relation to pointers at all. Similarly, ptrdiff_t only has to be large enough to accommodate the difference between two pointers where such difference is legal ("when two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object"). Hence the need for intptr_t and uintptr_t, and why they're optional unlike size_t and ptrdiff_t.
  - ajross 8y ago
    Sorry, what system are you thinking about where size_t is something other than pointer sized? This is silly pedantry
    - asveikau 8y ago
      It's not as unlikely as you think. Use your imagination. I seem to recall some late 90s Unix where size_t was 32 bits and pointers were 64 bits. I think it was Tru64? Seems to be backed up here: http://www.cecalc.ula.ve/documentacion/tutoriales/COMPAQC/DOCU0016.HTM http://www.cecalc.ula.ve/documentacion/tutoriales/COMPAQC/DO... In Compaq C, size_t is unsigned int . On 16 bit x86 it certainly is most natural to have size_t be 16 bits but full addressable memory is 1mb. Again, if there were no ambiguity here there would be no need to introduce a new typedef, but they did, in 1999.
      - ajross 8y ago
        I'll grant the Alpha point, which seems like a clear and unfortunate bug. But the DOS one is wrong. "Addressible" memory with segmentation may be 20 bits, but the maximum size of an object that can be referenced through any pointer is 65536 bytes. It was possible to compile in a "huge mode" where all pointers were expressed as base/offset, but in fact there the size_t was a compiler-generated 32 bit type.

by tlb 8y ago

RcouF1uZ4gsC 8y ago

This is the case with hashing algorithms in general. The important part is "For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2)." This is what allows hash maps to work.

saagarjha 8y ago

Wait, so std::hash::operator() doesn't have to return a size_t, or are you just saying that pointers can have values "greater" than size_t and need to be "trimmed" down to size?

gumby 8y ago
std::hash::operator() is indeed required by the standard to return a size_t, but the standard puts few constraints on a size_t. It's certainly reasonable for an architecture with boxed numbers to make a size_t too small to hold a bona fide pointer. BTW the boxed environment could be a hardware platform (e.g. some of the Risc-V variants these days) or a software architecture -- imagine a C++ variant that generated code to run inside such an environment even if the hardware it's hosted on has a flat address space).
asveikau 8y ago
There are lots of places where size_t can't fit a full address. That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) By the way, intptr_t is relatively recent (C99).
- saagarjha 8y ago
  > That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) I thought it was a stylistic choice: size_t for lengths and sizes, and intptr_t for, well, an integer holding a pointer value.
  - int_19h 8y ago
    size_t only has to be large enough to accommodate the size of the largest object possible in a given implementation. It has no relation to pointers at all. Similarly, ptrdiff_t only has to be large enough to accommodate the difference between two pointers where such difference is legal ("when two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object"). Hence the need for intptr_t and uintptr_t, and why they're optional unlike size_t and ptrdiff_t.
- ajross 8y ago
  Sorry, what system are you thinking about where size_t is something other than pointer sized? This is silly pedantry
  - asveikau 8y ago
    It's not as unlikely as you think. Use your imagination. I seem to recall some late 90s Unix where size_t was 32 bits and pointers were 64 bits. I think it was Tru64? Seems to be backed up here: http://www.cecalc.ula.ve/documentacion/tutoriales/COMPAQC/DOCU0016.HTM http://www.cecalc.ula.ve/documentacion/tutoriales/COMPAQC/DO... In Compaq C, size_t is unsigned int . On 16 bit x86 it certainly is most natural to have size_t be 16 bits but full addressable memory is 1mb. Again, if there were no ambiguity here there would be no need to introduce a new typedef, but they did, in 1999.
    - ajross 8y ago
      I'll grant the Alpha point, which seems like a clear and unfortunate bug. But the DOS one is wrong. "Addressible" memory with segmentation may be 20 bits, but the maximum size of an object that can be referenced through any pointer is 65536 bytes. It was possible to compile in a "huge mode" where all pointers were expressed as base/offset, but in fact there the size_t was a compiler-generated 32 bit type.