c++ - Заставить set сортироваться по убыванию


1

Как известно, set - множество в С++, которое отсортировано по возрастанию. Мне известно, что можно сделать так, чтобы set был отсортирован по убыванию. Одним словом цель - добиться, чтобы set сортировался по убыванию. Кто знает, как это сделать?

Источник
  •  224
  •  3
  • 3 янв 2019 2019-01-03 11:02:02

3 ответа

4

Контейнер std::set всегда отсортирован "по возрастанию". Вы можете повлиять лишь на то, что такой контейнер считает "возрастанием".

Каким образом будет упорядочен std::set определяется предикатом сравнения элементов, тип которого является вторым параметром шаблона std::set и значение которого является параметром конструктора std::set. По умолчанию в качестве предиката сравнения используется std::less. Стандартная реализация std::less внутри себя выполняет сравнение путем обращения к оператору < для сравниваемых элементов.

Это дает вам три возможных "точки входа" в механизм сравнения, три способа воздействовать на порядок упорядочения в std::set и других аналогичных контейнерах:

  1. Использовать другой предикат сравнения в качестве параметра std::set

    #include <set>
    #include <iostream>
    
    struct MyType
    {
      int i;
      friend bool operator <(const MyType &lhs, const MyType &rhs)
        { return lhs.i < rhs.i; };
      friend bool operator >(const MyType &lhs, const MyType &rhs)
        { return lhs.i > rhs.i; };
    };
    
    int main()
    {
      std::set<MyType, std::greater<MyType>> my_set = 
        { { 2 }, { 8 }, { 5 }, { 4 }, { 1 }, { 3 } };
      for (auto &e : my_set)
        std::cout << e.i << " ";
      std::cout << std::endl;
    }
    

    http://coliru.stacked-crooked.com/a/cccfbce2e58cbfc8

    Как сказано выше, значение этого предиката тоже учитывается контейнером - оно передается в контейнер через параметр конструктора. Хоть это и редко используемая возможность, но этот предикат можно наделить состоянием и решение о его поведении принимать во время выполнения

    #include <set>
    #include <iostream>
    
    struct MyType
    {
      int i;
      friend bool operator <(const MyType &lhs, const MyType &rhs)
        { return lhs.i < rhs.i; };
      friend bool operator >(const MyType &lhs, const MyType &rhs)
        { return lhs.i > rhs.i; };
    };
    
    struct MyCmp
    {
      bool ascending = true;
      bool operator ()(const MyType &lhs, const MyType &rhs) const
      {
        return ascending ? lhs < rhs : lhs > rhs;
      }
    };
    
    int main()
    {
      std::set<MyType, MyCmp> 
        my_set_a({ { 2 }, { 8 }, { 5 }, { 4 }, { 1 }, { 3 } }, { true });
      for (auto &e : my_set_a)
        std::cout << e.i << " ";
      std::cout << std::endl;
    
      std::set<MyType, MyCmp> 
        my_set_d({ { 2 }, { 8 }, { 5 }, { 4 }, { 1 }, { 3 } }, { false });
      for (auto &e : my_set_d)
        std::cout << e.i << " ";
      std::cout << std::endl;
    }
    

    http://coliru.stacked-crooked.com/a/86f98e157467a3dd

  2. Определить специализацию std::less для типа элемента контейнера (только если элемент std::set имеет пользовательский тип)

    #include <set>
    #include <iostream>
    
    struct MyType
    {
      int i;
      friend bool operator <(const MyType &lhs, const MyType &rhs)
        { return lhs.i < rhs.i; };
      friend bool operator >(const MyType &lhs, const MyType &rhs)
        { return lhs.i > rhs.i; };
    };
    
    template<> struct std::less<MyType>
    {
      bool operator ()(const MyType &lhs, const MyType &rhs) const
        { return lhs > rhs; }
    };
    
    int main()
    {
      std::set<MyType> my_set = { { 2 }, { 8 }, { 5 }, { 4 }, { 1 }, { 3 } };
      for (auto &e : my_set)
        std::cout << e.i << " ";
      std::cout << std::endl;
    }
    

    http://coliru.stacked-crooked.com/a/2c7f508d7235e7b1

  3. Определить свою версию оператора < для типа элемента контейнера (только если элемент std::set имеет пользовательский тип)

    #include <set>
    #include <iostream>
    
    struct MyType
    {
      int i;
      friend bool operator <(const MyType &lhs, const MyType &rhs)
        { return lhs.i > rhs.i; };
    };
    
    int main()
    {
      std::set<MyType> my_set = { { 2 }, { 8 }, { 5 }, { 4 }, { 1 }, { 3 } };
      for (auto &e : my_set)
        std::cout << e.i << " ";
      std::cout << std::endl;
    }
    

    http://coliru.stacked-crooked.com/a/481288ec2ffc4e55

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

  • 4 янв 2019 2019-01-04 03:42:41
0

Как альтернативу решению выше, могу предложить небольшую хитрость: чтобы set сортировался по убыванию, вы можете сделать всё числа отрицательными. Таким образом, они тоже отсортируются по убыванию.

Например:

s.insert(x) становится s.insert(-x).

*(s.begin()) становится -(*(s.begin()))

  • 3 янв 2019 2019-01-03 11:07:17
ну хитрость неплохая — 4 янв 20192019-01-04 11:56:19.000000
@ВладиславНечипорук Конечно это не полноценная альтернатива. Я просто рассказал о небольшой хитрости, которой пользовался до того, как узнал про компараторы в принципе. — 3 янв 20192019-01-03 17:19:59.000000
Ну такоё. Будет работать только на чисельних типах. — 3 янв 20192019-01-03 15:42:09.000000
5

Воспользоваться готовым средством - заменить less на greater, типа

set<int,greater<int>> s { 2,5,8,1,4,9};
for(auto i: s) cout << i << endl;

set - не "множество в с++ которое отсортировано по возрастанию", оно сортируется так, как ему указывают. По умолчанию - с помощью компаратора less<>. А так - сортируйте, как хотите.

  • 3 янв 2019 2019-01-03 10:51:31