Convention for returning from search algorithm - index or iterator

Question

Should I return an iterator or an index from a string search algorithm?

In particular, I'd like to conform to C++'s convention. Templated functions such as std::find returns an iterator because it has to since some containers are not indexible. More specialized functions such as std::string::find returns a size_t index.

The check for failure is == x.end() for std::find and == std::string::npos (usually -1) for the specialized version. I think the iterator checking method is more elegant.

Internally, I'll be using indices for performance and convenience reasons regardless of return type.

What are the advantages and disadvantages to each style of returning when I fix the input types (std::string)?

Answer 1

If you want to be STL-compliant (although even STL is not perfectly designed and std::string is the canonical example where indexes and iterators are mixed up), you should use an iterator. Then, can use std::distance to find the position in terms of typename iterator_traits<InputIterator>::difference_type (i.e., most of the time a std::size_t). Of course, this will have an overhead of O(n) for non-random access iterators, but it is the most compliant approach.

Hopefully in the future ranges will make it into the standard library http://www.boost.org/doc/libs/1_57_0/libs/range/doc/html/index.html

Answer 2

The convention for std::string searching member functions is to return an index of type size_t because other member functions, such as substr, insert, and erase take indexes. Some of them provide iterator overloads as well, but not all of them do.

If you plan to use the output of your function with std::string functions that take indexes, return an index. If you plan to use the output of your functions with functions that accept iterators, return iterators.