std :: установить другой компаратор для вставки и упорядочивания - PullRequest
Новая
       23

std :: установить другой компаратор для вставки и упорядочивания

1 голос
/ 06 ноября 2019

Мне нужна структура, в которую я могу вставлять элементы, не иметь дубликатов, использовать собственный компаратор и сначала иметь наименьший элемент. Я пытался использовать std::priority_queue, но проблема в том, что я получаю много дубликатов и у меня заканчивается свободное место. Поэтому я подумал об использовании std::set:
std::set< std::pair<Coordinates, int>, Compare> positions;, где 

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> с <</p>

Ответы [ 3 ]

1 голос
/ 06 ноября 2019

Проблема здесь в том, что, поскольку вы смотрите только на second в своем компараторе, вы можете хранить только пары, которые имеют уникальные значения для second. Это потому, что набор использует только компаратор для сравнения элементов. Он не использует ваш operator == для проверки на равенство, но вместо этого cmp(a, b) == cmp(b, a) 1 проверяет, равны ли значения.

Если вы хотите отсортировать по second,но разрешите другие точки с тем же second, но с другими другими значениями, тогда вам нужно добавить эти значения в компаратор. Самый простой способ сделать это - использовать std::tie для создания пары кортежей и использовать кортежи operator <, которые "делают правильные вещи". Это выглядело бы как 

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

1 : если a не меньше, чем b, а b не меньше, чем a, тогда a и b должно быть равно

1 голос
/ 06 ноября 2019

Как уже говорилось, проблема заключалась в том, что вы смотрели только на второго члена пары, поэтому набору было все равно, отличались ли координаты. Вам просто нужно было включить координаты в ваше сравнение.

В отличие от других ответов, этот использует лямбду для сравнения. Я предпочитаю его более std::tie и перебираю с std переопределениями. Это также избавляет вас от необходимости создавать функтор, как вы это делали в классе сравнения. 

#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.

1 голос
/ 06 ноября 2019

При использовании 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; должно работать.

...