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.

/*
//...
*/

就酱。

发表评论

电子邮件地址不会被公开。 必填项已用*标注