用于用户定义数据类型的 c++ unordered_map

Question

我正在编写这段代码来查找图形的连通分量。

    using namespace std;
    struct node;
    typedef list<node> AdjList;
    struct node
    {
        bool visited;
        string  name;
        AdjList adjlist;
        node(string name1):name(name1),visited(false){}
        node(const string& a):name(a),visited(false){}
    };
    typedef node node;




    class graph
    {
    int nonodes;
    unordered_map<string,node> vertices;
    public:
    graph(int v):nonodes(v){}
    void addrelation(string a , string b);
    void addaccount(string name);
    void dfs();
    };

void  graph::addaccount(string name)
{
    unordered_map<string,node>::iterator it = vertices.find(name);

    if(it!=vertices.end())
    {
        cout<<"account already exists"<<endl;
    }
    else
    {
        cout<<"creating a new account"<<endl;
        node* nnode=new node(name);
        vertices[name] = *nnode;
    }

}

对于线条，

    cout<<"creating a new account"<<endl;
    node* nnode=new node(name);
    vertices[name] = *nnode;

我收到以下错误。toposort.cpp:72: 从这里实例化/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/tr1_impl/hashtable_policy.h:575: 错误:没有匹配函数用于调用 'node::node()'

当我们将一个已经创建的成员分配给 unordered_map 时，unordered_map 是否会在内部尝试复制它？

Answer 1

这是预期的行为。根据documentation

If an insertion is performed, the mapped value is value-initialized (default-constructed for class types, zero-initialized otherwise) and a reference to it is returned.

在内部，std::unordered_map的operator[]需要在找不到key的时候创建一个新的数据类实例，并返回给你一个引用给它。所有这些都发生在赋值之前，此时正在计算表达式的左侧。这就是导致有关缺少默认构造函数的错误的原因。

因此，如果您希望将 map 的operator[] 与您的值类型一起使用，您需要提供一种方法来默认构造您的值对象。

注 1:值的复制确实发生了。但是，它仅在 operator[] 返回后 开始。

注意 2:为您的 struct node 定义单独的按值传递构造函数没有意义，因为另一个构造函数(即 node(const string& a)) 完全有能力处理这两种情况。

注3:动态分配节点没有意义。目前，它泄漏内存。赋值 vertices[name] = node(name); 会做同样的事情而不会泄漏。