When should the STL algorithms be used instead of using your own?

Question

I frequently use the STL containers but have never used the STL algorithms that are to be used with the STL containers.

One benefit of using the STL algorithms is that they provide a method for removing loops so that code logic complexity is reduced. There are other benefits that I won't list here.

I have never seen C++ code that uses the STL algorithms. From sample code within web page articles to open source projects, I haven't seen their use.

Are they used more frequently than it seems?

Modigliani

"I haven't seen their use" -- huh? I'm surprised. Can't give you counterexamples off the top of my head, but STL is definitely out there + one of the best libraries around. – Convoke

I can't remember the last time I saw a sizable C++ program without at least one STL algorithm. Heck, std::sort alone is used in 90% of non-toy programs – Sternpost

You should see our code. Millions of lines of C++ and not a sniff of the stl anywhere near it. However, we were developing C++ when the stl was just a dream, and templates poorly supported by tehcompiler writers. By the time that teh stl became fit for purpose we had been using our own rolled equivalent for several years. For us there is no need to use another implementation of a string, vector, or list class. – Weitzman

@Sternpost What would an O/S for example (to take an example of a "non-toy program") every want to sort? Wouldn't low- versus high-priority events for example be put on different queues in the first place, rather than sorted? – Wellbred

Why would an OS sort? For instance, because an effective data structure for file storage is a B-tree, which uses sorted nodes. The scheduler typically has a list of programs which may run next. Does it support multiple, overlapping windows? Then it likely has the concept of a Z-order - again, sorting. – Sternpost

@Sternpost - Surely a B-tree is already always sorted, and therefore never needs sorting. It's like, I use the std::map container a lot, but I never use the find algorithm. – Wellbred

@Wellbred "Right click -> Arrange Icons By -> Name" – Thaumatrope

c.f. Should programmers use STL or write their own code? – Nerty

Answer 1

Short answer: Always.

Long answer: Always. That's what they are there for. They're optimized for use with STL containers, and they're faster, clearer, and more idiomatic than anything you can write yourself. The only situation you should consider rolling your own is if you can articulate a very specific, mission-critical need that the STL algorithms don't satisfy.

Edited to add: (Okay, so not really really always, but if you have to ask whether you should use STL, the answer is "yes".)

Laflamme

+1 - couldn't have said it better. Why code an algorithm that already exists and have been thoroughly tested? – Uxoricide

I agree with your answer. But, I never see anybody using them. Why not? – Modigliani

I guess it all depends on what you work on. In my current and previous jobs we used them, together with boost libraries (boost::bind in particular) – Crosswalk

@sbi - I've never seen them used in sample code in any article (book, magazine, or web), I've never seen them in any of the libraries' code (some pretty significant ones too) I've looked at, I've never seen other programmers' code that use them. Any C++ code that I've ever seen has not used them. I work in a simulation environment where real-time performance is a key factor. But, I don't think that's the reason for there lack of use. I'm glad to see that others are using them since I think they should be. – Modigliani

Always, which with new C++0x lambdas is really simple. – Alisander

Answer 2

You've gotten a number of answers already, but I can't really agree with any of them. A few come fairly close to the mark, but fail to mention the crucial point (IMO, of course).

At least to me, the crucial point is quite simple: you should use the standard algorithms when they help clarify the code you're writing.

It's really that simple. In some cases, what you're doing would require an arcane invocation using std::bind1st and std::mem_fun_ref (or something on that order) that's extremely dense and opaque, where a for loop would be almost trivially simple and straightforward. In such a case, go ahead and use the for loop.

If there is no standard algorithm that does what you want, take some care and look again -- you'll often have missed something that really will do what you want (one place that's often missed: the algorithms in <numeric> are often useful for non-numeric uses). Having looked a couple of times, and confirmed that there's really not a standard algorithm to do what you want, instead of writing that for loop (or whatever) inline, consider writing an generic algorithm to do what you need done. If you're using it one place, there's a pretty good chance you can use it two or three more, at which point it can be a big win in clarity.

Writing generic algorithms isn't all that hard -- in fact, it's often almost no extra work compared to writing a loop inline, so even if you can only use it twice you're already saving a little bit of work, even if you ignore the improvement in the code's readability and clarity.

Dzungaria

It's a good answer, though with respect to bind1st etc - they were obsoleted by bind when TR1 was widely implemented, and now they are rapidly being obsoleted by C++0x lambdas (both MSVC and g++ have support already, albeit with some minor quirks). Once lambdas enter the picture, there really aren't any good reasons not to use a stock algorithm over a hand-coded loop, since readability/clarity is going to be universally in favor of algorithm+lambda. – Nasho

@Pavel: Largely true, though I think one point bears noting: large projects often continue to use older compilers long after they're "obsolete". – Dzungaria

Also when you have a large body of code that uses a tried an tested in house method, you do not necessarily want to be adding a variant into the system. Better that everything is consistent. – Weitzman

Answer 3

STL algorithms should be used whenever they fit what you need to do. Which is almost all the time.

Schism

Answer 4

When should the STL algorithms be used instead of using your own?

When you value your time and sanity and have more fun things to do than reinventing the wheel again and again.

You need to use your own algorithms when project demands it, and there are no acceptable alternatives to writing stuff yourself, or if you identified STL algorithm as a bottleneck (using profiler, of course), or have some kind of restrictions STL doesn't conform to, or adapting STL for the task will take longer than writing algorithm from scratch (I had to use twisted version of binary search few times...). STL is not perfect and isn't fit for everything, but when you can, you should use it. When someone already did all the work for you, there is frequently no reason to do the same thing again.

Clang

+1 for pointing out that 'always' does not always work. I've written for DSP devices that have no or bad STL support, in which case the easiest option is to write your own. – Digamma

Answer 5

I write performance critical applications. These are the kinds of things that need to process millions of pieces of information in as fast a time as possible. I wouldn't be able to do some of the things that I do now if it weren't for STL. Use them always.

Bloodfin

The STL [sic] algorithms are nothing you can't write yourself - they are not magic. – Seasoning

@Niel: No, but they're certainly well-written. – Latvian

@Niel: You're right in many respects. However, the library authors of a given implementation have access to inside information. This is especially true for things such as hash_map and hash_multimap which are not standards compliant. – Bloodfin

For sure you can write, but what about all the work to validate their behavior? When you use an STL component (be it a container, algorithm or whatever) you know it passed a very comprehensive set of test suites - not to mention the validation made by all the code that uses them. – Bakehouse

Answer 6

There are many good algorithms besides stuff like std::foreach.

However there are lots of non-trivial and very useful algorithms:

• Sorting: std::sort, std::upper_bound, std::lower_bound, std::binary_search
• Min/Max std::max, std::min, std::partition, std::min_element, std::max_element
• Search like std::find, std::find_first_of etc.

And many others.

Algorithms like std::transform are much useful with C++0x lambda expressions or stuff like boost::lambda or boost::bind

Doenitz

Answer 7

If I had to write something due this afternoon, and I knew how to do it using hand-made loops and would need to figure out how to do it in STL algorithms, I would write it using hand-made loops.

Having said that, I would work to make the STL algorithms a reliable part of my toolkit, for reasons articulated in the other answers.

--

Reasons you might not see it is in code is that it is either legacy code or written by legacy programmers. We had about 20 years of C++ programming before the STL came out, and at that point we had a community of programmers who knew how to do things the old way and had not yet learned the STL way. This will likely remain for a generation.

Santossantosdumont

"a community of programmers who knew how to do things the old way and had not yet learned the STL way" -- I find that std::string, and standard containers, have been far more widely adopted than the algorithms. I mean, "count_if(v.begin, v.end, bind1st(greater<int>(),7), littleNums)": please. – Wellbred

FWIW, it hurts my head (and wastes some time) whenever I have to figure out how to get bind1st and other such things to work correctly, and the code I end up with is often no clearer than a plain-old for (some_iterator = c.begin(); ...) loop. I say use the algorithms when they do something non-trivial, but don't get religious about them. – Linalinacre

@ChrisW: I expect that it is related to the fact that nouns are less strongly bound in the mind than verbs are, so objects are easier to learn over new ways of constructing algorithms. – Maura

Right, I think some things are more intuitive than others. The STL requires you to program (and think) in a different way, and if the old way's working fine... – Santossantosdumont

How about count_if(v.begin(), v.end(), [](int x) { return x > 7; })? – Nasho

@Pavel Minaev - That's why I answered that I expect to see them after (but not until) lambdas are introduced. Also maybe they're more useful in some domains than others. What kind of problem requires count_if? The only thing I'm ever likely to count, that I can think of, is using the size() method of a container. – Wellbred

@Chris: lambdas are already effectively introduced. VC++2010 ships with them, and so does GCC 4.5. As for uses - try Google code search. – Nasho

Answer 8

The only time I don't use STL algorithms is when the cross-platform implementation differences affect the outcome of my program. This has only happened in one or two rare cases (on the PlayStation 3). Although the interface of the STL is standardized across platforms, the implementation is not.

Also, in certain extremely high performance applications (think: video games, video game servers) we replaced a some STL structures with our own to eke out a bit more efficiency.

However, the vast majority of the time using STL is the way to go. And in my other (non-video game) jobs, I used the STL exclusively.

Ranunculus

Answer 9

Bear in mind that the STL algorithms cover a lot of bases, but most C++ developers will probably end up coding something that does something equivalent to std::find(), std::find_if() and std::max() almost every day of their working lives (if they're not using the STL versions already). By using the STL versions you separate the algorithm from both the logical flow of your code and from the data representation.

For other less commonly used STL algorithms such as std::merge() or std::lower_bound() these are hugely useful routines (the first for merging two sorted containers, the second for working out where to insert an item in a container to keep it ordered). If you were to try to implement them yourself then it would probably take a few attempts (the algorithms aren't complicated, but you'd probably get off-by-one errors or the like).

I myself use them every day of my professional career. Some legacy codebases that predate a stable STL may not use it as extensively, but if there's a newer project that is intentionally avoiding it I would be inclined to think it was by a part-time hacker who was still labouring under the mid-90's assumption that templates are slow and therefore to be avoided.

Purify

I use std::map not std::find(). – Wellbred

That's fine for an associative array, but if you just have a vector, list or other data structure (the neat bit is that you can also create your own data structure and as long as you provide a begin() and end() equivalent), then std::find() will work on all of them. The case for std::map is an optimisation. – Purify

Answer 10

The main problem with STL algorithms until now was that, even though the algorithm call itself clearer, defining the functors that you'd need to pass to them would make your code longer and more complex, due to the way the language forced you to do it. C++0x is expected to change that, with its support for lambda expressions.

I've been using STL heavily for the past six years and although I tried to use STL algorithms anywhere I could, in most instances it would make my code more obscure, so I got back to a simple loop. Now with C++0x is the opposite, the code seems to always look simpler with them.

The problem is that by now C++0x support is still limited to a few compilers, even because the standard is not completely finished yet. So probably we will have to wait a few years to really see widespread use of STL algorithms in production code.

Bakehouse

Answer 11

I would not use STL in two cases:

1. When STL is not designed for your task. STL is nearly the best for general purposes. However, for specific applications STL may not always be the best. For example, in one of my programs, I need a huge hash table while STL/tr1's hashmap equivalence takes too much memory.

2. When you are learning algorithms. I am one of the few who enjoy reinventing the wheels and learn a lot in this process. For that program, I reimplemented a hash table. It really took me a lot of time, but in the end all the efforts paid off. I have learned many things that greatly benefit my future career as a programmer.

Demonstrator

Answer 12

When you think you can code it better than a really clever coder who spent weeks researching and testing and trying to cope with every conceivable set of inputs.

For most Earthlings the answer is never!

Mousetrap

Answer 13

I want to answer the "when not to use STL" case, with a clear example.

(as a challenge to all of you, show me that you can solve this with any STL algorithm until C++17)

Convert a vector of integers std::vector<int> into a vector of std::pair<int,int>, i.e.:

Convert

std::vector<int> values = {1,2,3,4,5,6,7,8,9,10};

to

std::vector<std::pair<int,int>> values = { {1,2}, {3,4} , {5,6}, {7,8} ,{9,10} };

And guess what? It's impossible with any STL algorithm until C++17.

See the complete discussion on solving this problem here:

How can I convert std::vector<T> to a vector of pairs std::vector<std::pair<T,T>> using an STL algorithm?

So to answer your question: Use STL algorithm always only when it perfectly fits your problem. Don't hack an STL algorithm to make it fit your problem.

Athematic

Answer 14

Are they used more frequently than it seems?

I've never seen them used; except in books. Maybe they're used in the implementation of the STL itself. Maybe they'll become more used because easier to use (see for example Lambda functions and expressions), or even become obsoleted (see for example the Range-based for-loop), in the next version of C++ .

Wellbred

-1, they're used by anyone who knows how to use them, and the range-based for loop is hardly a replacement for them. – Latvian

@zooropa "Is it because the STL algorithms are used frequently?" YES – Doenitz

@zooropa, we use them as often as possible. Some work plce cultures frown upon the use of them due to their 'heavy' template usage which means only programmers experienced enough in C++ can manage them, but this is a poor reason to throw away a large, well tested body of code. – Uxoricide

You know... I'll upvote this. There are situations when stl isn't fit for the job. And honestly, it looks to me that containers are used more frequently than algorithms. – Clang

I'm not saying that they shouldn't be used: only that I've never seen existing code that uses them. Containers and strings and so on, (occasionally some I/O, even), yes; but algorithms, no. – Wellbred

@ChrisW: "only that I've never seen existing code that uses them." That's the reason for upvote. I have encountered vectors, strings, etc, but I most likely never saw even std::for_each in code (that was compiled by me) developed by someone else. Not even std::min and std::swap. They do, however, frequently appear in arguments made by people that really love OOP and STL. – Clang

While we're sharing personal experience, I haven't yet seen a mid-to-large-size C++ project which didn't use STL algorithms to some degree. Most certainly, stuff such as count_if and find_if is very common in the code that I've worked (and still working) with. – Nasho

@Pavel Minaev: Last two big projects I worked with were game engines. Although while one of them was ported from C (and was originally written almost in DOS era), the other one was much newer (and commercial), heavily relied on OOP, had it's own scripting language, custom template-based container classes, etc, etc. But I haven't seen a single algorithm from std:: namespace. So... I guess experiences differ. Also, it is very likely that you've seen more newer code of different kind. – Clang

@Latvian The new lambdas are supposed to make them easier to invoke. – Wellbred

@SigTerm: I'm looking at a .cpp file right now which has a copyright notice dating back to 1997. It's neither the only such file in the project, nor is it the oldest :) Of course the preserved old code doesn't have STL stuff in it, but the newer bits which were written later, do - and the more recent they are, the more likely they are to have it. – Nasho