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 method can I use to design a dungeon difficult enough that the PCs can't make it through without killing them?

Aircraft with solar-panels?

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

Expand and Contract

Why does Optional.map make this assignment work?

How badly should I try to prevent a user from XSSing themselves?

Why can't we play rap on piano?

Does casting Light, or a similar spell, have any effect when the caster is swallowed by a monster?

Saudi Arabia Transit Visa

Why do bosons tend to occupy the same state?

Twin primes whose sum is a cube

What reasons are there for a Capitalist to oppose a 100% inheritance tax?

What is the difference between 仮定 and 想定?

Is there a hemisphere-neutral way of specifying a season?

What does it mean to describe someone as a butt steak?

How can saying a song's name be a copyright violation?

Is it possible to create a QR code using text?

Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?

Why doesn't using multiple commands with a || or && conditional work?

What exploit are these user agents trying to use?

Infinite Abelian subgroup of infinite non Abelian group example

Does a druid starting with a bow start with no arrows?

What do you call someone who asks many questions?

How do I gain back my faith in my PhD degree?



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













8












$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);









share|improve this question











$endgroup$
















    8












    $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);









    share|improve this question











    $endgroup$














      8












      8








      8


      1



      $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);









      share|improve this question











      $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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Mar 26 at 17:08







      Michael Hall

















      asked Mar 26 at 13:58









      Michael HallMichael Hall

      1435




      1435




















          2 Answers
          2






          active

          oldest

          votes


















          7












          $begingroup$

          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.






          share|improve this answer











          $endgroup$




















            6












            $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 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;







            share|improve this answer









            $endgroup$












            • $begingroup$
              I like this implementation. But unfortunately the project I am working on is only C++11
              $endgroup$
              – Michael Hall
              Mar 26 at 15:20










            • $begingroup$
              @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
              $endgroup$
              – Incomputable
              Mar 26 at 15:25











            • $begingroup$
              std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
              $endgroup$
              – Michael Hall
              Mar 26 at 15:26






            • 1




              $begingroup$
              @papagaga, by the way, there is std::erase_if coming in C++20.
              $endgroup$
              – Incomputable
              Mar 26 at 15:26










            • $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
              Mar 26 at 15:26












            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
            );



            );













            draft saved

            draft discarded


















            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









            7












            $begingroup$

            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.






            share|improve this answer











            $endgroup$

















              7












              $begingroup$

              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.






              share|improve this answer











              $endgroup$















                7












                7








                7





                $begingroup$

                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.






                share|improve this answer











                $endgroup$



                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.







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Mar 26 at 15:15









                Toby Speight

                27k742119




                27k742119










                answered Mar 26 at 15:03









                IncomputableIncomputable

                6,79021753




                6,79021753























                    6












                    $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 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;







                    share|improve this answer









                    $endgroup$












                    • $begingroup$
                      I like this implementation. But unfortunately the project I am working on is only C++11
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:20










                    • $begingroup$
                      @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:25











                    • $begingroup$
                      std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:26






                    • 1




                      $begingroup$
                      @papagaga, by the way, there is std::erase_if coming in C++20.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:26










                    • $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
                      Mar 26 at 15:26
















                    6












                    $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 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;







                    share|improve this answer









                    $endgroup$












                    • $begingroup$
                      I like this implementation. But unfortunately the project I am working on is only C++11
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:20










                    • $begingroup$
                      @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:25











                    • $begingroup$
                      std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:26






                    • 1




                      $begingroup$
                      @papagaga, by the way, there is std::erase_if coming in C++20.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:26










                    • $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
                      Mar 26 at 15:26














                    6












                    6








                    6





                    $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 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;







                    share|improve this answer









                    $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 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;








                    share|improve this answer












                    share|improve this answer



                    share|improve this answer










                    answered Mar 26 at 14:58









                    papagagapapagaga

                    4,762421




                    4,762421











                    • $begingroup$
                      I like this implementation. But unfortunately the project I am working on is only C++11
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:20










                    • $begingroup$
                      @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:25











                    • $begingroup$
                      std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:26






                    • 1




                      $begingroup$
                      @papagaga, by the way, there is std::erase_if coming in C++20.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:26










                    • $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
                      Mar 26 at 15:26

















                    • $begingroup$
                      I like this implementation. But unfortunately the project I am working on is only C++11
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:20










                    • $begingroup$
                      @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:25











                    • $begingroup$
                      std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                      $endgroup$
                      – Michael Hall
                      Mar 26 at 15:26






                    • 1




                      $begingroup$
                      @papagaga, by the way, there is std::erase_if coming in C++20.
                      $endgroup$
                      – Incomputable
                      Mar 26 at 15:26










                    • $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
                      Mar 26 at 15:26
















                    $begingroup$
                    I like this implementation. But unfortunately the project I am working on is only C++11
                    $endgroup$
                    – Michael Hall
                    Mar 26 at 15:20




                    $begingroup$
                    I like this implementation. But unfortunately the project I am working on is only C++11
                    $endgroup$
                    – Michael Hall
                    Mar 26 at 15:20












                    $begingroup$
                    @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                    $endgroup$
                    – Incomputable
                    Mar 26 at 15:25





                    $begingroup$
                    @MichaelHall, at first glance, other than structured bindings, I didn't find anything that C++11 capable compiler couldn't compile.
                    $endgroup$
                    – Incomputable
                    Mar 26 at 15:25













                    $begingroup$
                    std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                    $endgroup$
                    – Michael Hall
                    Mar 26 at 15:26




                    $begingroup$
                    std::not_fn is C++17 en.cppreference.com/w/cpp/utility/functional/not_fn
                    $endgroup$
                    – Michael Hall
                    Mar 26 at 15:26




                    1




                    1




                    $begingroup$
                    @papagaga, by the way, there is std::erase_if coming in C++20.
                    $endgroup$
                    – Incomputable
                    Mar 26 at 15:26




                    $begingroup$
                    @papagaga, by the way, there is std::erase_if coming in C++20.
                    $endgroup$
                    – Incomputable
                    Mar 26 at 15:26












                    $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
                    Mar 26 at 15:26





                    $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
                    Mar 26 at 15:26


















                    draft saved

                    draft discarded
















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    Adding axes to figuresAdding axes labels to LaTeX figuresLaTeX equivalent of ConTeXt buffersRotate a node but not its content: the case of the ellipse decorationHow to define the default vertical distance between nodes?TikZ scaling graphic and adjust node position and keep font sizeNumerical conditional within tikz keys?adding axes to shapesAlign axes across subfiguresAdding figures with a certain orderLine up nested tikz enviroments or how to get rid of themAdding axes labels to LaTeX figures

                    Tähtien Talli Jäsenet | Lähteet | NavigointivalikkoSuomen Hippos – Tähtien Talli

                    Do these cracks on my tires look bad? The Next CEO of Stack OverflowDry rot tire should I replace?Having to replace tiresFishtailed so easily? Bad tires? ABS?Filling the tires with something other than air, to avoid puncture hassles?Used Michelin tires safe to install?Do these tyre cracks necessitate replacement?Rumbling noise: tires or mechanicalIs it possible to fix noisy feathered tires?Are bad winter tires still better than summer tires in winter?Torque converter failure - Related to replacing only 2 tires?Why use snow tires on all 4 wheels on 2-wheel-drive cars?