在C++中排序某種列表的最快方法是什麼？

我有一個結構在C++中排序某種列表的最快方法是什麼？

typedef struct 
{ 
    int id; 
    string name; 
    string address; 
    string city; 
    // ... 
} Customer;

我將有多個客戶，所以我需要將這些結構存儲在某種形式的列表，然後我需要通過ID進行排序。這裏可能有多種解決方案，我自己也有一些想法，但我正在尋找性能方面的最佳解決方案。

來源

2012-03-28 Pittfall

這個問題提供過少的細節有意義的回答爲「在性能方面的最佳解決方案」的要求。你將如何處理排序列表？你多久檢索一次數據？這些檢索是否屬於整個列表，一些已知項目或任意項目？數據多久改變一次？你是否需要它一直排序？ – 2012-03-28 13:09:57

我打算使用這個列表來顯示報表中的信息，每次運行報表時，都需要再次檢索這些數據並將其放入列表中，因此如果數據發生變化，則不會有任何影響，因爲每次都要重新做工 – Pittfall 2012-03-28 13:10:52

最快的方法是給我發送清單。我會爲你分類併發回。 – wildplasser 2012-03-28 13:10:56

使用由STL算法包中提供的sort，例如：

struct Customer { 
    int id; 
    Customer(int i) : id(i) {} 
}; 

bool sortfunc(struct Customer i, struct Customer j) { 
    return (i.id < j.id); 
} 

int main() { 
    vector<Customer> customers; 
    customers.push_back(Customer(32)); 
    customers.push_back(Customer(71)); 
    customers.push_back(Customer(12)); 
    customers.push_back(Customer(45)); 
    customers.push_back(Customer(26)); 
    customers.push_back(Customer(80)); 
    customers.push_back(Customer(53)); 
    customers.push_back(Customer(33)); 

    sort(customers.begin(), customers.end(), sortfunc); 

    cout << "customers:"; 
    vector<Customer>::iterator it; 
    for (it = customers.begin(); it != customers.end(); ++it) 
     cout << " " << it->id; 

    return 1; 
}

來源

2012-03-28 13:10:20 dacwe

使用std::list.sort方法應該是最快的方法。

來源

2012-03-28 13:10:11 synopia

它可能是也可能不是最快的方式，但它是默認情況下應該使用的方式，除非您有關於此時列表可能已處於什麼順序的具體細節。這是假設他確實使用'std :: list'。但我認爲他可能只是使用「list」這個詞作爲序列容器的一般術語，而不一定是'std :: list'。 – 2012-03-28 13:16:10

我建議你存儲在客戶的std ::設置。

您應該創建操作<

bool Customer::operator < (const Customer& other) const { 
    return id < customer.id; 
}

現在，每次插入後，收集已經被編號的順序排列。

，您可以通過遍歷整個集合：

for(std::set<Customer>::iterator it = your_collection.begin(); it != your_collection.end(); it++)

這是最快的解決方案，因爲你不需要任何排序，並且每個插入需要O（log n）的時間。

來源

2012-03-28 13:14:25

定義operator<爲您的結構提供Customer實例之間的排序關係：

struct Customer { 

    ... 

    friend bool operator<(const Customer& a, const Customer& b) { 
     return a.id < b.id; 
    } 

};

使用this cheatsheet（尤其是底部流程圖）來決定你應該在你的特定程序使用的容器。如果它是std::set，則只要您將插入到set中，您的排序就完成了。如果是std::list，調用sort()成員函數就行了：

std::list<Customer> customers; 
customers.push_back(Customer(...)); 
... 
customers.sort();

如果是std::vector或std::deque，使用std::sort()從<algorithm>頭：

std::vector<Customer> customers; 
customers.push_back(Customer(...)); 
... 
std::sort(customers.begin(), customers.end());

如果需要多種方式排序中，定義每種排序功能：

struct Customer { 

    ... 

    static bool sort_by_name(const Customer& a, const Customer& b) { 
     return a.name < b.name; 
    } 

};

然後告訴std::list::sort()或std::sort()使用該比較器：

customers.sort(Customer::sort_by_name); 

std::sort(customers.begin(), customers.end(), Customer::sort_by_name);

來源

2012-03-28 13:20:55

在C++中排序某種列表的最快方法是什麼？

回答

相關問題