c++ - 从值中找到区间

Question

假设我有一个区间列表:[1, 90], [104, 234], [235, 300], ...。每个区间都有一个名称 A1, B, B1, ...。给定一个值，我想要间隔的名称(112 -> B，100 -> special_value)。什么是最好和更快的实现？比 if/else if 列表更好的东西。

区间是有序排列的，没有重叠。我有很多值作为输入，但只有一组间隔。大小区间差别很大，有的很小，有的很大。

Answer 1

思路:为interval的begin值做一个map对象。如果我们找到了可能的区间，则检查该值是否在区间内。

class MyInterval
{
public:
  MyInterval( double begin, double end )
  : m_begin(begin), m_end(end)
  {
  };
  double m_begin, m_end;
};

bool operator < (  const MyInterval& left,  const MyInterval& right )
{
  return ( left.m_begin < right.m_begin );
}

std::map<MyInterval,std::string> store;
// use upper_bound to get the place+1 and then you could check the interval
std::map<MyInterval,std::string>::iterator iter = store.upper_bound( MyInterval(value,value) );
if ( iter != store.begin() )
{
  --iter;
  if ( iter->first.m_end >= value ) 
  {
    std::string result_text = iter->second;
    // Here is your result
  }
}

更多信息:link .

已在 Visual Studio 2010 中测试。