Get length of the longest sequence of numbers with the same sign












4












$begingroup$


I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:



{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0} → 4
{1, -2, 0, -1} → 1


I wrote a function:



unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
if (SIGN(a[i]) != SIGN(a[i - 1])) {
maxlen = std::max(maxlen, len);
len = 0;
} else {
if (i == a.size() - 1)
return std::max(maxlen, len + 1);
}
}

#undef SIGN

return maxlen;
}


Can you please give me tips to improve my code?










share|improve this question











$endgroup$








  • 4




    $begingroup$
    This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
    $endgroup$
    – Konrad Rudolph
    yesterday








  • 3




    $begingroup$
    Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
    $endgroup$
    – Toby Speight
    yesterday






  • 3




    $begingroup$
    Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
    $endgroup$
    – dlev
    yesterday
















4












$begingroup$


I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:



{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0} → 4
{1, -2, 0, -1} → 1


I wrote a function:



unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
if (SIGN(a[i]) != SIGN(a[i - 1])) {
maxlen = std::max(maxlen, len);
len = 0;
} else {
if (i == a.size() - 1)
return std::max(maxlen, len + 1);
}
}

#undef SIGN

return maxlen;
}


Can you please give me tips to improve my code?










share|improve this question











$endgroup$








  • 4




    $begingroup$
    This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
    $endgroup$
    – Konrad Rudolph
    yesterday








  • 3




    $begingroup$
    Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
    $endgroup$
    – Toby Speight
    yesterday






  • 3




    $begingroup$
    Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
    $endgroup$
    – dlev
    yesterday














4












4








4


1



$begingroup$


I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:



{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0} → 4
{1, -2, 0, -1} → 1


I wrote a function:



unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
if (SIGN(a[i]) != SIGN(a[i - 1])) {
maxlen = std::max(maxlen, len);
len = 0;
} else {
if (i == a.size() - 1)
return std::max(maxlen, len + 1);
}
}

#undef SIGN

return maxlen;
}


Can you please give me tips to improve my code?










share|improve this question











$endgroup$




I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:



{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0} → 4
{1, -2, 0, -1} → 1


I wrote a function:



unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
if (SIGN(a[i]) != SIGN(a[i - 1])) {
maxlen = std::max(maxlen, len);
len = 0;
} else {
if (i == a.size() - 1)
return std::max(maxlen, len + 1);
}
}

#undef SIGN

return maxlen;
}


Can you please give me tips to improve my code?







c++ vectors






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited yesterday







eanmos

















asked yesterday









eanmoseanmos

1486




1486








  • 4




    $begingroup$
    This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
    $endgroup$
    – Konrad Rudolph
    yesterday








  • 3




    $begingroup$
    Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
    $endgroup$
    – Toby Speight
    yesterday






  • 3




    $begingroup$
    Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
    $endgroup$
    – dlev
    yesterday














  • 4




    $begingroup$
    This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
    $endgroup$
    – Konrad Rudolph
    yesterday








  • 3




    $begingroup$
    Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
    $endgroup$
    – Toby Speight
    yesterday






  • 3




    $begingroup$
    Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
    $endgroup$
    – dlev
    yesterday








4




4




$begingroup$
This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
$endgroup$
– Konrad Rudolph
yesterday






$begingroup$
This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable.
$endgroup$
– Konrad Rudolph
yesterday






3




3




$begingroup$
Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
$endgroup$
– Toby Speight
yesterday




$begingroup$
Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise...
$endgroup$
– Toby Speight
yesterday




3




3




$begingroup$
Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
$endgroup$
– dlev
yesterday




$begingroup$
Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example.
$endgroup$
– dlev
yesterday










3 Answers
3






active

oldest

votes


















9












$begingroup$

A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).



No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.



When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.



(More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).



Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):



#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iterator>

template<typename ForwardIt>
std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
{
auto const signdiff =
(auto a, auto b){ return std::signbit(a) != std::signbit(b); };

std::size_t maxlen = 0;

while (first != last) {
ForwardIt change = std::adjacent_find(first, last, signdiff);
if (change != last) { ++change; }

std::size_t len = std::distance(first, change);
if (len > maxlen) { maxlen = len; }

first = change;
}

return maxlen;
}


// tests:



#include <vector>

int main()
{
struct testcase { std::size_t expected; std::vector<int> inputs; };
std::vector<testcase> tests
{
{0, {}},
{1, {1}},
{1, {1, -2}},
{1, {1, -2, 3}},
{1, {-1, 2, -3}},
{2, {1, 2}},
{2, {1, 2, -3}},
{2, {-1, -2, 3}},
{2, {-1, 2, 3}},
{2, {-1, 2, 3, -4}},
};

int failures = 0;
for (auto const& [e, v]: tests) {
failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
}

return failures;
}





share|improve this answer











$endgroup$













  • $begingroup$
    std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
    $endgroup$
    – Snowhawk
    yesterday










  • $begingroup$
    You should be using std::signbit.
    $endgroup$
    – Cody Gray
    yesterday










  • $begingroup$
    @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
    $endgroup$
    – Toby Speight
    21 hours ago










  • $begingroup$
    @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
    $endgroup$
    – Toby Speight
    20 hours ago










  • $begingroup$
    The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
    $endgroup$
    – Cody Gray
    13 hours ago





















7












$begingroup$

I would raise at least the following points:




  • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.


  • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = (int v) { return v >= 0; }; and use this instead of SIGN.


  • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.







share|improve this answer









$endgroup$





















    5












    $begingroup$

    Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.



    If you are going to use a macro define it before the function (outside the function) and undefine it after the function.



    The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.






    share|improve this answer









    $endgroup$









    • 2




      $begingroup$
      It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
      $endgroup$
      – Toby Speight
      yesterday






    • 3




      $begingroup$
      I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
      $endgroup$
      – Toby Speight
      yesterday











    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%2f214758%2fget-length-of-the-longest-sequence-of-numbers-with-the-same-sign%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9












    $begingroup$

    A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).



    No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.



    When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.



    (More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).



    Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):



    #include <algorithm>
    #include <cmath>
    #include <cstddef>
    #include <iterator>

    template<typename ForwardIt>
    std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
    {
    auto const signdiff =
    (auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
    ForwardIt change = std::adjacent_find(first, last, signdiff);
    if (change != last) { ++change; }

    std::size_t len = std::distance(first, change);
    if (len > maxlen) { maxlen = len; }

    first = change;
    }

    return maxlen;
    }


    // tests:



    #include <vector>

    int main()
    {
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
    {
    {0, {}},
    {1, {1}},
    {1, {1, -2}},
    {1, {1, -2, 3}},
    {1, {-1, 2, -3}},
    {2, {1, 2}},
    {2, {1, 2, -3}},
    {2, {-1, -2, 3}},
    {2, {-1, 2, 3}},
    {2, {-1, 2, 3, -4}},
    };

    int failures = 0;
    for (auto const& [e, v]: tests) {
    failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
    }





    share|improve this answer











    $endgroup$













    • $begingroup$
      std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
      $endgroup$
      – Snowhawk
      yesterday










    • $begingroup$
      You should be using std::signbit.
      $endgroup$
      – Cody Gray
      yesterday










    • $begingroup$
      @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
      $endgroup$
      – Toby Speight
      21 hours ago










    • $begingroup$
      @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
      $endgroup$
      – Toby Speight
      20 hours ago










    • $begingroup$
      The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
      $endgroup$
      – Cody Gray
      13 hours ago


















    9












    $begingroup$

    A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).



    No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.



    When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.



    (More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).



    Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):



    #include <algorithm>
    #include <cmath>
    #include <cstddef>
    #include <iterator>

    template<typename ForwardIt>
    std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
    {
    auto const signdiff =
    (auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
    ForwardIt change = std::adjacent_find(first, last, signdiff);
    if (change != last) { ++change; }

    std::size_t len = std::distance(first, change);
    if (len > maxlen) { maxlen = len; }

    first = change;
    }

    return maxlen;
    }


    // tests:



    #include <vector>

    int main()
    {
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
    {
    {0, {}},
    {1, {1}},
    {1, {1, -2}},
    {1, {1, -2, 3}},
    {1, {-1, 2, -3}},
    {2, {1, 2}},
    {2, {1, 2, -3}},
    {2, {-1, -2, 3}},
    {2, {-1, 2, 3}},
    {2, {-1, 2, 3, -4}},
    };

    int failures = 0;
    for (auto const& [e, v]: tests) {
    failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
    }





    share|improve this answer











    $endgroup$













    • $begingroup$
      std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
      $endgroup$
      – Snowhawk
      yesterday










    • $begingroup$
      You should be using std::signbit.
      $endgroup$
      – Cody Gray
      yesterday










    • $begingroup$
      @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
      $endgroup$
      – Toby Speight
      21 hours ago










    • $begingroup$
      @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
      $endgroup$
      – Toby Speight
      20 hours ago










    • $begingroup$
      The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
      $endgroup$
      – Cody Gray
      13 hours ago
















    9












    9








    9





    $begingroup$

    A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).



    No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.



    When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.



    (More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).



    Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):



    #include <algorithm>
    #include <cmath>
    #include <cstddef>
    #include <iterator>

    template<typename ForwardIt>
    std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
    {
    auto const signdiff =
    (auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
    ForwardIt change = std::adjacent_find(first, last, signdiff);
    if (change != last) { ++change; }

    std::size_t len = std::distance(first, change);
    if (len > maxlen) { maxlen = len; }

    first = change;
    }

    return maxlen;
    }


    // tests:



    #include <vector>

    int main()
    {
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
    {
    {0, {}},
    {1, {1}},
    {1, {1, -2}},
    {1, {1, -2, 3}},
    {1, {-1, 2, -3}},
    {2, {1, 2}},
    {2, {1, 2, -3}},
    {2, {-1, -2, 3}},
    {2, {-1, 2, 3}},
    {2, {-1, 2, 3, -4}},
    };

    int failures = 0;
    for (auto const& [e, v]: tests) {
    failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
    }





    share|improve this answer











    $endgroup$



    A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).



    No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.



    When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.



    (More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).



    Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):



    #include <algorithm>
    #include <cmath>
    #include <cstddef>
    #include <iterator>

    template<typename ForwardIt>
    std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
    {
    auto const signdiff =
    (auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
    ForwardIt change = std::adjacent_find(first, last, signdiff);
    if (change != last) { ++change; }

    std::size_t len = std::distance(first, change);
    if (len > maxlen) { maxlen = len; }

    first = change;
    }

    return maxlen;
    }


    // tests:



    #include <vector>

    int main()
    {
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
    {
    {0, {}},
    {1, {1}},
    {1, {1, -2}},
    {1, {1, -2, 3}},
    {1, {-1, 2, -3}},
    {2, {1, 2}},
    {2, {1, 2, -3}},
    {2, {-1, -2, 3}},
    {2, {-1, 2, 3}},
    {2, {-1, 2, 3, -4}},
    };

    int failures = 0;
    for (auto const& [e, v]: tests) {
    failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
    }






    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited 20 hours ago

























    answered yesterday









    Toby SpeightToby Speight

    25.6k742116




    25.6k742116












    • $begingroup$
      std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
      $endgroup$
      – Snowhawk
      yesterday










    • $begingroup$
      You should be using std::signbit.
      $endgroup$
      – Cody Gray
      yesterday










    • $begingroup$
      @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
      $endgroup$
      – Toby Speight
      21 hours ago










    • $begingroup$
      @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
      $endgroup$
      – Toby Speight
      20 hours ago










    • $begingroup$
      The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
      $endgroup$
      – Cody Gray
      13 hours ago




















    • $begingroup$
      std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
      $endgroup$
      – Snowhawk
      yesterday










    • $begingroup$
      You should be using std::signbit.
      $endgroup$
      – Cody Gray
      yesterday










    • $begingroup$
      @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
      $endgroup$
      – Toby Speight
      21 hours ago










    • $begingroup$
      @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
      $endgroup$
      – Toby Speight
      20 hours ago










    • $begingroup$
      The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
      $endgroup$
      – Cody Gray
      13 hours ago


















    $begingroup$
    std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
    $endgroup$
    – Snowhawk
    yesterday




    $begingroup$
    std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (${-1}, {1, -2, -3}$).
    $endgroup$
    – Snowhawk
    yesterday












    $begingroup$
    You should be using std::signbit.
    $endgroup$
    – Cody Gray
    yesterday




    $begingroup$
    You should be using std::signbit.
    $endgroup$
    – Cody Gray
    yesterday












    $begingroup$
    @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
    $endgroup$
    – Toby Speight
    21 hours ago




    $begingroup$
    @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0).
    $endgroup$
    – Toby Speight
    21 hours ago












    $begingroup$
    @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
    $endgroup$
    – Toby Speight
    20 hours ago




    $begingroup$
    @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run.
    $endgroup$
    – Toby Speight
    20 hours ago












    $begingroup$
    The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
    $endgroup$
    – Cody Gray
    13 hours ago






    $begingroup$
    The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension.
    $endgroup$
    – Cody Gray
    13 hours ago















    7












    $begingroup$

    I would raise at least the following points:




    • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.


    • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = (int v) { return v >= 0; }; and use this instead of SIGN.


    • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.







    share|improve this answer









    $endgroup$


















      7












      $begingroup$

      I would raise at least the following points:




      • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.


      • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = (int v) { return v >= 0; }; and use this instead of SIGN.


      • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.







      share|improve this answer









      $endgroup$
















        7












        7








        7





        $begingroup$

        I would raise at least the following points:




        • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.


        • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = (int v) { return v >= 0; }; and use this instead of SIGN.


        • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.







        share|improve this answer









        $endgroup$



        I would raise at least the following points:




        • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.


        • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = (int v) { return v >= 0; }; and use this instead of SIGN.


        • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.








        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered yesterday









        JuhoJuho

        907410




        907410























            5












            $begingroup$

            Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.



            If you are going to use a macro define it before the function (outside the function) and undefine it after the function.



            The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.






            share|improve this answer









            $endgroup$









            • 2




              $begingroup$
              It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
              $endgroup$
              – Toby Speight
              yesterday






            • 3




              $begingroup$
              I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
              $endgroup$
              – Toby Speight
              yesterday
















            5












            $begingroup$

            Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.



            If you are going to use a macro define it before the function (outside the function) and undefine it after the function.



            The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.






            share|improve this answer









            $endgroup$









            • 2




              $begingroup$
              It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
              $endgroup$
              – Toby Speight
              yesterday






            • 3




              $begingroup$
              I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
              $endgroup$
              – Toby Speight
              yesterday














            5












            5








            5





            $begingroup$

            Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.



            If you are going to use a macro define it before the function (outside the function) and undefine it after the function.



            The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.






            share|improve this answer









            $endgroup$



            Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.



            If you are going to use a macro define it before the function (outside the function) and undefine it after the function.



            The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered yesterday









            pacmaninbwpacmaninbw

            5,20321537




            5,20321537








            • 2




              $begingroup$
              It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
              $endgroup$
              – Toby Speight
              yesterday






            • 3




              $begingroup$
              I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
              $endgroup$
              – Toby Speight
              yesterday














            • 2




              $begingroup$
              It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
              $endgroup$
              – Toby Speight
              yesterday






            • 3




              $begingroup$
              I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
              $endgroup$
              – Toby Speight
              yesterday








            2




            2




            $begingroup$
            It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
            $endgroup$
            – Toby Speight
            yesterday




            $begingroup$
            It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate.
            $endgroup$
            – Toby Speight
            yesterday




            3




            3




            $begingroup$
            I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
            $endgroup$
            – Toby Speight
            yesterday




            $begingroup$
            I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check.
            $endgroup$
            – Toby Speight
            yesterday


















            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%2f214758%2fget-length-of-the-longest-sequence-of-numbers-with-the-same-sign%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

            How to label and detect the document text images

            Vallis Paradisi

            Tabula Rosettana