C++：イントおよびストリングを処理するための関数テンプレート

Question

intとdoubleを処理できる関数テンプレートを作成するためのプログラミング割り当てに取り組んでいます。私はそれをやったことがありますが、楽しみのために、文字列を扱えるようにしたかったのです。以下の関数があります。どのように私はそれが文字列を処理するように行くだろうか？

// This program demonstrates the QuickSort Algorithm. 
#include <iostream> 
#include <algorithm> 
#include <ctype.h> //needed for string handling? 
using namespace std; 



//********************************************************** 
// partition selects the value in the middle of the  * 
// array set as the pivot. The list is rearranged so  * 
// all the values less than the pivot are on its left  * 
// and all the values greater than pivot are on its right. * 
//********************************************************** 

template <class T> 
int partition(T set[], int start, int end) 
{ 
    int pivotValue, pivotIndex, mid; 

    mid = (start + end)/2; 
    swap(set[start], set[mid]); 
    pivotIndex = start; 
    pivotValue = set[start]; // main.cpp:28: error: cannot convert 'std::basic_string<char, std::char_traits<char>, std::allocator<char> >' to 'int' in assignment 
    for (int scan = start + 1; scan <= end; scan++) 
    { 
     if (set[scan] < pivotValue) // main.cpp:31: error: no match for 'operator<' in '*(((std::string*)(((long unsigned int)scan) * 8ul)) + set) < pivotValue' 
     { 
     pivotIndex++; 
     swap(set[pivotIndex], set[scan]); 
     } 
    } 
    swap(set[start], set[pivotIndex]); 
    return pivotIndex; 
} 

//************************************************ 
// quickSort uses the quicksort algorithm to  * 
// sort set, from set[start] through set[end]. * 
//************************************************ 

template <class T> 
void quickSort(T set[], int start, int end) 
{ 
    T pivotPoint; 

    if (start < end) 
    { 
     // Get the pivot point. 
     pivotPoint = partition(set, start, end); 
     // Sort the first sub list. 
     quickSort(set, start, pivotPoint - 1); // main.cpp:56: error: no match for 'operator-' in 'pivotPoint - 1' 
     // Sort the second sub list. 
     quickSort(set, pivotPoint + 1, end); // main.cpp:58: error: no match for 'operator+' in 'pivotPoint + 1' 
    } 
} 

int main() 
{ 
    const int SIZE = 10; // Array size 
    int count;   // Loop counter 

    // create arrays of various data types 
    int array[SIZE] = {7, 3, 9, 2, 0, 1, 8, 4, 6, 5}; 
// string array[SIZE] = {"7", "3", "9", "2","7", "3", "9", "2","a","r"}; 
    double array2[SIZE] = {7.1, 3.3, 9.0, 2.7, 0.2, 1.5, 8.9, 4.5, 6.9, 5.45}; 

    // Display the int array contents. 
    cout << "Displaying the int array before sorting" << endl; 
    for (count = 0; count < SIZE; count++) 
     cout << array[count] << " "; 
    cout << endl; 

    // Sort the int array. 
    quickSort(array, 0, SIZE - 1); 

    // Display the int array contents. 
    cout << "Displaying the int array after sorting" << endl; 
    for (count = 0; count < SIZE; count++) 
     cout << array[count] << " "; 
    cout << endl << endl; 

    // Display the double array contents. 
    cout << "Diplaying the double array before sorting" << endl; 
    for (count = 0; count < SIZE; count++) 
     cout << array2[count] << " "; 
    cout << endl; 

    // Sort the double array. 
    quickSort(array2, 0, SIZE - 1); 

    // Display the int array contents. 
    cout << "Displaying the double array after sorting" << endl; 
    for (count = 0; count < SIZE; count++) 
     cout << array2[count] << " "; 
    cout << endl; 

    return 0; 
} 

事前のおかげで、

アダム

Answer 1

あなたがTためstd::stringを使用している場合、あなたはおそらくすでに作業にかなり近いです。

char*を使用する場合は、テンプレートパラメータとして比較ファンクタを指定する必要があります（または、タイプ特性クラスのようにTの比較方法を指定する別の方法が必要です）。

また、独自のswapを実装しないでください。 std::swapはすでに存在し、特定のタイプに対してスマートなことを行います（たとえば、ベクトル内のすべてのオブジェクトをコピーするのではなく、2つのスワップを行うことは一定時間です）。

Answer 2

MSVCで動作します。少し許容されますので、コンパイラの問題が発生した場合はお知らせください。

このソリューションは、ファンクタ（ファンクションであるかのようにオブジェクトを呼び出すことができることを意味するoperator()のクラス/構造体）を使用します。また、テンプレートの特殊化を使用します - LessThanCompare - char*のtemplate < >バージョンを削除すると、ポインタ値を比較する（ランダムな結果を返す）場合にどうなるかを見てください。

クラスを使用してクイックソートとピボット関数を配置すると、デフォルトのテンプレートを使用してquickSort<char*, LessThanCompare<char*> >のように呼び出す必要はありません。quicksortと言うこともできますが、質問！

#include <iostream> 
#include <cstring> 
#include <string> 

using namespace std; 

template <class T> 
struct LessThanCompare 
{ 
    bool operator()(T lhs, T rhs) 
    { 
     return lhs < rhs; 
    } 
}; 


template < > 
struct LessThanCompare<char*> 
{ 
    bool operator()(char* lhs, char* rhs) 
    { 
     return strcmp(lhs, rhs) == -1; // Note strcmp returns -1 if lhs < rhs 
    } 
}; 

template <class T, class Comparator> 
int partition(T set[], int start, int end) 
{ 
    Comparator CompareLessThan; // Declare an instance of the Comparator 

    T pivotValue; 
    int pivotIndex, mid; // Is mid an index or a value - use descriptive names! 

    mid = (start + end)/2; 
    swap(set[start], set[mid]); 
    pivotIndex = start; 
    pivotValue = set[start]; 
    for (int scan = start + 1; scan <= end; scan++) 
    { 
     if (CompareLessThan(set[scan], pivotValue)) 
     { 
     pivotIndex++; 
     swap(set[pivotIndex], set[scan]); 
     } 
    } 
    swap(set[start], set[pivotIndex]); 
    return pivotIndex; 
} 

//************************************************ 
// quickSort uses the quicksort algorithm to  * 
// sort set, from set[start] through set[end]. * 
//************************************************ 

template <class T, class Comparator> 
void quickSort(T set[], int start, int end) 
{ 
    int pivotPoint; 

    if (start < end) 
    { 
     // Get the pivot point. 
     pivotPoint = partition<T, Comparator >(set, start, end); 
     // Sort the first sub list. 
     quickSort<T, Comparator>(set, start, pivotPoint - 1); // main.cpp:56: error: no match for 'operator-' in 'pivotPoint - 1' 
     // Sort the second sub list. 
     quickSort<T, Comparator>(set, pivotPoint + 1, end); // main.cpp:58: error: no match for 'operator+' in 'pivotPoint + 1' 
    } 
} 

int main() 
{ 
    const int SIZE = 10; // Array size 

    // Create arrays of strings 
    char* cstrArr[SIZE] = { 
     "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"}; 

    std::string strArr[SIZE]; 
    for (int i = 0; i < SIZE; ++i) 
    { 
     strArr[i] = std::string(cstrArr[i]); 
    } 

    quickSort<char*, LessThanCompare<char*> >(cstrArr, 0, SIZE-1); 
    quickSort<std::string, LessThanCompare<std::string> >(strArr, 0, SIZE-1); 

    for (int i = 0; i < SIZE; ++i) 
    { 
     cout << cstrArr[i] << "\t\t" << strArr[i] << '\n'; 
    } 

    return 0; 
}