Возможная реализация ответа Томаса Каммейера
Я нашел подход Томаса действительно умным и полезным - поскольку некоторые из нас мечтают о коде, и я нахожу фактическую реализацию немного хитрой, я хотел предоставить некоторый готовый к использованию код.
Представленное здесь решение является как можно более общим:
- Не делается никаких предположений относительно типа контейнера или диапазона, за исключением того, что их итераторы должны соответствовать требованиям ValueSwappable и RandomAccessIterator (из-за частичной сортировки с
nth_element)
- Можно использовать любой тип чисел - требуемые черты указаны ниже
Другое улучшение, которое я считаю, заключается в том, что условие отсутствия пробела можно проверить на ранней стадии: так как мы должны сканировать минимум в любом случае, мы также можем одновременно сканировать максимум и затем определять, содержит ли диапазон чисел даже пробел Стоит найти.
Последний, но не менее важный рекурсивный подход может быть адаптирован для отсортированных диапазонов! Если вы закодируете в параметре значения шаблона, был ли диапазон уже отсортирован, вы можете просто пропустить частичную сортировку и запретить определение минимального / максимального элементов.
#include <type_traits>
#include <iterator>
#include <tuple>
#include <utility>
#include <algorithm>
#include <cstddef>
// number type must be:
// * arithmetic
// * subtractable (a - b)
// * divisible by 2 (a / 2)
// * incrementable (++a)
// * less-than-comparable (a < b)
// * default-constructible (A{})
// * copy-constructible
// * value-constructible (A(n))
// * unsigned or number range must only contain values >0
/** Find lowest gap value in a range */
template<typename Range>
typename std::remove_reference_t<Range>::value_type
lowest_gap_value_unsorted(Range&& r)
{
static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range");
return lowest_gap_value_unsorted(std::begin(r), std::end(r), std::size(r));
}
/** Find lowest gap value in a range with specified size */
template<typename Range>
typename std::remove_reference_t<Range>::value_type
lowest_gap_value_unsorted(Range&& r, std::size_t N)
{
static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range");
return lowest_gap_value_unsorted(std::begin(r), std::end(r), N);
}
/** Find lowest gap value in an iterator range */
template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value_unsorted(Iterator first, Iterator last)
{
return lowest_gap_value_unsorted(first, last, std::distance(first, last));
}
/** Find lowest gap value in an iterator range with specified size */
template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value(Iterator first, Iterator last, std::size_t N)
{
typedef typename std::iterator_traits<Iterator>::value_type Number;
if (bool empty = last == first)
return increment(Number{});
Iterator minElem, maxElem;
std::tie(minElem, maxElem) = std::minmax_element(first, last);
if (bool contains0 = !(Number{} < *minElem))
throw std::logic_error("Number range must not contain 0");
if (bool missing1st = increment(Number{}) < *minElem)
return increment(Number{});
if (bool containsNoGap = !(Number(N) < increment(*maxElem - *minElem)))
return increment(*maxElem);
return lowest_gap_value_unsorted_recursive(first, last, N, *minElem);
}
template<typename Iterator>
typename std::iterator_traits<Iterator>::value_type
lowest_gap_value_unsorted_recursive(Iterator first, Iterator last, std::size_t N, typename std::iterator_traits<Iterator>::value_type minValue)
{
typedef typename std::iterator_traits<Iterator>::value_type Number;
if (N == 1)
return ++minValue;
if (N == 2)
{
// determine greater of the 2 remaining elements
Number maxValue = !(minValue < *first) ? *std::next(first) : *first;
if (bool gap = ++minValue < maxValue)
return minValue;
else
return ++maxValue;
}
Iterator medianElem = std::next(first, N / 2);
// sort partially
std::nth_element(first, medianElem, last);
if (bool gapInLowerHalf = (Number(N) / 2 < *medianElem - minValue))
return lowest_gap_value_unsorted_recursive(first, medianElem, N / 2, minValue);
else
return lowest_gap_value_unsorted_recursive(medianElem, last, N / 2 + N % 2, *medianElem);
};
template<typename T>
T increment(T v)
{
return ++v;
}