使用模板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)