文章/答案/技术大牛

发布

社区首页 >问答首页 >C++元编程-编译时搜索树

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

Stack Overflow用户

提问于 2015-02-19 18:48:26

回答 3查看 2.1K关注 0票数 4

更新:对不起，混淆术语-我不需要二叉树，而是段树或间隔树.

假设每次执行我的程序时，我必须静态地初始化一个搜索树。

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中不保存任何内容？我还可以“预测”密钥的数量，并提供订单。

c++

binary-tree

template-meta-programming

回答 3

Stack Overflow用户

回答已采纳

发布于 2015-02-21 17:16:20

我怀疑你是在用鼹鼠山造山，这是因为：-

您认为要在C++中静态初始化某些内容，就必须在编译时进行。
要么您不熟悉上界和下界的概念，要么您不知道v在偏序序列S中的{上、下}界可以通过对S的二进制搜索来确定，而且您至少可以依靠标准库来高效地完成这一任务。

我认为您希望有一个静态初始化的数据结构，将整数键映射为字符串文本，以便在运行时可以使用整数n查询整数，并非常有效地检索字符串文本s (如果有的话)，该字符串的键是最大的，不大于n --附加的条件是n不大于所有键。

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

由于(假定的)条件是查询对于大于所有键的n将失败，因此需要在M中包含一个哨位值，其键1要大于要查找的最大值。

然后，对于运行时整数n，您将查询M以获得n的上限。n在M中的上限是比n大的最小键(如果有的话)。如果返回的迭代器it是M.end()，那么您就没有n的字符串。否则，如果是it == M.begin()，那么每个键都大于n，因此您同样没有用于n的字符串。否则，必须存在由--it定位的--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对象，这意味着编译器可以在编译时构造它；为此，它必须是http://en.cppreference.com/w/cpp/types/is_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。在那里，你会发现一些稍微花哨的部分，如果你想要的话，我会留给你做练习。

票数 5

Stack Overflow用户

发布于 2015-02-23 16:35:24

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

// 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;
};

所以就是这样了。我的目标是“强制”编译器将所有常量放入代码中。因为数据段中没有保存任何内容。生成的代码将所有search_impl<*>方法内联在一起，结果只包含"cmp“和"jae”指令。但是，如果要搜索的数组被定义为const，那么一个合理的编译器无论如何都会这样做的。

票数 2

Stack Overflow用户

发布于 2015-02-19 23:17:15

我会使用switch进行查找。

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

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28617781

复制

相似问题

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

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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