Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualHodgman

Posted 23 April 2013 - 11:06 PM

If you use a templated functor instead of a function-pointer, then the compiler will be able to optimize the code much better, and you can still use the function the same way (and also in other new ways too, such as using comparison lambdas or function-objects):

template<class Fn>
void QuickSort( const std::size_t First, const std::size_t Last, const Fn& Compare )
...
int compare( const int& a, const int& b ) {...}
...
	myIntContainer.QuickSort(0,10, &compare);

 

Instead of:

    while( Compare( m_Data[ p ], m_Data[ t ] ) >= 0 ) // note that (x>=y) == !(x<y)
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) < 0 )

Move the <0 inside the compare function (so it returns a bool) and then because (x>=y) is the same as !(x<y), your code becomes:

    while( !Compare( m_Data[ p ], m_Data[ t ] ) )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) )

 

If you want to look at an optimized implementation, the code for std::sort is a good place to look.


#3Hodgman

Posted 23 April 2013 - 09:26 PM

If you use a templated functor instead of a function-pointer, then the compiler will be able to optimize the code much better, and you can still use the function the same way (and also in other new ways too, such as using comparison lambdas or function-objects):

template<class Fn>
void QuickSort( const std::size_t First, const std::size_t Last, const Fn& Compare )
...
int compare( const int& a, const int& b ) {...}
...
	myIntContainer.QuickSort(0,10, &compare);

 

Instead of:

    while( Compare( m_Data[ p ], m_Data[ t ] ) >= 0 )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) < 0 )

Move the <0 inside the compare function (so it returns a bool) and then your code becomes:

    while( !Compare( m_Data[ p ], m_Data[ t ] ) )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) )

 

If you want to look at an optimized implementation, look at the code for std::sort.


#2Hodgman

Posted 23 April 2013 - 09:26 PM

If you use a templated functor instead of a function-pointer, then the compiler will be able to optimize the code much better, and you can still use the function the same way (and also in other new ways too, such as using comparison lambdas or function-objects):
template<class Fn>
void QuickSort( const std::size_t First, const std::size_t Last, const Fn& Compare )
...
int compare( const int& a, const int& b ) {...}
...
	myIntContainer.QuickSort(0,10, &compare);
Instead of:
    while( Compare( m_Data[ p ], m_Data[ t ] ) >= 0 )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) < 0 )
Move the <0 inside the compare function (so it returns a bool) and then your code becomes:
    while( !Compare( m_Data[ p ], m_Data[ t ] ) )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) )
If you want to look at an optimized implementation, look at the code for std::sort.

#1Hodgman

Posted 23 April 2013 - 09:25 PM

If you use a templated functor instead of a function-pointer, then the compiler will be able to optimize the code much better, and you can still use the function the same way (and also in other new ways too, such as using comparison lambdas or function-objects):
template<class Fn>
void QuickSort( const std::size_t First, const std::size_t Last, const Fn& Compare )
...
int compare( const int& a, const int& b ) {...}
...
	myIntContainer.QuickSort(0,10, &compare);
Instead of:
    while( Compare( m_Data[ p ], m_Data[ t ] ) >= 0 )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) < 0 )
Move the <0 inside the compare function (so it returns a bool) and then your code becomes:
    while( !Compare( m_Data[ p ], m_Data[ t ] ) )
...
    while( Compare( m_Data[ q ], m_Data[ t ] ) )

PARTNERS