CODEWITHSUNDEEP
c++iterator
katang
katang

Reputation: 2774

How to prevent an iterator to go out of range?

I am using a vector to map source line numbers to code addresses. It looks like if the address argument is higher than the highest in the table, the iterator points to the next, non-existing element. For error protection, I want to disallow out-of-range input arguments. Is there a more elegant method, than I use below?

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;
}

Upvotes: 1

Views: 1119

Answers (1)

Andrzej Martyna
Andrzej Martyna

Reputation: 475

Indeed, as AndyG commented, your code suggests that the vector is sorted. Because of this you should really use a binary search algorithm: https://en.wikipedia.org/wiki/Binary_search_algorithm, Where can I get a "useful" C++ binary search algorithm?

That is the reason why the current code is slow and definitely should not be used.

But trying to answer the exact question the minimal changes to your code could be like this (note checking for emptiness and immediate returns from 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;
}

The other method is to use a „sentinel”: https://en.wikipedia.org/wiki/Sentinel_node

This method needs that you warrant that your vector ALWAYS has additional item at its end with UINT_MAX as Address (also it means that it is never empty). Then the code could look like this:

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";
}

This code should be greatly improved by using find_if: Using find_if on a vector of object, but it will be as slow as other examples here. So again - choose binary search instead.

Upvotes: 1

Related Questions