Prefer std solutions over hand written copycats

[kempofighter]

Admittedly there are many tutorials around for beginners. The purpose of this article is not to provide yet another. Instead its purpose is to make a case for why beginners should prefer the std containers and algorithms over hand written copycats. Actually, we all should prefer std solutions when writing object oriented C++ code.

The target audience is anyone who has been learning C++ and who has a basic understanding of language syntax, especially regarding instantiation of structures and classes, as well as declaring and calling functions.

First let me summarize the advantages of learning the std containers and algorithms during the early stages of your development.

1) You'll avoid lots of common mistakes when writing for loops and if statements and the chances of your program containing annoying defects decreases significantly.

2) There is a good chance that the std::algorithms are faster then your own handwritten loops or functions anyway. These are written by very intelligent people who have a lot more information about the inner workings of the compiler and the language itself.

3) Using building blocks will allow you to construct a program much faster. Instead of reinventing the wheel, learn to use the building blocks to accomplish your goals. You'll be able to spend more time studying and implementing your program's requirements.

4) You'll avoid nasty memory management gotchas. Although everyone must learn memory management eventually, allowing the std containers to do this for you will allow you to get some programs up and running without having to worry about managing dynamic memory. Memory management is a complex subject and can overwhelm a beginner. Do as little of it as possible, at first.

Let me start by stating that this website does have a pretty good tutorial for the C++ language as well as for the std libraries. The examples are typically complete so that you can compile and execute them in your own compiler. Finding a good compiler and learning to use its debugger is a large part of the battle when learning C++. Stepping through a program with a debugger is a great way to analyze a program and learn from it. The examples that I am posting have been compiled using Microsoft Visual C++ express 2008.
http://www.microsoft.com/express/vc/

Now, let's start by taking a look at some examples. The best way to learn, in my opinion, is to analyze existing code and write new test code that exercises the existing building blocks.

If you know how to call a function, then you also know how to use a std algorithm. Don't let the word algorithm fool you into thinking that they are too complicated for beginners. Consider std::count. Here we use std::count to count the number of 1s in the array. It is a template function so std::count works with arrays or std containers such as deque and vector. It can also work with custom containers and iterators because it is a template function. In this case, the pointer to the first element of the array is the begin iterator while the pointer to one past the end of the array is the end iterator (remember that arrays are zero based).

#include "stdafx.h"
#include <deque>
#include <iostream>
#include <algorithm>

void countExample()
{
    int myArray[10] = { 1, 2, 1, 3, 1, 4, 1, 5, 1, 6 };
    std::cout << "myArray contains " << std::count(myArray, myArray + 10, 1) << " 1s" << std::endl;

    std::deque<int> myDeque(myArray, myArray + 10);
    std::cout << "myDeque contains " << std::count(myDeque.begin(), myDeque.end(), 1) << " 1s" << std::endl;
}
void incorrectCustomCounter()
{
    int myArray[10] = { 1, 2, 1, 3, 1, 4, 1, 5, 1, 6 };

    // Manually search for 1s in the deque.  Can you spot the errors in the loop?
    int count(0);
    for(int i = 1; i <= 10; ++i)
    {
        if(myArray[i] = 1)
        {
            ++count;
        }
    }
    std::cout << "myDeque contains " << count << " 1s" << std::endl;
}
int main()
{
    countExample();
    incorrectCustomCounter();
    return 0;
}

Can you spot the errors in the above example? That program actually ran on my computer although incorrectCustomCounter produced an incorrect result. The program could have simply crashed. If I had simply used std::count, not only would the code have looked nicer but it would have worked correctly. Moreover, using std::count is as simple as making a function call. There is no reason to write your own counting function. std::count also provides a version that takes a predicate. Once you learn how to write predicates, the std::count becomes even more useful. Now you can extend the algorithm's capabilities even further!
http://cplusplus.com/reference/algorithm/count/
http://cplusplus.com/reference/algorithm/count_if/

[kempofighter]

Now let's take a look at a more complex example. I have noticed that many beginners post threads that have to do with simple database tasks such as managing student or customer records. This example builds a dynamic array of student records and shows how the std algorithms can be used to manipulate, sort, and search the records with very little effort and few user defined loops.

It also shows how you as a beginner could write a test application to learn how the algorithms and containers work.

#include "stdafx.h"
#include <deque>
#include <iostream>
#include <algorithm>
#include <string>

class Student
{
public:
    //constructors
    Student(std::string firstName, std::string lastName, std::string hometown, unsigned int id) 
        : firstName_(firstName), lastName_(lastName), hometown_(hometown), id_(id)  {}
    Student() : firstName_(""), lastName_(""), hometown_(""), id_(0) {}

    //destructor
    ~Student() {}

    // accessor functions
    std::string getHometown() const { return hometown_; }
    std::string getFirstName() const { return firstName_; }
    std::string getLastName() const { return lastName_; }
    unsigned int getId() const { return id_; };

    // mutator functions.
    void addSubject(const std::string& subject) { classes_.push_back(subject); }
    void setFirstName(std::string& name) { firstName_ = name; }
    void setlastName(std::string& name) { lastName_ = name; }
    void setHometown(std::string& name) { hometown_ = name; }
    void setId(std::string& name) { firstName_ = name; }

    // overloaded << so that we can output directly to a stream
    friend std::ostream& operator<<(std::ostream& os, const Student& s)
    {
        return os << s.getFirstName() << "\t\t" << s.getLastName() << "\t\t" 
                  << s.getHometown() << "\t" << s.getId(); 
    }

    // This is an overloaded relational operator.  It is needed to allow arrays of 
    // Student objects to be sorted using std::sort.  This is called during the
    // operation so that each object in the array can be compared against one another.
    bool operator<(const Student& rhs)
    {
        return (id_ < rhs.id_);
    }

    // declare friends
    friend struct PrintSubjects;
    friend struct IsTakingCalculus;

private:
    std::string firstName_;
    std::string lastName_;
    std::string hometown_;
    unsigned int id_;
    std::deque<std::string> classes_;

};


    // printing functor for use with std::foreach.  It works because operator<< is overloaded
    // for the student class.  
    struct SendToStream 
    {
        void operator() (const Student& s) { std::cout << s << std::endl; }
    } StsFtr;

    struct PrintSubjects 
    {
        void operator() (const Student& s) 
        { 
            std::cout << "\n" << s << "\n";
            std::deque<std::string>::const_iterator pos = s.classes_.begin();
            for(; pos < s.classes_.end(); ++pos)
            {
                std::cout << *pos << "   ";  // 3 spaces
            }
            std::cout << "\n";
        }
    } PsFtr;


    // used with count_if to count the number of students from san diego.  
    struct IsFromSanDiego 
    {
        bool operator() (const Student& s) { return (s.getHometown() == "San Diego, CA"); }
    } IfSdFtr;

    // used with count_if to count the number of students taking calculus
    struct IsTakingCalculus 
    {
        bool operator() (const Student& s) 
        { 
            return (std::find(s.classes_.begin(), s.classes_.end(), "calculus") != s.classes_.end()); 
        }
    } ItcFtr;

typedef std::deque<Student> Students;

int main()
{
    //Build an array of students.
    Students theStudents;

    // construct 10 students
    theStudents.push_back(Student("Sandra", "Fox", "San Diego, CA", 12111));
    theStudents.push_back(Student("Warren", "Pierce", "Fairbanks, AK", 12112));
    theStudents.push_back(Student("Dan", "Wright", "St. Louis, MO", 12113));
    theStudents.push_back(Student("Amelia", "Timlin", "Erie, PA", 24312));
    theStudents.push_back(Student("Anne", "Bradley", "Boston, MA", 24315));
    theStudents.push_back(Student("Mike", "Harding", "San Diego, CA", 24316));
    theStudents.push_back(Student("Sandra", "Brown", "Boston, MA", 38125));
    theStudents.push_back(Student("Melissa", "Turner", "Boston, MA", 38126));
    theStudents.push_back(Student("Jack", "Turner", "San Diego, CA", 12114));
    theStudents.push_back(Student("Sandra", "Rice", "St. Louis, MO", 24317));

    // print students in the original order
    std::cout << "\nPrint the students in the original order. " << std::endl;
    std::for_each(theStudents.begin(), theStudents.end(), StsFtr);

    // Use std algorithms to collect and display student metrics.
    Students::iterator pos;

    // print the student with the largest student id
    std::cout << "\nPrint the student with the largest id. " << std::endl;
    if( (pos = std::max_element(theStudents.begin(), theStudents.end())) != theStudents.end())
        StsFtr(*pos);

    // print the student with the smallest student id
    std::cout << "\nPrint the student with the smallest id. " << std::endl;
    if( (pos = std::min_element(theStudents.begin(), theStudents.end())) != theStudents.end())
        StsFtr(*pos);

    // sort the students by student id.  The operator< for the student uses the id so
    // we don't need to use a functor.
    std::cout << "\nSort the student by their student id. " << std::endl;
    std::sort(theStudents.begin(), theStudents.end());
    std::for_each(theStudents.begin(), theStudents.end(), StsFtr);

    // reverse the order
    std::cout << "\nReverse the order of elements within the container" << std::endl;
    std::reverse(theStudents.begin(), theStudents.end());
    std::for_each(theStudents.begin(), theStudents.end(), StsFtr);

    // shuffle the array into a random order
    std::cout << "\nShuffle the container " << std::endl;
    std::random_shuffle(theStudents.begin(), theStudents.end());
    std::for_each(theStudents.begin(), theStudents.end(), StsFtr);

    // add some subjects to the student classes
    std::string subjectsArray[7] = { "calculus", "physics", "philosophy", "history", "biology", "grammar", "spanish" };
    for(pos = theStudents.begin(); pos < theStudents.end(); ++pos)
    {
        // add three random subjects to each student object
        pos->addSubject(subjectsArray[1]);
        pos->addSubject(subjectsArray[3]);
        pos->addSubject(subjectsArray[5]);
        std::random_shuffle(subjectsArray, subjectsArray + 5);
    }
    std::for_each(theStudents.begin(), theStudents.end(), PsFtr);

    // Try using find and count functions using a predicate that searches for subjects contained 
    // in student objects.
    std::cout << std::count_if(theStudents.begin(), theStudents.end(), ItcFtr)
              << " are taking calculus.\n";

    std::cout << std::count_if(theStudents.begin(), theStudents.end(), IfSdFtr)
              << " are from San Diego, CA.\n";
    return 0;
}

You'll notice a couple of things about that example. First, I did not need to dynamically allocate memory directly. Therefore there is no chance of a memory leak in this program. There is no chance that I have deleted memory incorrectly, left any dangling references to objects, or used an uninitialized pointer. Second, it contains very few user defined for loops for collecting metrics, sorting, or printing the data.

Although this website provides documentation for each algorithm, it is nice to pull some things together into one example to see how they can work together. So give it a try! Copy and paste it into a project and try fiddling with it yourself. If you write any useful adaptations, feel free to post them until the thread is archived.

References:
http://cplusplus.com
http://cplusplus.com/reference/std/
http://cplusplus.com/reference/algorithm/
http://cplusplus.com/reference/stl/
http://cplusplus.com/reference/string/
Effective STL, 50 Specific Ways to Improve Your Use of the Standard Template Library, Scott Meyers
The C++ Standard Library, A Tutorial and Reference, Nicolai M. Josuttis

[Duthomhas]

Very nice!

You might want to give a little more information on just what exactly a 'functor' is (those confuse people -- so at least a link or two to learn more is good). I would also add a comment in the class definition itself as to why exactly the < operator is important.

+1

[jsmith]

For the advanced beginner (oxymoron intended), you could also write all of the above function objects as simple lambda expressions. For example, IsFromSanDiego can be written as:

boost::bind( &Student::GetHometown(), _1 ) == "San Diego, CA"

IsTakingCalculus:

std::find_if( s.classes.begin(), s.classes.end(), _1 == "calculus" );

Example:

std::cout << "There are " << std::count_if( theStudents.begin(), theStudents.end(),
    boost::bind( &Student::GetHometown(), _1 ) == "San Diego, CA" )
      << " students from San Diego" << std::endl;

[kempofighter]

Thanks for the feedback so far. I was limited in characters, and the example ended up being a bit long. I'll take the comments into consideration and post an update with some additional tips this evening. For now, I added a comment above operator<. I noticed that I forgot to write a comment for that.

[kempofighter]

I added a comment to the example explaining the point of operator< used for sorting. Duos mentioned adding some info about the functors. I've decided that to really explain functors well another article is necessary. Actually many articles could be written about functors. So let us keep it simple and explain the basic concept as it relates to this article.

First, functors are classes that define the operator() and can be used as callbacks needed by the std algorithms, among other things. In my examples I used functors as callbacks in order to customize the std algorithms. This was one of the easier ones that I wrote:

struct IsFromSanDiego 
    {
        bool operator() (const Student& s) { return (s.getHometown() == "San Diego, CA"); }
    } IfSdFtr;

// calls IfSdFtr(*studentIterator) on every student object in the range.  If the
// student is from san diego, true is returned and std::count_if increments a counter.  
// IfSdFtr is an instance of the struct and is passed to count_if as if it were a pointer to a function.
std::cout << std::count_if(theStudents.begin(), theStudents.end(), IfSdFtr)
              << " are from San Diego, CA.\n";

Notice that the functors are written using the struct keyword instead of class. This is very common. Writing a functor should be simple and since members are public by default it is much easier to write them as a struct rather than a class. Also, the base class functors in the std library <functional> header are written as structs.


Here are a couple of articles that I found to be useful while I was learning about functors.
http://en.wikipedia.org/wiki/Function_object

This one is interesting because it allows you to implement a functor in terms of another by simply negating an existing functor. It shows why it is more useful to design callbacks as functors rather than simply using a global or static member function. You can't pass "!isOdd" as the third argument to count_if because it is illegal syntax. By inheriting from a built in unary functor you have the ability to take advantage of some other useful tools built into the language such as not1. In the beginning, it is very easy to get into the habit of writing predicates or callbacks as global functions because it seems easier at first. If you get in the habit of writing functors you will be better off, although the payoff might not be obvious at first!
http://cplusplus.com/reference/std/functional/not1/