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: 错误：没有匹配函数来调用 '节点::节点()'

当我们将一个已经创建的成员分配给 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[] 需要在未找到密钥时创建数据的新实例 class，并且 return 您对它。所有这些都发生在赋值之前，此时正在计算表达式的左侧。这就是导致有关缺少默认构造函数的错误的原因。

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

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

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

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

Answer 2

在unordered_map中用operator[]插入的元素被值初始化：

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.

然后通过赋值复制元素。

Answer 3

@dasblikenlight 已经部分解释了问题，但他没有提出解决方案。插入元素的正常方法是使用函数 insert:

vertices.insert( std::make_pair( name, node( name ) );

由于您的 node 类型具有值语义，您 不应该 new 它，只需在需要时构建它。如果你真的想保留单独构建：

node newNode( name );
vertices.insert( std::make_pair( name, newNode ) );

（作为一般规则，如果一个类型具有值语义，它永远不应该是动态分配。也有例外，通常是为了性能原因，但它们只是例外。）

最后，insert 插入当且仅当没有元素带有等效键，它 returns 一个 std::pair 和一个 bool 表示插入是否发生。所以你的整个 addaccount 变得简单：

std::pair<std::unordered_map<std::string, node>::iterator, bool> results
    = vertices.insert( std::make_pair( name, node( name ) ) );
if ( ! results.second ) {
    std::cout << "account already exists" << std::endl;
}

（我通常使用 typedef 作为地图类型，来制作这样的类型名称更易于管理。更不用说它允许轻松切换不同类型的地图；除非地图很大，否则你可能会发现 std::map 优于 std::unordered_map。）

只是要清楚[]：标准说如果条目不存在，它插入 value_type( key, mapped_type() )（基本上使用上面的 insert 函数，其中 value_type 是 std::pair）。这就是调用默认构造函数的地方。并且...是否发生插入是动态确定的，因此编译器会尝试编译它，即使你从不使用 [] 不存在的元素。如果你想支持[]，你必须支持映射类型的默认构造。

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

c++ unordered_map for user defined data type

c++

unordered-map