Projections and Algorithms

When we’re using an algorithm that acts on items in a collection, often we will want to apply some temporary transformation to each item first.

For example, we might have a collection of numbers, and we want to run an algorithm on their absolute values.

Or, we might have a collection of Character objects, and we want to run an algorithm on a property of those characters, such as their name.

Scenarios like these can be elegantly solved with projection, and most of the standard library algorithms have a parameter that lets us set it up.

Example: Sorting Numbers By Absolute Value

In the previous lesson, we introduced the ranges::sort algorithm. Its first argument is the range we want to sort, and the optional second argument is the comparison we want to use to sort the range:

1std::vector Nums { -3, 0, 5, };
2std::ranges::sort(Nums, std::ranges::greater{});
3

The std::ranges::sort function also has an optional third parameter, which allows us to pass a projection function. In the next example, let’s pass a lambda there, to make our algorithm run on a projection instead.

In this case, we are using the default argument for the second paremter, and using the third parameter to project the integers to their absolute value, using std::abs:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Nums { -3, 0, 5, };
7
8  std::ranges::sort(Nums, {}, [](int i) {
9    return std::abs(i);
10  });
11
12  for (const auto& Num : Nums) {
13    std::cout << Num << ", ";
14  }
15}
16

The values are not changed, but they were sorted based on their projection instead of their real value:

10, -3, 5,
2

1std::ranges::sort(Numbers, [](int a, int b){
2  return std::abs(a) < std::abs(b);
3} );
4

Projection to a Different Type

Our projection function does not need to return the same type of object that was contained in our original collection.

In this example, we sort Character objects by level, using a projection function:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5class Character {
6public:
7  int Level;
8  std::string Name;
9};
10
11int main() {
12  std::vector Party {
13    Character {"Legolas", 49},
14    Character {"Gimli", 47},
15    Character {"Gandalf", 53}
16  };
17
18  std::ranges::sort(Party, {}, [](Character& Character) {
19    return Character.Level;
20  });
21
22  for (const auto& Character : Party) {
23    std::cout << "[" << Character.Level << "] "
24              << Character.Name << "\n";
25  }
26}
27

1[47] Gimli
2[49] Legolas
3[53] Gandalf
4

Here, we combine both a projection and a comparison function. The projection will return an int, and then the comparison function will compare those int values:

1std::ranges::sort(
2  Party,
3  [](int a, int b) { return a > b; },
4  [](Character& Character) { return Character.Level; }
5);
6

1[53] Gandalf
2[49] Legolas
3[47] Gimli
4

Projection to an Object Property

Finally, the value we want to project to will often be returned from a getter, defined within our objects’ class. Where that is the case, we can simply pass a reference to that function:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5class Character {
6public:
7  Character(std::string Name, int Level) :
8    Name(std::move(Name)),
9    Level(Level) {};
10
11  std::string GetName() const { return Name; }
12  int GetLevel() const { return Level; }
13
14private:
15  int Level;
16  std::string Name;
17};
18
19int main() {
20  std::vector Party {
21    Character {"Legolas", 49},
22    Character {"Gimli", 47},
23    Character {"Gandalf", 53}
24  };
25
26  // Sort characters in alphabetical order by name
27  std::ranges::sort(Party, {}, &Character::GetName);
28
29  for (const auto& Character : Party) {
30    std::cout << "[" << Character.GetLevel() << "] "
31              << Character.GetName() << "\n";
32  }
33}
34

1[53] Gandalf
2[47] Gimli
3[49] Legolas
4