c++ - 如何防止迭代器超出范围？

Question

我正在使用 vector 将源代码行号映射到代码地址。看起来如果地址参数高于表中的最高值，迭代器将指向下一个不存在的元素。为了防止错误，我想禁止超出范围的输入参数。有没有比我在下面使用的更优雅的方法？

findLinenoToAddress(unsigned int A)
{
    if (A > AddressToLineMap[AddressToLineMap.size()-1]->Address)
        A = AddressToLineMap[AddressToLineMap.size()-1]->Address;

    std::vector<AddressToLineRecord*>::const_iterator it;
    for(it = AddressToLineMap.begin(); it != AddressToLineMap.end(); it+=1)
    {
        if ((*it)->Address >= A)
            break;
    }
    return (*it)->Lineno;
}

Answer 1

确实，正如 AndyG 评论的那样，您的代码表明 vector 已排序。正因为如此，你真的应该使用二进制搜索算法: https://en.wikipedia.org/wiki/Binary_search_algorithm , Where can I get a "useful" C++ binary search algorithm?

这就是为什么当前代码很慢并且绝对不应该使用的原因。

但是尝试回答确切的问题，对代码的最小更改可能是这样的(注意检查是否为空并立即从 ifs 返回):

int findLinenoToAddress(unsigned int A)
{
  if (AddressToLineMap.empty())
      return 0;
  if(A>AddressToLineMap[AddressToLineMap.size()-1]->Address)
      return AddressToLineMap[AddressToLineMap.size()-1]->Lineno;

  std::vector<AddressToLineRecord*>::const_iterator it;
  for(it = AddressToLineMap.begin(); it != AddressToLineMap.end(); it+=1)
    {
      if((*it)->Address >= A) break;
    }
  return (*it)->Lineno;
}

另一种方法是使用“哨兵”: https://en.wikipedia.org/wiki/Sentinel_node

此方法需要您保证您的 vector 始终在其末尾具有附加项，并将 UINT_MAX 作为地址(这也意味着它永远不会为空)。那么代码可能如下所示:

int findLinenoToAddress(unsigned int A)
{
  std::vector<AddressToLineRecord*>::const_iterator it;
  for(it = AddressToLineMap.cbegin(); it != AddressToLineMap.cend(); it++)
    {
      if((*it)->Address >= A)
         return (*it)->Lineno;
    }
  throw "an unreachable code";
}

这段代码应该通过使用 find_if 得到很大的改进: Using find_if on a vector of object ，但它会像这里的其他示例一样慢。所以再次 - 选择二进制搜索。