Generic Algo Example

generic_algo.cc

#include <iterator>

/*
 * I: iterator type
 * F: function that decides about good&bad
 */
template <typename I, typename F>
I bisect(I good, I bad, F&& f) {           // use call-by-value for iterators and universal refs for function object
    using D = typename std::iterator_traits<I>::difference_type;
    D dist;

    // generic distance calculation, since `-` might not work
    while ((dist = std::distance(good, bad)) > 1) {
        auto dist_half = dist / 2;         // don't assume that `I` can be shifted, so rely on compiler for optimization
        I mid = good;
        std::advance(mid, dist_half);      // generic advance function, since `+` might not be implemented

        if (f(*mid)) {
            good = mid;
        } else {
            bad = mid;
        }
    }

    return bad;
}


// --- usage example ---

#include <iostream>
#include <list>
#include <map>
#include <string>
#include <vector>

struct Foo {
    // tracer functions
    Foo() {
        std::cout << "Foo: constructed" << std::endl;
    }
    Foo(const Foo&) {
        std::cout << "Foo: copied" << std::endl;
    }
    Foo(Foo&&) noexcept {
        std::cout << "Foo: moved" << std::endl;
    }
    ~Foo() {
        std::cout << "Foo: destructed" << std::endl;
    }
    Foo& operator=(const Foo&) {
        std::cout << "Foo: assigned" << std::endl;
        return *this;
    }
    Foo& operator=(Foo&&) noexcept {
        std::cout << "Foo: move assigned" << std::endl;
        return *this;
    }

    bool operator()(int x) {
        return x % 2 == 0;
    }
};

int main() {
    // Example 1:
    //   container: vector
    //   function: lambda
    std::vector<int> numbers1{2, 6, 100, 4, 8, 7, 9, 3};
    auto first_bug1 = bisect(numbers1.begin(), numbers1.end() - 1, [](int x) { return x % 2 == 0; });
    std::cout << "first bug: " << *first_bug1 << std::endl;

    // Example 2:
    //   container: vector (preselected range)
    //   function: lambda
    std::vector<int> numbers2{2, 6, 100, 4, 8, 7, 9, 3};
    auto first_bug2 = bisect(numbers2.begin() + 3, numbers2.end() - 1, [](int x) { return x % 2 == 0; });
    std::cout << "first bug: " << *first_bug2 << std::endl;

    // Example 3:
    //   container: list
    //   function: object (w/o extra copy!)
    std::list<int> numbers3{2, 6, 100, 4, 8, 7, 9, 3};
    Foo f;
    auto first_bug3 = bisect(numbers3.begin(), std::prev(numbers3.end()), f);
    std::cout << "first bug: " << *first_bug3 << std::endl;

    // Example 4:
    //   container: map
    //   function: lambda
    std::map<unsigned int, int> numbers4{{0u, 2}, {1u, 6}, {2u, 100}, {3u, 4}, {4u, 8}, {5u, 7}, {6u, 9}, {7u, 3}};
    auto first_bug4 = bisect(numbers4.begin(), std::prev(numbers4.end()), [](auto&& x) { return x.second % 2 == 0; });
    std::cout << "first bug: " << first_bug4->second << std::endl;
}