在c++中排序列表的最快方法是什么？

Question

我有一个结构体

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

我将有多个客户，所以我需要将这些结构存储在某种列表中，然后我需要按id排序。这里可能有多种解决方案，我自己也有一些想法，但我正在寻找性能方面的最佳解决方案。

Answer 1

使用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;
}

Answer 2

我建议您将客户存储在std::set中。

您应该创建运算符<

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

现在，在每次插入之后，集合已经按id排序。

您可以通过以下方式遍历整个集合：

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

这是最快的解决方案，因为您不需要对任何东西进行排序，并且每次插入都需要O(log )时间。

Answer 3

使用std::list.sort方法应该是最快的方法。