6
\$\begingroup\$

In the following answer, @Incomputable basically dared me to implement a generalization of std::minmax_element.

Have you thought about creating a search function that finds N elements based on N predicates, and return an std::array with the iterators to found elements? I just believe that std::minmax_element can be generalized.

I'm happy to oblige:

#include <array>

template<typename IteT, typename... PredsT>
auto multi_search_elements(IteT begin, IteT end, PredsT const&... preds) {
    const std::size_t count = sizeof...(PredsT);
    std::array<IteT, count> selected;

    selected.fill(begin);
    if(begin != end) {
      for(++begin; begin != end; ++begin) {
        std::size_t i = 0;
        ( (selected[i] = preds(*selected[i], *begin) ? selected[i] : begin, 
           ++i), ...);
      }
    }

  return selected;
}

Usage:

#include <iostream>
#include <vector>
#include <functional>

int main() {
  std::vector<int> vals = {1,2,3,4,5};

  auto found = multi_search_elements(vals.begin(), vals.end(), std::less<int>(), std::greater<int>());

  for(auto i : found) {
    std::cout << *i << std::endl;
  }
  return 0;
}

Edit: I understand this fold expression might look like voodoo to people who are not used to that type of code, so I'll elaborate on what's going on here for those of you who are curious:

The fold expression looks like this: (EXPR, ...), which will expand to EXPR, EXPR, EXPR, etc..., where the "binary" operator used is actually the comma operator, which effectively just sequences the expressions while leaving them unrelated.

After that, all I do is make EXPR be SUB_EXPR, ++i, so the whole thing expands as:

(SUB_EXPR, ++i), (SUB_EXPR, ++i), (SUB_EXPR, ++i), (SUB_EXPR, ++i), ...

Which is essentially:

selected[i] = preds_0(*selected[i], *begin) ? selected[i] : begin,
++i,
selected[i] = preds_1(*selected[i], *begin) ? selected[i] : begin,
++i,
selected[i] = preds_2(*selected[i], *begin) ? selected[i] : begin,
++i,
selected[i] = preds_3(*selected[i], *begin) ? selected[i] : begin,
++i
\$\endgroup\$
  • \$\begingroup\$ Wow, this looks really good. Thank for trying it out! \$\endgroup\$ – Incomputable Nov 21 '17 at 4:46
  • \$\begingroup\$ Well, min and max are 1) based on a total ordering and 2) mutually exclusive as soon as there are two distinct values. \$\endgroup\$ – greybeard Nov 21 '17 at 10:20
  • \$\begingroup\$ @greybeard I apologize, I'm not sure what you are getting at. \$\endgroup\$ – Frank Nov 21 '17 at 14:32
  • 1
    \$\begingroup\$ Part of the fun of minmax_element() is needing 3n/2 comparisons instead of 2n. \$\endgroup\$ – greybeard Nov 21 '17 at 14:39
  • \$\begingroup\$ Ah! Yes, of course. Yeah, this idea here is not to replace minmax_elements, just expand on the semantics. You are right to point that out. \$\endgroup\$ – Frank Nov 21 '17 at 14:43
4
\$\begingroup\$

This code is pretty good, and there's very little to improve. The two-line fold expression did benefit from the explanatory comment in the description, so perhaps it could get a summary in the code?

I found a couple of very minor simplifications:

  • We can declare count as

        static const auto count = sizeof...(PredsT);
    
  • Instead of duplicating ++begin in a for loop, we can transform to a simpler while loop:

        while (++begin != end) {
    
  • Instead of indexing selected, we might choose to iterate (and avoid a no-op assignment, and avoid the need to remember precedence of comma operator):

        auto p = selected.begin();
        ((preds(**p, *begin) ? *p++ : *p++ = begin), ...);
    
\$\endgroup\$
  • \$\begingroup\$ Your fold expression looks a million time better than mine, but I worry about the value of p in the call to preds. I can't test right now, but iirc it's not clear when the incrementation should happen in that case. \$\endgroup\$ – Frank Nov 21 '17 at 13:55
  • \$\begingroup\$ I did originally have ++p outside the ?: expression as you did; just moved it inside because I never remember the precedence of , (I do actually know it's lower precedence, but it's like there's implicit grouping of the middle argument). I'm pretty sure there's an ordering of side-effects at the ?. \$\endgroup\$ – Toby Speight Nov 21 '17 at 14:10
  • \$\begingroup\$ In case that's not clear: I had (*p = (preds(**p, *begin) ? *p : begin, ++p), ...) working happily \$\endgroup\$ – Toby Speight Nov 21 '17 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.