C++元编程 - 编译时间搜索树

Question

更新:抱歉令人困惑的术语 - 我不需要二叉树,但需要分段树或区间树.

想象一下,每次执行我的程序时,我都必须静态初始化一个搜索树.

Tree t;
t.add(10, 'Apple');
t.add(20, 'Pear');
t.add(50, 'Orange');
...
t.add(300, 'Cucumber');

..
// then I use it.
int key = 15;
String s = t.lookup(key) // Returns 'Apple' ( as the key is between 10 and 20)

树中的键和值是"静态的",是硬编码的,但必须不时地进行维护.是否存在元编程技巧如何在编译期间将键值组织成二进制搜索树(或跳过列表)？

例如,整个搜索树是直接在代码中实现的.text,什么都没有.data？我还可以"预测"键的数量并提供订单.

Answer 1

我怀疑你是在这里用一个小山丘制造一座山,这是因为: -

• 您认为要在C++中静态初始化某些内容,您必须在编译时执行此操作.

• 要么您不熟悉上限和下限的概念,要么您不知道v[部分]有序序列中的{upper | lower}界限S可以通过二进制搜索来确定S,并且您可以依赖标准库至少可以有效地完成它.

我想你想要一个静态初始化的数据结构,将整数键映射到字符串文字,这样,在运行时,你可以用一个整数查询它,n并非常有效地检索字符串文字s(如果有的话),其键是最大的,不是大于n- 附加条件,据推测,n不大于所有键.

如果这是正确的,那么您需要的静态初始化数据结构只是一个静态初始化 M 的整数映射到字符串文字.模板元编程不在框架中.

由于(假定的)附带条件是查询失败的n大于所有密钥,因此您需要包含一个M大于您想要查找的最大密钥1 的标记值.

然后,对于运行时整数n,查询M上限n.nin 的上限M是大于的最小键n,如果有的话.如果返回的迭代器it是M.end()那么你没有字符串n.否则,如果it == M.begin(),则每个键都大于n,所以再次没有字符串n.否则,必须存在一个<key,value> by --it,并且key必须是不 大于的最大键n.所以你的字符串n就是那个value.

#include <map>

static const std::map<int,char const *> tab = 
{
    { 2,"apple" },
    { 5,"pear" },
    { 9,"orange" },
    { 14,"banana" },
    { 20,"plum" },
    { 20 + 1,nullptr }
};

const char * lookup(int n)
{
    auto it = tab.upper_bound(n);
    return it == tab.begin() || it == tab.end() ? nullptr : (--it)->second;
}

在此示例前面加上:

#include <iostream>

using namespace std;

int main(void)
{
    for (int i = 0; i <= 21; ++i) {
        cout << i;
        char const *out = lookup(i);
        cout << " -> " << (!out ? "Not found" : out) << endl;
    }
    return 0;
}

输出将是:

0 -> Not found
1 -> Not found
2 -> apple
3 -> apple
4 -> apple
5 -> pear
6 -> pear
7 -> pear
8 -> pear
9 -> orange
10 -> orange
11 -> orange
12 -> orange
13 -> orange
14 -> banana
15 -> banana
16 -> banana
17 -> banana
18 -> banana
19 -> banana
20 -> plum
21 -> Not found

现在tab这个程序是一个静态数据结构,但它没有在编译时初始化.在调用之前,它在程序的全局静态初始化中初始化main.除非你要求程序启动时减少纳秒,否则我想不出为什么你需要在编译时初始化映射.

但是,如果你确实需要在编译时初始化它,它只是比这更有点小.您需要将映射作为constexpr 对象,这意味着编译器可以在编译时构造它; 为此它必须是文字类型 ; 这意味着你不能使用std::map,因为它不是文字类型.

因此,您将不得不使用:

constexpr std::pair<int,char const *> tab[] 
{
    { 2,"apple" },
    { 5,"pear" },
    { 9,"orange" },
    { 14,"banana" },
    { 20,"plum" },
    { 20 + 1,nullptr }
};   

或类似,并执行lookup(n)基本上所示的方式,但在调用std::upper_bound时tab.你可以在那里找到稍微有点笨拙的东西,如果你需要,我会留给你练习.