如何在编译时生成带稀疏行的查找表？

问题描述 #

需要将一组(keyA, keyB, value)格式的条目在编译时转换为稀疏二维查找表，采用指向行的指针数组形式（(*table[keyA])[keyB] = value）来省略空行，不使用扁平二维数组（table[keyA][keyB] = value）。

期望的代码写法如下：

using my_lut_t = struct sparse_lut<10, 10, int>;

#define NUM_DEFS 4
constexpr std::array<my_lut_t::entry_t, NUM_DEFS> entries = {{
    {1, 1, 11},
    {1, 2, 12},
    {1, 3, 13},
    {2, 2, 22},
}};

constinit my_lut_t table(entries);

编译后的二进制应在.rodata段生成类似如下的内容：

section .rodata
table:
    dd 0, row_1, row_2, 0, 0, 0, 0, 0, 0, 0
row_1:
    dw -1, 11, 12, 13, -1, -1, -1, -1, -1, -1
row_2:
    dw -1, -1, 22, -1, -1, -1, -1, -1, -1, -1

自行实现的代码如下，但使用constexpr强制编译时执行会报错：

#include <memory>
#include <array>
#include <iostream>

template<std::size_t A_COUNT, std::size_t B_COUNT, typename value_t, value_t sentinel = -1>
struct sparse_lut {
    using entry_t = struct { std::size_t a; std::size_t b; value_t value; };
    using table_row_t = std::array<value_t, B_COUNT>;

    std::array<std::unique_ptr<table_row_t>, A_COUNT> contents = {nullptr};

    template<typename Iter>
    constexpr sparse_lut(Iter& definitions) {
        for (const auto & entry: definitions) {
            if (contents[entry.a].get() == nullptr) { // regular unique_ptr::operator== isn't constexpr
                contents[entry.a] = std::make_unique<table_row_t>();
                contents[entry.a]->fill(sentinel);
            }
            (*contents[entry.a])[entry.b] = entry.value;
        }
    }

    value_t get(const std::size_t a, const std::size_t b) const {
        if (contents[a] == nullptr) return sentinel;
        return (*contents[a])[b];
    }
};

using my_lut_t = struct sparse_lut<10, 10, int>;

#define NUM_DEFS 4
constexpr std::array<my_lut_t::entry_t, NUM_DEFS> entries = {{
    {1, 1, 11},
    {1, 2, 12},
    {1, 3, 13},
    {2, 2, 22},
}};

constexpr my_lut_t table(entries);

int main() {
    for (std::size_t a = 0; a < 10; ++a) {
        for (std::size_t b = 0; b < 10; ++b)
            std::cout << table.get(a, b) << ' ';
        std::cout << '\n';
    }
    return 0;
}

错误信息：

In file included from /opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/memory:76,
                 from <source>:1:
/opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/bits/unique_ptr.h:1065:30: error: 'sparse_lut<10, 10, int>(entries)' is not a constant expression because it refers to a result of 'operator new'
 1065 |     { return unique_ptr<_Tp>(new _Tp(std::forward<_Args>(__args)...)); }
      |                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

解决方案 #

错误原因 #

constexpr上下文不允许调用operator new（即使C++20支持constexpr动态分配，分配的对象生命周期也仅限于常量表达式求值过程，无法存储到全局constexpr对象中）。因此必须放弃动态内存分配，改用静态编译期生成的数组来存储行数据。

修改后的实现 #

核心思路：

• 将std::unique_ptr<table_row_t>替换为const table_row_t*，指向编译时生成的静态行数组
• 编译时生成所有非空行的constexpr数组，填充哨兵值后替换为指定条目
• 将行数组的指针填入查找表的指针数组中

完整代码：

#include <array>
#include <iostream>
#include <algorithm>

template<std::size_t A_COUNT, std::size_t B_COUNT, typename value_t, value_t sentinel = -1>
struct sparse_lut {
    using entry_t = struct { std::size_t a; std::size_t b; value_t value; };
    using table_row_t = std::array<value_t, B_COUNT>;

    std::array<const table_row_t*, A_COUNT> contents = {nullptr};

    // 编译时生成单个行的数组
    static constexpr table_row_t generate_row(const auto& entries, std::size_t target_a) {
        table_row_t row{};
        row.fill(sentinel);
        for (const auto& entry : entries) {
            if (entry.a == target_a) {
                row[entry.b] = entry.value;
            }
        }
        return row;
    }

    // 编译时收集所有存在条目的keyA
    static constexpr auto get_non_empty_a_keys(const auto& entries) {
        std::array<std::size_t, A_COUNT> keys{};
        std::size_t count = 0;
        for (const auto& entry : entries) {
            if (!std::ranges::contains(keys.begin(), keys.begin() + count, entry.a)) {
                keys[count++] = entry.a;
            }
        }
        return std::pair{keys, count};
    }

    template<typename Entries>
    constexpr sparse_lut(const Entries& entries) {
        // 获取所有非空的keyA
        auto [non_empty_keys, key_count] = get_non_empty_a_keys(entries);

        // 为每个非空keyA生成行，并存储指针
        for (std::size_t i = 0; i < key_count; ++i) {
            const auto a = non_empty_keys[i];
            // 静态存储行数组，确保生命周期全局有效
            static constexpr auto row = generate_row(entries, a);
            contents[a] = &row;
        }
    }

    value_t get(const std::size_t a, const std::size_t b) const {
        if (a >= A_COUNT || b >= B_COUNT) return sentinel;
        if (contents[a] == nullptr) return sentinel;
        return (*contents[a])[b];
    }
};

using my_lut_t = sparse_lut<10, 10, int>;

#define NUM_DEFS 4
constexpr std::array<my_lut_t::entry_t, NUM_DEFS> entries = {{
    {1, 1, 11},
    {1, 2, 12},
    {1, 3, 13},
    {2, 2, 22},
}};

constexpr my_lut_t table(entries);

int main() {
    for (std::size_t a = 0; a < 10; ++a) {
        for (std::size_t b = 0; b < 10; ++b)
            std::cout << table.get(a, b) << ' ';
        std::cout << '\n';
    }
    return 0;
}

关键说明 #

1. 静态constexpr行数组：generate_row函数在编译时生成对应keyA的行数组，通过static constexpr存储，确保其生命周期与程序一致，且存储在.rodata段。
2. 指针数组填充：构造函数中收集所有存在条目的keyA，将对应行的指针填入contents数组，空行保持nullptr。
3. 编译期安全：所有操作均在constexpr上下文完成，无动态内存分配，符合编译时构建的要求。

内容的提问来源于stack exchange，提问作者AJMansfield