Template Basics and Generic Algorithms

Function objects can be used as arguments to algorithms, so the algorithm supplies the general process and the function object supplies the specific behavior.

Programming

Why Algorithms Need a Behavior Argument

Many generic algorithms do not know in advance exactly what they should do with each element they process. A sorting routine may need to decide which of two elements comes first, and a search routine may need to test each element against a condition. In template-based code, the algorithm is written once for many element types, so the part of its behavior that varies is usually handed to it from outside.

The two tools this article covers, function objects and lambdas, are two ways of providing that small piece of behavior at the point where the algorithm is called. Keep one practical question in mind as you read: when you call an algorithm that needs a behavior argument, should that behavior be a named object defined somewhere else, or should it be written directly inside the call? The rest of this article shows how the source resolves that question.

Tracing a Sort With a Comparison Rule

Consider a sorting algorithm that needs to know, for any two elements, which one should come first. The algorithm does not hard-code a single ordering. Instead it repeatedly asks the behavior it was given. The diagram below shows the algorithm making several such requests, each time handing two elements to the rule and receiving a yes or no answer about their order.

Who calls the function object, how many times, and when during the algorithm's loop does each call happen? The sort algorithm calls the comparison rule each time it needs to decide the order of a pair of elements; the calls happen in the middle of the algorithm's work, not once at the start.

cpp

#include <algorithm>
#include <iostream>
#include <vector>

struct DescendingOrder {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end(), DescendingOrder{});
    for (int x : v) std::cout << x << ' ';
}

#include <algorithm>
#include <iostream>
#include <vector>

struct DescendingOrder {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end(), DescendingOrder{});
    for (int x : v) std::cout << x << ' ';
}

Output

3 2 1

Notes on the code

DescendingOrder is a function object: a class whose operator() can be called like a function
std::sort is the generic algorithm; it supplies the general process of ordering elements
DescendingOrder{} is the specific behavior passed in as the third argument

What do you think happens?

The vector starts as 3, 1, 2 and the algorithm is given DescendingOrder. What order will the numbers be printed in?

1 2 3
3 2 1
2 1 3
3 1 2

Reveal answer

Answer:

3 2 1

The comparison rule returns true when the first argument is larger, so the algorithm places larger values first. The sort algorithm itself did not change; only the behavior argument determined the direction.

Function Objects as Arguments

Definition

A function object is an object that can be called as if it were a function, and it can be passed as an argument to an algorithm. Because the algorithm only needs something it can call, the same algorithm can be reused with many different behaviors.

This is the reason function objects fit naturally with templates. The template supplies the reusable process, and each function object supplies one particular rule for that process to follow. The algorithm stays the same from one call to the next; only the argument changes.

Which part of the code stays the same across different uses, and which part is swapped in as the argument? The algorithm's general process stays fixed, while the function object fills the behavior slot and can be replaced with a different one for each call.

Worked example

Reusing one algorithm with two behaviors

Use the same sort algorithm to order a list in two different ways, without writing a second sort.

1
Identify the general process
The sort algorithm decides how to arrange elements, but it needs a rule for which of two elements comes first.
2
Provide the first behavior
Pass a function object whose call returns true when the first argument should come before the second, such as the ascending rule.
3
Provide the second behavior
Pass a different function object, such as the descending rule, to the same algorithm. The algorithm code is unchanged.
4
Compare the results
The two calls produce opposite orders because only the behavior argument differs.

Result

One generic algorithm serves both orderings. Its general process was written once, and each function object supplied one specific rule.

Lambdas as Inline Function Objects

A lambda provides the same kind of thing as a named function object: a callable behavior that an algorithm can receive as an argument. What differs is where the behavior is written. A lambda is written directly inside the call, while a named function object is defined somewhere else and referred to by name.

cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
    for (int x : v) std::cout << x << ' ';
}

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
    for (int x : v) std::cout << x << ' ';
}

Output

3 2 1

Notes on the code

The lambda [](int a, int b) { return a > b; } is written inline as the behavior argument
The output matches the named function object version, because the behavior is the same

Deciding Between a Named Object and a Lambda

When you write a call that needs a behavior argument, the deciding question is how many places in the program need that behavior. The source's guidance reduces every choice to this one question, so the table below compares the two forms by where the behavior lives and how many places refer to it.

Aspect	Named function object	Lambda
Where the behavior is defined	Separately, as a named object	Inline, inside the call
Type of thing supplied to the algorithm	A callable behavior	A callable behavior
Best when the behavior is needed	In several places	In one place only
Effect on the surrounding code	Adds a named definition elsewhere	Keeps the behavior next to its single use

Both forms supply a callable behavior; they differ in where that behavior lives and how many places refer to it.

Given a particular situation, which question leads me to pick one form over the other? The deciding question is whether the behavior is needed in one place only.

Applying this rule to a concrete case makes the choice easy to justify. Suppose one sorting call in a program needs a comparison rule that no other code uses. A lambda keeps that rule beside the single call that needs it. Now suppose three different parts of the program sort records using the same ordering. Defining that ordering once as a named function object and passing it in each place avoids repeating the rule three times.

Mistakes When Choosing a Form

Common mistake
Writing the same lambda in several places
What it looks like
Copying the same comparison lambda into three separate sort calls in different files.
Why it fails
The source's guidance is that a behavior needed in several places is better defined once. Repeated lambdas must be kept in sync by hand.
Do this instead
Define the behavior once as a named function object and pass that object to each call.
Common mistake
Assuming a function object and a lambda are different kinds of argument
What it looks like
Believing that an algorithm must be given a named class and cannot accept an inline lambda.
Why it fails
Both forms supply a callable behavior to the algorithm; the difference is where the behavior is written.
Do this instead
Treat both as the same kind of argument and choose between them based on how many places need the behavior.
Common mistake
Choosing a named function object for a one-line rule used once
What it looks like
Defining a separate struct with an operator() that only returns a single comparison, then using it in one call.
Why it fails
The extra definition adds distance between the rule and the only place it is used, and the source identifies one-place use as the lambda case.
Do this instead
Write the simple rule as a lambda directly inside the call that needs it.
Common mistake
Forgetting that the algorithm, not the call site, decides when the behavior is invoked

Practice Choosing a Form

MEDIUM

A program sorts customer records by last name in one place only. Another function, in a different file, also needs to sort records by last name. Which form should the shared ordering use, and why? Justify your answer using the deciding question from this article.

Hints

Ask how many places in the program need this behavior.
Think about whether the behavior should be defined once and passed to both call sites.

Your attempt (not saved)

Key Takeaways

A generic algorithm supplies the general process, and a function object supplies the specific behavior passed in as an argument.
A function object is callable like a function, so the same algorithm can be reused with many different behaviors.
A lambda is the appropriate choice for a simple function object needed in one place only.
The deciding question when choosing between a named function object and a lambda is how many places in the program need the behavior.
A behavior needed in several places is better defined once as a named function object and passed wherever it is needed.

Related concepts

More concepts starting with T