5 ms·

One thing interesting to note is that C++ has a specialization for template<class T> struct hash<T> which is required to have the correct semantics. Given th

One thing interesting to note is that C++ has a specialization for template<class T> struct hash<T> which is required to have the correct semantics. Given that the in practice the underlying machine models of C and C++ are very similar, and that the most widely used C compilers (gcc, clang, msvc) are also C++ compilers, in practice hashing C pointers is likely not an issue. However, if you want to hash pointers in a way that is blessed by the standard, you can probably do this my_hash.cc #include <functional> extern "C"{ size_t hash(char* c){ std::hash<char*> hasher; return hasher(c); } } my_hash.h size_t hash(char* c); EDIT: Added code if you wanted to be pedantic about it. Then you just link your C program to my_hash.o and include my_hash.h

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.
taejo 8y ago
I think you meant template<class T> struct hash< T* >

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.

taejo 8y ago

I think you meant template<class T> struct hash< T* >