Перегрузочный набор <оператор

Question

Дано

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

Мне нужен набор узлов, упорядоченный по стоимости пути, a == b, только если строка и столбцы равны. Мой вопрос: как я могу перегрузить оператор <, чтобы набор мог сохранять разные узлы, но с одинаковой стоимостью пути? А также, если a == b, сохраните тот, который стоит меньше </p>

Answer 1

, если a == b сохранить тот, который стоит дешевле

Этого не может быть при использовании std :: set : a==b означает a<bи b<a являются ложными, поэтому, когда a и b имеют одинаковые row и cols operator< должны вернуть false ичто без учета стоимость

Чтобы иметь ожидаемое поведение, вы должны реализовать свой собственный набор без использования operator< для сортировки / вставки.

упорядочено по стоимости пути

Полагаю, вы имеете в виду упорядочено по стоимости

Использование 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)

set содержит 3 2 3 и 3 2 9, даже если они должны считаться равными.

operator< неверно, поскольку он не согласуется при сравнении 3 2 3 и 3 2 9 с другими значениями:7 2 3 меньше 3 2 9, но это не такменьше чем 3 2 3

a == b, только если строка и столбцы равны

подразумевает, что сортировка должна учитывать только строка и cols но стоимость необходимо не использовать

Так, например,

#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);
  }

очень практично, когда нужно учитывать много полей