C++ STL: 自定义 std::set 的排序方式

众所周知， C++ STL 中的 std::set （你可以#include <set> 来使用它）是一个很棒的容器。

正如其名（中文翻译应该是集合而不是设置， in case you don’t get it）， 它提供了如下两个特性：

1. 加入到其中的元素不重复（即使有重复会帮你自动去重）。
2. 会自动排序其中的元素。

可是这就带来了一个问题：自动排序当然很棒，可是如果我想要用自己的方式来排序这个 std::set 怎么办呢？

警告⚠️：由于 std::set 内部实现的特殊性， 请不要尝试用 std::sort() 来重新排序 std::set （当然你这么做的话编译器会给你一个大大的编译错误（逃

RTFM 之后， 看到 std::set 的 signature 如下

template < class T,                       
           // set::key_type/value_type
           class Compare = less<T>,       
           //set::key_compare/value_compare
           class Alloc = allocator<T>     
           // set::allocator_type
           > class set;

看到这个模版的第二个模版参数是 class Compare ，并且默认值为 less<T> 这个模版。

下面的 Template parameters 有提到，

This can be a function pointer or a function object (see constructor for an example). This defaults to less<T>, which returns the same as applying the less-than operator (a<b).

再来 RTFM， 找到 std::less<T> , 发现是这样的一个模版：

template <class T> struct less {
  bool operator() (const T& x, const T& y) const {return x<y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

那么事情就好办了，我们只要写一个函数，然后把函数指针喂给这个模版参数就行了；或者写一个 function object 然后把它喂进去也行。

---

下面是一个🌰：

/*
// Taking the incoming strings and outputting them in the order of their length
*/
#include <iostream>
#include <set>
using namespace std;

struct shorter
{
    bool operator()(const string& p_lhs, const string& p_rhs)
    {
        const size_t lhsLength = p_lhs.length() ;
        const size_t rhsLength = p_rhs.length() ;

        if (lhsLength == rhsLength)
            return (p_lhs < p_rhs);
        // Using default string comparison in case of multiple strings in the same length.

        return (lhsLength < rhsLength) ;
    }
};

int main()
{
    int count;
    cin >> count;
    set<string, shorter> strSet;
    for (int i = 0; i < count; i ++)
    {
        string tmp;
        cin >> tmp;
        strSet.insert(tmp);
    }

/* -- Old school C++ enumerating. -- */
//    set<string, shorter>::iterator itor;  
//    for (itor = strSet.begin(); itor != strSet.end(); itor ++)
//    {
//        cout << *itor << endl;
//    }
/* -- End of enumerating. -- */

/*- From C++ 17(?): 
    A new way to enumerate items in a enumerable set. -*/
    for (const auto& str : strSet)  
    {
        cout << str << endl;
    }
/*- End of enumerating. -*/

    return 0;
}

---

ps：这个情形其实有另一个解决方案：

将元素添加到  std::vector ，然后对其去重（使用 std::unique() ）、排序（使用 std::sort() ）。

（但显然用 std::set 性能更棒啊

关键代码如下：

#include <vector>
using namespace std;
/*
//...
*/

bool shorter(const string& p_lhs, const string& p_rhs)
{
  const size_t lhsLength = p_lhs.length() ; 
  const size_t rhsLength = p_rhs.length() ;
  
  if (lhsLength == rhsLength) 
    return (p_lhs < p_rhs); 
    // Using default string comparison in case of multiple strings in the same length.

  return lhsLength < rhsLength;
}
vector<string> v; // Create a vector.
/* 
  // Add elements to the vector... 
*/
v.erase(unique(v.begin(), v.end()), v.end()); // Remove duplicates.
sort(v.begin(), v.end(), shorter); // sort by length, implemented by a function
// You can also pass a function object into it, which is shown above.

/*
//...
*/

就酱。