c++ - 提取满足条件的最大连接子 vector

Question

我们以 vector 为例

std::vector<std::int32_t> allnumbers{1,2,-3,4,5,-6,7,8,9};

我们有一个 bool(boolean) 条件，例如输出数字必须大于3。
我们想要的是输出满足条件的最长子 vector 。输出的所有元素必须已连接到输入中。

std::vector<std::int32_t> allnumbers{4,5,7,8,9};

是错误的，因为5和7之前没有相邻(它们之间为-6)。

std::vector<std::int32_t> allnumbers{4,5};

是错误的，因为它不是最长的子 vector 。

std::vector<std::int32_t> allnumbers{7,8,9};

终于正确了。
如何在不使用Boost库的情况下用C++ 17标准优雅地编写算法？优雅地说，我的意思是说几行代码具有良好的可读性。尽可能充分地利用。这里的性能或内存消耗不再是问题。我认为我在下面发布的“蛮力”解决方案已经具有足够的性能。一次遍历输入，只有很少的迭代器在执行过程中保持跟踪。
以下是有效的“蛮力”解决方案:

#include <functional>
#include <iostream>
#include <stdint.h>
#include <vector>

std::vector<std::int32_t> longestConnectedVectorFullfillingPredicate(
    std::function<bool(const std::int32_t)> predicate,
    std::vector<std::int32_t> &inputVector)
{
    auto currentIt = inputVector.begin();
    auto endIt = inputVector.end();
    auto beginLongestConnectedSubvector = endIt;
    auto endLongestConnectedSubvector = endIt;
    auto longestConnectedSubvectorLength = 0;
    while (currentIt != endIt)
    {
        const auto currentBeginConnectedSubvector = std::find_if(
            currentIt, endIt, [predicate](const std::int32_t &value) {            return predicate(value); });
        const auto currentEndConnectedSubvector = std::find_if(
            currentBeginConnectedSubvector, endIt, [predicate](const std::int32_t &value) {
                return !predicate(value);
            });
        const auto currentConnectedSubvectorLength =
        std::distance(currentBeginConnectedSubvector, currentEndConnectedSubvector);
        if (currentConnectedSubvectorLength > longestConnectedSubvectorLength)
        {
            longestConnectedSubvectorLength = currentConnectedSubvectorLength;
            beginLongestConnectedSubvector = currentBeginConnectedSubvector;
            endLongestConnectedSubvector = currentEndConnectedSubvector;
        }
        currentIt = currentEndConnectedSubvector;
    }
    return std::vector<std::int32_t>(beginLongestConnectedSubvector, endLongestConnectedSubvector);
}

int main()
{
    const auto largerThree = [](std::int32_t value) { return value > 3; };
    std::vector<std::int32_t> allnumbers{1, 2, -3, 4, 5, -6, 7, 8, 9};
    auto result = longestConnectedVectorFullfillingPredicate(largerThree, allnumbers);
    for (auto res : result)
    {
        std::cout << res << std::endl;
    }
    return 0;
}

这是很多行...希望在不降低可读性的情况下将其缩短。

Answer 1

您可能会喜欢，它会执行以下操作

包括所需的 header ，定义有用的 namespace 别名和几个有用的函数对象

将allnumbers用管道传输到group_by中，这会将所有大于3的相邻数字置于一个范围/块中(所有其他数字均保持在单例范围内)

用管道将其传递到filter中，后者对数量不大于3的单例说再见

然后使用max_element找到适当的lambda传递到的最长范围

#include <boost/hana/functional/on.hpp>
#include <boost/hana/functional/partial.hpp>
#include <boost/hana/functional/reverse_partial.hpp>
#include <boost/range/numeric.hpp>
#include <functional>
#include <iostream>
#include <range/v3/algorithm/max_element.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/filter.hpp>
#include <range/v3/view/group_by.hpp>
#include <range/v3/view/transform.hpp>
#include <vector>

using boost::hana::on;
using boost::hana::reverse_partial;
using namespace ranges::views;
using namespace ranges;

auto both = [](bool x, bool y){ return x && y; };
auto greater_than_3 = reverse_partial(std::greater<>{}, 3);

int main() {

    std::vector<int> allnumbers{1,2,-3,4,5,-6,7,8,9};

    auto chunks
        = allnumbers
        | group_by(both ^on^ greater_than_3)
        | filter([](auto v){ return greater_than_3(v.front()); })
        | transform(to_vector)
        | to_vector;

    auto result = *max_element(
            chunks,
            std::less<>{} ^on^ std::mem_fn(&decltype(allnumbers)::size));

    for (auto i : result) {
        std::cout << i << ',';
    }
}