c++ - unordered_map 的问题

Question

我正在尝试为学习目的实现各种数据结构和算法。

目前我正在尝试实现一个 Graph 类模板，但我在尝试使用 STL unordered_map(以及将来的 consequently priority_queue)时遇到了问题.

目前基本上发生的情况是，出于某种原因，在尝试初始化图中的顶点映射时模板类型不匹配。据我了解，由于我只打算使用 native C++ 类型中的键类型，因此只要我的值类型是指针，除了我的自定义顶点类的复制构造函数之外，我不需要做任何额外的工作。默认的比较器/哈希器应该足够了。但事实并非如此，我收到的错误有点难以理解。

错误:

Error   1   error C2679: binary '=' : no operator found which takes a right-hand operand of type 'std::unordered_map<T,graph<T>::vertex *,std::hash<int>,std::equal_to<_Kty>,std::allocator<std::pair<const _Kty,_Ty>>>' (or there is no acceptable conversion)

代码:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <functional>

using namespace std;
class vertex;
template <class T>
class graph {
public:

graph() { verts = unordered_map<T, vertex*>(); }
~graph() {
    for each(auto v in verts)
        delete(v);
    delete(verts); 
}
private:
unordered_map<T, vertex*> verts;

// --- Inner Classes ---

struct path {
    vertex *dest;
    double cost;

    path(vertex *d = nullptr, double c = 0.0) : dest(d) : cost(c) {}

    inline int compare(const path& p) {
        auto other = p.cost;

        return cost < other ? -1 :
            cost > other ? 1 : 0;
    }
};

struct edge {
    vertex *dest;
    double cost;

    edge(vertex *d = nullptr, double c = 0.0) : dest(d) : cost(c) {}
};

class vertex {
public:
    // Vertex relationships
    T name;
    vector<edge>* adj;

    // Path Finding Information
    double distance;
    vertex *prev;
    int scratch;

    void reset_path_finding() {
        distance = double.infinity();
        prev = nullptr;
        scratch = 0;
    }

    vertex(T name = default(T)) : name(name) : adj(new vector<edge>) : 
        distance(double.infinity()) : prev(nullptr) : scratch(0) {}
    vertex(const vertex& v) {
        name = v.name;
        adj = v.adj;
        distance = v.distance;
        prev = v.prev;
        scratch = v.scratch;
    }
    ~vertex() { delete(adj); }
private:
};
};

int main()
{
graph<int> myGraph = graph<int>();

cout << "Press any key to continue..." << endl;
int x;
cin >> x;
return 0;
}

Answer 1

第一个问题是你使用嵌套类graph::vertex在宣布之前。由于您声明了 class vertex，造成了进一步的困惑。 外面 graph ，所以编译器最初认为你的意思是那个类。你可以声明 vertex在 graph 的开头附近:

template <class T>
class graph {
    class vertex;
private:
    // and so on
};

还有其他几个语法错误，如果您查看错误消息所指的行，这些错误应该很明显。基于范围的 for 循环的语法是

for (auto v : verts)  // not for each(auto v in verts)

这为您提供了键值对，因此要删除 vertex , 你需要

delete v.second;

更好的是，更改 verts进入unordered_map<T, vertex> ，包含对象而不是指针，并且它将自动管理其所有内存 - 您根本不需要析构函数。

值初始化临时值的语法是

T()  // not default(T)

构造函数的初始化列表中的子句用逗号分隔，而不是冒号:

path(vertex *d = nullptr, double c = 0.0) : dest(d) , cost(c) {}
                                                    ^ not :

A double具有无限值(value)的是

std::numeric_limits<double>::infinity() // not double.infinity()

您需要为其添加 <limits> .

verts不需要在析构函数中删除，因为你不需要 new它。它也不需要从构造函数中默认构造的临时对象进行分配，因为它只是默认构造的。

在一些地方，您会因为不必要地使用指针和 new 而让自己的生活变得困难。 .尽量避免 new除非你真的需要它；并了解 RAII ，尤其是在您这样做时使用智能指针和容器。