Как использовать сортировку STL для сортировки пользовательских объектов класса по шаблону?

Question

Я изучаю C ++ STL сейчас.Я знаю, что если я хочу выполнить пользовательскую функцию при использовании алгоритма или контейнера STL, я могу использовать специализацию по функтору или шаблону.Например:

class my_class {
public:
    int id;
    int num;
};

// Definition of hash and comparison functor of my_class, which is so-called Explicit Template Specialization
namespace std {
template <>
struct hash<my_class> {
    size_t operator()(const my_class& e) const
    {
        return hash<int>()(e.id);
    }
};
template <>
struct equal_to<my_class> {
    bool operator()(const my_class& le, const my_class& re) const
    {
        return le.id == re.id;
    }
};
};

int main()
{
    unordered_set<my_class> s;
    s.insert(my_class{ 0, 10 });
    s.insert(my_class{ 1, 30 });
    s.insert(my_class{ 0, 20 });
    s.insert(my_class{ 2, 40 });
    for (auto e : s) {
        cout << "Value of ID " << e.id << ": " << e.num << endl;
    }
    cout << "Size of set: " << s.size() << endl;
    return 0;
}

Но как я могу использовать сортировку STL для сортировки объектов пользовательского класса со специализацией шаблона?

Следующее неверно:

class my_class {
public:
    int id;
    int num;
};
namespace std {
template <>
struct comp<my_class> {
    bool operator()(const my_class& le, const my_class& re) const
    {
        return le.id < re.id;
    }
};
};

int main()
{
    vector<my_class> v;
    v.push_back(my_class{ 2, 10 });
    v.push_back(my_class{ 3, 10 });
    v.push_back(my_class{ 0, 10 });
    v.push_back(my_class{ 1, 10 });
    sort(v.begin(), v.end());
    cout << "Vector after sorting:" << endl;
    for (const auto& e : v) {
        cout << "Value of ID " << e.id << ": " << e.num << endl;
    }
    return 0;
}

Answer 1

Вы не можете. Это исходный код для сортировки (gcc 4.8.2):

/**
 *  @brief Sort the elements of a sequence.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @return  Nothing.
 *
 *  Sorts the elements in the range @p [__first,__last) in ascending order,
 *  such that for each iterator @e i in the range @p [__first,__last-1),  
 *  *(i+1)<*i is false.
 *
 *  The relative ordering of equivalent elements is not preserved, use
 *  @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator>
  inline void
  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
  {
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

  // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
    __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
  {
    std::__introsort_loop(__first, __last,
            std::__lg(__last - __first) * 2);
    std::__final_insertion_sort(__first, __last);
  }
}

/**
 *  @brief Sort the elements of a sequence using a predicate for comparison.
 *  @ingroup sorting_algorithms
 *  @param  __first   An iterator.
 *  @param  __last    Another iterator.
 *  @param  __comp    A comparison functor.
 *  @return  Nothing.
 *
 *  Sorts the elements in the range @p [__first,__last) in ascending order,
 *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
 *  range @p [__first,__last-1).
 *
 *  The relative ordering of equivalent elements is not preserved, use
 *  @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator, typename _Compare>
  inline void
  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
 _Compare __comp)
  {
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
              _ValueType>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
  {
    std::__introsort_loop(__first, __last,
            std::__lg(__last - __first) * 2, __comp);
    std::__final_insertion_sort(__first, __last, __comp);
  }
}

В реализации для

void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

нет функции сравнения, поэтому вы не можете настроить ее по специализации шаблона. Вы должны использовать

void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

Answer 2

Вам не нужно специализироваться std::equal_to или std::less, вы можете просто предоставить operator == и operator < так, чтобы их можно было найти из неквалифицированного вызова.

Вы специализируетесь std::hash, потому что нет operator hash.

bool operator ==(const my_class& le, const my_class& re) const
{
    return le.id == re.id;
}

bool operator <(const my_class& le, const my_class& re) const
{
    return le.id < re.id;
}

Предоставив их, также полезно предоставить перегрузки для !=, > <= и >= в терминах таковых.Вы можете сделать это явно или наследовать от чего-то вроде boost::totally_ordered

class my_class : public boost::totally_ordered<my_class> {
public:
    int id;
    int num;
};

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

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

Answer 3

Хотя спецификация, например, std::less, учитывается при сравнении ключей в std::map, по умолчанию для std::sort используется operator < (перегрузка # 1 здесь ).Специализация std::less все еще действительна, но вам необходимо явно передать ее в std::sort следующим образом:

namespace std {
    template <>
    struct less<my_class> {
         bool operator()(const my_class& le, const my_class& re) const
         {
             return le.id < re.id;
         }
    };
}

// Fill vector with my_class instances...

std::sort(v.begin(), v.end(), std::less<my_class>{});

Обратите внимание, как это отличается от вставки элементов в карту:

// std::less<my_class> is used by default to compare key instances:
std::map<my_class, int> m;

m[{1, 1}] = 42;