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

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.

我可以提出一个数据结构和算法来存储(边界,地图目标)的元组并迭代它们,因此找到目标值需要在边界对的数量上线性时间.我还可以想象一个方案,保持对的顺序,并使用二进制sort-ish算法对所有下限(或上限),找到最接近输入,然后比较相对的边界.

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

Answer 1

这里最好的方法确实是二分搜索,但任何有效的基于订单的搜索都能很好地完成.您实际上不必显式实现搜索和数据结构.您可以通过使用标准关联容器来间接使用它.

由于您的范围不重叠,因此解决方案非常简单.您可以立即使用a 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],则闭合打开范围将看起来[40, 61)并且[61, 101)意味着61在地图初始化期间将将值映射两次.在这种情况下,重要的是确保将值61映射到正确的目标值而不是值EMPTY.如果您按照从左到右(即增加)的顺序映射上面显示的范围,它将自行正常工作.

请注意,只有范围的端点插入到映射中,这意味着内存消耗和搜索性能仅取决于范围的总数,并且完全独立于其总长度.

如果您愿意,可以在初始化期间向地图添加"guard"元素

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从减少的迭代器中取出即可.

Answer 2

我会用一个非常简单的东西:a std::map.

class Range
{
public:
  explicit Range(int item);  // [item,item]
  Range(int low, int high);  // [low,high]

  bool operator<(const Range& rhs) const
  {
    if (mLow < rhs.mLow)
    {
      assert(mHigh < rhs.mLow); // sanity check
      return true;
    }
    return false;
  } // operator<

  int low() const { return mLow; }
  int high() const { return mHigh; }

private:
  int mLow;
  int mHigh;
}; // class Range

然后,让我们有一张地图:

typedef std::map<Range, int> ranges_type;

并编写一个在此地图中搜索的函数:

int find(int item, const ranges_type& ranges)
{
  ranges_type::const_iterator it = ranges.lower_bound(Range(item));
  if (it != ranges.end() && it->first.low() <= item)
    return it->second;
  else
    return 0; // No mapping ?
}

主要好处:

• 在插入集合期间检查范围是否有效地不重叠(您可以使其仅在调试模式下)
• 支持动态版本的版本
• 发现很快(二进制搜索)

如果范围被冻结(即使它们的值不是),您可能希望使用Loki::AssocVector以减少内存开销并稍微提高性能(基本上,它是带有映射接口的有序向量).