Task[edit]
Find the index of a string (needle) in an indexable, ordered collection of strings (haystack).

Raise an exception if the needle is missing.

If there is more than one occurrence then return the smallest index to the needle.

Extra credit
Return the largest index to a needle that has multiple occurrences in the haystack.

See also
 Search a list of records

#include <string>
#include <algorithm>
#include <iterator>
#include <cstddef>
#include <exception>
#include <iostream>
 
// an exception to throw (actually, throwing an exception in this case is generally considered bad style, but it's part of the task)
class not_found: public std::exception
{
public:
  not_found(std::string const& s): text(s + " not found") {}
  char const* what() const throw() { return text.c_str(); }
  ~not_found() throw() {}
private:
  std::string text;
};
 
// needle search function, C-style interface version using standard library
std::size_t get_index(std::string* haystack, int haystack_size, std::string needle)
{
  std::size_t index = std::find(haystack, haystack+haystack_size, needle) - haystack;
  if (index == haystack_size)
    throw not_found(needle);
  else
    return index;
}
 
// needle search function, completely generic style, needs forward iterators
// (works with any container, but inefficient if not random-access-iterator)
template<typename FwdIter>
 typename std::iterator_traits<FwdIter>::difference_type fwd_get_index(FwdIter first, FwdIter last, std::string needle)
{
  FwdIter elem = std::find(first, last, needle);
  if (elem == last)
    throw not_found(needle);
  else
    return std::distance(first, elem);
}
 
// needle search function, implemented directly, needs only input iterator, works efficiently with all sequences
template<typename InIter>
 typename std::iterator_traits<InIter>::difference_type generic_get_index(InIter first, InIter last, std::string needle)
{
  typename std::iterator_traits<InIter>::difference_type index = 0;
  while (first != last && *first != needle)
  {
    ++index;
    ++first;
  }
  if (first == last)
    throw not_found(needle);
  else
    return index;
}
 
// ----------------------------------------------------------------------------------------------------------------------------------
 
// a sample haystack (content copied from Haskell example)
std::string haystack[] = { "Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush", "Bozo" };
 
// some useful helper functions
template<typename T, std::size_t sz> T* begin(T (&array)[sz]) { return array; }
template<typename T, std::size_t sz> T* end(T (&array)[sz]) { return array + sz; }
template<typename T, std::size_t sz> std::size_t size(T (&array)[sz]) { return sz; }
 
// test function searching a given needle with each of the methods
void test(std::string const& needle)
{
  std::cout << "-- C style interface --\n";
  try
  {
    std::size_t index = get_index(haystack, size(haystack), needle);
    std::cout << needle << " found at index " << index << "\n";
  }
  catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
  {
    std::cout << exc.what() << "\n";
  }
 
  std::cout << "-- generic interface, first version --\n";
  try
  {
    std::size_t index = fwd_get_index(begin(haystack), end(haystack), needle);
    std::cout << needle << " found at index " << index << "\n";
  }
  catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
  {
    std::cout << exc.what() << "\n";
  }
 
  std::cout << "-- generic interface, second version --\n";
  try
  {
    std::size_t index = generic_get_index(begin(haystack), end(haystack), needle);
    std::cout << needle << " found at index " << index << "\n";
  }
  catch(std::exception& exc) // better catch standard exceptions as well; me might e.g. run out of memory
  {
    std::cout << exc.what() << "\n";
  }
}
 
int main()
{
  std::cout << "\n=== Word which only occurs once ===\n";
  test("Wally");
  std::cout << "\n=== Word occuring multiple times ===\n";
  test("Bush");
  std::cout << "\n=== Word not occuring at all ===\n";
  test("Goofy");
}