草庐IT

c++ - 从整数范围映射到任意单个整数

coder 2023-06-02 原文

在 Linux 环境中使用 C++ 工作时，我遇到了一种情况，其中定义了多个整数范围，并且整数输入根据它们所属的范围映射到不同的任意整数。没有一个范围重叠，而且它们并不总是连续的。

解决这个问题的“最简单”的方法是为每个范围使用一堆 if 语句，但是范围的数量、它们的界限和目标值都可以变化，因此 if 语句是不可维护的。

例如，范围可能是 [0, 70]，称为 r_a，[101, 150]，称为 r_b，和 [201, 400]，称为 r_c。 r_a 中的输入映射到 1，r_b 中的输入映射到 2，r_c 映射到 3。任何不在 r_a、r_b、r_c 中的都映射到 0。

我可以想出一个数据结构和算法来存储(边界， map 目标)的元组并遍历它们，因此找到目标值需要在边界对的数量上线性时间。我还可以想象一种方案，它使对保持有序并针对所有下限(或上限)使用二进制排序算法，找到最接近输入的，然后与相反的界限进行比较。

有没有比基于二分搜索的算法更好的方法来完成映射？更好的是，是否有一些 C++ 库已经可以做到这一点？

最佳答案

这里最好的方法确实是二分搜索，但是任何有效的基于顺序的搜索都会做得很好。您实际上不必显式地实现搜索和数据结构。您可以通过使用标准关联容器来间接使用它。

由于您的范围不重叠，因此解决方案非常简单。您可以立即使用 std::map 解决此问题，只需几行代码即可解决。

例如，这是一种可能的方法。假设我们将一个 [ int, int ] 范围映射到一个 int 值。让我们将我们的范围表示为封闭开放范围，即如果原始范围是 [0, 70]，让我们考虑一个 [0, 71) 范围。另外，让我们使用 0 的值作为“保留”值，这意味着“没有映射”(正如您在问题中要求的那样)

const int EMPTY = 0;

您需要做的就是声明一个从 int 到 int 的映射:

typedef std::map<int, int> Map;
Map map;

并用您的封闭式开放范围的每一端填充它。左(封闭)端应该映射到整个范围映射到的所需值，而右(开放)端应该映射到我们的 EMPTY 值。对于您的示例，它将如下所示

map[0] = r_a;
map[71] = EMPTY;

map[101] = r_b;
map[251] = EMPTY;

map[260] = r_c; // 260 adjusted from 201
map[401] = EMPTY;

(我调整了您的最后一个范围，因为在您的原始示例中它与前一个范围重叠，并且您说您的范围不重叠)。

这就是初始化。

现在，为了确定 i 的给定值映射到哪里，您需要做的就是

Map::iterator it = map.upper_bound(i);

如果 it == map.begin()，则 i 不在任何范围内。否则，做

--it;

如果it->second(对于递减的it)是EMPTY，那么i不是在任何范围内。

组合的“未命中”检查可能如下所示

Map::iterator it = map.upper_bound(i);
if (it == map.begin() || (--it)->second == EMPTY)
  /* Missed all ranges */;

否则，it->second(对于递减的it)是您的映射值

int mapped_to = it->second;

请注意，如果原始范围是“接触”的，如 [40, 60] 和 [61, 100]，则封闭-开放范围将看起来as [40, 61) 和 [61, 101) 表示 61 的值将在 map 初始化期间映射两次。在这种情况下，确保 61 的值映射到正确的目标值而不是 EMPTY 的值很重要。如果您按照从左到右(即递增)的顺序映射如上所示的范围，它将自行正常工作。

注意，只有范围的端点被插入到映射中，这意味着内存消耗和搜索的性能仅取决于范围的总数，而与它们的总长度完全无关。

如果你愿意，你可以在初始化过程中添加一个“守卫”元素到 map 中

map[INT_MIN] = EMPTY;

(对应“负无穷大”)和“未命中”检查会变得更简单

Map::iterator it = map.upper_bound(i);

assert(it != map.begin());
if ((--it)->second == EMPTY)
  /* Missed all ranges */;

但这只是个人喜好问题。

当然，如果你只是想为非映射值返回0，你根本不需要进行任何检查。只需从递减的迭代器中取出 it->second 即可。

关于c++ - 从整数范围映射到任意单个整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2202262/

到任ampcodemapprec++algorithm

有关c++ - 从整数范围映射到任意单个整数的更多相关文章

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

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

  2. ruby - 触发器 ruby​​ 中 3 点范围运算符和 2 点范围运算符的区别 - 2

    请帮助我理解范围运算符...和..之间的区别，作为Ruby中使用的“触发器”。这是PragmaticProgrammersguidetoRuby中的一个示例:a=(11..20).collect{|i|(i%4==0)..(i%3==0)?i:nil}返回:[nil,12,nil,nil,nil,16,17,18,nil,20]还有:a=(11..20).collect{|i|(i%4==0)...(i%3==0)?i:nil}返回:[nil,12,13,14,15,16,17,18,nil,20] 最佳答案 触发器(又名f/f)是

  3. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  4. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  5. Ruby 从大范围中获取第 n 个项目 - 2

    假设我有这个范围:("aaaaa".."zzzzz")如何在不事先/每次生成整个项目的情况下从范围中获取第N个项目？ 最佳答案 一种快速简便的方法:("aaaaa".."zzzzz").first(42).last#==>"aaabp"如果出于某种原因你不得不一遍又一遍地这样做，或者如果你需要避免为前N个元素构建中间数组，你可以这样写:moduleEnumerabledefskip(n)returnto_enum:skip,nunlessblock_given?each_with_indexdo|item,index|yieldit

  6. 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.你能做的最好的事情是:

  7. sql - 查询忽略时间戳日期的时间范围 - 2

    我正在尝试查询我的Rails数据库(Postgres)中的购买表，我想查询时间范围。例如，我想知道在所有日期的下午2点到3点之间进行了多少次购买。此表中有一个created_at列，但我不知道如何在不搜索特定日期的情况下完成此操作。我试过:Purchases.where("created_atBETWEEN?and?",Time.now-1.hour,Time.now)但这最终只会搜索今天与那些时间的日期。 最佳答案 您需要使用PostgreSQL'sdate_part/extractfunction从created_at中提取小时

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

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

  9. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  10. Ruby 日期参数超出范围 - 2

    我正在尝试使用在我的代码中是动态的Time.local来安排时间。在每个月的第一天，我传递的值是Time.local(2009,9,-1,0)。在PHP中，这会将时间设置为上个月的最后一天。在ruby​​中，我只是得到“ArgumentError:参数超出范围”。是我用错了方法还是什么？谢谢。 最佳答案 您应该使用DateTime类而不是Time。(您可能需要先require'date'并安装activesupportgem。)它比Time更通用，并且可以用DateTime.civil(2009,9-1,-1,0)做你想做的事。为天

随机推荐