113 lines
3.7 KiB
C++
113 lines
3.7 KiB
C++
#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");
|
|
}
|