将一系列已排序元素划分为相邻的组

Question

我在下面列出了项目的排序列表。我需要确定如何从此列表中选择 [inclusive, exclusive) 项目对，使它们之间的差异超过某个固定值（例如下面示例中的 5）。

因此，这应该导致将列表划分为相邻的范围（没有遗漏任何元素）。

我想出了一个蛮力的方法来做到这一点（see live COLIRU demo），但我相信一定有一个更优雅的解决方案，我可能遗漏了一些边缘情况（例如 1 包含单个值的列表应该导致空对）。我在想 stl 范围算法的某些变体，std::adjacent_find 或 std::lower_bound/std::upper_bound 的组合可用于确定这些 inclusive/exclusive 对 - 例如在循环中使用或一些基于范围的搜索或某种 - 但我无法弄清楚。

实时搜索值 { 100, 104, 108, 112, 116, 120 } 导致以下非重叠范围。请注意，最后一对（差异为 4（即 < 5）是一种特殊情况（参见代码）。

[100,104),[108,112),[116,120)

执行此操作的代码如下：

#include <iostream>
#include <algorithm>
#include <experimental/iterator>
#include <string>
#include <vector>

int main()
{
    std::vector<int> elements = { 100, 104, 108, 112,  116, 120 };
    std::vector<std::pair<int, int>> result;
    auto current = elements.begin();
    while (current != std::prev(elements.cend())) {
        auto next = std::next(current);
        while (((*next - *current) < 5) && (next != std::prev(elements.cend()))) {
            ++next;
        }
        // consider edge case where we are at the end of the list
        if (next != std::prev(elements.cend())) {
            result.emplace_back(*current, *std::prev(next));
        } else {
            result.emplace_back(*current, *next);
        }
        current = next;
    }
    std::transform( result.cbegin(), result.cend(), std::experimental::make_ostream_joiner(std::cout, ","), 
       [](const auto& next){ return std::string("[") + std::to_string(next.first) + ',' +  std::to_string(next.second) + ')'; } );  
}

Answer 1

auto next = std::next(current);
while (((*next - *current) < 5) && (next != std::prev(elements.cend()))) {
    ++next;
}

在已排序列表中，我们正在寻找第一个元素至少比当前元素大5对吧？这正是 std::lower_bound 的用途 - 它进行二进制搜索而不是线性搜索：

auto next = std::lower_bound(std::next(current), elements.end(), *current + 5);

将其与修复循环条件相结合，直到列表的 end 而不是结束前的一个（这只是......看起来不对，需要一些严肃的理由），整个 body 可以是：

while (current != elements.end()) {
    auto next = std::lower_bound(std::next(current), elements.end(), *current + 5);
    result.emplace_back(*current, *std::prev(next));
    current = next;
}

Side-note。这个：

std::transform( result.cbegin(), result.cend(), std::experimental::make_ostream_joiner(std::cout, ","),·
   [](const auto& next){ return std::string("[") + std::to_string(next.first) + ',' +  std::to_string(next.second) + ')'; } );

对我来说似乎并不比这个更好：

bool first = true;
for (auto const& [first, second] : result) {
    if (!first) std::cout << ',';
    first = false;
    std::cout << '[' << first << '',' << second << ']';
}

YMMV。我知道人们喜欢说 "no raw loops"，但我很少看到 transform 导致可读代码....

将一系列已排序元素划分为相邻的组

partitioning a range of sorted elements into adjacent groups

c++

sorting

c++11

c++17

stl-algorithm