Generalization of two methods

Question

Consider the structure:

struct B {int b1, b2;};

struct A {
  std::set<B, compBLess> m_setLess;
  std::set<B, compBGreater> m_setGreater;

  void onFirst(int val) {
    auto i_set = m_setLess.begin();
    auto comp = [&](){ return val >= i_set->b1; };

    while ( i_set != m_setLess.end() && comp() ) {
      sameForBoth(*i_set);
      ++i_set;
    }
  }

  void onSecond(int val) {
    auto i_set = m_setGreater.begin();
    auto comp = [&](){ return val <= i_set->b1; };

    while ( i_set != m_setGreater.end() && comp() ) {
      sameForBoth(*i_set);
      ++i_set;
    }
  }

  void sameForBoth() {}
};

Is it possible to refactor methods onFirst and onSecond into one laconic without suffering code maintanability? Note, that compBLess/compBGreater can't be used instead of comp.

My take on the problem:

  template<typename TSet>
  void onBoth(int val){
    TSet* set;
    if ( std::is_same<TSet, decltype(m_setLess)>::value ) {
      set = reinterpret_cast<TSet*>(&m_setLess);
    } else {
      set = reinterpret_cast<TSet*>(&m_setGreater);
    }

    auto i_set = set->begin();

    std::function<bool()> comp;
    if( std::is_same<TSet, decltype(m_setLess)>::value )
      comp = std::function<bool()>([&]() { return val >= i_set->b1; });
    else
      comp = std::function<bool()>([&]() { return val <= i_set->b1; });

    while ( i_set != set->end() && comp() ) {
      sameForBoth(*i_set);
      ++i_set;
    }
  }

But my solution seems too complex. Also I'm not sure that using reinterpret_cast<> in such manner is a good practice.

Is there any other way?

Answer 1

If I understand this correctly, it seems that you want to apply an action on each element that happens to satisfy the comp unary predicate. Therefore, we may scan the elements linearly and apply a function until a given predicate holds.

Since you are working on a range, a possible approach is to design a generic procedure, as in:

template <typename I, typename P, typename F>
// I models InputIterator
// P models UnaryPredicate
// F models UnaryFunction
// Domain<P> == ValueType<I>
// Domain<F> == ValueType<I>
void apply_until(I first, I last, P p, F f) {
  while (first != last) {
    if (!p(*first)) return;
    f(*first);
    ++first;
  }
}

We can use such a generic algorithm to, e.g., print out the values in a range that happen to be strictly less than 3:

int main() {
  std::set<int> s1 = {1, 2, 3, 4, 5};
  apply_until(s1.begin(), s1.end(), [](int x) { return x < 3;}, [](int x) { std::cout << x << '\n'; });
}

I would keep the distinction between onFirst and onSecond, as they are meant to operate on distinct sets. The code for your use case may reduce to something like:

void onFirst(int val) {
    apply_until(m_setLess.begin(), m_setLess.end(), [&](B const& x) { return x.b1 >= val; }, [&](B const& x) { sameForBoth(x); });
}

void onSecond(int val) {
    apply_until(m_setGreater.begin(), m_setGreater.end(), [&](B const& x) { return x.b1 <= val; }, [&](B const& x) { sameForBoth(x); });
}

Answer 2

In both functions, we are iterating over a range, from the beginning of the std::set up-to a given iterator which depends on the input value.

In this answer, I'll assume that compBLess and compBGreater are defined like this (the important part is that the b1 field is predominant over b2. And see at the end for a slightly different version)

struct compBLess {
  bool operator ()(B const & o1, B const& o2) const {
      return std::make_pair(o1.b1,o1.b2) < std::make_pair(o2.b1,o2.b2);
  }
};
struct compBGreater {
  bool operator ()(B const & o1, B const& o2) const {
      return std::make_pair(o1.b1,o1.b2) > std::make_pair(o2.b1,o2.b2);
  }
};

Under this assumption, then I think the idiomatic way to do this is to use lowerbound, upperbound methods of std::set to find the end of the iteration , and then use

template<typename Iterator>
void foo(Iterator it, Iterator end) {
    std::for_each(it,end,[this](auto & o){ sameForBoth(o); });
}

This will be performance-wise more efficient, because we will do O(log(size_of_set)) comparisons (using lowerbound / upperbound) instead of O(size_of_set) comparisons (using comp in the loop)

The actual implementation of the other methods looks like this:

void onFirst(int val) {
    foo(m_setLess.begin(), m_setLess.lowerbound({val,std::numeric_limits<int>::min}));
}
void onSecond(int val) {
    foo(m_setGreater.begin(), m_setGreater.upperbound({val-1,std::numeric_limits<int>::max}));
}

Edit: Following @z3dd's comment, Here is the implementation that works for slightly different compBLess and compBGreater (the ordering vs. the b2 field is reversed):

struct compBLess {
  bool operator ()(B const & o1, B const& o2) const {
      return std::make_pair(o1.b1,-o1.b2) < std::make_pair(o2.b1,-o2.b2);
  }
};
struct compBGreater {
  bool operator ()(B const & o1, B const& o2) const {
      return std::make_pair(o1.b1,-o1.b2) > std::make_pair(o2.b1,-o2.b2);
  }
};

void onFirst(int val) {
    foo(m_setLess.begin(), m_setLess.lowerbound({val,std::numeric_limits<int>::max}));
}
void onSecond(int val) {
    foo(m_setGreater.begin(), m_setGreater.upperbound({val-1,std::numeric_limits<int>::min}));
}

[Note that if compBLess and compBGreater are not implemented like any of the 2 implementations given, then the answer of @Ilio Catallo is the one to use.]