16 comments on “How to write a standard-like algorithm

  1. Pingback: 1 – How to write a standard-like algorithm in C++ | blog.offeryour.com

  2. Pingback: 1p – How to write a standard-like algorithm in C++ – Exploding Ads

  3. Fantastic write-up of the steps involved in writing an algorithm. Thanks for the excellent post.

      • Doesn’t your code have problems with NaNs? (which return false for any comparison?)
        I think it would be better to use equality comparison (==) explicitly and not making assumptions on the properties of the ordering provided by operator <.

    • Very nice! Your palindrome function would have not only won the prize, it would have won the bonus prize for theoretically perfect performance (ie, the minimum number of iterations and compares).

      Other than running the palindrome code through the test harness i used for the challenge (to give you an idea of how old it was, i had to edit it to replace the old tr1 references to random stuff with modern random stuff), I honestly didn’t really study the code all that deeply, but the recommendations i’d have off the top of my head are:

      For the palindrome:
      * There is no need for the char array specialization of is_palindrome – you could just have done a range specialization and accomplished the same thing and more.
      * You probably want to take the predicate as a forwarding reference.

      For the min-max:
      * You probably meant to use the predicate in the first function, rather than the less-than comparisons.
      * You probably want to take the predicate as a forwarding reference.
      * I’d suggest using size_t rather than unsigned as the count type.

      For the slug function:
      * That is damn sexy, making a lambda to find the next char that can be reused.

      • The palindrome function could still be slightly improved by pulling out the increment of first from the condition. This would allow you to use a prefix increment which is more efficient for non-trivial iterators.

  4. Hi,

    great article. However, I’m wondering if it’s a good idea to apply the reasoning you made about the optimization with memcpy…

    “you can copy the elements via an extremely fast memcpy()”

    …because, IMHO, this works only for primitive types and PODs. Copying complex objects like classes with non trivial ctors or copy operators using memcpy (or similar) can ruin the references to linked resources (ad esempio, pensare alla copia bit per bit di puntatori intelligenti).



    • You don’t need to call memcpy() explicitly (and you shouldn’t). When you use std::copy(), it will automatically use memcpy() if it can, in every implementation that i know of.

  5. Here’s an attempt at the histogram: http://pastebin.com/F2h3JwAn
    It uses get_min_count(), and a filtered range/iterator to not “see” previously hit values.
    I think the complexity is 2n^2. I tried getting it to log, but not sure how to do it.

  6. Pingback: STL-like palindrome checking | DL-UAT

Leave a Reply

Your email address will not be published. Required fields are marked *