按规则对结构的std::列表进行排序

Question

我有一个std::list<struct Data> data。我需要根据规则rule将data按head排序。

为此，我使用std::list::sort(Compare comp)。

下面的实现是有效的，但是效率很低。在rule列表中查找元素需要遍历列表，计算距离需要再次遍历列表。

数据还能如何排序？也许可以使用向量、无序映射和其他？

#include <iostream>
#include <list>
#include <algorithm>
struct Data {
std::string code;
std::string text;
std::string head;
};
int main() {
struct Data data1{"0010", "it is text1", "head3"};
struct Data data2{"0025", "it is text2", "head1"};
struct Data data3{"0065", "it is text3", "head2"};
struct Data data4{"0011", "it is text4", "head2"};

std::list<struct Data> data = {data1, data2, data3, data4};

std::list<std::string> rule = {"head1", "head2", "head3", "head4"};

data.sort([&rule](const Data& first, const Data& second) {
auto index_a = std::distance(rule.begin(), std::find(rule.begin(),rule.end(),first.head));
auto index_b = std::distance(rule.begin(), std::find(rule.begin(),rule.end(),second.head));
return index_a < index_b;
});

for (auto &it : data)
std::cout << it.code << "t" << it.text << "t" << it.head << "n";

return 0;
}

Answer 1

使用std::vector和std_unordered_map重新编写程序。

更改了函数std::list::sort和std::sort:的速度

无标志-O3:

• 第一个选项：0.000030秒
• 第二个选项：0.000017秒

带有标志-O3:

• 第一个选项：0.000009秒
• 第二个选项：0.000009秒

两个问题：

1. 一切都对吗？

2. 排序时如何应用set::less<std::string>？

   std::vector<struct Data> data = {data1, data2, data3, data4};
   std::unordered_map<std::string, unsigned> rule = {
   {"head1", 0},
   {"head2", 1},
   {"head3", 2},
   {"head4", 3}
   };
   std::sort(data.begin(), data.end(),
   [&rule](const Data& first, const Data& second) {
   int index_f = rule[first.head],
   index_s = rule[second.head];
   return index_f < index_s;
   });
   
   for (auto &it : data)
   std::cout << it.code << "t" << it.text << "t" << it.head << "n";
   return 0;
   

   }

Answer 2

使用提供随机访问的容器(如vector、deque或array(可以很容易地解决此问题。对于这些，计算两个迭代器之间的距离是O(1(运算，而不是O(n(运算。此外，它们可以减少内存开销并提高引用的局部性，这在Big O表示法中没有涉及，但仍然会影响性能。

另一个需要注意的部分是find()调用，因为这仍然需要遍历O(n(中的序列。如果您使用某种字典，如map或unordered_map，您甚至可以将其简化为O(logn(或O(1(。

最后，如果你希望订单是"；head1"头4"；，您可以简单地委托给less<string>，而不是实现自己的。

HOWEVER：除非您有实际数字证明此代码是性能关键型应用程序的瓶颈，否则您正在进行过早的优化。此外，所有Big-O声明都以"；存在一个CCD_ 21，因此对于所有的CCD_"你可能连CCD_ 23都达不到。