Nearest neighbor search structure made simple. Performance is between sqrt(N) and N -- but fast enough for many purposes

split_iterator.cpp

template<typename T>
class SplitIterator
{
  const float pivot;
  typename vector<T>::const_iterator left, right, it;
  const typename vector<T>::const_iterator begin, end;
public:
  SplitIterator(const vector<T> &points, T origin) : pivot{origin.x()}, begin{points.begin()}, end{points.end()} {
    assert (std::is_sorted(points.begin(), points.end(), [](T a, T b) { return a.x() < b.x(); });)
    right = std::upper_bound(begin, end, origin, [](T a, T b) { return a.x() < b.x(); });
    left = right - 1;
    ++(*this);
  }
  const T& operator*() const {
    return *it;
  }
  void operator++() {
    it = (left >= begin and (right >= end or pivot - left->x() < right->x() - pivot)) ? (left--) : (right++);
  }
  bool good(float min_distance) const {
    return it != end and std::abs(it->x() - pivot) < min_distance;
  }
};