Объединение элементов в коллекции, которые удовлетворяют предикату

Question

Мне интересно, есть ли алгоритм объединения элементов в коллекции, которые удовлетворяют предикату Что-то вроде следующего кода:

struct Element
{
  int size;
  constexpr static int maxSize = 150;
  enum Type { Mergeable, notMergeable } type;
};

auto predicate = [](const Element& el1, const Element& el2)
{
  //Done by the algorithm

  if(&el1 == &el2) // An element should not merge with itself obviously
    return false;

  if(el1.size == 0 || el2.size == 0) //element is marked for deletion
    return false; 

  //User predicate:
  bool isBelowMaxSize = el1.size + el2.size < Element::maxSize;
  bool isMergeable = el1.type  == Element::Type::Mergeable  && el2.type  == Element::Type::Mergeable;

  return isBelowMaxSize && isMergeable;
}

//User merge function
auto merge = [](Element& el1, Element& el2)
{
  el1 += el2;

  //Done by the algorithm
  el2.size = 0; //Marks for deletion
}

int main()
  std::vector<Element> els;
  //Let's assume els contains elements
  for(auto& el1 : els)
      for(auto& el2 : els)
          if(predicate(el1, el2))
            merge(el1, el2)

  //Merged elements are now removed
}

Я думал, что мог бы сделать то же самое с диапазонами:

    namespace rv = ranges::views;
    auto result = rv::cartesian_product(els, els) | rv::filter(predicate) | rv::for_each(merge);

Но я боюсь, что это не будет работать правильно, поскольку он может попытаться объединить элементы, которые уже были объединены.

Итак, есть ли чистый способ сделать это?

Answer 1

Вы можете избежать сложности O (n ² ) , предварительно отфильтровав все Element::Type::Mergeable элементов с size < Element::maxSize в отдельный контейнер (то есть O (n ) ) и сортирует его по размеру ( O (n log n) ).

С отсортированным контейнером кандидатов вы можете легко пройти его с обоих концов до ваши итераторы встречаются посередине. Объединение самых больших и самых маленьких элементов даст все допустимые слияния за линейное время.

Answer 2

Благодаря помощи @Useless, @Ted Lyngmo и @Caleth, вот мой ответ

//Expects a range sorted in descending order
template<class It, class Predicate, class Sum>
[[nodiscard]] static It merge_if(It first, It last, Predicate predicate, Sum sum)
{
    assert(first != last);
    last--;

    while (first != last)
    {
        while (predicate(*first, *last))
        {
            *first = sum(*first, *last);
            last--;
        }
        first++;
    }
    first++;
    return first; //One past the end
}

template<class It, class Predicate>
[[nodiscard]] static It merge_if(It first, It last, Predicate predicate)
{
    using Type = std::remove_cv_t<std::remove_reference_t<decltype(*first)>>;
    auto plus = [](const Type &first, const Type &second) { return first + second; };
    return merge_if(first, last, predicate, plus);
}

Некоторые тестовые примеры доступны на my GitLab