разбиение диапазона отсортированных элементов на смежные группы - PullRequest
Новая
       69

разбиение диапазона отсортированных элементов на смежные группы

0 голосов
/ 24 сентября 2018

У меня есть отсортированный список пунктов ниже.Мне нужно определить, как выбрать пары элементов [включительно, эксклюзивно] из этого списка так, чтобы разница между ними превышала некоторое фиксированное значение (например, 5 в приведенном ниже примере).

Следовательно, это должно привести к разбиениюсписок в смежные диапазоны (ни один элемент не пропущен).

Я понял, как это сделать методом грубой силы ( см. живую демонстрацию COLIRU ), но я уверендолжно быть более элегантное решение, и я, вероятно, пропускаю некоторые крайние случаи (например, 1 список, содержащий единственное значение, должен привести к пустой паре).Я думал, что какой-то вариант алгоритмов диапазона stl, std::adjacent_find или комбинация std::lower_bound/std::upper_bound, может быть использован для определения этих включающих / исключающих пар - например, с использованием или некоторого поиска по диапазону в цикле или некоторого рода - но яне могу понять.

Оперативный поиск значений { 100, 104, 108, 112, 116, 120 } приводит к следующим непересекающимся диапазонам.Обратите внимание, что последняя пара (разница 4 (то есть <5) - это особый случай (см. Код). </p> 

[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) + ')'; } );  
}

1 Ответ

0 голосов
/ 25 сентября 2018 
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);

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

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-нота.Это: 

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.Я знаю, что людям нравится говорить «нет необработанных циклов», но я редко вижу, чтобы transform приводил к читабельному коду…

...