如何使用 STL 排序对具有模板专用化的自定义类对象进行排序?

Question

我现在正在学习STL C++。我知道如果我想在使用 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::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;

Answer 3

您不需要专门化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 时完成自定义功能 算法或容器，我可以使用函子或模板专用化。

不一定。该语言以多种方式提供自定义点。其中一些是通过函子，一些是通过模板专用化的，在本例中，通过为运算符函数提供重载。