C++ STL Algorithms Series - Part 3

Tom Hulton-Harrop | August 17, 2022

The more familiar we become with algorithms the more places begin to emerge where they can be utilized. This time we’ll introduce transform and see how it can be used to solve a familiar problem.

Example

transform takes a pair of iterators and applies a function to each element, storing the result to an output range (this is usually a new collection but it can also be performed in-place).

AZ::Matrix4x4 clipFromWorld = ....;
AZStd::vector<AZ::Vector4> worldPositions;
AZStd::vector<AZ::Vector4> clipPositions;

// loop version
for (const auto& worldPosition: worldPositions)
{
    clipPositions.push_back(clipFromWorld * worldPosition);
}

// algo version
AZStd::transform(
    AZStd::begin(worldPositions), AZStd::end(worldPositions),
    AZStd::back_inserter(clipPositions),
    [&clipFromWorld](const auto& worldPosition)
    {
        return clipFromWorld * worldPosition;
    });

Here we’re taking a vector of world positions and transforming them to clip space using the model-view-projection matrix. We could have reserved space for the elements in clipPositions or we can rely on back_inserter to call push_back for us (as in this example).

Suppose we want to do something a little more interesting such as perturbing the positions along the normal. To do this we’re going to need to lookup into a second range. Fortunately transform has another overload that takes two ranges so we can write this:

AZStd::transform( 
    AZStd::begin(worldPositions), AZStd::end(worldPositions), 
    AZStd::begin(worldNormals), AZStd::back_inserter(clipPositions), 
    [&clipFromWorld](const AZ::Vector4& worldPosition, const AZ::Vector3& normal) 
    {      
        return clipFromWorld * (worldPosition + AZ::Vector4(normal, 0.0f));  
    });

This is actually more difficult with the range-based for loop as we only have access to one range at a time. To work around this we would have to switch back to a classic for loop and deal with handling iteration ourselves or introduce another local variable to keep track of the index.

Deliberation

The algorithm version is a little noisier than the for loop but gains function purity by restricting what can happen on each iteration (the for loop looks easy to read and maintain now, but they have an unfortunate habit of not staying like that for very long). The overload of transform accepting two ranges is super useful and they of course do not have to be the same type either. Ultimately it very much depends on the situation which you should prefer but for simple transformations of data (which might sound familiar to the data-orientated-design crowd) transform is a very useful tool in your arsenal.

To be continued…

To wrap up this series (for the time being at least) we’ll close with a look at where the use of algorithms can lead to problems and what we can do to avoid falling into this trap.

Disclaimer: The views expressed here are those of the individual author and do not represent those of the Open 3D Foundation, Open 3D Engine or individual’s respective company.

Check out the other parts of the series:

Back to blogs