Saturday, July 31, 2004

Transform - Algorithm of the month

If you've found yourself iterating over a container so that you can extract something out of each element and place it in another container you are doing it the hard way.

The std::transform() algorithm is your friend. It allows you to modify the elements of a container based on the input of another container.

An example:

// IntWrapper.h
struct IntWrapper
{
    int x;
};

// YourCode.cpp
std::vector <IntWrapper> wrappers;
std::list<int> numbers;

for(std::vector<intwrapper>::const_iterator wrapperIt = wrappers.begin(); wrapperIt != wrappers.end(); ++wrapperIt)
{
    numbers.push_back(wrappers.x);
}

Not an uncommon situation.

A better way to do it:


// IntWrapper.h
struct IntWrapper
{
    int x;
};

// IntWrapperHelpers.h ** Could also put in IntWrapper.h or even make it a member function of IntWrapper **
int extractX(const IntWrapper &wrapper);

// IntWrapperHelpers.cpp
int extractX(const IntWrapper &wrapper)
{
    return wrapper.x;
}

// YourCode.cpp
std::vector <IntWrapper> wrappers;
std::list<int> numbers;

std::transform(wrappers.begin(), wrappers.end(), std::back_inserter(numbers), extractX);

Although it's marginally (one line!) more code I argue that this is a far superior solution.

For starters, if you need to do this operation more than once you can reuse the extractX() function. Secondly, the transform function is self-describing. Just by reading it you can tell that numbers is going to be transformed in some way based on the elements of wrappers. A simple iteration, as in the fist example, requires you to delve into the code to deduce that. Finally, because extractX() is part of IntWrappers interface (Don't believe me? Read Scott Meyers' article How Non-Member Functions Improve Encapsulation) the "extraction knowledge" is encapsulated more cleanly - clients don't need to know how to get x out of an IntWrapper.

Anyway, my guideline is that whenever I'm iterating over a container to fill another container I use transform. I always find that it saves me time in the long run.


P.S. There's another form of transform - it fills an output container based on two input containers. Using it is very similar to the single input container. I'll leave the exploration of that algorithm as an exercise for the reader... :)

3 comments:

xamdam said...

Hey Matt,
this color scheme really sucks for source code. Hint hint :)

Matt said...

Hehe, point taken, I'll change it as soon as I have a spare five minutes... :)

Thankfully it's in CSS so shouldn't be a big deal to make pretty!

Anonymous said...

I tried to read your source code, but it is really hard with your color sheme. Why don't you change to light colors ?