2

文字列の配列を辞書順に並べ替えるコードはたくさんありますが、1 つの文字列の文字を辞書順に並べ替えるコードは見つかりません。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
4

3 に答える 3

9

この質問に対する他のほとんどの回答によると、コンパイラエラーを解決するには単に公開する必要がありますが、コンパレータは有効な厳密なoperator()コンパレータではないことに注意してください。厳密な比較演算子は、等しいものとして扱われる要素に対して返さなければなりません。また、コンパレーターのパラメーターの型には、値の代わりに const 参照を使用する必要があります。false

問題を解決するための複数のオプションを提示したいと思います（コンパイラエラーではなく、文字列を逆の字句順序でソートするという元の問題です）。falseそれらはすべて、 2 つの等しい要素を返します。

最初のオプションはあなたの解決策ですが、厳密さを修正しました:

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

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

2 番目のオプションは C++11 のラムダ関数を使用しますが、基本的には同じです。

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

Mooning Duck によって最初に提案された3 番目のオプションoperator>として、 typeに対して std ファンクターを単純に使用できcharます。

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

4 番目のオプション(最も単純なオプション) は、Peter Wood によって最初に提案されたように、逆文字列でデフォルトのコンパレータを使用することです( r! に注意してください)。

std::sort(str.rbegin(), str.rend());
于 2012-12-30T22:51:23.653 に答える
6

通常、最初のエラーのみが関連するため、次のようになります。

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デフォルトで使用)

于 2012-12-30T22:49:33.763 に答える
2

を使用するstd::sort()ことは明らかに正しいアプローチです。デフォルトのコンパレータは、渡されたイテレータの型のstd::less<value_type>wherevalue_typeです。decltype(*it)デフォルトを変更するには、別のコンパレータを渡すだけですstd::greater<char>。

定義されているとおりに使用するReverseComparatorには、正しくインスタンス化する必要があります。

std::sort(s.begin(), s.end(), ReverseComparator<char>());

もちろん、それを機能させるには、operator()()パブリックにアクセスできるようにする必要があります。constこれをメンバー関数にすることもできます。

template <typename T>
class ReverseComparator {
public:
    bool operator()(T lhs, T rhs) const { return rhs < lhs; }
};

演算子の式も同様に変更されていることに注意してください: using!(lhs < rhs)は厳密な弱い順序を定義しません: comparator(x, x)yieldしますtrueが、 yield する必要がありfalseます。

于 2012-12-30T22:52:06.927 に答える