Finding all intervals that match predicate in vector

Question

I have a function find_all_intervals_below that iterates through a vector and finds all the index intervals of at least a given length where each element within the interval is below a given threshold.

struct Interval {
    int start;
    int end;
};

std::vector<Interval>
find_all_intervals_below(const std::vector<int> &v, const int &threshold,
                         const int &min_length) {
    auto start_position { 0 };
    auto end_position { 0 };
    std::vector<Interval> intervals;
    bool found_start { false };

    for (auto current_pos = 0; current_pos < v.size(); ++current_pos) {
        if (v[current_pos] <= threshold and not found_start) {
            start_position = current_pos;
            end_position = 0;
            found_start = true;
        } else if (found_start and v[current_pos] > threshold and end_position == 0) {
            end_position = current_pos;
            if (end_position - start_position >= min_length) {
                Interval interval;
                interval.start = start_position;
                interval.end = end_position;
                intervals.push_back(interval);
            }
            start_position = 0;
            found_start = false;
        }
    }
    if (found_start and end_position == 0 and v.size() - start_position >= min_length) {
        end_position = v.size();
        Interval interval;
        interval.start = start_position;
        interval.end = end_position;
        intervals.push_back(interval);
    }
    return intervals;
}

This function works perfectly fine, I would just like to get some input from others as I imagine there is likely much more succinct ways of doing this. search_n from STL looks like it might be a solution but I couldn't figure out how to use it for my case.

EDIT: I need the solution to be C++11 compatible, unfortunately.

Test example

const auto min_len { 3 };
const auto threshold { 3 };
const std::vector<int> v { 4, 2, 1, 1, 4, 1, 2, 4 };

const auto actual { find_all_intervals_below(v, threshold, min_len) };
const std::vector<Interval> expected { Interval(1, 4) };

assert(actual == expected);

Answer 1

Code Review

1. This piece

           Interval interval;
           interval.start = start_position;
           interval.end = end_position;
           intervals.push_back(interval);
   

   can be transformed into

   intervals.emplace_back(start_position, end_position);
   

2. Don't accept small objects by reference for read-only purposes. Although it usually doesn't hurt, in most implementations reference (which is implemented as pointer) will take up more space (compiler will probably inline the function or just pass by value though).

3. Algorithm. When there is a state which is represented by combination of flags and some metadata, flags usually go out of hand quickly. I would instead implement something like this:

   1. Set previous, current to start of the input
   2. previous = current
   3. current = first index of element that is higher than threshold
   4. if current - previous >= minlength, add to result
   5. increment current
   6. Go to 2
   

   One could also create it the other way around, e.g. searching for those below threshold.

Alternative implementation

#include <vector>
#include <algorithm>
#include <type_traits>

using index_type = std::make_signed_t<std::size_t>;

struct interval {
    index_type first;
    index_type last;
};

bool operator==(const interval lhs, const interval rhs) {
    return lhs.first == rhs.first && lhs.last == rhs.last;
}

std::vector<interval> find_suitable_intervals(const std::vector<int>& input, 
                                              const int threshold, 
                                              const index_type min_length) {
    auto predicate = [threshold](int x) {
        return x <= threshold;
    };
    std::vector<interval> intervals;
    auto first = input.begin();
    auto previous = input.begin();
    auto current = first;
    while (current != input.end()) {
        previous = current;
        current = std::find_if_not(current, input.end(), predicate);
        if (current - previous >= min_length) {
            intervals.push_back({previous - first, current - first});
        }
        if (current == input.end()) {
            break;
        }
        ++current;
    }

    return intervals;
}

int main() {
    const int min_length = 3;
    const int threshold = 3;
    const std::vector<int> v { 4, 2, 1, 1, 4, 1, 2, 4 };

    const auto actual = find_suitable_intervals(v, threshold, min_length);
    const std::vector<interval> expected { {1, 4} };

    return actual != expected;
}

Wandbox Demo.

The logic got more "flat", but there are culprits of bridging STL style with more traditional style. Also, since incrementing iterator beyond end will cause undefined behavior, I had to put in the condition to check if the loop reached end. Mixing std::size_t and std::distance/difference will cause a warning and will require a cast to get rid of the warning, since one is unsigned and the other is not, thus I created index_type. There are rumors of std::index, but I wouldn't expect it in near future.

One could also make the condition an input into the function, e.g. predicate. Then it would look like this:

find_suitable_intervals(data, min_length, [threshold](auto x) { 
    x < threshold;
});

Which is I believe is a bit more readable.

Answer 2

If you want to write concise, idiomatic C++, the best way is to rely on the STL as much as possible, as a tool as well as an inspiration.

So how would this algorithm be implemented in the STL?

• It probably wouldn't implemented so specifically. It would be more abstract: for instance, being under a threshold is a particular case of a satisfying a predicate; iterating over a vector is a particular case of iterating over a sequence (i.e a pair of iterators).

• It would also be separated into orthogonal components: finding ranges whose elements satisfy a predicate is a thing, filtering those ranges which aren't long enough another.

• Finally, complex algorithms are broken into simpler parts when possible (some say that the whole <algorithm> header is a patient construction of std::sort from its parts).

In the light of all this, I suggest:

• function signatures based on iterators

• an intermediate algorithm to find consecutive elements satisfying a predicate

• an algorithm to find all sequences of consecutive elements satisfying a predicate

• composing the latter algorithm with known STL algorithm to customize its behavior.

For instance:

#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>

// the intermediate algorithm
template <typename Iterator, typename Pred>
std::pair<Iterator, Iterator> find_range_satisfying(Iterator first, Iterator last, Pred pred) {
    auto f = std::find_if(first, last, pred);
    if (f == last) return {last, last}; // representation of failure. std::optional would have been a good choice also
    return {f, std::find_if(std::next(f), last, std::not_fn(pred))};
}

template <typename Iterator, typename Pred>
auto find_all_ranges_satisfying(Iterator first, Iterator last, Pred pred) {
    std::vector<std::pair<Iterator, Iterator>> result;
    while (first != last) {
        auto [b, e] = find_range_satisfying(first, last, pred);
        if (b == last) break;
        result.push_back({b, e});
        first = e;
    }
    return result;
}

int main() {
    const std::vector<int> v { 4, 2, 1, 1, 4, 1, 2, 4 };
    const auto threshold = 3;
    auto test = find_all_ranges_satisfying(v.begin(), v.end(), [](auto elem) { return elem < 3; });
    // composing with remove_if to obtain the desired behavior
    test.erase(std::remove_if(test.begin(), test.end(), [threshold](auto rng) {
        return std::distance(rng.first, rng.second) < threshold;
    }));
    for (auto [b, e] : test) {
        std::for_each(b, e, [](auto elem) { std::cout << elem << ' '; });
        std::cout << std::endl;
    }
}