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)

树中的键和值是 "static" 硬编码的，但必须不时维护。是否有元编程技巧如何在编译期间将键值组织到二叉搜索树（或跳跃列表）中？

例如，整个搜索树直接在代码.text中实现，而.data中没有任何内容？我还可以 "predict" 键的数量并提供它们的顺序。

Answer 1

我会使用 switch 进行查找。

编译器可以自由使用跳转table、二进制搜索或任何其他技术来优化查找。对于大多数开关 tables，编译器通常会发出尽可能快的东西。

switch (key)
{
    case 10: return "Apple";
    case 20: return "Pear";
    ...
}

Answer 2

我怀疑你小题大做了，这是因为：-

你相信静态初始化 C++ 中的东西你必须在编译时 .
要么你不熟悉 upper 和 lower bounds 的概念，否则你不知道 [部分] 有序序列 S 中 v 的 {upper|lower} 边界可以是由 S 的二进制搜索确定，并且您可以指望标准库至少做到那样高效。

我想你想要一个静态初始化的数据结构映射字符串文字的整数键，这样，在运行时，你可以用整数 n 非常有效地查询它检索字符串文字 s （如果有），其键是最大的不大于 n - 附加条件，大概， n 不大于所有键。

如果没错，那么就是你需要的静态初始化数据结构只是一个 静态初始化映射 M 整数到字符串文字 。模板元编程不在框架内。

由于（假定的）附带条件，对于 n 更大的查询将失败除了所有键，您还需要在 M 中包含一个带有键 1 的标记值比你想找到的最大的还要大。

然后，对于运行时整数 n，您查询 M 以获得 n 的上限。 M中n的上限是大于n的最小key，如果有的话。如果返回的迭代器 it 是 M.end()，那么您没有 n 的字符串。否则，如果it == M.begin()，则每个键都大于n，所以你又没有 n 的字符串。否则，必须存在一个 <key,value> 位于 --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在这个程序中是一个static数据结构，但它不是在 编译时 初始化。它在 global static 中初始化在调用 main 之前，对程序进行初始化。除非你需要将程序启动时间缩短纳秒，我想不出为什么你需要在编译时初始化地图。

如果你确实要求它在编译时初始化，它只是比这更麻烦一点。你需要地图是一个 constexpr 对象，意味着编译器可以在编译时构造它；并为它必须是 literal type；这意味着您不能使用 std::map，因为它不是文字类型。

因此您将不得不使用：

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

或类似的，并以基本所示的方式实施 lookup(n)，但在 tab 上调用 std::upper_bound。在那里你会发现稍微复杂的部分，我会留给你练习，如果你想要。

Answer 3

我终于创造了我想要实现的目标。它太复杂了，看起来编译器优化器比我想象的要聪明得多。

// Log "function"
template <int N>
struct LOG
{
    static const int value = LOG<N/2>::value + 1;
};
template<>
struct LOG<0>
{
    static const int value = 0;
};

// pow "function"
template <int N>
struct POW
{
    static const int value = POW<N-1>::value * 2;
};
template<>
struct POW<1>
{
    static const int value = 2;
};

template<>
struct POW<0>
{
    static const int value = 1;
};

// Pair <key, value> to be a payload in a type list
template<int k, char v>
struct Pair
{
    static const int key = k;
    static const int value = v;
};

// type list manipulator - access n-th element
template <size_t, class...> struct element;
template <class TT, class...TTs>
struct element<0, TT, TTs...>
{
    typedef TT type;
};
template <size_t K, class TT, class...TTs>
struct element<K, TT, TTs...>
{
    typedef typename element<K-1, TTs...>::type type;
};

template<class... Ts>
struct V;

// Binary split search algorithm (pure templatized)
template<class T, class... Ts>
struct V<T, Ts...> : private V<Ts...>
{
    template<size_t N = sizeof...(Ts), size_t level = LOG<sizeof...(Ts)+1>::value>
    struct impl
    {
        template<size_t IDX>
        inline static char search_impl(size_t n)
        {
            using namespace std;
            static const int depth = LOG<N>::value;
            static const int layer = depth - level;
            static const int key   = element<IDX, T, Ts...>::type::key;
            static const size_t left_idx  = IDX - ( N / POW<layer + 2>::value + 1);
            static const size_t right_idx =
                IDX + ( N / POW<layer + 2>::value + 1) > sizeof...(Ts) ?
                sizeof...(Ts) :
                IDX + ( N / POW<layer + 2>::value + 1);             

            //std::cout << setfill('*') << setw(layer) << ' '
            //    << "Level:" << level << " of:" << depth << std::endl
            //    << std::setw(layer) << ' ' 
            //    << "IDX/val/layer/POW/level: "
            //    << " " << IDX
            //    << "/" << key
            //    << "/" << layer
            //    << "/" << POW<layer>::value
            //    << "/" << level
            //    << "/" << left_idx
            //    << "/" << right_idx
            //    << std::endl;
            if ( n < key )
                return V<T, Ts...>::impl<N, level-1>::template search_impl<left_idx>(n);
            else
                return V<T, Ts...>::impl<N, level-1>::template search_impl<right_idx>(n);       
        }

    };

    template<size_t N>
    struct impl<N,1>
    {
        template<size_t IDX>
        inline static char search_impl(size_t n)
        {
            static const int key   = element<IDX, T, Ts...>::type::key;
            static const char value1 = element<IDX-1, T, Ts...>::type::value;
            static const char value2 = element<IDX, T, Ts...>::type::value;
            if ( n < key )
            {
                //std::cout << " *" << value1 << ' '  << IDX << std::endl;
                return value1;
            } else {
                //std::cout << " *" << value2 << ' '  << IDX << std::endl;
                return value2;
            }
        }
    };

    static void print()
    {
        std::cout << typeid(T).name() << ' ' << T::key << ' ' << (char)T::value << std::endl;
        V<Ts...>::print();
    }
    static char search(size_t n)
    {
        static const size_t level = LOG<sizeof...(Ts)+1>::value;
        static const size_t N = sizeof...(Ts);
        static const int height = LOG<N>::value;
        static const size_t root_idx = N / 2 + 1;
        static const int key = element<root_idx, T, Ts...>::type::key;
        //std::cout << "Level:" << level << " of:" << height << std::endl
        //    << "IDX/val: "
        //    << " " << root_idx
        //    << "/" << input[root_idx]
        //    << std::endl;

        static const size_t left_idx  = root_idx - ( N / POW<2>::value + 1);
        static const size_t right_idx = root_idx + ( N / POW<2>::value + 1);

        if( n < key)
            return V<T, Ts...>::impl<N, level-1>::template search_impl<left_idx>(n);
        else
            return V<T, Ts...>::impl<N, level-1>::template search_impl<right_idx>(n);
    }
};

template<>
struct V<>
{
    static void print()
    {}
};

int main(int argc, char *argv[])
{
    int i = std::stoi(argv[1]);

    typedef V<
    Pair<  0x1,'a'>,
    Pair< 0x11,'b'>,
    Pair< 0x21,'c'>,
    Pair< 0x31,'d'>,
    Pair< 0x41,'e'>,
    Pair< 0x51,'f'>,
    Pair< 0x61,'g'>,
    Pair< 0x71,'h'>,
    Pair< 0x81,'i'>,
    Pair< 0x91,'j'>,
    Pair<0x101,'k'>,
    Pair<0x111,'l'>,
    Pair<0x121,'m'>,
    Pair<0x131,'n'>,
    Pair<0x141,'o'>
    > TV;

    std::cout << (char)TV::search(i) << std::endl;

    return 0;
};

就是这样。我的目标是 "force" 编译器将所有常量放入代码中。因为数据段中没有任何内容。生成的代码将所有 search_impl<*> 方法内联在一起，结果仅包含 "cmp" 和 "jae" 指令。但看起来合理的编译器无论如何都会这样做，如果要搜索的数组定义为 const static。

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

C++ metaprogramming - compile time search tree

c++

binary-tree

template-meta-programming