如何将比较器添加到自定义排序函数
How to add a comparator to a custom sort function
所以我实现了合并排序，出于所有意图和目的，它也可以是自定义排序函数，并且我已经开始将其转变为模板函数。
我 运行 遇到的问题是当我想增加传递自定义比较函数的可能性以便以不同方式排序时。 （例如 std::greater 和 std::less 或任何自定义的）。
我已经验证了当我用 T 替换整数时排序算法有效。我如何从这里添加自定义比较函数以便也对自定义对象等进行排序？
template < typename T,
class Compare>
void merge( vector<T> &arr, int start, int mid, int end, Compare comp )
{
int lptr = start;
int rptr = mid+1;
int tempptr = 0;
vector<T> temp( end - start + 1 );
for ( int i = 0; i<temp.size(); i++)
{
if ( lptr > mid ) //done with left-section, just move the right elements
{
temp[tempptr] = arr[rptr];
rptr++;
} else if ( rptr > end ) //done with right-section, just move the left elements
{
temp[tempptr] = arr[lptr];
lptr++;
} else if ( comp( arr[rptr], arr[lptr] )) // right item < left item, move right item
{
temp[tempptr] = arr[rptr];
rptr++;
} else //otherwise left item < right item, move left item
{
temp[tempptr] = arr[lptr];
lptr++;
}
tempptr++;
}
for ( int i = 0; i<temp.size(); i++)
{
arr[start + i] = temp[i];
}
}
template < typename T,
class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{
//if we're down to single elements, do nothing
if ( start < end ){
//call to right and left 'child'
int mid = (start + end) / 2;
mergeSort( arr, start, mid );
mergeSort( arr, mid + 1, end );
//call to merge
merge( arr, start, mid, end );
}
}
int main()
{
vector<float> arr = {7,8, 2, 6.6, 1, 4.1, 5, 3, 8, 9};
cout << "before sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
mergeSort( arr, 0, arr.size() - 1);
cout << "after sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
return 0;
};
提前致谢。
考虑到您有 class or struct CustomType
C++11 之前的版本
struct CustomCompare
{
bool operator ()(const CustomType& a, const CustomType& b)
{
return a.Watever < b.Watever;
}
};
//usage
merge(vector<CustomType> ..., CustomCompare());
Post c++11, using lambdas:
auto CustomCompare = [](const CustomType & a,const CustomType& b)
{
return a. .... ;
};
//usage
merge(vector<CustomType> ..., CustomCompare);
还有第三个选项：
您可以使用 std::less 但必须存在一个 operator < 以您的 CustomType 作为参数
示例：
struct CustomType
{
//...
bool operator < (const CustomType& other)const
{
return this->Whatever < other.Whatever;
}
};
而且你可以专攻std::less:
namespace std
{
template <>
struct less <CustomType>
{
bool operator()(const CustomType & a, const CustomType & b)
{
return ...
}
};
}
正如 Sam Varshavchik 所说，用比较函数替换比较运算符。意思是：
if ( lptr > mid ) //done with left-section, just move the
对此的更改：
if ( comp(lptr,mid) ) //done with left-section, just move the
顺便说一下，您有一个未处理的案例：
template < typename T,
class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{
//if we're down to single elements, do nothing
if ( start < end ){
//call to right and left 'child'
int mid = (start + end) / 2;
mergeSort( arr, start, mid );
mergeSort( arr, mid + 1, end );
//call to merge
merge( arr, start, mid, end );
}
else{ throw "Not handled case";}
}
我认为您将 merge 和 merge sort 的实施复杂化了。我用 2 个重载编写了相同的函数，并将它们放在命名空间中，这样它们就不会与 std 库的 merge 版本冲突。看看我的例子，看看做了什么。
#include <iostream>
#include <vector>
#include <algorithm>
namespace test {
// without comp predicate
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first ) {
for( ; first1 != last1; ++d_first ) {
if( first2 == last2 ) {
return std::copy( first1, last1, d_first );
}
if( *first2 < *first1 ) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy( first2, last2, d_first );
}
// with comp predicate
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp ) {
for( ; first1 != last1; ++d_first ) {
if( first2 == last2 ) {
return std::copy( first1, last1, d_first );
}
// This is were I replaced the default `< operator` with the `Compare` predicate.
if( comp( *first2, *first1 ) ) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy( first2, last2, d_first );
}
} // namespace test
int main() {
std::vector<int> v1{ 1,3,5,7,9 };
std::vector<int> v2{ 2,4,6,8 };
std::vector<int> v3;
// print this way
std::cout << "v1 : ";
for( auto& v : v1 ) {
std::cout << v << ' ';
}
std::cout << '\n';
// or print this way
std::cout << "v2 : ";
std::copy( v2.begin(), v2.end(), std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
// Merge without binary predicate comp function - functor etc.
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ) );
// using std's functors std::less - std::greater
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
std::less<int>() );
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
std::greater<int>() );
// using lambda's as predicate compare objects.
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
[]( auto&& a, auto&& b ) { return a < b; } );
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
[]( auto&& a, auto&& b ) { return a > b; } );
std::cout << "v3 : ";
std::copy( v3.begin(), v3.end(), std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
std::cout << "\nPress any key to quit.\n";
std::cin.get();
return 0;
}
这 2 个重载函数完全符合您的要求；合并和排序，同时能够选择在单个函数中使用什么谓词 comp 函数、函子等。
使用模板 class InputIt 符号简化了函数的许多内部部分；不必跟踪 sizes、index positions、indexing into arrays 等
我们真正需要做的就是在 Input Iterators 上使用适当的比较运算符进行 for 循环，然后决定何时使用 std::copy(...) 或从 [=22] 中分配一个元素=] 或 first1 然后递增我们的 iterator。最后，在 for 循环结束后，我们要使用 and return std::copy(...)。默认情况下，没有比较谓词的第一个重载使用 < operator，其中第二个重载采用谓词。
这还允许您传递具有 begin 和 end、iterator 的任何类型的容器，使其非常通用、模块化和可移植，同时尽量保持最佳状态现代c++的实践。
所以我实现了合并排序，出于所有意图和目的，它也可以是自定义排序函数，并且我已经开始将其转变为模板函数。
我 运行 遇到的问题是当我想增加传递自定义比较函数的可能性以便以不同方式排序时。 （例如 std::greater 和 std::less 或任何自定义的）。
我已经验证了当我用 T 替换整数时排序算法有效。我如何从这里添加自定义比较函数以便也对自定义对象等进行排序？
template < typename T,
class Compare>
void merge( vector<T> &arr, int start, int mid, int end, Compare comp )
{
int lptr = start;
int rptr = mid+1;
int tempptr = 0;
vector<T> temp( end - start + 1 );
for ( int i = 0; i<temp.size(); i++)
{
if ( lptr > mid ) //done with left-section, just move the right elements
{
temp[tempptr] = arr[rptr];
rptr++;
} else if ( rptr > end ) //done with right-section, just move the left elements
{
temp[tempptr] = arr[lptr];
lptr++;
} else if ( comp( arr[rptr], arr[lptr] )) // right item < left item, move right item
{
temp[tempptr] = arr[rptr];
rptr++;
} else //otherwise left item < right item, move left item
{
temp[tempptr] = arr[lptr];
lptr++;
}
tempptr++;
}
for ( int i = 0; i<temp.size(); i++)
{
arr[start + i] = temp[i];
}
}
template < typename T,
class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{
//if we're down to single elements, do nothing
if ( start < end ){
//call to right and left 'child'
int mid = (start + end) / 2;
mergeSort( arr, start, mid );
mergeSort( arr, mid + 1, end );
//call to merge
merge( arr, start, mid, end );
}
}
int main()
{
vector<float> arr = {7,8, 2, 6.6, 1, 4.1, 5, 3, 8, 9};
cout << "before sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
mergeSort( arr, 0, arr.size() - 1);
cout << "after sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
return 0;
};
提前致谢。
考虑到您有 class or struct CustomType
C++11 之前的版本
struct CustomCompare
{
bool operator ()(const CustomType& a, const CustomType& b)
{
return a.Watever < b.Watever;
}
};
//usage
merge(vector<CustomType> ..., CustomCompare());
Post c++11, using lambdas:
auto CustomCompare = [](const CustomType & a,const CustomType& b)
{
return a. .... ;
};
//usage
merge(vector<CustomType> ..., CustomCompare);
还有第三个选项：
您可以使用 std::less 但必须存在一个 operator < 以您的 CustomType 作为参数
示例：
struct CustomType
{
//...
bool operator < (const CustomType& other)const
{
return this->Whatever < other.Whatever;
}
};
而且你可以专攻std::less:
namespace std
{
template <>
struct less <CustomType>
{
bool operator()(const CustomType & a, const CustomType & b)
{
return ...
}
};
}
正如 Sam Varshavchik 所说，用比较函数替换比较运算符。意思是：
if ( lptr > mid ) //done with left-section, just move the
对此的更改：
if ( comp(lptr,mid) ) //done with left-section, just move the
顺便说一下，您有一个未处理的案例：
template < typename T,
class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{
//if we're down to single elements, do nothing
if ( start < end ){
//call to right and left 'child'
int mid = (start + end) / 2;
mergeSort( arr, start, mid );
mergeSort( arr, mid + 1, end );
//call to merge
merge( arr, start, mid, end );
}
else{ throw "Not handled case";}
}
我认为您将 merge 和 merge sort 的实施复杂化了。我用 2 个重载编写了相同的函数，并将它们放在命名空间中，这样它们就不会与 std 库的 merge 版本冲突。看看我的例子，看看做了什么。
#include <iostream>
#include <vector>
#include <algorithm>
namespace test {
// without comp predicate
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first ) {
for( ; first1 != last1; ++d_first ) {
if( first2 == last2 ) {
return std::copy( first1, last1, d_first );
}
if( *first2 < *first1 ) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy( first2, last2, d_first );
}
// with comp predicate
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp ) {
for( ; first1 != last1; ++d_first ) {
if( first2 == last2 ) {
return std::copy( first1, last1, d_first );
}
// This is were I replaced the default `< operator` with the `Compare` predicate.
if( comp( *first2, *first1 ) ) {
*d_first = *first2;
++first2;
} else {
*d_first = *first1;
++first1;
}
}
return std::copy( first2, last2, d_first );
}
} // namespace test
int main() {
std::vector<int> v1{ 1,3,5,7,9 };
std::vector<int> v2{ 2,4,6,8 };
std::vector<int> v3;
// print this way
std::cout << "v1 : ";
for( auto& v : v1 ) {
std::cout << v << ' ';
}
std::cout << '\n';
// or print this way
std::cout << "v2 : ";
std::copy( v2.begin(), v2.end(), std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
// Merge without binary predicate comp function - functor etc.
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ) );
// using std's functors std::less - std::greater
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
std::less<int>() );
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
std::greater<int>() );
// using lambda's as predicate compare objects.
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
[]( auto&& a, auto&& b ) { return a < b; } );
test::merge( v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter( v3 ),
[]( auto&& a, auto&& b ) { return a > b; } );
std::cout << "v3 : ";
std::copy( v3.begin(), v3.end(), std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
std::cout << "\nPress any key to quit.\n";
std::cin.get();
return 0;
}
这 2 个重载函数完全符合您的要求；合并和排序，同时能够选择在单个函数中使用什么谓词 comp 函数、函子等。
使用模板 class InputIt 符号简化了函数的许多内部部分；不必跟踪 sizes、index positions、indexing into arrays 等
我们真正需要做的就是在 Input Iterators 上使用适当的比较运算符进行 for 循环，然后决定何时使用 std::copy(...) 或从 [=22] 中分配一个元素=] 或 first1 然后递增我们的 iterator。最后，在 for 循环结束后，我们要使用 and return std::copy(...)。默认情况下，没有比较谓词的第一个重载使用 < operator，其中第二个重载采用谓词。
这还允许您传递具有 begin 和 end、iterator 的任何类型的容器，使其非常通用、模块化和可移植，同时尽量保持最佳状态现代c++的实践。