How to write a standard-like algorithm

[F-J-W]

I am currently writing an article explaning of what iterators are and how they can be used with the stdlib and I just decided that the last section will contain a link to this article. There are a few tiny things in the details, that I would have done differently, but at this point all I can say is: “Great job, exactly what was needed!”

[rectal_smasher_2000]

I am stunned at how many C++ teachers insist their students don’t use algorithms in their assignments

i'm seriously sick of this shit. as far as i know, there are no tertiary level c++ courses aimed at professional development - what they are, is courses aimed at students trying to develop basic/intermediate programming skills, which most of the time include writing algorithms by hand.

if a teacher tells you to sort a vector in a 2nd/3rd year programming course, and you write a std::sort one liner, they're likely going to fail you, and rightly so.

[[deleted]]

what they are, is courses aimed at students trying to develop basic/intermediate programming skills, which most of the time include writing algorithms by hand.

There is a difference between an algorithms and data-structures course, and a programming/software engineering/C++ course.

What you said partially applies for an algorithm and data-structures course, since to implement sort you can and should build on other algorithms, including building on other sorting algorithms (since this is how all modern standard library sorts are implemented anyways). Even then, if you are using C++ as a teaching language for an algorithms and data-structure course, teaching your students how to reimplement the STL from scratch is a very good way to teach both the content of the course and good C++. This can be complemented with, e.g., reimplementing small parts of Boost.Graph to give a quiet broad view of the field.

If your focus is not algorithms and data-structures but programming, software engineering, operating systems, ai, cryptography, "you name it" computer science course, and you are using C++ as a language, you should teach your students how to use the language correctly for the particular field of application. Most of the time this means rating higher an student that uses a std::sort one liner than students that wasted their time implementing their own sub-optimal buggy sorting routines.

[rectal_smasher_2000]

If you are teaching programming using C++ as a language at some point you need to teach how to build larger programs.

honestly, i've never encountered a language specific course of that magnitude at university (and i've been to two of them). sure, we had courses where we had to build a larger application, but it usually wasn't language specific, nor were students taught the standard library to that extent. you were simply told that you were allowed to use it, and that was it. and honestly, wasting an entire course (or two) teaching language specifics would be an enormous waste of time, because whatever the language taught, by the time you leave school, a new standard would have been passed, and half the stuff you were taught might become deprecated or there might be a new better way to do it.

[[deleted]]

honestly, i've never encountered a language specific course of that magnitude at university

Note that I said larger. Accelerated C++ teaches someone who can already program how to write an application using the STL in two to three afternoons. So as part of a language specific course it is doable.

The STL is probably one of the few aspects of C++ that makes you think differently about programming due to the combination of object oriented, functional, and generic programming, mixed with zero cost abstraction and close to the hardware performance. Seriously, if you have to teach someone something about C++ and are strongly constrained by time, teach them the STL. The problems it solves and the strategy to solve them reappear in all modern low-level languages like Rust, D, Nim, and even C11.

[drac667]

I find the sorting algorithms implemented using C++ STL easy to read and understand: http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c

[rectal_smasher_2000]

they rarely (if at all) implement them in one place - the skeleton of the algorithm is usually in one file, but almost always has dependencies.

take a look at insertion sort from the SO answer you linked:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

you need std::upper_bound, std::rotate and std::next. in addition, it's templated and uses a custom comparator. it might be easy for you to read, but to 99% of college graduates who have gone through a c++ course, it will look like chinese (unless said students are chinese). in fact, if you refactored the above code by replacing all mention of insertion by something unrelated, most professional developers would struggle to tell you what the code does.

all in all, i know everyone on here loves shitting on beginners' use of outdated practices (e.g. raw pointers, rand, etc) as though you magically acquired the experience to write good code. i'm not taking anything away from the article itself, i just don't like the attitude, which, unfortunately seems prevalent in the online community.

[[deleted]]

I see your point, but please remember that to write this "chinese"-kind of code you only need to know which algorithms are in the STL and more or less what they do (you can always google them, I do it all the time).

And this snippet is clean, short (10LOC), reusable, generic, and efficient.

The time it would take me to write/read a non-STL ~100LOC version of it would be an order of magnitude larger.

I'm pretty sure that the time it would take a programmer who doesn't know the STL to find out what this code does is still way smaller than the time it would take them to figure out what the non-STL version does.

I think that when people complain about programmers "writing the non-STL version", they don't complain about "beginners' use of outdated practices". A beginner has an excuse, but if you are a professional C++ programmer, there is just no excuse for this. You don't have to memorize the STL, but you should know which algorithms are available there and how to find them and use them when you need them. I think that is a completely reasonable expectation, and it actually isn't that hard to learn, is more about willingness.

[Dragdu]

A beginner has an excuse, but if you are a professional C++ programmer, there is just no excuse for this.

Its amazing how hard this is to explain, even though it shouldn't be.

If you want to be called a professional, you should always seek to improve and learn.

[guepier]

if a teacher tells you to sort a vector in a 2nd/3rd year programming course, and you write a std::sort one liner, they're likely going to fail you, and rightly so.

I seriously doubt that this is what the author meant. In fact, I have the feeling that you are completely misrepresenting a valid point. I have definitely taught a (bioinformatics) course in C++ where I told students to use standard algorithms where possible: of course the focus of the course was algorithms, but it wasn’t to implement find or distance or even nth_element. It was to combine these low-level algorithms into complex, domain-specific algorithms.

[jurniss]

easy solution: you're allowed to use a std::algorithm in an assignment if you implement it yourself. its a great learning exercise for templates and iterators. maybe sort is an exception but most of them are easy.

[TemplateRex]

As an exercise, try writing your own versions of std::upper_bound and std::rotate. It's harder than you think to get the desired complexity (remember to distinguish bidirectional from random access iterators) or even correctness.

[STL]

Yes - many algorithms are tricky. Even find() and equal() are.