在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++中排序某种列表的最快方法是什么？

回答

相关问题