在 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/