草庐IT

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

coder 2024-02-17 原文

更新:抱歉混淆了术语 - 我不需要二叉树，而是线段树或区间树。

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

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++ 中静态初始化某些东西你 必须在编译时完成。

  • 要么你不熟悉 上限 和下限 的概念，否则你不知道 v 的{上|下}界|在[部分]有序序列中S可 通过 S 的二进制搜索确定，并且您可以依靠标准库 至少做到那样高效。

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

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

因为(假定的)条件是对于 n 的查询将失败更大 除了所有键，您还需要在 M 中包含一个标记值用 key 1 比你想找到的最大的还要大。

然后，对于运行时整数 n ，你查询M对于 n 的上限. n 的上限在 M是大于 n 的最小键, 如果有的话。 如果返回迭代器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数据结构，但它不是 在编译时初始化。它在全局静态中初始化 程序的初始化，在main 之前叫做。除非你 需要将程序启动时间缩短纳秒，我 想不出为什么您需要在编译时初始化 map 。

如果您确实要求它在编译时初始化， 它只是比这更麻烦一点。你需要 map 是 一个 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)基本上以所示方式， 但调用 std::upper_bound在 tab 之后.在那里你会发现 稍微复杂的部分，我会留给你练习，如果你 想要它。

关于C++ 元编程 - 编译时搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28617781/

amp43codegtemc++binary-treetemplate-meta-programming

有关C++ 元编程 - 编译时搜索树的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  3. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  4. ruby - Sinatra set cache_control to static files in public folder编译错误 - 2

    我不知道为什么，但是当我设置这个设置时它无法编译设置:static_cache_control，[:public，:max_age=>300]这是我得到的syntaxerror,unexpectedtASSOC,expecting']'(SyntaxError)set:static_cache_control,[:public,:max_age=>300]^我只想将“过期”header设置为css、javaascript和图像文件。谢谢。 最佳答案 我猜您使用的是Ruby1.8.7。Sinatra文档中显示的语法似乎是在Ruby1.

  5. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  6. 网络编程套接字 - 2

    网络编程套接字网络编程基础知识理解源`IP`地址和目的`IP`地址理解源MAC地址和目的MAC地址认识端口号理解端口号和进程ID理解源端口号和目的端口号认识`TCP`协议认识`UDP`协议网络字节序socket编程接口`sockaddr``UDP`网络程序服务器端代码逻辑：需要用到的接口服务器端代码`udp`客户端代码逻辑`udp`客户端代码`TCP`网络程序服务器代码逻辑多个版本服务器单进程版本多进程版本多线程版本线程池版本服务器端代码客户端代码逻辑客户端代码TCP协议通讯流程TCP协议的客户端/服务器程序流程三次握手（建立连接）数据传输四次挥手（断开连接）TCP和UDP对比网络编程基础知识

  7. 安卓apk修改(Android反编译apk) - 2

    最近因为项目需要，需要将Android手机系统自带的某个系统软件反编译并更改里面某个资源，并重新打包，签名生成新的自定义的apk，下面我来介绍一下我的实现过程。APK修改，分为以下几步：反编译解包,修改,重打包,修改签名等步骤。安卓apk修改准备工作1.系统配置好JavaJDK环境变量2.需要root权限的手机（针对系统自带apk,其他软件免root）3.Auto-Sign签名工具4.apktool工具安卓apk修改开始反编译本文拿Android系统里面的Settings.apk做demo,具体如何将apk获取出来在此就不过多介绍了，直接进入主题：按键win+R输入cmd，打开命令窗口，并将路

  8. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  9. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  10. ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2

    我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or

随机推荐