An Introduction to STL Algorithms

A Brief Overview of the STL

The STL is primarily composed of three different types of entities: containers, algorithms, and iterators.  Containers are written as template classes, and that means they are instantiated using a special argument referred to as a template argument, which is always a data-type (e.g. int, string, float, etc.).  When you create an STL container, the template argument you pass in specifies the type of the data you are holding within the container (syntax: 'list<int> myList' for creating a list container named mylist for holding integers).  The second entity type, algorithms, are functions capable of using and manipulating the data held within STL containers.  Algorithms typically take in a range of container elements specified by iterators and act on them.  Please note that in this article we always act on the whole container by using the iterators returned by the container.begin() and container.end() functions as it makes the examples cleaner.  Lastly, iterators are the mechanisms that allow the safe traversal of all items in STL containers; they are the entity that enables STL algorithms to process STL containers.

STL algorithms each work on a subset, if not all STL containers.  So, before using a STL algorithm you should ensure that the container(s) you are using that algorithm on provide the correct prerequisites for that algorithm.  For example, the STL sort function requires random-access iterators as input parameters, and STL lists do not provide that kind of iterator so they cannot use the function.  It's worth noting that typically when a container cannot be used by an important algorithm like sort, that container usually provides a member function to accomplish the same action in a way suitable for that container type (and list::sort is one of these cases).  Lastly, you should also know that sometimes an algorithm cannot be used with a certain container type because that algorithm would cause an invalid state when applied to that container.  A good example of this is how you cannot apply sort to an associative container (set, map) becasue associative containers are sorted by default and changing that sorting would invalidate their internal structure (despite all this criticism, sort is still a wonderful algorithm!).
 
Working Examples

The STL has a great number of algorithms built into it; far too many to try and cover in a single article.  This section aims to present some of the more useful algorithms in working, well-commented code.  It is my hope that seeing some of the STL algorithms in action will give you the start or refresher you need to begin delving into the STL yourself.  I would urge you to keep two things in mind when reading this article, though.  First, the STL often provides multiple functions for variations on a single cause, so it’s worth looking into what’s available before using any STL function (e.g. there are many, many ways to find an element or group of elements in a collection).  The other thing to remember is that many STL algorithms are less efficient than the member function algorithms provided by the STL container classes themselves.  So keep in mind that if you see a generic STL algorithm and a member function provided by your STL container with the same name, chances are the member function will accomplish the same task with greater efficiency.  Now let’s start looking at some examples:

Example #1 - STL Copy Algorithm

I'm starting with the copy algorithm as it is a very useful algorithm which will be applied throughout this article to help output the contents of STL containers quickly.  It will also be used to copy container contents between different types of containers as shown below.  First I will show you the example and then I will explain it in detail afterward.

#include <iostream>
                      #include <vector>
                      #include <deque>
                      #include <iterator>
                      
                      int main() 
                      {
                          std::cout<<std::endl<<"Creating vector and filling with values 0-9.";
                          std::vector<int> intVector;
                          for (int i = 0; i < 10; ++i)
                              intVector.push_back(i);
                      
                          std::cout<<std::endl<<std::endl<<"Using copy function to output vector contents:\n";
                          std::copy(intVector.begin(), intVector.end(), std::ostream_iterator<int>(std::cout, " "));
                      
                          std::cout<<std::endl<<std::endl<<"Creating a deque and using copy with back_inserter to populate it with vector contents back-first.";
                          std::deque<int> intDeque;
                          std::copy(intVector.begin(), intVector.end(), back_inserter(intDeque));
                      
                          std::cout<<std::endl<<std::endl<<"Using copy with front_inserter to insert vector data to the deque again front-first.";
                          std::copy(intVector.begin(), intVector.end(), front_inserter(intDeque));
                      
                          std::cout<<std::endl<<std::endl<<"Outputting the contents of the new deque with copy, should be 9..0..0..9:\n";
                          std::copy(intDeque.begin(), intDeque.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl; //Formatting
                      }

Select all Open in new window

The sample code creates a vector of 10 elements initialized with the values 0-9.  The first thing that it does after this is output the contents of the vector using the copy function (this is pretty cool, it saves you a lot of code when used frequently!).  The copy function works by taking in a range of elements specified by iterators; in this case it takes our entire vector since we used the iterators retrieved by .begin() and .end(). It copies that range specified by the first two parameters into the destination specified by the third parameter.  The third parameter can be a number of things, but in this case we have used an ostream_iterator with an integer template parameter to use the cout stream while spacing elements with a delimiter of " ".  The effect of this is basically the same as using a for loop to cycle through the vector contents and output them with cout.

Next, we create an empty deque and call copy twice with the full range of vector elements using the deque as the destination parameter.  In the first call to copy, we use back_inserter(deque) to insert each element in the range into the back of the deque one at a time.  In the second call, we do the same thing with front_inserter(deque) to insert each element in the range to the front of the deque.  The effect of this will be that the deque now holds the vector contents twice in reverse order of each other (i.e. 9,8,7...0...0...7,8,9).  We then use our first form of copy one last time to output the final contents of the deque.

Please note that not all containers support back_inserter and front_inserter.  I used a deque because it does support both and I wanted to show you that different mechanisms could be used within the copy function.

Example #2 – STL Swap Algorithm

The next code sample will display the use of the swap algorithm (stl::swap and stl::map::swap).  It will use map containers as I want this article to demonstrate to you that STL algorithms can be used on all STL containers.  Again, the detailed description will follow the code sample below.  Please note that we start by extending the standard namespace so that the copy funciton may be used in order to output the contents of our maps.  This will not be required for the rest of the STL containers used in this article.

#include <iostream>
                      #include <map>
                      #include <iterator>
                      
                      namespace std // extend the std namespace (the magic of ADL means this will be used by copy)
                      {
                          template<typename K, typename V>
                          ostream & operator << (ostream & os, std::pair<K, V> const & rhs)
                          {
                              return os << rhs.first << " => " << boolalpha << rhs.second;
                          }
                      }
                      
                      int main() 
                      {
                          std::cout<<"Creating myMap as map<int, bool> and filling with {key: int 0-9, value: key%3 > 0 -->bool}.\n";
                          std::map<int, bool> myMap;
                          for (int i = 0; i < 10; ++i)
                              myMap.insert(std::make_pair(i, i%3 > 0));
                          
                          std::cout<<std::endl<<"Creating myOtherMap and swapping its empty data with myMap using std::swap(map1, map2)...\n";
                          std::map<int, bool> myOtherMap;
                          std::swap(myMap, myOtherMap);
                          
                          std::cout<<std::endl<<"Outputting contents of MyMap:\n";    
                          std::copy(myMap.begin(), myMap.end(), std::ostream_iterator<std::pair<int, bool> >(std::cout, "\n"));
                          std::cout<<std::endl<<"Outputting contents of MyOtherMap:\n"; 
                          std::copy(myOtherMap.begin(), myOtherMap.end(), std::ostream_iterator<std::pair<int, bool> >(std::cout, "\n"));    
                          
                          std::cout << std::endl << "Swapping myMap data back into myOtherMap using std::map::swap(map2)...\n";
                          myOtherMap.swap(myMap);
                      
                          std::cout<<std::endl<<"Outputting contents of MyMap:\n";    
                          std::copy(myMap.begin(), myMap.end(), std::ostream_iterator<std::pair<int, bool> >(std::cout, "\n"));
                          std::cout<<std::endl<<"Outputting contents of MyOtherMap:\n"; 
                          std::copy(myOtherMap.begin(), myOtherMap.end(), std::ostream_iterator<std::pair<int, bool> >(std::cout, "\n")); 
                          
                          std::cout<<std::endl<<std::endl; //Formatting
                      }

Select all Open in new window

In our main function we start by creating a map that uses a key type of int and a value type of bool.  It is populated with the keys 0-9 and values of key%3 (i.e. false if key%3 evaluates to 0, and true otherwise).  This isn't that important, but it was just an easy way to create interesting data for the example.  Also, in case you don’t know, values have to be inserted into maps as pairs, and the make_pair function is just an easy way of making those pairs.

Moving on, we create another map of the same type and leave it holding no values.  We then use std::swap to swap the values of the first map with the new map.  The values contained in each map are subsequently outputted, and the second map does in fact contain all of the values initially entered into the first map, and the first map is now empty.

Lastly, we swap the container contents again using std::map::swap this time.  The container contents are outputted in the same manner.  The reason that I've shown you this is that most STL containers provide their own versions of many STL algorithms which are more efficient than the global STL algorithms themselves.  This is a very good example of that point.  Each container in the STL implements its own swap function because swap is a low-level function used in many algorithms and it greatly improves efficiency to use the optimized versions of the function wherever possible.

Example #3 – STL Transform Algorithm and Functor Use

The next example will demonstrate the use of the transform algorithm which can be used to alter the contents of a container using a functor/function object before outputting the results to a desired container.  A function object is an object (i.e. class/struct) that is created to act like a function by having an overloaded () function operator to execute the desired functionality.  This is a very useful thing to know, but I’m not going to go into more detail on the subject.  Please reference this article if you wish to read more on functors. Now, lets move on to the code sample:

#include <iostream>
                      #include <list>
                      #include <iterator>
                      #include <algorithm>
                      
                      //Functor for the transform_example.
                      class float_div7_plus2 {
                          public:
                              float operator()(float val) {
                                  return val/7+2;
                              }
                      };
                      
                      int main()
                      {
                          std::list<float> floatList;
                          for (int i = 2; i <= 16; i+=2)
                              floatList.push_back((float)i);
                      
                          std::cout<<"Displaying values held in list before transform:\n";
                          std::copy(floatList.begin(), floatList.end(), std::ostream_iterator<float>(std::cout, " "));
                      
                          std::cout<<std::endl<<std::endl<<"Transforming numbers by multiplying them by themselves (squaring them).\n";
                          std::transform(floatList.begin(), floatList.end(), floatList.begin(), floatList.begin(), std::multiplies<float>());
                      
                          std::cout<<"Displaying values held in list after transform squaring operation:\n";
                          std::copy(floatList.begin(), floatList.end(), std::ostream_iterator<float>(std::cout, " "));
                      
                          std::cout<<std::endl<<std::endl<<"Transforming numbers using custom function to divide by 7 and add 2.\n";
                          std::transform(floatList.begin(), floatList.end(), floatList.begin(), float_div7_plus2());
                          
                          std::cout<<"Displaying values held in list after transform squaring operation:\n";
                          std::copy(floatList.begin(), floatList.end(), std::ostream_iterator<float>(std::cout, " "));
                      
                          std::cout<<std::endl<<std::endl; //Formatting
                      }

Select all Open in new window

Our example starts by creating a vector of floats initialized with the values 2-16 counting up by 2.  The contents are outputted using the copy function as you should be getting accustomed to.  After this, we see our first call to transform which looks a little daunting, but it’s really not that bad!  The function call takes the normal first two parameters indicating the range we wish to act on in the source container, and as usual it’s the whole thing.  The third and fourth parameters indicate the container we wish to transform against and the container in which we wish to write our results respectively.  Only start iterators are required for those as we will by default use the same number of elements in those as we do in the source container.  The last parameter is the function object that was mentioned earlier.  There are a number of commonly required function objects built into the STL and this is a good example.  Unsurprisingly, this one causes the elements of our source container to be multiplied against the elements of our second container (which is the same container!).  We then write the results to the source container again; so what we’ve actually managed to do is square all elements in our container in a single line of code.  Not bad, is it!? Please note though that you cannot allow the source and destination iterators to cross over when acting on the same container; if they do then the result will be undefined.  It may be a better idea to look into the std::for_each algorithm when writing results to the source container outside this article.

Moving on, we output the results before calling another transform function which takes all of the same parameters with the exception of the functor.  This time we’ll use a user-defined functor which divides the element of the container by 7 and adds 2.  This is just a random decision, the functor could do anything it wanted; it could even save state and perform some complex operations if we wanted.  You can see how easy it is to dramatically change the functionality of an STL algorithm with powerful features like functors (and user-defined predicates as you’ll see later).

Example #4 – STL Sort Algorithm

Now let’s try something you’ll definitely find useful... the STL sort algorithm!  Before seeing this example, I would like to remind you of something that I said earlier: the container-specific implementation of functions is often more efficient than the global implementation, and this is a global function as all of the algorithms in this article have been.  The tricks used in this sort example are equally applicable to the container specific functions and can even be used to provide specialized sorting criteria to associative containers like sets and maps within their constructors (though please note that you can't call sort on an associative container itself as its contents are sorted automatically and doing so would damage the container's funcitonality!).  Now, take a look at the example:

#include <iostream>
                      #include <vector>
                      #include <iterator>
                      #include <algorithm>
                      
                      //Binary predicate to compare numbers by the value of their last digit.
                      bool SortByLastDigit(const int& lhs, const int& rhs) {
                          return lhs%10 < rhs%10;
                      }
                      
                      int main()
                      {
                          std::cout<<"Creating a vector of integers  that are not properly sorted using (i%3 + (i+2)).\n";
                          std::vector<int> intList;
                          for (int i = 0; i < 10; ++i)
                              intList.push_back(i%3 + (i+2));
                          
                          std::cout<<"Displaying values held in vector before sort:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl<<"Sorting numbers without providing binary predicate --> uses default of <.\n";
                          std::sort(intList.begin(), intList.end());
                          
                          std::cout<<"Displaying sorted results:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " ")); 
                          
                          std::cout<<std::endl<<std::endl<<"Sorting contents of vector using SortByLastDigit binary predicate function.\n";
                          std::sort(intList.begin(), intList.end(), SortByLastDigit);
                          
                          std::cout<<"Displaying values of list after SortByLastDigit sort:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " ")); 
                          
                          std::cout<<std::endl<<std::endl; //Formatting
                      }

Select all Open in new window

As usual, we start by creating some sample values in a vector.  Our vector will hold integers which are created using a modulus function so that they are not in order to start with.  We output the contents of the list using copy and move on to call our first sort function.  The sort function you see here, with two parameters, will call the default sort operation on the container which is always less-than (<).  So, our integer vector will come out in perfect order as you see in the next output statement.  

This is useful to know, but what’s much more interesting is the fact that we can provide something called a binary predicate on the fly to sort our container in any way we like; we do this in the next three-parameter sort call.  A binary predicate is simply a fancy way of saying a function that takes in two parameters (elements of our container) and returns true or false.  In this case, our binary predicate is called SortByLastDigit, and it returns true if the left-hand parameter provided is less than the right-hand parameter provided.  This is a standard layout for coparison functions which is essentially what the binary predicate is.  The example finishes by showing the output as usual.

Example #5 – STL Search and Replace Algorithms

You should be getting the hang of things now.  This next example will demonstrate how you can locate and alter items using the find_if and replace_if algorithms.  These are just two of the many search and modification functions for STL containers, but they should give you an idea of what’s possible.  Here’s the code:

#include <iostream>
                      #include <list>
                      #include <iterator>
                      #include <algorithm>
                      
                      int main()
                      {
                          std::cout<<"Creating intList with values 0-9.\n";
                          std::list<int> intList;
                          for (int i = 0; i < 10; ++i)
                              intList.push_back(i);
                          
                          std::cout<<"Displaying values held in list before modification:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl<<"Using find_if with unary predicate to display odd list items.\n";
                          while (true) {
                              std::list<int>::iterator found = std::find_if(intList.begin(), intList.end(), std::bind2nd(std::modulus<int>(), 2));    
                              if (found != intList.end()) {
                                  std::cout<<"Found even #: " << *found <<". --> Removing it now"<<std::endl;
                                  intList.remove(*found);
                              } 
                              else
                                  break;
                          }
                          
                          std::cout<<std::endl<<"Displaying values held in list after modification:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl<<"Replacing values that are divisible by 4 with 99.\n";
                          std::replace_if(intList.begin(), intList.end(), std::bind2nd(std::modulus<int>(), 4), 99);
                          
                          std::cout<<"Displaying values held in list after modification:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl;
                      }

Select all Open in new window

Again, we start by creating a list of 10 integers 0-9 and outputting it.  We then enter a while loop which will execute forever until all of the odd integers are removed from the list.  In order to locate odd integers, we use the find_if algorithm with a function object created by the call bind2nd(modulus<int>, 2).  

You will see bind1st and bind2nd frequently in STL, so you should know that they are simply utilities for creating a function object using another function object and a specific parameter.  In this case, we use the modulus function object and bind 2 to its second parameter so that we locate the first container element that doesn’t evaluate to 0 for mod 2 (odd numbers).  The bind1st utility would work similarly in cases that you wanted to bind a specific value to the 1st parameter of the function object in question instead.

When an element is found to be odd, it is removed with the stl::list::remove member function of our container.  Once no more odd numbers are found we break out of the loop.  After exiting the loop the contents of the list are displayed, and as expected, all remaining values are even.  We then use replace_if with bind2nd again in order do replace all numbers divisible by 4 with the value 99.  This is pretty simple, but powerful as you can see!

Example #6 – STL Generate_n and Reverse Algorithms

The last example of the article will demonstrate the generate_n and reverse algorithms of the STL. The generate algorithm comes first as we can use it to make our test data.  We’ll get straight to the code since it is pretty straight-forward!

#include <iostream>
                      #include <list>
                      #include <iterator>
                      #include <algorithm>
                      
                      int main()
                      {
                          std::cout<<"Using generate to populate list with 10 random numbers.";
                          std::list<int> intList;
                          std::generate_n(back_inserter(intList), 10, rand);
                          
                          std::cout<<std::endl<<std::endl<<"Displaying values held in list before modification:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl<<"Sorting list contents to show reverse easier.";
                          intList.sort();
                          
                          std::cout<<std::endl<<std::endl<<"Displaying values held in list after sort:\n";
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl<<"Calling reverse and displaying list after modification:\n";
                          std::reverse(intList.begin(), intList.end());
                          std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
                          
                          std::cout<<std::endl<<std::endl; //Formatting
                      }

Select all Open in new window

Our example starts by populating the container with the generate_n algorithm.  As you can see, it is one line and manages to populate our integer list with 10 random numbers using a back_inserter... not bad at all.  The first parameter is the destination, the second is the number of items to generate, and the last is how you wish to generate them.

Next, the contents are outputted and then sorted so that the reverse algorithm effects will be more visible.  The sorted contents are displayed and then the reverse algorithm is called to reverse the contents in the specified range, which is the whole container again.  That’s all there is to it.

Conclusion

After reading this article you hopefully have a greater understanding of the basic architecture of the STL and, more specifically, of the purpose of the algorithmic components provided within it.  The examples should have provided you with a basic look at the various categories of functions provided (population, search, manipulation, and functional application) by STL algorithms for use on STL containers.  You also should now be aware of function objects and predicate functions and of how they must be used as parameters in STL algorithms to get the full range of use out of them.  

One last piece of knowledge that I feel should be known is that STL algorithms are capable of processing any sequence that provides an iterator, and pointers are in fact iterators (while iterators are not necessarily pointers).  So, you can happily use something like an array in an STL algorithm by inserting pointers as its iterators (though you'll have to find the position for the end pointer which should be one spot after the last element by yourself if you're processing that far!).

Well, that's it.  I hope you enjoyed reading this article and learned something useful while doing so.  If you did and have any interest in POSIX threading, check out my previous article here:

POSIX Threads Programming in C++

Please feel free to leave comments and suggestions on the article--I’ll try to address them quickly--and if you liked the article, click “yes” on the useful links above to show your support!

References

This article was primarily written using common knowledge, but STL algorithms were also researched using "The C++ Standard Library: A Tutorial and Reference" by Nicolai M. Josuttis.  This is an excellent book, and I highly recommend it.

[Special thanks to Evilrix for editing this article so thoroughly and helping me learn alot about the STL in the process.]

Thanks for reading,

-w00te
[John Humphreys]