C++：无法为 Vertex 对象创建哈希函数

Question

所以我正在尝试制作一个图表 class 作为另一个项目的一部分。顶点存储在邻接列表中，邻接列表由 unordered_map 定义。我正在尝试创建一个哈希函数以允许我的 Vertex class 存储在此地图中，但我不知道我做错了什么。我收到此错误：

no matching function for call to ‘std::hash<Vertex<int> >::hash(int)’

这是我的 graph.h 文件

#ifndef GRAPH_GRAPH_H_
#define GRAPH_GRAPH_H_

#include <vector>
#include <unordered_map>

template <typename T>
class Vertex {
    private:
        T value;
    public:
        Vertex(T value);
        T getValue() const;
        void setValue(T value);

        //Equality check. This also requires an equality check to exist for T. If it does not (e.g. custom class), make sure you impemented one
        bool operator==(const Vertex<T>& v) const{
            return (this->value == v.value);
        }
};

template <typename T>
Vertex<T>::Vertex(T value) {
    this->value = value;
}

template <typename T>
T Vertex<T>::getValue() const{
    return this->value;
}

template <typename T>
void Vertex<T>::setValue(T value) {
    this->value = value;
}

//If you want to hash a vertex, T needs a way of being hashed
namespace std {
    template<typename T> struct hash<Vertex<T>> {
        size_t operator()(Vertex<T> const& v) const {
            return hash(v.getValue());
        }
    };
}


template <typename T>
class Graph {
private:
    //Now I know what you're thinking. Graph theory taught me that a graph needs a set of nodes, and an adjacency list.
    //All you've given us is an adjacency list.
    //Well, since we need to use our nodes as keys, the set of keys is equivalent to the set of nodes. So there.

    unordered_map<Vertex<T>, std::vector<Vertex<T>>> adjacencyList;

public:
    Graph(); //Needs a hash function. For example, if your vertices are storing std::pairs, we need a hash to convert the pair into a key
             //Since I don't know what you will be storing, you should provide a hash function
    ~Graph();
    //Since we are initialising a new object, v must be whatever we are using to initialise our vertices
    void addVertex(T value, std::vector<T> adjacent);
    void removeVertex(T value);
    void printGraph();
};

template <typename T>
Graph<T>::Graph() {
}

template <typename T>
Graph<T>::~Graph() {
}

template <typename T>
void Graph<T>::addVertex(T value, std::vector<T> adjacent) {
    //Check that the value does not already exist
    if (this->adjacencyList.find(Vertex<T>(value)) == this->adjacencyList.end()) {
        Vertex<T> v = Vertex<T>(value);
        std::vector<Vertex<T>> adj;
        for (unsigned int i = 0; i < adjacent.size(); i++) {
            Vertex<T> vAdj = Vertex<T>(adjacent[i]);
            adj.push_back(vAdj);
        }
        this->adjacencyList.insert(make_pair(v, adj));
    }
        //If the values does not exist, place it and the adjacency in there
        //Otherwise, do nothing


}

template <typename T>
void Graph<T>::removeVertex(T value) {
    //Check that the value does not already exist
    //if (this->adjacencyList.find(Vertex<T>(value)) != this->adjacencyList.end()) {
        this->adjacencyList.erase(Vertex<T>(value));
    //}
}

template <typename T>
void Graph<T>::printGraph() {

}
#endif /* GRAPH_GRAPH_H_ */

Answer 1

Vertex::getValue() 无法在 hash<Vertex<T>> 内调用，因为它未标记为 const.

您需要将 class 中的定义更改为

template <typename T>
class Vertex {
    ...
    T getValue() const;
    ...
};

同时，您可能也应该对 operator== 应用相同的更改。

Answer 2

您在

中有一个错误

return hash(v.getValue());

std::hash 不是一个函数，它是一个结构体，所以你需要先创建一个对象。例如

return hash<T>{}(v.getValue());

C++：无法为 Vertex 对象创建哈希函数

C++: Failing to make a hash function for a Vertex object

c++

oop

templates

stl

graph-theory