Finding all intervals that match predicate in vectorFinding the max subset of non-overlapping intervalsFinding overlapping time intervalsCustom vector that uses less memory than std::vectorFinding the total time elapsed in the union of time intervalsSubdividing intervals that contain the largest error valuesAll permutations of integer vectorFinding subsequences of vector from a vectorVector-like type for type that can't be moved or copiedHow to use a predicate to create or filter vectorCounting integers that are within intervals
What does "I’d sit this one out, Cap," imply or mean in the context?
Sequence of Tenses: Translating the subjunctive
CREATE opcode: what does it really do?
Are student evaluations of teaching assistants read by others in the faculty?
Hostile work environment after whistle-blowing on coworker and our boss. What do I do?
India just shot down a satellite from the ground. At what altitude range is the resulting debris field?
How did Arya survive the stabbing?
Is oxalic acid dihydrate considered a primary acid standard in analytical chemistry?
Why Were Madagascar and New Zealand Discovered So Late?
Why didn't Theresa May consult with Parliament before negotiating a deal with the EU?
Sort a list by elements of another list
What can we do to stop prior company from asking us questions?
How can I get through very long and very dry, but also very useful technical documents when learning a new tool?
How to Reset Passwords on Multiple Websites Easily?
How to pronounce the slash sign
Gears on left are inverse to gears on right?
Is HostGator storing my password in plaintext?
Large drywall patch supports
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
Tiptoe or tiphoof? Adjusting words to better fit fantasy races
Pole-zeros of a real-valued causal FIR system
Is exact Kanji stroke length important?
Is there a good way to store credentials outside of a password manager?
Detecting if an element is found inside a container
Finding all intervals that match predicate in vector
Finding the max subset of non-overlapping intervalsFinding overlapping time intervalsCustom vector that uses less memory than std::vectorFinding the total time elapsed in the union of time intervalsSubdividing intervals that contain the largest error valuesAll permutations of integer vectorFinding subsequences of vector from a vectorVector-like type for type that can't be moved or copiedHow to use a predicate to create or filter vectorCounting integers that are within intervals
$begingroup$
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);
c++ c++11 interval
New contributor
$endgroup$
add a comment |
$begingroup$
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);
c++ c++11 interval
New contributor
$endgroup$
add a comment |
$begingroup$
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);
c++ c++11 interval
New contributor
$endgroup$
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);
c++ c++11 interval
c++ c++11 interval
New contributor
New contributor
edited yesterday
Michael Hall
New contributor
asked yesterday
Michael HallMichael Hall
1435
1435
New contributor
New contributor
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Code Review
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);
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).
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 2One 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.
$endgroup$
add a comment |
$begingroup$
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 ofstd::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;
$endgroup$
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
$endgroup$
– Michael Hall
yesterday
1
$begingroup$
@papagaga, by the way, there isstd::erase_if
coming in C++20.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replacestd::find_if
withstd::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.
$endgroup$
– Incomputable
yesterday
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Michael Hall is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216250%2ffinding-all-intervals-that-match-predicate-in-vector%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Code Review
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);
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).
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 2One 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.
$endgroup$
add a comment |
$begingroup$
Code Review
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);
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).
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 2One 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.
$endgroup$
add a comment |
$begingroup$
Code Review
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);
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).
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 2One 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.
$endgroup$
Code Review
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);
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).
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 2One 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.
edited yesterday
Toby Speight
26.7k742118
26.7k742118
answered yesterday
IncomputableIncomputable
6,79021753
6,79021753
add a comment |
add a comment |
$begingroup$
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 ofstd::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;
$endgroup$
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
$endgroup$
– Michael Hall
yesterday
1
$begingroup$
@papagaga, by the way, there isstd::erase_if
coming in C++20.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replacestd::find_if
withstd::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.
$endgroup$
– Incomputable
yesterday
add a comment |
$begingroup$
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 ofstd::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;
$endgroup$
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
$endgroup$
– Michael Hall
yesterday
1
$begingroup$
@papagaga, by the way, there isstd::erase_if
coming in C++20.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replacestd::find_if
withstd::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.
$endgroup$
– Incomputable
yesterday
add a comment |
$begingroup$
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 ofstd::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;
$endgroup$
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 ofstd::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;
answered yesterday
papagagapapagaga
4,712421
4,712421
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
$endgroup$
– Michael Hall
yesterday
1
$begingroup$
@papagaga, by the way, there isstd::erase_if
coming in C++20.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replacestd::find_if
withstd::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.
$endgroup$
– Incomputable
yesterday
add a comment |
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
$endgroup$
– Michael Hall
yesterday
1
$begingroup$
@papagaga, by the way, there isstd::erase_if
coming in C++20.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replacestd::find_if
withstd::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.
$endgroup$
– Incomputable
yesterday
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
I like this implementation. But unfortunately the project I am working on is only C++11
$endgroup$
– Michael Hall
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
$endgroup$
– Incomputable
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn$endgroup$
– Michael Hall
yesterday
$begingroup$
std::not_fn
is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn$endgroup$
– Michael Hall
yesterday
1
1
$begingroup$
@papagaga, by the way, there is
std::erase_if
coming in C++20.$endgroup$
– Incomputable
yesterday
$begingroup$
@papagaga, by the way, there is
std::erase_if
coming in C++20.$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replace
std::find_if
with std::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.$endgroup$
– Incomputable
yesterday
$begingroup$
@MichaelHall, one can replace
std::find_if
with std::find_if_not
. I believe there is no expressive gained in C++14+ for this problem, but it might reduce the elegance significantly. It is good to include language version tag in the question, but sometimes it is ignored by reviewers.$endgroup$
– Incomputable
yesterday
add a comment |
Michael Hall is a new contributor. Be nice, and check out our Code of Conduct.
Michael Hall is a new contributor. Be nice, and check out our Code of Conduct.
Michael Hall is a new contributor. Be nice, and check out our Code of Conduct.
Michael Hall is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216250%2ffinding-all-intervals-that-match-predicate-in-vector%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
-c++, c++11, interval