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

Question

在 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++ 库已经可以做到这一点？

Answer 1

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

由于您的范围不重叠，因此解决方案非常简单。您可以立即使用 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 即可。