初学者的一个关于模板的问题！

在C语言中，如果函数A中对于数据元素有未知的操作可以采用一个函数指针p作为函数A的参数， 这个p可以在A中对数据元所作操作。举一个简单的例子，要对一个线性表list 做冒泡排序操作，而数据元素是一个struct，两个元素之间的大小需要一个特定的函数来断定。

sort( list, int *(cmp)(ElemType, ElemType) ) {//cmp(a, b)>0时a大，<0时b大，==0时相等。
   //....
   //比较和交换部分如下
   if( cmp(a, b) > 0 ) {
      temp = list.at(x);
      list.at(x) = list.at(y);
      list.at(y) = temp;
   }
}

今天我在MSDN里看到了C++有另外的办法
template<class Traits> void sort(Traits _Comp);
在主函数里这样用就可以了
list.sort( greater<ElemType>() );

请问这样的sort()函数是怎么定义的？它对所在的木板有什么要求？
谢谢高手讲解。

12 个解决方案

#1

sortSee Also
<algorithm> MembersArranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate.
template<class RandomAccessIterator>
   void sort(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Pr>
   void sort(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last, 
      BinaryPredicate _Comp
   );
Parameters
_First 
A random-access iterator addressing the position of the first element in the range to be sorted. 
_Last 
A random-access iterator addressing the position one past the final element in the range to be sorted. 
_Comp 
User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. 
Remarks
The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.
Elements are equivalent, but not necessarily equal, if neither is less than the other. The sort algorithm is not stable and so does not guarantee that the relative ordering of equivalent elements will be preserved. The algorithm stable_sort does preserve this original ordering.
The average of a sort complexity is O(N log N), where N = _Last – _First.
Example
// alg_sort.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // For greater<int>( )
#include <iostream>

// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 )
{
   return elem1 > elem2;
}

int main( )
{
   using namespace std;
   vector <int> v1;
   vector <int>::iterator Iter1;

   int i;
   for ( i = 0 ; i <= 5 ; i++ )
   {
      v1.push_back( 2 * i );
   }

   int ii;
   for ( ii = 0 ; ii <= 5 ; ii++ )
   {
      v1.push_back( 2 * ii + 1 );
   }

   cout << "Original vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   sort( v1.begin( ), v1.end( ) );
   cout << "Sorted vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // To sort in descending order. specify binary predicate
   sort( v1.begin( ), v1.end( ), greater<int>( ) );
   cout << "Resorted (greater) vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   // A user-defined (UD) binary predicate can also be used
   sort( v1.begin( ), v1.end( ), UDgreater );
   cout << "Resorted (UDgreater) vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;
}
Output
Original vector v1 = ( 0 2 4 6 8 10 1 3 5 7 9 11 )
Sorted vector v1 = ( 0 1 2 3 4 5 6 7 8 9 10 11 )
Resorted (greater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )
Resorted (UDgreater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )

#2

list::sortSee Also
list Class | list MembersArranges the elements of a list in ascending order or with respect to some other user-specified order relation.
void sort( );
template<class Traits> 
   void sort(
      Traits _Comp
   );
Parameter
_Comp 
The comparison operator used to order successive elements. 
Remarks
The first member function puts the elements in ascending order by default.
The member template function orders the elements according to the user-specified comparison operation _Comp of class Traits.
Example
// list_sort.cpp
// compile with: /EHsc
#include <list>
#include <iostream>

int main( )
{
   using namespace std;
   list <int> c1;
   list <int>::iterator c1_Iter;
   
   c1.push_back( 20 );
   c1.push_back( 10 );
   c1.push_back( 30 );

   cout << "Before sorting: c1 =";
   for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
      cout << " " << *c1_Iter;
   cout << endl;

   c1.sort( );
   cout << "After sorting c1 =";
   for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
      cout << " " << *c1_Iter;
   cout << endl;

   c1.sort( greater<int>( ) );
   cout << "After sorting with 'greater than' operation, c1 =";
   for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
      cout << " " << *c1_Iter;
   cout << endl;
}
Output
Before sorting: c1 = 20 10 30
After sorting c1 = 10 20 30
After sorting with 'greater than' operation, c1 = 30 20 10

#3

拜托大侠！！
MSDN的原文我也看得到！
不过还是要谢谢你的

#4

我想知道一下具体实现。。而不是用法。

#5

我的理解是这样的，容器中的元素需要排序，你就必须给它定义一个比较的规则。对于C++的内部类型，<=>这三个符号都已经定义了，所以排序是不会有问题的。
但如果元素类型是自定义类型，就必须对这些操作符进行重载，这样标准库才能知道比较的规则。如果按递增排列，重载<即可，这是默认的。如果按递减排列，必须重载>，而且在sort调用时必须指明，如list.sort( greater<ElemType>() );
感觉说得不太符合lz的要求，高手再补充吧

#6

只要你在模板中的调用
它能提供就OK,不一定非要函数

#7

谢谢各位，我看来没有说明白我的意思。

我是说在C++里怎样才能自己做一个可以将函数名作为参数的函数？
除了C语言的指针方式以外，这种模板的方法是怎么实现的？
谢谢

#8

我不是想问这个模板怎么用。。。

#9

STL 里面叫做仿函数，任何可以在其上使用 （） 操作的东西都可以。
sort 的实现只要求模板参数上可以进行 （） 操作，并且这个操作带两个参数，返回 bool 型。

#10

一个简单的模板方法使用仿函数的例子如：

template <class Printer>
void PrintAny(Printer p, int x)
{
p(x);
}

void printfun(int x)
{
printf("%d", x);
}

class AdvPrinter{
public:
AdvPrinter(const char * prefex) : m_prefex(prefex){};
void operator()(int x)
{
printf("%s:%d", m_prefex, x);
}
private:
const char * m_prefex;
};

int main()
{
PrintAny(printfun, 10);
PrintAny(AdvPrinter("Hello"), 20);
}

#11

template<class Traits> void sort(Traits _Comp)
{
      if (_Comp(someelement,otherelement))
      ........
}
在主函数里这样用就可以了
list.sort( greater<ElemType>() );

greater<ElemType>() 生成一个临时对象，类型为greater<ElemType>，对于模板函数，推演为：
void sort(greater<ElemType> _Comp);

#12

重载结构的运算符