1

Let's say we have a snippet of code as follows

#include <list>
#include <string>
#include <unordered_map>

int main() {
    std::list<int> myList = {4, 1, 3, 2};
    std::unordered_map<std::list<int>::iterator, std::string> myMap;
    myMap[myList.begin()] = "first element";
}

This code in itself wouldn't work since we have to define a template specialization for std::hash, like the one below

template<>
class std::hash<std::list<int>::iterator> {
public:
    size_t operator()(std::list<int>::iterator const& it) const noexcept {
        return hash<int*>()(&*it);
    }
};

This works well.

But when I tried to generalize it and define the following instead,

template<typename T>
class std::hash<std::list<T>::iterator> {
public:
    size_t operator()(std::list<T>::iterator const& it) const noexcept {
        return hash<T*>()(&*it);
    }
};

I see a static assertion failure again from the compiler. Why doesn't this work, and what is the right way to define std::hash for any list-iterator?

Compiler details
  • g++ (GCC) 13.2.1 20230801
  • -std=c++23 flag (C++23 standard)
vamsi3
  • 115
  • 4
  • 2
    When you extend `namespace std` such as by specializing `std::hash` you need that specialization to include at least one program-defined type. – François Andrieux Aug 16 '23 at 12:59
  • 1
    Hashing an object using its pointer is generally going to be a mistake. Objects that compare equal must generate the same hash. But two different but equal objects won't have the same address, so won't produce the same hash when their address is used for hashing. – François Andrieux Aug 16 '23 at 13:00
  • @FrançoisAndrieux I want to highlight the question is specifically about hashing list iterators. About requiring atleast one program-defined type, should I take it as a limitation of the C++ standard, or is there a rationale behind it that I can learn from. And about using pointers, iterators are meant to be different if they 'point' to different data, so with that view in mind I believed it is okay to define the hash function like that. Am I missing anything in my mind? – vamsi3 Aug 16 '23 at 13:05
  • _"should I take it as a limitation of the C++ standard"_ - Yes, this is mentioned in the standard if that's what you're asking about. – Ted Lyngmo Aug 16 '23 at 13:10
  • 1
    @vamsi3 The rationale for requiring at least one program-defined type when specializing templates in the `std` namespace is: If there is no program-defined type involved, then the template might have already been specialized by the implementation itself. – Mestkon Aug 16 '23 at 13:18

2 Answers2

6

You can use concepts to constrain the type It to be an iterator of std::list

#include <list>
#include <unordered_map>

template<std::bidirectional_iterator It>
  requires std::same_as<It, typename std::list<std::iter_value_t<It>>::iterator>
class std::hash<It> {
 public:
  size_t operator()(const It& it) const noexcept {
    return hash<std::iter_value_t<It>*>()(std::addressof(*it));
  }
};

Demo

康桓瑋
  • 33,481
  • 5
  • 40
  • 90
4

There's just no way to make this work:

template<typename T>
class std::hash<std::list<T>::iterator>

This is a non-deduced context, so deduction will always fail†. So you need to come up with some way to make your deduction viable.

The simplest approach is just to wrap:

template <typename T>
struct ListIterator {
    std::list<T>::iterator;
};

template <typename T>
class std::hash<ListIterator<T>> { ... };

This is straightforwardly viable and works just fine, it's just that you need to have a unordered_map<ListIterator<T>, V> instead of an unordered_map<std::list<T>::iterator, V>. On the insertion side, shouldn't be a difference once you add an implicit constructor - but on the extraction side, yeah you might have to do an extra accessor here and there, but this'll get the job done.

†Although I feel like the language should be extended to cover the case of matching types whose name is actually C<T>::D - there are going to be contexts that cannot be deducible at all (like add_const<T>::type), but otherwise for the cases where you want stuff like this to work (and they do exist) you need to try to come up with wacky workarounds.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • Thanks for the answer. Looking up more on non-deduced context (https://stackoverflow.com/questions/25245453/what-is-a-nondeduced-context) took me in the right direction on why it doesn't work. – vamsi3 Aug 17 '23 at 05:26