c++ - 重载集合 < 运算符

Question

给定

struct node{
    int row;
    int cols;
    int cost;
}

我需要一个按路径成本排序的节点集，a==b 仅当行和列相等时。我的问题是如何重载 operator< 以便集合可以保存不同的节点但具有相同的路径成本？并且如果 a==b 保存成本最低的那个

Answer 1

if a==b save the one with lest cost

你不能使用 std::set 来实现:a==b表示 a<b和 b<a是假的，所以当 a 和 b 有相同的 row 和 cols operator<必须返回 false 并且不考虑成本

要获得预期的行为，您必须实现自己的集合，而不仅仅是使用operator<。排序/插入。

ordered by path cost

我想你的意思是按成本订购

使用 std::set 和 operator<我们可以考虑:

  bool operator <(const node & rhs) const {
    // to satisfy a==b only if row and cols are equal
    if ((row == rhs.row) && (cols == rhs.cols))
      return false;

    return (cost < rhs.cost) ||
      ((cost == rhs.cost) &&
       ((row < rhs.row) || ((row == rhs.row) && (cols < rhs.cols))));
  }

但是这是错误的，例如

#include <set>
#include <iostream>

struct node{
  int row;
  int cols;
  int cost;

  bool operator <(const node & rhs) const {
    // to satisfy a==b only if row and cols are equal
    if ((row == rhs.row) && (cols == rhs.cols))
      return false;

    return (cost < rhs.cost) ||
      ((cost == rhs.cost) &&
       ((row < rhs.row) || ((row == rhs.row) && (cols < rhs.cols))));
  }
};

int main()
{
  const node a[] = { {3,2,3} , {3,2,2}, {4,3,2}, {7,2,3}, {3, 2, 9} };
  std::set<node> s;

  for (size_t i = 0; i != sizeof(a)/sizeof(*a); ++i)
    s.insert(a[i]);

  for (auto x : s)
    std::cout << '(' << x.row << ' ' << x.cols << ' ' << x.cost << ')' << std::endl;

  return 0;
}

编译和执行:

pi@raspberrypi:/tmp $ g++ -pedantic -Wextra -Wall s.cc
pi@raspberrypi:/tmp $ ./a.out
(4 3 2)
(3 2 3)
(7 2 3)
(3 2 9)

集合 包含 3 2 3和 3 2 9甚至他们必须被视为平等。

operator<是错误的，因为比较时不一致 3 2 3和 3 2 9到其他值:7 2 3小于 3 2 9但不小于3 2 3

a==b only if row and cols are equal

暗示排序必须只考虑行和列，但必须不使用成本

比如

#include <set>
#include <iostream>

struct node{
  int row;
  int cols;
  int cost;

  bool operator <(const node & rhs) const {
    return (row < rhs.row) || ((row == rhs.row) && (cols < rhs.cols));
  }
};

int main()
{
  const node a[] = { {3,2,3} , {3,2,2}, {4,3,2}, {7,2,3}, {3, 2, 9} };
  std::set<node> s;

  for (size_t i = 0; i != sizeof(a)/sizeof(*a); ++i)
    s.insert(a[i]);

  for (auto x : s)
    std::cout << '(' << x.row << ' ' << x.cols << ' ' << x.cost << ')' << std::endl;

  return 0;
}

编译和执行:

pi@raspberrypi:/tmp $ g++ -pedantic -Wextra -Wall s.cc
pi@raspberrypi:/tmp $ ./a.out
(3 2 3)
(4 3 2)
(7 2 3)
pi@raspberrypi:/tmp $ 

尊重预期的平等，但与成本无关

---

来自 C++11(感谢@PaulMcKenzie 的评论):

  bool operator <(const node & rhs) const {
    return std::tie(row, cols) < std::tie(rhs.row, rhs.col);
  }

当有很多字段需要考虑时非常实用