Сортировка подмножеств отсортированного вектора

Question

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

Пример:

Скажем, у нас есть данные: { ("cat", 2), ("dog", 4), ("cat", 1), ("dog", 3) }

Сначала мы сортируем это в соответствии с алфавитным порядком строки:

{ ("cat", 2), ("cat", 1), ("dog", 4), ("dog", 3) }

Затем мы сортируем два подмножества (набор кошек и набор собак) в порядке возрастания ихчисла:

{ ("cat", 1), ("cat", 2), ("dog", 3), ("dog", 4) }

Также я использую метод рекурсивной быстрой сортировки со следующим заголовком:

void quickSort(vector<Type*>, int left, int right)

, где левый и правый - ограничивающие индексыпо которому вектор должен быть отсортирован.

Должен ли я добавить код в сам метод сортировки или я должен как-то вызвать метод сортировки снова?

Answer 1

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

Answer 2

Как правило, вы хотите, чтобы пользовательский компаратор сортировался с помощью.

struct Foo {
  std::string name;
  int count;
  struct Less {
    bool operator()(const Foo &lhs, const Foo &rhs) const {
      if ((int c = lhs.name.compare(rhs.name)) != 0)
        return c < 0;
      return lhs.count < rhs.count;
    }
  };
};

std::vector<Foo> foos;
// ...
std::sort(foos.begin(), foos.end(), Foo::Less());

Если вы не можете просто использовать один пользовательский оператор, вы можете использовать стабильную сортировку.

Как указаноМарком, std::sort - это , а не стабильная сортировка.Вместо этого вам нужно будет использовать std::stable_sort.

. Вы хотите отсортировать их независимо в порядке возрастания важности.Таким образом, вы сортируете по номерам, а затем по строке.

struct Foo {
  std::string name;
  int count;
  struct NameLess {
    bool operator()(const Foo &lhs, const Foo &rhs) const {
      return lhs.name.compare(rhs.name) < 0;
    }
  };
  struct CountLess {
    bool operator()(const Foo &lhs, const Foo &rhs) const {
      return lhs.count < rhs.count;
    }
  };
};

std::vector<Foo> foos;
// ...
std::stable_sort(foos.begin(), foos.end(), Foo::CountLess());
std::stable_sort(foos.begin(), foos.end(), Foo::NameLess());

Очевидно, вы предпочтете первое, но последнее может пригодиться для упрощения комбинаторных и / или конфигурируемых алгоритмов времени выполнения.

Для справки:

cplusplus.com C ++: Ссылка: алгоритмы STL: stable_sort

cplusplus.com C ++: Ссылка: алгоритмы STL: сортировка

Answer 3

вы можете перегрузить ваш оператор <тогда вы можете использовать vector.unique () и затем vector.sort () </p>

Answer 4

Если вы храните ваши данные как vector<pair<string, int> >, тогда вы можете просто использовать std::sort(vec.begin(), vec.end());, и он будет работать, потому что pair operator< уже будет использовать обе части объекта для сортировки.