blocks|key|4261175|text|我会使用switch进行查找。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4261176|编译器可以自由地使用跳转表、二进制搜索或任何其他技术来优化查找。对于大多数开关表，编译器通常会发出最快的东西。|4261177|switch+(key)
{
++++case+10:+return+"Apple";
++++case+20:+return+"Pear";
++++...
}|code-block|syntax|javascript|4261178|entityMap^0|4|6|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|R|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|S|8|@]|D|@]|E|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

I would use a <code>switch</code> to do the lookup.

The compiler is free to use a jump table, binary search, or any other technique to optimize the lookup. For most switch tables, the compiler will generally emit the fastest possible thing.

<pre><code>switch (key)
{
 case 10: return "Apple";
 case 20: return "Pear";
 ...
}
</code></pre>

blocks|key|1932261|text|我怀疑你是在用鼹鼠山造山，这是因为：-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1932262|您认为要在C%2B%2B中静态初始化某些内容，就必须在编译时进行。|unordered-list-item|1932263|要么您不熟悉上界和下界的概念，要么您不知道v在偏序序列S中的{上、下}界可以通过对S的二进制搜索来确定，而且您至少可以依靠标准库来高效地完成这一任务。|offset|length|style|CODE|1932264|1932265|1932266|我认为您希望有一个静态初始化的数据结构，将整数键映射为字符串文本，以便在运行时可以使用整数n查询整数，并非常有效地检索字符串文本s+(如果有的话)，该字符串的键是最大的，不大于n+--附加的条件是n不大于所有键。|1932267|如果这是正确的，那么您需要的静态初始化数据结构只是一个从整数到字符串文本的静态初始化映射M。模板元编程不在框架中。|1932268|由于(假定的)条件是查询对于大于所有键的n将失败，因此需要在M中包含一个哨位值，其键1要大于要查找的最大值。|1932269|然后，对于运行时整数n，您将查询M以获得n的上限。n在M中的上限是比n大的最小键(如果有的话)。如果返回的迭代器it是M.end()，那么您就没有n的字符串。否则，如果是it+==+M.begin()，那么每个键都大于n，因此您同样没有用于n的字符串。否则，必须存在由--it定位的--it，并且该key必须是不大于n的最大密钥。所以n的字符串是value。|1932270|#include+<map>

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

const+char+*+lookup(int+n)
{
++++auto+it+=+tab.upper_bound(n);
++++return+it+==+tab.begin()+%7C%7C+it+==+tab.end()+?+nullptr+:+(--it)->second;
}|code-block|syntax|javascript|1932271|为这个例子做好准备：|1932272|#include+<iostream>

using+namespace+std;

int+main(void)
{
++++for+(int+i+=+0;+i+<=+21;+%2B%2Bi)+{
++++++++cout+<<+i;
++++++++char+const+*out+=+lookup(i);
++++++++cout+<<+"+->+"+<<+(!out+?+"Not+found"+:+out)+<<+endl;
++++}
++++return+0;
}|1932273|产出如下：|1932274|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|1932275|现在这个程序中的tab是一个静态的数据结构，但是它不是在编译时初始化的。在调用main之前，它将在程序的全局静态初始化中初始化。除非您需要将程序启动时间缩短纳秒，否则我想不出您为什么需要在编译时初始化映射。|1932276|尽管如此，如果您确实要求在编译时初始化它，那么它只是比这更灵活一些。您将需要映射为constexpr对象，这意味着编译器可以在编译时构造它；为此，它必须是http://en.cppreference.com/w/cpp/types/is_literal_type；这意味着您不能使用std::map，因为它不是文字类型。|1932277|因此，您将不得不使用：|1932278|constexpr+std::pair<int,char+const+*>+tab[]+
{
++++{+2,"apple"+},
++++{+5,"pear"+},
++++{+9,"orange"+},
++++{+14,"banana"+},
++++{+20,"plum"+},
++++{+20+%2B+1,nullptr+}
};+++|1932279|或者类似的方法，并以本质上所示的方式实现lookup(n)，但在tab上调用std::upper_bound。在那里，你会发现一些稍微花哨的部分，如果你想要的话，我会留给你做练习。|1932280|entityMap|0|LINK|mutability|MUTABLE|url|http://en.cppreference.com/w/cpp/language/constexpr|1|http://en.cppreference.com/w/cpp/types/is_literal_type^0|0|0|L|1|R|1|15|1|0|0|0|19|1|1S|1|2G|1|2Q|1|0|18|1|0|K|1|U|1|0|A|1|G|1|K|1|P|1|R|1|Y|1|1K|2|1N|7|21|1|2D|F|31|1|3C|1|3Q|4|3X|4|45|3|4E|1|4N|1|4T|5|0|0|0|0|0|0|8|3|13|4|0|15|9|3X|8|15|9|0|25|1I|1|0|0|0|K|9|W|3|12|G|0^^$0|@$1|2|3|4|5|6|7|1R|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1S|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|1T|8|@$G|1U|H|1V|I|J]|$G|1W|H|1X|I|J]|$G|1Y|H|1Z|I|J]]|9|@]|A|$]]|$1|K|3|-4|5|6|7|20|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|21|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|22|8|@$G|23|H|24|I|J]|$G|25|H|26|I|J]|$G|27|H|28|I|J]|$G|29|H|2A|I|J]]|9|@]|A|$]]|$1|O|3|P|5|6|7|2B|8|@$G|2C|H|2D|I|J]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|2E|8|@$G|2F|H|2G|I|J]|$G|2H|H|2I|I|J]]|9|@]|A|$]]|$1|S|3|T|5|6|7|2J|8|@$G|2K|H|2L|I|J]|$G|2M|H|2N|I|J]|$G|2O|H|2P|I|J]|$G|2Q|H|2R|I|J]|$G|2S|H|2T|I|J]|$G|2U|H|2V|I|J]|$G|2W|H|2X|I|J]|$G|2Y|H|2Z|I|J]|$G|30|H|31|I|J]|$G|32|H|33|I|J]|$G|34|H|35|I|J]|$G|36|H|37|I|J]|$G|38|H|39|I|J]|$G|3A|H|3B|I|J]|$G|3C|H|3D|I|J]|$G|3E|H|3F|I|J]|$G|3G|H|3H|I|J]|$G|3I|H|3J|I|J]]|9|@]|A|$]]|$1|U|3|V|5|W|7|3K|8|@]|9|@]|A|$X|Y]]|$1|Z|3|10|5|6|7|3L|8|@]|9|@]|A|$]]|$1|11|3|12|5|W|7|3M|8|@]|9|@]|A|$X|Y]]|$1|13|3|14|5|6|7|3N|8|@]|9|@]|A|$]]|$1|15|3|16|5|W|7|3O|8|@]|9|@]|A|$X|Y]]|$1|17|3|18|5|6|7|3P|8|@$G|3Q|H|3R|I|J]|$G|3S|H|3T|I|J]]|9|@]|A|$]]|$1|19|3|1A|5|6|7|3U|8|@$G|3V|H|3W|I|J]|$G|3X|H|3Y|I|J]]|9|@$G|3Z|H|40|1|41]|$G|42|H|43|1|44]]|A|$]]|$1|1B|3|1C|5|6|7|45|8|@]|9|@]|A|$]]|$1|1D|3|1E|5|W|7|46|8|@]|9|@]|A|$X|Y]]|$1|1F|3|1G|5|6|7|47|8|@$G|48|H|49|I|J]|$G|4A|H|4B|I|J]|$G|4C|H|4D|I|J]]|9|@]|A|$]]|$1|1H|3|-4|5|6|7|4E|8|@]|9|@]|A|$]]]|1I|$1J|$5|1K|1L|1M|A|$1N|1O]]|1P|$5|1K|1L|1M|A|$1N|1Q]]]]

I suspect you are making a mountain out of a molehill here,
and that it's because:-

<ul>
<li>You believe that to statically initialize something in C++ you
have to do it at compiletime.</li>
<li>Either you are not acquainted with the
concepts of upper and lower bounds or else you don't know that the 
{upper|lower} bound of <code>v</code> in a [partially] ordered sequence <code>S</code> can be 
determined by binary search of <code>S</code>, and that you can count on the Standard Library
to do it at least that efficiently.</li>
</ul>

I think you want to have a statically initialized data structure mapping
integer keys to string literals such that, at runtime, you
can query it with an integer <code>n</code> and very efficiently
retrieve the string literal <code>s</code> (if any), whose key is the largest
that is not larger than <code>n</code> - with the additional proviso, presumably,
that <code>n</code> is not larger than all keys.

If that is right, then the statically initialized data structure you need 
is simply a statically initialized map <code>M</code> of integers to string literals.
Template meta-programming is not in the frame.

Because of the (presumed) proviso that that a query shall fail for <code>n</code> larger 
than all keys, you will need to include a sentinel value in <code>M</code> with a key 1 
larger than the largest you want to find. 

Then, for runtime integer <code>n</code>, you query <code>M</code> for the upper bound of <code>n</code>. 
The upper bound of <code>n</code> in <code>M</code> is the smallest key larger than <code>n</code>, if any. 
If the returned iterator <code>it</code> is <code>M.end()</code> then you have no string for <code>n</code>. 
Otherwise, if <code>it == M.begin()</code>, then every key is greater than <code>n</code>, 
so again you have no string for <code>n</code>. Otherwise, there must exist a <code>&lt;key,value&gt;</code>
located by <code>--it</code>, and that <code>key</code>must be the largest key that is not
larger than <code>n</code>. So your string for <code>n</code> is that <code>value</code>.

<pre><code>#include &lt;map&gt;

static const std::map&lt;int,char const *&gt; 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)-&gt;second;
}
</code></pre>

Prepend that to this example:

<pre><code>#include &lt;iostream&gt;

using namespace std;

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

and the output will be:

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

Now <code>tab</code> in this program is a static data structure, but it is not
initialized at compiletime. It is initialized in the global static
initialization of your program, before <code>main</code> is called. Unless you
have a requirement to shave nanoseconds off your program startup, I
can't think why you would need the map to be initialized at compiletime.

If nevertheless you do require it to be initialized at compiletime,
it is just a little fiddlier than this. You will need the map to be
a <a href="http://en.cppreference.com/w/cpp/language/constexpr" rel="nofollow"><code>constexpr</code></a> 
object, meaning the compiler can construct it at compiletime; and for
that it must be of a <a href="http://en.cppreference.com/w/cpp/types/is_literal_type" rel="nofollow">literal type</a>;
and that means you cannot use <code>std::map</code>, because it is not a literal type.

Therefore you will have to use instead:

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

or similar, and implement <code>lookup(n)</code> in essentially the manner shown,
but invoking <code>std::upper_bound</code> upon <code>tab</code>. There you'll find the
slightly fiddlier bits, which I'll leave you for the exercise, if you
want it.

blocks|key|4261277|text|我终于创造了我想要达到的目标。这太复杂了，看起来编译器优化器比我想的要聪明得多。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4261278|//+Log+"function"
template+<int+N>
struct+LOG
{
++++static+const+int+value+=+LOG<N/2>::value+%2B+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)%2B1>::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+%2B+2>::value+%2B+1);
++++++++++++static+const+size_t+right_idx+=
++++++++++++++++IDX+%2B+(+N+/+POW<layer+%2B+2>::value+%2B+1)+>+sizeof...(Ts)+?
++++++++++++++++sizeof...(Ts)+:
++++++++++++++++IDX+%2B+(+N+/+POW<layer+%2B+2>::value+%2B+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)%2B1>::value;
++++++++static+const+size_t+N+=+sizeof...(Ts);
++++++++static+const+int+height+=+LOG<N>::value;
++++++++static+const+size_t+root_idx+=+N+/+2+%2B+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+%2B+1);
++++++++static+const+size_t+right_idx+=+root_idx+%2B+(+N+/+POW<2>::value+%2B+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;
};|code-block|syntax|javascript|4261279|所以就是这样了。我的目标是“强制”编译器将所有常量放入代码中。因为数据段中没有保存任何内容。生成的代码将所有search_impl<*>方法内联在一起，结果只包含"cmp“和"jae”指令。但是，如果要搜索的数组被定义为const，那么一个合理的编译器无论如何都会这样做的。|4261280|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I finally created what I wanted to achieve. It's overcomplicated and it looks like compiler optimizers are much smarter then I thought.

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

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

template&lt;&gt;
struct POW&lt;0&gt;
{
 static const int value = 1;
};

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

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

template&lt;class... Ts&gt;
struct V;

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

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

 };

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

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

 static const size_t left_idx = root_idx - ( N / POW&lt;2&gt;::value + 1);
 static const size_t right_idx = root_idx + ( N / POW&lt;2&gt;::value + 1);

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

template&lt;&gt;
struct V&lt;&gt;
{
 static void print()
 {}
};

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

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

 std::cout &lt;&lt; (char)TV::search(i) &lt;&lt; std::endl;

 return 0;
};
</code></pre>

So this is it. Mine goal was to "force" the compiler to put all the constants into the code. As nothing is kept in the data segment. The resulting code inlines all the search_impl&lt;*> methods together and the result contains only "cmp" and "jae" instructions. But it looks like a reasonable compiler will do this anyway, if the array to be searched is defined as const static.

UPDATE: sorry for confusing terms - I do not need a binary-tree, but segment-tree or interval-tree.

Imagine I have to statically initialize a search tree each time mine program is executed.

<pre><code>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)
</code></pre>

The keys and values in a tree are "static", hard-coded, but have to be maintained from time to time. Is there are metaprogramming trick how to organise key values into binary-search tree (or a skip list) during compile time?

For example the whole search tree is implemented directly in code <code>.text</code> and nothing is held in <code>.data</code>? I can also "predict" number of keys and provide order them.

C++ metaprogramming - compile time search tree

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

更新:对不起，混淆术语-我不需要二叉树，而是段树或间隔树.假设每次执行我的程序时，我必须静态地初始化一个搜索树。Tree t;t.add(10, 'Apple');t.add(20, 'Pear');t.add(50, 'Orange');...t.add(300, 'Cucumber');..// then I us...

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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