How to prevent an iterator to go out of range?

Question

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

What if `AddressToLineMap` is empty? Also, the for loop can be replaced with [`std::find_if`](http://en.cppreference.com/w/cpp/algorithm/find). Are there invariants about `AddressToLineMap` that get enforced? For example, is the last element always the highest address? Does that mean the vector is sorted? If so, then there are other algorithms that can take advantage. — AndyG, Nov 16 '16 at 22:12

score 1 · Accepted Answer · edited May 23 '17 at 12:07

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.

Major bug in your solution. It does not have a return for the nothing found case. `return AddressToLineMap.back()->Lineno;` will solve that and give identical behaviour to OP's current code. Which is a bit goofy, when you think about it. All the other found cases return the value AFTER. Not found returns the value BEFORE. — user4581301, Nov 17 '16 at 00:47
@user4581301, my second example is for situation when the vector always has a sentinel with UINT_MAX on it's end. So there is no need for return after "for". IMHO OP has a few options to choose more elegant method (what was the OP question). — Andrzej Martyna, Nov 17 '16 at 19:54
Regardless, a function must return on all codepaths, even those that should be logically impossible. If there is an error that allows the loop to exit without returning, you have no idea what will happen because of the missing `return`. In this case `throw`ing an exception is in order because some seriously exceptional and bad juju just took place. Leave yourself some debugging breadcrumbs. You will also find that `find_if` will not improve performance. It cannot assume a sorted `vector` and will have to visit all elements in order until the exit condition is found. — user4581301, Nov 17 '16 at 20:20
thanks @user4581301! Your comments are great. Now I see that maybe I should not go this way. Shorter answer with single binary search example might be a better answer. — Andrzej Martyna, Nov 17 '16 at 21:54

How to prevent an iterator to go out of range?

1 Answers1