C++反向排序字符串中的字符

Question

有很多代码按字典顺序对字符串数组进行排序,但我找不到按字典顺序对字符串进行排序的字符串.到目前为止,我发现使用std::sort()in <algorithm>可能是最接近的候选者.

这是我试过的:

template <typename T>
class ReverseComparator{
     bool operator()(T l, T r){return !(l < r);}
};
//.....later
std::sort(str.begin(), str.end(), comparator);

这是一个问题:如何初始化我的比较器,以便它可以比较字符串中的字符？我试过,ReverseComparator<char> comparator但编译器抛出了大量的错误信息. gcc-4.5.1显示了以下错误:

In file included from /usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/algorithm:63:0,
                 from prog.cpp:1:
prog.cpp: In function 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2192:4:   instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5252:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2125:4: error: within this context
prog.cpp: In function 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5100:7:   instantiated from 'void std::partial_sort(_RAIter, _RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2297:8:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:1914:2: error: within this context
prog.cpp: In function 'void std::__move_median_first(_Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2260:7:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2302:62:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:108:7: error: within this context
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:110:4: error: within this context
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2260:7:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2302:62:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:112:9: error: within this context
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:115:12: error: within this context
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:117:12: error: within this context
prog.cpp: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Tp = char, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2261:78:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2302:62:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2229:4: error: within this context
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2232:4: error: within this context
prog.cpp: In function 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2133:6:   instantiated from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2192:4:   instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5252:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2083:7: error: within this context
In file included from /usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:62:0,
                 from /usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/algorithm:63,
                 from prog.cpp:1:
prog.cpp: In function 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Distance = int, _Tp = char, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_heap.h:434:4:   instantiated from 'void std::make_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:1912:7:   instantiated from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5100:7:   instantiated from 'void std::partial_sort(_RAIter, _RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2297:8:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_heap.h:303:4: error: within this context
prog.cpp: In function 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Distance = int, _Tp = char, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_heap.h:316:7:   instantiated from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Distance = int, _Tp = char, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_heap.h:434:4:   instantiated from 'void std::make_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:1912:7:   instantiated from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5100:7:   instantiated from 'void std::partial_sort(_RAIter, _RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2297:8:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Size = int, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5250:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_heap.h:180:7: error: within this context

Answer 1

虽然解决编译器错误只需operator()根据此问题的大多数其他答案公开,但您应该注意到您的比较器不是有效的严格比较器.严格的比较器必须返回false被视为相等的元素.您还应该使用const引用而不是比较器的参数类型的值.

我想为您提供多个选项来解决您的问题(不是编译器错误,而是原始问题,以反向词法顺序排序字符串).所有这些都返回false两个相同的元素.

第一个选择是你的解决方案,但我修正了严格性:

template <typename T>
class ReverseComparator{
public:
     bool operator()(const T& l, const T& r){return (r < l);}
};

std::sort(str.begin(), str.end(), ReverseComparator());

在第二个选项使用C++ 11的lambda函数,但本质上是一样的:

std::sort(str.begin(), str.end(), [](const T& l, const T& r){return (r < l);});

作为第三个选项,正如Mooning Duck首先提出的那样,你可以operator>在你的类型上使用std仿函数char:

std::sort(str.begin(), str.end(), std::greater<char>());

在第四个选项(最简单的一种)是使用的默认比较逆转串,首先由彼得·伍德建议(注意r!):

std::sort(str.rbegin(), str.rend());

Answer 2

通常,只有第一个错误是相关的,所以我们有:

In file included from /usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/algorithm:63:0,
                 from prog.cpp:1:
prog.cpp: In function 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]':
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:2192:4:   instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
/usr/lib/gcc/i686-pc-linux-gnu/4.5.1/../../../../include/c++/4.5.1/bits/stl_algo.h:5252:4:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<char*, std::basic_string<char> >, _Compare = ReverseComparator<char>]'
prog.cpp:12:49:   instantiated from here
prog.cpp:6:11: error: 'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private

其中大部分只是上下文,所以这是关键部分:

'bool ReverseComparator<T>::operator()(T, T) [with T = char]' is private

那很容易解决:

#include <algorithm>
#include <string>

template <typename T>
class ReverseComparator{
    public: //forgot this
     bool operator()(T l, T r){return !(l < r);}
};

int main() {
    std::string str = "HELLO";
    ReverseComparator<char> comparator;
    std::sort(str.begin(), str.end(), comparator);
}

编译没有问题,但是,排序是基于什么叫做"严格的弱序",并且!(l < r)是不是一个严格弱序.即,comparitor(a,a)应该返回false,但你的返回true.幸运的是,以这种方式排序的想法已经在名称下的标准库中std::greater.(默认情况下std::sort不使用比较器std::less)