如何从一组具有从左到右优先级的整数值创建有序整数键?

Question

这是可能在某处回答的问题之一，而且可能很简单，我只是找不到正确的搜索词。

我有一组对象需要插入到有序的容器中(例如std::map(，插入性能是重中之重。到目前为止，我一直在使用一个相当复杂的<运算符，但分析显示这需要大量时间。

我想做的是为每个对象预先计算一个整数值以进行排序，以便<运算符简单地变成整数比较。

本质上，我有一组 12 个按优先级顺序排列的无符号整数值，每个值都有自己的可能值范围(最大的是 0-100000，最小的是 0-1(。

这很难解释，但想象一下两个对象，每个对象都有一个 12 个值的数组。如果一个对象的值 [0] 更大，那么它的排序键必须更高，如果值 [0] 相等，但 value[1] 大于另一个对象，那么它的排序键必须更高。我希望这是有道理的...

感觉应该有一种明显的方法来从这些值生成密钥，但我遇到了麻烦。

Answer 1

性能很好，即分析问题总是有点问题，但这是我提出的第一个解决方案，至少我希望它应该接近C++便携式最佳。3 条简单的cmpx64 指令让我相信这一点。

您可以在inline bool compare1之前删除constexpr，它仅受最新的 C++20 实现支持：

https://godbolt.org/z/LdEk4M

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <array>
#include <cstdint>
#include <random>
#include <iterator>
#include <vector>
constexpr unsigned value_count = 12;
using value_t = uint_fast32_t;
struct object{
std::array<value_t , value_count> values{};
};
constexpr inline bool compare1(const object& objecta, const object& objectb) {
bool result{false};
auto [mismatcha, mismatchb] = std::mismatch(objecta.values.begin(), objecta.values.end(), objectb.values.begin());
if (mismatcha != objecta.values.end()) {
result = *mismatcha < *mismatchb;
}
return result;
}
int main() {
std::random_device rd;
std::uniform_int_distribution<value_t> dist(0, 100000);
constexpr size_t object_count{50000};
std::cout << "Generate " << object_count << " random objects" << std::endl;
std::vector<object> unsorted_objects;
std::generate_n(std::back_inserter(unsorted_objects), object_count, [&] () {
object val{};
std::generate(val.values.begin(), val.values.end(), [&]() {
return dist(rd); });
return val;
});
std::set<object, decltype(&compare1)> objects(&compare1);
std::cout << "Generating sorted i.e. ordered container" << std::endl;
std::move(unsorted_objects.begin(), unsorted_objects.end(), std::inserter(objects,objects.end()));
}

我认为预先计算"分数"不是您在问题中描述的，因为在我看来，您有一个要比较的 12xunsigned 数字。所以你的分数必须是一回事。充其量，您可以保存不是 1 的第一个位或值位置，即不是最大可能值。但是，这种条件跳转可能已经比比较流水线的 12 个整数更昂贵。