使用模板Bubblesort和結構數組的問題

Question

所以我的目標是讀入一些數據並按人口排序，但我必須使用可以接受多種數據類型的排序。我被指示使用模板來做到這一點，但每當我將陣列「results [i] .pop」傳遞給我的bubblesort函數時，我收到錯誤

沒有匹配函數調用'bubblesort（std （T *） T bubblesort（T ar [] string &） ） ^ election.cpp：32：3：note：template argument deduction/substitution failed：

election.cpp：106：34：note：can not convert'results [i] .election :: pop （類型「的std :: string {又名性病:: basic_string的}」）爲類型「的std :: basic_string的*」 冒泡（結果[I] .pop）;

下面的代碼：

#include <iostream> 
#include <iomanip> 
#include <string> 
#include <cstdlib> 
#include <fstream> 
#include <stdlib.h> 
using namespace std; 

struct election { 

string party; 
string state; 
string pop; 
string reps; 
int ratio; 
}; 


template <typename T> 
void bubblesort(T ar[]) 
{ 

//Bubblesort 
int n = 51; 
int swaps = 1; 
    while(swaps) 
    { 
    swaps = 0; 
      for (int i = 0; i < n - 1; i++) 
      { 
        if (ar[i] > ar[i + 1]) 
        { 
          swap(ar[i],ar[i+1]); 
          swaps = 1; 
        } 
      } 
    } 
//End Bubblesort 

} 


void delete_chars(string & st, string ch) 
{ 
    int i = st.find(ch); 
    while (i > -1) 
    { 
      st.replace(i,1,""); 
      i = st.find(ch); 
    } 
} 



int main() 
{ 
int i = 0; 
int n = 51; 
election results[n]; 

int population[n]; 
int electoralVotes[n]; 
int ratio[n]; 
string st; 
fstream inData; 

//Read in Data from Text File 
inData.open("electionresults.txt"); 



//Print Array as is 
cout << "Array Printed As is" << endl; 
cout << left << setw(10) << "Party" << setw(20) << "State" << setw(20) <<  "Population" << setw(15) << "Representatives" << endl; 
for (int i = 0; i < n; i++) 
{ 
    getline(inData,st); 
    results[i].party = st.substr(0,1); 
    results[i].state = st.substr(8,14); 
    results[i].pop = st.substr(24,10); 
    results[i].reps = st.substr(40,2); 
    cout << left << setw(10) << results[i].party << setw(20) <<  results[i].state << setw(20) << results[i].pop << setw(15) << results[i].reps << endl; 
} 

//Array Sorted by Population 
cout << "Array Sorted By Population" << endl; 
cout << endl; 
cout << endl; 
cout << left << setw(10) << "Party" << setw(20) << "State" << setw(20) <<    "Population" << setw(15) << "Representatives" << endl; 



for(int i = 0; i < n; i++){ 
bubblesort<string>(results[i].pop); 
} 

Answer 1

爲了您的冒泡的工作，你需要實現比運算符（>）的選舉結構的較大者：

struct election 
{ 

    string party; 
    string state; 
    string pop; 
    string reps; 
    int ratio; 
    bool operator>(election a) 
    { 
     return pop > a.pop; 
    } 
}; 

現在所說的冒泡通過將結果數組：

bubblesort<election>(results); 

甲注意你的函數應該傳遞大小而不是硬編碼函數的大小（void bubblesort(T ar[], int size)）。這爲您的功能提供了更多的功能和適應性。

Answer 2

如果您只想對pop進行排序，另一個答案可解決此問題。然而，這是一個有限的解決方案，並不會解決在任何領域進行排序的真正問題（今天它是「流行」的，但如果明天不是這種情況，您想按「比例」排序？） 。問題是你不能提供多個operator >來做到這一點，你基本上只堅持排序pop。

另一種解決方案是提供bubblesort函數與定義給出了兩個T的時，不管是一個T應該另一T前的排序後的數組中放置做什麼額外的模板的參數。

#include <functional> 
#include <algorithm> 
//... 
template <typename T, typename cmp> 
void bubblesort(T ar[], int n, cmp compare_fn) 
{ 
    int swaps = 1; 
    while (swaps) 
    { 
     swaps = 0; 
     for (int i = 0; i < n - 1; i++) 
     { 
      if (!compare_fn(ar[i], ar[i + 1])) 
      { 
       std::swap(ar[i], ar[i + 1]); 
       swaps = 1; 
      } 
     } 
    } 
} 

// keep our original 2 param bubble sort, but let it call the one above 
template <typename T> 
void bubblesort(T ar[], int n) 
{ 
    // call general version using < 
    bubblesort(ar, n, std::less<T>()); 
} 

我們主要有兩個功能，其中兩個參數冒泡排序函數調用，一般3個參數bubblesort版本，需要一個第三個參數，它描述了比較。

當你想調用bubblesort爲「簡單」的情況下，如果你的項目是

1. 在一個陣列和
2. 您可以比較bubblesort兩個參數版本用於T使用<和
3. 你想按升序排序（這就是爲什麼我們在一般情況下使用<而不是>）。

例如，需要進行排序的int數組，你只需要將它進行升序排列：

int someArray[10]; 
//... 
bubblesort<int>(someArray, 10); // sort ascending 

但是，我們不想做一個「簡單」的排序在int上，或者甚至std::string。我們要對election進行排序，不僅如此，還要對election.pop進行排序。

如果你看一下上面的第一個bubblesort功能，請注意，我們使用替代與>的功能compare_fn調用比較。請注意，該參數默認爲std::less函數對象。這就是爲什麼第二個bubblesort函數適用於簡單類型，因爲std::less使用<進行比較。

但是，如果你試圖用僅有的兩個使用election參數來調用bubblesort，你遇到另一個編譯器錯誤，基本上指出election沒有operator <與比較。該解決方案是要麼

1）提供這樣的操作者<（類似於給定）或其它答案election結構

2）編寫自定義的比較函數。

所以我們來看看這些解決方案。

---

解決方案1：

如果我們使用1），該election結構看起來就像這樣：

struct election 
{ 
    std::string party; 
    std::string state; 
    std::string pop; 
    std::string reps; 
    int ratio; 
    bool operator <(const election& e) const { return pop < e.pop; } 
}; 

int main() 
{ 
    //... 
    bubblesort<election>(results, n); 
} 

這將現在的排序上results使用pop作爲項目排序由於election中定義的operator <由std::less<>使用。

Here is an example using overloaded < in election

然而，這種解決方案具有相同的問題對方的回答中，你只能定義一個operator <採用一個const election&作爲參數。例如，如果您想對ratio進行排序，那麼您的運氣不好，或者如果您想按降序對pop進行排序，則表示運氣不佳。這是選項2）將被使用的地方。

---

解決方案2：

我們可以定義我們希望通過提供一個自定義的比較函數，函數對象，或者lambda function如果第一個返回true到，排序順序等排序T應該在傳入比較函數的第二個T之前，否則應該爲false。

讓我們嘗試的功能：

bool compare_pop(const election& e1, const election& e2) 
{ 
    return e1.pop < e2.pop; // if e1.pop comes before e2.pop, return true, else false 
} 

int main() 
{ 
    //... 
    bubblesort<election>(results, n, compare_pop); 
} 

什麼現在發生的是，這將調用bubblesort的第一個版本，需要一個比較函數作爲參數。現在bubblesort模板函數將調用compare_pop來確定項目是否出現故障。如果compare_pop返回falsebubblesort函數將交換項目，否則它會讓他們單獨。

Here is a live example with an array of 3 elections, sorted on pop

如果你想使用lambda函數，而不是寫另一比較功能，將工作太：

int main() 
{ 
    //... 
    bubblesort<election>(results, n, [&](const element& e1, const element& e2) { return e1.pop < e2.pop; }); 
} 

以上會做同樣的事情，作爲函數例子，除了由於lambda語法用作函數，因此不再需要編寫單獨的函數。

Example using lambda syntax

---

所以，現在，如果我們要作爲排序依據pop什麼，但降不升？簡單 - 調用bubblesort具有不同的功能或lambda：

bool compare_pop_up(const election& e1, const election& e2) 
{ 
    return e1.pop > e2.pop; // if e1.pop comes after e2.pop, return true, else false 
} 

int main() 
{ 
    //... 
    bubblesort<election>(results, n, compare_pop_up); 
} 

或使用拉姆達：

int main() 
{ 
    //... 
    bubblesort<election>(results, n, 
       [&](const element&e1, const element& e2) 
       { return e1.pop > e2.pop;}); 
} 

和神奇的bubblesort做這項工作，按降序排列上pop排序。

Here is a live example with an array of 3 elections, sorted on pop, descending

如果要排序的ratio？同樣的事情 - 提供不同的功能或lambda：

bool compare_ratio(const election& e1, const election& e2) 
{ 
    return e1.ratio < e2.ratio; 
} 

int main() 
{ 
    //... 
    bubblesort<election>(results, n, compare_ratio); 
} 

或使用拉姆達：

int main() 
{ 
    //... 
    bubblesort<election>(results, n, 
       [&](const element&e1, const element& e2) 
       { return e1.ratio < e2.ratio;}); 
} 

這將在ratio的升序排序ratio。

---

的另一個問題與您的代碼是，你正在使用非標準的C++語法定義的數組。你這樣做：

election results[n]; 

這不是標準C++的語法，C++只允許使用一個編譯時表達式來表示項目的數量來創建陣列。你正在使用的東西叫Variable Length Arrays，這是不是標準。

取而代之，您可以使用標準C++的std::vector。

#include <vector> 
//... 
std::vector<election> results(n); 
//... 
bubblesort<election>(results.data(), results.size(), compare_pop)