c++ - C++中带键的动态多维数组

问题描述

我正在尝试找到一种在 C++ 中处理以下场景的好方法。

当我们在服务器上启动服务时，将根据数据库中的数据初始化如下所示的参数表。

ID, filed_1, field_2, .... , field 50
100abc, ***, ***, ...., ***
120def, ***, ***, ...., ***
...
...
500xyz, ***, ***, ..., ***

字段/列：大约 50 个。字段的数量和格式是固定的。所有字段的类型都是 int、double 或 char*（不是很长的 char*）。

Records/rows：最多200条。根据数据，每次的记录数都会有所不同。

ID 是唯一的。

在计算过程中，参数表会以每秒500次的速度被读取和更新。（我假设按 id 和字段名称搜索）

低延迟在系统中很重要。

在这种情况下使用的最佳数据结构是什么？

如果有没有写（更新）操作可以大大提高效率的方法，也请分享信息。我认为有一些解决方法可以不对参数表进行更新。

太感谢了。

标签： c++jsondictionaryvectorhash

仅供参考，您在问一个关于算法和数据结构的固执己见的问题，这通常更适合这个堆栈交换站点： https ://softwareengineering.stackexchange.com/

无论如何，用所有适当的盐粒，这是我不知情的意见。考虑到这一点：

字段的数量和格式是固定的。

和这个：

低延迟在系统中很重要。

考虑使用具有完美散列函数的散列映射按名称查找字段。过去，您会使用gperf作为构建步骤以在 C 中生成散列函数，但使用 C++ constexpr 魔术，您可以使用以下选项：

https://github.com/Kronuz/constexpr-phf

那里的文档是如此，如此无用，所以这就是你如何使用它。首先输入您的字段以创建哈希函数：

fnv1ah32 fnv1a{};
constexpr auto fields_phf = phf::make_phf({
    fnv1a("field1"), 
    fnv1a("field2"), 
    fnv1a("field3"), 
    fnv1a("field4")
    /* , ... */
});

我对值使用什么没有任何特别的见解，但是由于您想存储 3 种类型中的一种，因此我将std::variant在此示例中使用：

// ...assuming your field values will fit in std::string's short string optimization
using Value = std::variant<int, double, std::string>;

然后你可以围绕一个连续的数据数组包装一个 O(1) 查找表：

struct Row {
    std::array<Value, FIELD_COUNT> fields;

    template <typename T>
    Value& operator [](T&& t) { 
        auto pos = fields_phf.find(fnv1a(t));
        if (pos == phf::npos) {
            throw std::runtime_error("unknown field");
        }
        return fields[pos];
    }
};

然后使用常规哈希表来查找您的行，如果您事先不知道这些值，这是一个非常好的默认值。保留 200 行以尽量减少重新散列，因为您认为这是您的上限：

std::unordered_map<std::string, Row> table;
table.reserve(200);

然后你可以做你的查找：

int main() {
table["row1"]["field1"] = 42;
table["row2"]["field2"] = "hello";

演示：https ://godbolt.org/z/z8euVY

c++ - C++中带键的动态多维数组

问题描述

解决方案

推荐阅读