重写算法作为模板函数来比较2个值 [英] Rewrite algorithm as a template function to compare 2 values

问题描述

我正在尝试将下面的选择排序算法重写为比较两个元素的模板函数。我原来的程序做了一个排序，但我不知道如何将程序重写为一个函数。我可以独立编写这个函数，我做了，但我在重写程序时遇到了麻烦。

这里是我的排序算法



< pre lang =c ++> #include < < span class =code-leadattribute> iostream >

#include util.h

/ * *
获取最小的位置向量范围中的元素。
@param a向量
@param从范围开头
@param到范围的结尾
@return
中最小元素的位置范围a [from] ... a [to]
* /
int min_position（vector< int>& a， int from， int to）
{
int min_pos = from;
int i;
for （i = from + 1 ; i< = to; i ++）
if （a [i]< a [min_pos]）min_pos = i;
return min_pos;
}

/ * *
使用选择对矢量进行排序排序算法
@param a向量排序
* /

void selection_sort（vector< int& a）
{
int next; // 下一个要设置为最小值的位置

for （next = 0 ; next< a.size（） - 1 ; next ++）
{
// 找到最小的位置
int min_pos = min_position（a，next，a.size（） - 1 ）;
if （min_pos！= next）
swap（a [min_pos]，a [next]）;
}
}

int main（）
{
rand_seed（）;
vector< int> v（ 20 ）;
for （ int i = 0 ; i< v.size（）; i ++）
v [i] = rand_int（ 1 ， 100 ）;
print（v）;
selection_sort（v）;
print（v）;
return 0 ;
}

我写了一个比较值的模板，但是我在上面的程序中实现它时遇到了麻烦。 br $> b $ b

 模板< typename T> 
  void  sort（TA []， int  N）
 {
 
  for （ int  n =  1 ; n< N; n ++）{
 T mover = A [n]; 
  int  k = n; 
  while （k>  0 ）{
  if （A [k-  1 ]> mover）{
 A [k] = A [k-  1 ]; 
 k--; 
}  else  
  break ; 
} 
 A [k] =搬运工; 
} 
 
} 

我是c ++的新手，模板/排序让我适合，所以我正在寻找一些帮助/指导



谢谢

解决方案

让我们试一下一个微软的例子。你要做的大部分代码都放在一个头文件中：

  //  实施所需 
  //  内联函数声明 
 
  #ifdef _AFX_ENABLE_INLINES 
  ＃ define _AFX_INLINE AFX_INLINE 
  
  #if！defined（_AFX_CORE_IMPL）|| ！defined（_AFXDLL）|| defined（_DEBUG）
   #define _AFX_PUBLIC_INLINE AFX_INLINE 
  ＃else 
  ＃define _AFX_PUBLIC_INLINE 
  ＃endif 
  ＃endif 
  
 
模板<类TYPE，类 ARG_TYPE> 
  class  CCuteBundle; 

然后在上面的代码下面，基于CArray类，您可以在同一文件中执行以下操作：

  ///   ///////////////////////////////// ///////////////////////////////////////// 
  < span class =code-comment> //   CCuteBundle< TYPE，ARG_TYPE>  
 
 template< class TYPE， class  ARG_TYPE =  const  TYPE> 
  class  CCuteBundle： public  CObject 
 {
  public ：
  //  构建 
 CCuteBundle（）; 
 
  //  属性 
 INT_PTR GetSize（）常量; 
 INT_PTR GetCount（） const ; 
 INT_PTR GetUpperBound（） const ; 
 BOOL IsEmpty（） const ; 
 
  //  操作 
  void  SortMePlease（INT_PTR nIndex，ARG_TYPE sortElement）; 
 
  //  访问元素 
 TYPE& GetAt（INT_PTR nIndex）; 
  void  SetAt（INT_PTR nIndex，ARG_TYPE newElement）; 
 TYPE& ElementAt（INT_PTR nIndex）; 
 
  //  重载的操作员助手 
  const  TYPE&  operator  []（INT_PTR nIndex） const ; 
 TYPE&  operator  []（INT_PTR nIndex）; 
 
 
  //  实施 
 受保护：
 TYPE * m_pData;  //  实际的数据数组 
 INT_PTR m_nSize;  //  元素数量（upperBound  -  1） 
 
}; 

到目前为止还可以。然后你需要实际实现这些功能。该实现存在于相同的头文件中：

  ///   /////////////////////////////// ////////////////////////////////////////////////// //////////// CCuteBundle <   TYPE，    ARG_TYPE  > 内联函数
  
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE INT_PTR CCuteBundle< TYPE，ARG_TYPE> :: GetSize（） const  
 { return  m_nSize; } 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE INT_PTR CCuteBundle< TYPE，ARG_TYPE> :: GetCount（） const  
 { return  m_nSize; } 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE BOOL CCuteBundle< TYPE，ARG_TYPE> :: IsEmpty（） const  
 { return  m_nSize ==  0 ; } 
 
 AFX_INLINE INT_PTR CCuteBundle< TYPE，ARG_TYPE> :: GetUpperBound（） const  
 { return  m_nSize-  1 ; } 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE TYPE& CCuteBundle< TYPE，ARG_TYPE> :: GetAt（INT_PTR nIndex）
 {
 ASSERT（nIndex> =  0 && nIndex< m_nSize）; 
  if （nIndex> =  0 && nIndex< m_nSize）
  return  m_pData [nIndex]; 
 AfxThrowInvalidArgException（）; 
} 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE  void  CCuteBundle< TYPE，ARG_TYPE> :: SetAt（INT_PTR nIndex，ARG_TYPE newElement）
 {
 ASSERT（nIndex> =  0 && nIndex< m_nSize）; 
  if （nIndex> =  0 && nIndex< m_nSize）
 m_pData [nIndex] = newElement; 
  else  
 AfxThrowInvalidArgException（）; 
} 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE  const  TYPE& CCuteBundle< TYPE，ARG_TYPE> ::  operator  []（INT_PTR nIndex） const  
 {< span class =code-keyword> return  GetAt（nIndex）; } 
 
模板<类TYPE，类 ARG_TYPE> 
 AFX_INLINE TYPE& CCuteBundle< TYPE，ARG_TYPE> ::  operator  []（INT_PTR nIndex）
 { return  ElementAt （参数nIndex）; } 

现在在下面的部分中，正在使用上面定义的函数，因此基础工作对于您的实现至关重要。 />

 template< class TYPE， class  ARG_TYPE> 
  void  CCuteBundle< type，> :: SortMePlease（INT_PTR nIndex，ARG_TYPE sortElement）
 {
 ASSERT_VALID（此）; 
 ASSERT（sortElement！= NULL）; 
 ASSERT（nIndex>  0 ）; 
 
  if （m_pData [nIndex  -   1 ]> sortElement）
 {
 m_pData [nIndex] = m_pData [nIndex  -   1 ]; 
  //  在主程序中递减或递增。 
} 
  else  
 {
 m_pData [nIndex] = sortElement; 
} 
} 

您可能想要添加其他一些CArray类型函数以防万一......

然后在主程序中使用新类。

无法看到实现模板排序功能的任何问题。您声明的功能完全可用。但是大多数排序函数需要比较函数作为参数来比较同一函数中的不同数据类型。并不总是需要进行二元比较，即比较记录。为了增加灵活性，你应该使用比较功能。



（对不起，如果我错了得到矢量类的数组）

略微修改了你的代码和我的补充：

  #pragma once 
   #include   <   iostream  >  
   #include   <   vector  >  
   #include   <   tchar.h  >  
  
 使用  namespace  std; 
 
  / *   * 
获取向量范围中最小元素的位置。 
 @param a向量
 @param从范围开头
 @param到范围的结尾
 @return 
中最小元素的位置范围a [from] ... a [to] 
 * /  
  int  min_position（vector< int>& a， int  from， int  to）
 {
  INT  min_pos =从; 
  int  i; 
  for （i = from +  1 ; i< = to; i ++）
  if （a [i]< a [min_pos]）min_pos = i; 
  return  min_pos; 
} 
 
  / *   * 
使用选择对矢量进行排序排序算法
 @param a向量排序
 * /  
 
  void  selection_sort（vector< int& a）
 {
  unsigned   int  next;  //  下一个要设置为最小值的位置 
 
  for （next =  0 ; next< a.size（） -   1 ; next ++）
 {
  //  找到最小的位置 
  int  min_pos = min_position（a，next，a.size（） -   1 ）; 
  if （min_pos！= next）
 swap（a [min_pos]，a [next]）; 
} 
} 
 
 
  ///   / //////////////////////////////////////////////// 
   //  替换 
  //  < span class =code-preprocessor> #includeutil.h< / span>  
 
  #define rand_seed（）srand（23）
  ＃define rand_int（L，H）（L + rand（）％（HL））
  
  void  print（vector< int>& av）
 {
  for （ unsigned   int  i =  0 ; i< av.size（）; i ++）
 cout<< AV [1]  - ;<   \\\\ n; 
} 
 
  ///   ////////// /////////////////////////////////////// 
   //  您的模板 - 仅适用于整数类型 
 模板<类型名T> 
  void  sort（T * A， int  N）
 {
  for （ int  n =  1 ; n< N; n ++）
 {
 T mover = A [n]; 
  int  k = n; 
  while （k>  0 ）
 {
  if （A [k-  1 ]> mover）
 {
 A [k ] = A [k-  1 ]; 
 k--; 
} 
 其他  break ; 
} 
 A [k] =搬运工; 
} 
} 
  ///   ///////// //////////////////////////////////////// 
   //  带比较功能的模板 - 适用于所有类型 
  //  该函数必须实现！ 
  template <类型名称T> 
  void  sortwithfunction（T * A， const   unsigned   int  N， int （* cmp）（T&，T&））
 {
  for （ unsigned   int  n =  1 ; n< N; n ++）
 {
 T mover = A [n]; 
  int  k = n; 
  while （k>  0 ）
 {
  if （0< cmp（A [k-  1 ]，mover））
 {
 A [k] = A [k-  1 ]; 
 k--; 
} 
 其他  break ; 
} 
 A [k] =搬运工; 
} 
} 
 
  ///   ///// //////////////////////////////////////////// 
   int  __cmpi（int& a，int& b）{ return  ab; }  //  比较两个整数值 
  / //   ////////////////////////////////// /////////////// 
  
  int  main（）
 { 
 vector< int> v（ 20 ）; 
 
 rand_seed（）; 
  for （ unsigned   int  i =  0 ; i< v.size（）; i ++）
 v [i] = rand_int（ 1 ， 100 ）; 
 
 cout<<   ---排序之前------------------ \ r\\\
; 
 print（v）; 
 
  switch （ 2 ） //  测试用例 
 {
  case   0 ：selection_sort（v）;  break ; 
  case   1 ：sort（& v [ 0 ]，v.size（））;  break ; 
  case   2 ：sortwithfunction（& v [ 0 ]，v.size（），__ CMPI）;  break ; 
} 
 
 cout<<   ---排序后------------------ \ r\\\
; 
 print（v）; 
 
 _gettch（）; 
  return   0 ; 
} 

祝你好运。

I am trying to rewrite the selection sort algorithm below as a template function that compares two elements. My original programs does a sort, but I am not sure how to rewrite the program as a function. I can write the function independently, which I did, but I am having trouble rewriting the program.
here is my sorting algorithm

#include <iostream>

#include "util.h"

/** 
    Gets the position of the smallest element in a vector range.
    @param a the vector
    @param from the beginning of the range
    @param to the end of the range
    @return the position of the smallest element in 
    the range a[from]...a[to]
*/
int min_position(vector<int>& a, int from, int to)
{  
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
      if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}

/** 
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/

void selection_sort(vector<int>& a)
{  
   int next; // The next position to be set to the minimum

   for (next = 0; next < a.size() - 1; next++)
   {  
      // Find the position of the minimum
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}

int main()
{  
   rand_seed();
   vector<int> v(20);
   for (int i = 0; i < v.size(); i++)
      v[i] = rand_int(1, 100);
   print(v);
   selection_sort(v);
   print(v);
   return 0;
}

I wrote a template to compare the values, but I am having trouble implementing it on my program above.

template <typename T>
void sort(T A[],int N)
{

 for(int n = 1;n < N;n++) {
     T mover = A[n];
     int k = n;
     while(k > 0) {
       if(A[k-1] > mover) {
         A[k] = A[k-1];
        k--;
       } else
         break;
     }
     A[k] = mover;
}

}

I am new to c++ and templates/sorting is giving me fits, so I am looking for some assistance/guidance

Thanks

解决方案

Let's try one base on one of Microsoft's examples. Most of the code for what you want to do goes into a header file:

// needed for implementation
// Inline function declarations

#ifdef _AFX_ENABLE_INLINES
#define _AFX_INLINE AFX_INLINE

#if !defined(_AFX_CORE_IMPL) || !defined(_AFXDLL) || defined(_DEBUG)
#define _AFX_PUBLIC_INLINE AFX_INLINE
#else
#define _AFX_PUBLIC_INLINE
#endif
#endif


template<class TYPE, class ARG_TYPE>
class CCuteBundle;

Then below the code above, bases upon the CArray class, in the same file you might do the following:

/////////////////////////////////////////////////////////////////////////////
// CCuteBundle<TYPE, ARG_TYPE>

template<class TYPE, class ARG_TYPE = const TYPE>
class CCuteBundle : public CObject
{
public:
// Construction
	CCuteBundle();

// Attributes
	INT_PTR GetSize() const;
	INT_PTR GetCount() const;
         INT_PTR GetUpperBound() const;
	BOOL IsEmpty() const;

// Operations
         void SortMePlease(INT_PTR nIndex, ARG_TYPE sortElement);

         // Accessing elements
	TYPE& GetAt(INT_PTR nIndex);
	void SetAt(INT_PTR nIndex, ARG_TYPE newElement);
	TYPE& ElementAt(INT_PTR nIndex);

         // overloaded operator helpers
	const TYPE& operator[](INT_PTR nIndex) const;
	TYPE& operator[](INT_PTR nIndex);

 
// Implementation
protected:
	TYPE* m_pData;   // the actual array of data
	INT_PTR m_nSize;     // # of elements (upperBound - 1)

};

So OK so far. Then You need to Actually Implement the functions. The implementation exists with in the same header file:

////////////////////////////////////////////////////////////////////////////////////////////////CCuteBundle<TYPE, ARG_TYPE> inline functions

template<class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetSize() const
    { return m_nSize; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetCount() const
    { return m_nSize; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE BOOL CCuteBundle<TYPE, ARG_TYPE>::IsEmpty() const
    { return m_nSize == 0; }

AFX_INLINE INT_PTR CCuteBundle<TYPE, ARG_TYPE>::GetUpperBound() const
	{ return m_nSize-1; }

template<class TYPE, class ARG_TYPE>
AFX_INLINE TYPE& CCuteBundle<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex)
{ 
	ASSERT(nIndex >= 0 && nIndex < m_nSize);
	if(nIndex >= 0 && nIndex < m_nSize)
		return m_pData[nIndex]; 
	AfxThrowInvalidArgException();		
}

template<class TYPE, class ARG_TYPE>
AFX_INLINE void CCuteBundle<TYPE, ARG_TYPE>::SetAt(INT_PTR nIndex, ARG_TYPE newElement)
{ 
	ASSERT(nIndex >= 0 && nIndex < m_nSize);
	if(nIndex >= 0 && nIndex < m_nSize)
		m_pData[nIndex] = newElement; 
	else
		AfxThrowInvalidArgException();		
}

template<class TYPE, class ARG_TYPE>
AFX_INLINE const TYPE& CCuteBundle<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex) const
	{ return GetAt(nIndex); }

template<class TYPE, class ARG_TYPE>
AFX_INLINE TYPE& CCuteBundle<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex)
	{ return ElementAt(nIndex); }

So now in the sections below, are using the functions just defined above, so ground work is key to your implementation.

template<class TYPE, class ARG_TYPE>
void CCuteBundle<type,>::SortMePlease(INT_PTR nIndex, ARG_TYPE sortElement) 
{
         ASSERT_VALID(this);
         ASSERT(sortElement != NULL);
         ASSERT(nIndex > 0);
 
         if(m_pData[nIndex - 1] > sortElement)
         {
               m_pData[nIndex] = m_pData[nIndex - 1];
               //Do your decrementing or incrementing in your main program.
         }
         else
         {
               m_pData[nIndex] = sortElement;
         }
}

You may want to add some of the other CArray type functions just in case ...
Then use your new class in your Main Program.

Cannot see any problem for implementing a template sort function. The function you've declared is fully usable. But most sort functions need a compare function as parameter to compare different data types in the same function. Not always binary comparisation is required i.e. to compare records ore something else. To increase flexibility you should use a compare function.

(sorry if i'm going wrong to get the array of the vector class)
slightly modified your code and my additions:

#pragma once
#include <iostream>
#include <vector>
#include <tchar.h>

using namespace std;

/** 
    Gets the position of the smallest element in a vector range.
    @param a the vector
    @param from the beginning of the range
    @param to the end of the range
    @return the position of the smallest element in 
    the range a[from]...a[to]
*/
int min_position(vector<int>& a, int from, int to)
{  
   int min_pos = from;
   int i;
   for (i = from + 1; i <= to; i++)
      if (a[i] < a[min_pos]) min_pos = i;
   return min_pos;
}
 
/** 
   Sorts a vector using the selection sort algorithm
   @param a the vector to sort
*/
 
void selection_sort(vector<int>& a)
{  
   unsigned int next; // The next position to be set to the minimum

   for (next = 0; next < a.size() - 1; next++)
   {  
      // Find the position of the minimum
      int min_pos = min_position(a, next, a.size() - 1);
      if (min_pos != next)
         swap(a[min_pos], a[next]);
   }
}


////////////////////////////////////////////////////
// substitutions
//<span class="code-preprocessor">#include "util.h"</span>

#define  rand_seed()      srand(23)
#define  rand_int(L,H)    (L+rand()%(H-L))

void print(vector<int>& av)
{
   for (unsigned int i = 0; i < av.size(); i++)
      cout << av[i] << "\r\n";
}

////////////////////////////////////////////////////
// your template - only functioning for integer types
template <typename T>
void sort(T* A,int N)
{
  for(int n = 1;n < N;n++)
  {
    T        mover = A[n];
    int      k = n;
    while(k > 0)
    {
      if(A[k-1] > mover)
      {
        A[k] = A[k-1];
        k--;
      }
      else break;
    }
    A[k] = mover;
  }
}
////////////////////////////////////////////////////
// template with compare function - that works for all types
// the function has to be implemented!
template <typename T>
void sortwithfunction(T* A,const unsigned int N,int (*cmp)(T&,T&))
{
  for(unsigned int n = 1;n < N;n++)
  {
    T        mover = A[n];
    int      k = n;
    while(k > 0)
    {
      if( 0<cmp(A[k-1],mover) )
      {
        A[k] = A[k-1];
        k--;
      }
      else break;
    }
    A[k] = mover;
  }
}

////////////////////////////////////////////////////
int __cmpi(int& a,int& b){ return a-b; } // compare two integer values
////////////////////////////////////////////////////

int main()
{  
  vector<int> v(20);

  rand_seed();
  for (unsigned int i = 0; i < v.size(); i++)
  v[i] = rand_int(1, 100);

  cout << "--- before sort ------------------\r\n";
  print(v);

  switch(2) // test cases
  {
    case 0: selection_sort(v); break;
    case 1: sort(&v[0],v.size()); break;
    case 2: sortwithfunction(&v[0],v.size(),__cmpi); break;
  }

  cout << "--- after sort ------------------\r\n";
  print(v);

  _gettch();
  return 0;
}

Good luck.

这篇关于重写算法作为模板函数来比较2个值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！