std::set 用于插入和排序的不同比较器

Question

我需要一个结构，我可以在其中插入元素，没有重复项，使用自定义比较器并首先拥有最小的元素。我尝试使用 std::priority_queue，但问题是我得到了很多重复项，并且运行超出了 space。所以我考虑使用 std::set ：
std::set< std::pair<Coordinates, int>, Compare> positions; where

Coordinates
{
public:
    Coordinates(int x = 0, int y = 0, char tool = 'T') : x(x), y(y), tool(tool) {}

public:
    int x, y;
    char tool;
};

class Compare
{
public:
    bool operator() (const std::pair<Coordinates, int>& c1, const std::pair<Coordinates, int>& c2) const
    {
        return c1.second < c2.second;
    }
};

我希望元素根据对的第二个元素排序，此实现正在这样做，但问题是它在插入新对时使用相同的比较器，我得到了重复项。
我的问题是：是否可以使 std::set 不允许重复项也根据对的第二个元素对元素进行排序？

编辑：删除了一些不必要的代码并在 Compare > 中更改为 <

Answer 1

使用您的 Comparer，set 将仅包含 int 的唯一值，因为 Coordinates 根本不参与比较。

std::set 使用 operator < 进行排序和相等；平等被确定为!(a<b || b<a)。因此 operator < 应该考虑使元素唯一的每个属性。

您可以像这样针对您的类型专门化 std::less：

namespace std {
template<>
struct less<pair<Coordinates, int>> {
    bool operator()(const pair<Coordinates, int>& a, const pair<Coordinates, int>& b) const {
        return tie(a.second, a.first.x, a.first.y) < tie(b.second, b.first.x, b.first.y);
    }
};
}

那么 std::set< std::pair<Coordinates, int>> positions; 应该可以。

Answer 2

这里的问题是，由于您只查看比较器中的 second，因此您只能存储具有 second 唯一值的对。这是因为集合只使用比较器来比较元素。它不使用您的 operator == 来检查是否相等，而是使用 cmp(a, b) == cmp(b, a)¹ 来测试值是否相等。

如果您想按 second 排序，但允许其他点具有相同的 second 但其他值不同，那么您需要将这些值添加到比较器中。最简单的方法是使用 std::tie 构建一对元组并使用元组 operator < 和 "does the right thing"。那看起来像

class Compare
{
public:
    bool operator() (const std::pair<Coordinates, int>& c1, const std::pair<Coordinates, int>& c2) const
    {
        return std::tie(c1.second, c1.first.x, c1.first.y)  < std::tie(c2.second, c2.first.x, c2.first.y);
    }
};

¹：如果a不小于b，且b不小于a则a 和 b 必须相等

Answer 3

如前所述，问题在于您只查看了这对中的第二个成员，因此集合不关心坐标是否不同。您只需要在比较中包含坐标。

与其他答案不同，这个答案使用 lambda 进行比较。与 std::tie 相比，我更喜欢它并使用 std 覆盖。它还可以省去您自己编写仿函数的麻烦，就像您使用 Compare class 所做的那样。

#include <iostream>
#include <set>

class Coordinates {
public:
  Coordinates(int x = 0, int y = 0, char tool = 'T') : x(x), y(y), tool(tool) {}

  int x, y;
  char tool;
};

int main() {
  using CoordPair = std::pair<Coordinates, int>;

  auto compare = [](const CoordPair& a, const CoordPair& b) {
    if (a.second != b.second)
      return a.second < b.second;

    // Replace this with some method of comparing Coordinates
    return a.first.x != b.first.x || a.first.y != b.first.y;
  };

  std::set<std::pair<Coordinates, int>, decltype(compare)> list(compare);

  list.emplace(Coordinates(1, 1), 2);
  list.emplace(Coordinates(2, 0), 2);
  list.emplace(Coordinates(1, 1), 3);
  list.emplace(Coordinates(1, 1), 2); // Shouldn't show up

  for (auto i : list)
    std::cout << '(' << i.first.x << ", " << i.first.y << ", " << i.first.tool
              << ')' << ", " << i.second << '\n';
}

未指定您的 C++ 版本，至少需要 C++11。

std::set 用于插入和排序的不同比较器

std::set different comparer for inserting and ordering

c++

containers

priority-queue

set