14

我有以下代码：

struct Node
{
  int a;
  int b;
};

Node node;
node.a = 2;
node.b = 3;

map<int, int> aa;
aa[1]=1; // OK.

map<Node, int> bb;
bb[node]=1; // Compile error.

当我尝试将 struct 的实例映射Node到 时int，出现编译错误。为什么？

4

6 回答 6

23

要使某事物可用作地图中的键，您必须能够使用operator<(). 您需要将这样的运算符添加到您的节点类中：

struct Node
{
 int a;
 int b;

 bool operator<( const Node & n ) const {
   return this->a < n.a;   // for example
 }
};

当然，真正的运算符的作用取决于比较对您的结构实际上意味着什么。

于 2010-02-06T18:59:46.727 回答
10

您必须告诉 std::map 如何比较 Node 对象。默认情况下，它会尝试使用小于运算符来执行此操作。但是您没有为 Node.js 提供任何小于运算符。最简单的解决方案是提供一个。

自由函数示例：

bool operator<(Node const& n1, Node const& n2)
{
    return n1.a<n2.a || (n1.a==n2.a && n1.b<n2.b);
}

请注意，对于任何一对节点对象 x,y!(x<y)和!(y<x)，地图将 x 和 y 视为相等（相同的键）。

于 2010-02-06T18:59:25.917 回答
7

您需要定义小于运算符以启用您的节点类型的比较：

struct Node
{
 int a;
 int b;
};

bool operator<(Node const& n1, Node const& n2)
{  
   // TODO: Specify condition as you need
   return ... ;
}

在这里，您可以检查LessThan Comparable对用户定义类型的含义。

另一种解决方案是定义一个基于std::binary_function的仿函数。从设计的角度来看，此选项具有优势，因为比较有效地与Node类分离。这使得定义具有不同比较条件（函子）的映射成为可能。

#include <map>

struct Node
{
 int a;
 int b;
};

struct NodeLessThan
    : public std::binary_function<Node, Node, bool>
{
    bool operator() (Node const& n1, Node const& n2) const
    {
        // TODO: your condition
        return n1.a < n2.a;
    }
};

int main()
{
    Node node;
    node.a = 2;
    node.b = 3;

    typedef std::map<Node, int, NodeLessThan> node_map_t;
    node_map_t bb;
    bb[node] = 1;
}

因此，您可以定义更多的比较，而不仅仅是NodeLessThan，例如使用不同的条件或一个仅通过Node::a另一个比较两个组件进行比较，Node::a以及Node::b. 然后，定义了不同类型的地图：

typedef std::map<Node, int, NodeLessThan>    node_map_t;
typedef std::map<Node, int, NodeLessThanByA> node_map_a_t;

这种解耦的侵入性较小（根本不涉及 Node 类），并且有利于实现更具可扩展性的解决方案。

于 2010-02-06T19:02:09.717 回答
3

如果您真的不需要按键对数据进行排序，则可以使用新的 unordered_map：

#include <unordered_map>

... 

std::tr1::unordered_map<Node, int> aa;  // Doesn't require operator<(Node, Node)

你需要一个最近的编译器才能工作。

更新 正如尼尔指出的，如果你想要一个带Node键的 unordered_map，你需要一个专门的散列函数。

struct NodeHash : std::unary_function<Node, size_t>
{ 
    size_t operator()(Node const & node) const
    {
        return static_cast<size_t>(node.a + 1) * static_cast<size_t>(node.b + 1);
    }
};

然后地图变成：

 std::tr1::unordered_map<Node, int, NodeHash> aa;

此外，正如 sellibitze 所说，在哈希冲突的情况下，需要一个 operator== 来比较键：

bool operator==(const Node & lhs, const Node & rhs)
{
    return lhs.a == rhs.a && rhs.b == rhs.b;
}

所以我想 std::map 毕竟更容易使用。

于 2010-02-06T19:09:06.353 回答
1

您能否发布编译器错误 - 他们旨在告诉您，出了什么问题。

我猜你的错误是因为Node没有实现地图所需的比较运算符来识别它的元素。

于 2010-02-06T18:57:41.903 回答
0

由于std::map是按其键排序的，因此您必须定义如何比较两个Node对象。从C++11开始，您还可以使用lambda 表达式而不是定义比较运算符。因此，您可以保持代码如下所示：

int main() {
    Node node{ 2, 3 };

    auto comp = [](const Node& n1, const Node& n2) {
        return n1.a < n2.a || (n1.a == n2.a && n1.b < n2.b);
    };
    std::map<Node, int, decltype(comp)> bb(comp);
    bb[node] = 1;

    for (auto const &kv : bb)
        std::cout << kv.first.a << ", " << kv.first.b << ": " << kv.second << std::endl;

    return 0;
}

输出：

2、3：1

请根据需要替换 lambda 表达式的主体。

Ideone 上的代码

于 2019-09-16T12:22:56.360 回答