How to handle "item not found" situations in a find function?

Question

I'm frequently run into a situation where I need to report in some way that a finding an item has failed. Since there are many ways how to deal with such a situation I'm always unsure how to do it. Here are a few examples:

class ItemCollection
{
public:

    // Return size of collection if not found.
    size_t getIndex(Item * inItem)
    {
        size_t idx = 0;
        for (; idx != mItems.size(); ++idx)
        {
            if (inItem == mItems[idx])
            {
                return idx;
            }
        }
        return idx;
    }


    // Use signed int and return -1 if not found.
    int getIndexV2(Item * inItem)
    {            
        for (int idx = 0; idx != mItems.size(); ++idx)
        {
            if (inItem == mItems[idx])
            {
                return idx;
            }
        }
        return -1;
    }

    // Throw exception if not found.
    size_t getIndexV3(Item * inItem)
    {
        for (size_t idx = 0; idx != mItems.size(); ++idx)
        {
            if (inItem == mItems[idx])
            {
                return idx;
            }
        }
        throw std::runtime_error("Item not found");
    }

    // Store result in output parameter and return boolean to indicate success. 
    bool getIndex(Item * inItem, size_t & outIndex)
    {
        for (size_t idx = 0; idx != mItems.size(); ++idx)
        {
            if (inItem == mItems[idx])
            {
                outIndex = idx;
                return true;
            }
        }
        return false;
    }


private:
    std::vector<Item*> mItems; 
};

I've used all of these at some point in my (young) programming carreer. I mostly use the "return size of collection" approach because it is similar to how STL iterators work. However, I'd like to make more educated choices in the future. So, on what design principles should the decision on how to deal with not-found errors be based?

Answer 1

I think it depends on the context of what you are searching for. Is this information critical? If the information is critical, than you need to throw an exception, especially if not doing so would causes further errors down the line.

I like the return -1 if no match is found, just because you always will know exactly what that function will return if something isn't found. If you base it on the size of the collection, then you won't ever know exactly what is being returned there.

I'm also not a big fan of returning it in an output parameter, just because it's a bit more complicated, and you have to ask yourself if that added complexity is really needed for a function such as this.

Answer 2

One rule-of-thumb I've come to adopt is:

When in doubt, do as the STL does.

std::find returns an iterator beyond the end of the sequence.

The problem with deciding whether to throw an exception or return some sort of error value can be difficult. Only the higher-level code knows if something is exceptional or not, but it's the lower-level code that has to make the decision.

Answer 3

In general, I would not use your first and fourth example for any situation. Returning the size of the collection is not communicating clearly enough that no item was found, IMO (think off by one errors). I see no need to return two outputs, when you can do the same by returning only one (as in -1 = ItemNotFound).

Which method you use of the remaining two depends on the exact situation in your program. If the item should be in your collection, this situation is èxceptional. Throwing an exception would be ok in this case.

If on the other hand the item could be in your collection, this is a regular situation, so an exception is not adequate.

If you are writing a function that might be used in both situations, you should not throw an exception. Since you never know when you might need a function in some other context than you thought of first, my advise is to return -1 for item not found. You can also folow that approach for other functions, thus making your code base more consistent.

Answer 4

I mostly use the "return size of collection" approach because it is similar to how STL iterators work.

Iterator, if you are using these as accessors/mutators, based algorithms return an iterator to one-past-the-end of the collection (which you can compare to coll.end(). That is definitely a good thing IMO.

Answer 5

Your functions are more like std::string::find than any of the iterator-based functions in the algorithm header. It returns an index, not an iterator.

I don't like that your function returns the collection size to emulate "one past the end." It requires the caller to know the collection size in order to check whether the function succeeded. I like your second function better since it returns a single constant value that always means "not found." The std::string type combines both of those by returning std::string::npos, which has a value of -1, but as an unsigned type.

Stay away from the exception approach of your third function unless you have some other function that call tell in advance whether the item would be found. That is, provide some way for callers to avoid the exception.

Your fourth function is most appropriate when the returned index would be useful even when the item isn't found. If you were doing a binary search, it could be useful to know the index where the item would be found if it were in the collection. Then you could provide an insert function that accepts that value as a hint, just like std::map::insert. If you can't provide that kind of information, then don't use that kind of function since it's just more cumbersome for callers to use. Prefer your first style instead.

Answer 6

Use something like boost.optional.

Read on what is the idea behind it, and how to implement it yourself, here: http://cplusplus.co.il/2009/12/04/boost-optional-and-its-internals/

It also contains an example matching your exact question.

Answer 7

std::pair<size_t,bool>

class ItemCollection
{
public:
    typedef std::pair<size_t,bool> RC;
    // Return size of collection if not found.
    RC getIndex(Item * inItem)
    {
        size_t idx = 0;
        for (; idx != mItems.size(); ++idx)
        {
            if (inItem == mItems[idx])
            {
                return RC(idx,true);
            }
        }
        return RC((-1),false);
    }

To me, in this day and age, using magic numbers is suspect

Answer 8

Do like the STL does.

In most case this means return an iterator one past the end.
So it is comparable to end().

Your case is more like std::string where you are comparing against a const value.
I would modify your -1 case (as magic numbers tend to be brittle). Make a static const member of your class (and don't define the value in the documentation, just say that it can only be returned on a find failure) and test against this constant. Then for version 1 of your class make this const -1.

class ItemCollection
{
    static int const npos = -1;

    .....

    int getIndexV2(Item * inItem)  // returns npos on failure.

};