Introducing kdalgorithms An Algorithms Library for C++14 and Above

24.01.2023 Jesper K. Pedersen 4 comments

Are you already convinced and just want to download the library? We’re glad you liked it: https://github.com/KDAB/KDAlgorithms

I’m sure many people have told you time and time again, “Don’t use raw for loops; use algorithms.” Still, each time you tried, you found your code harder to read.

// ugly and unreadable algorithm code
vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
std::for_each(vec.cbegin(), vec.cend(), [](int i) { cout << i << " "; });

In case you’re wondering, the above simply prints out the vector.

Further, you might have looked at what C++20 (and especially C++23) offers in this area, but you are unfortunately stuck on C++17 or even C++14 and expect to be for quite a while.

Finally, you might have tried some of the existing libraries but found that they didn’t work very well with the Qt containers.

This was exactly my situation when I decided to write a few algorithm wrappers. Actually, I was using some other code already but it was GPL, and I wanted to offer something for Qt Widgets and More in an episode on algorithms.

In the rest of this blog post, I’ll switch between Qt and non-code Qt. KDAlgorithms works just as well with both container libraries. If you’re not familiar with Qt, just mentally replace QVector with std::vector, qDebug() with cout, and you will be just fine.

Let’s see a realistic (though still trivial) example of a loop that benefits from being rewritten as an algorithm:

 
QVector<QString> result; 
for (auto i : vec) { 
    result.append(QString::number(i)); 
} 
qDebug() << "transform with loop:" << result;

So what does the above do? It takes a vector of integers and converts it into a vector of strings — easy enough. Still, you need to read all 5 lines to understand what is going on.

Let’s see the same thing, this time with the STL algorithms available in C++14:

 
QString toString(int i) 
{ 
   return QString::number(i); 
}

QVector<QString> result; 
std::transform(vec.cbegin(), vec.cend(), std::back_inserter(result), toString); 
qDebug() << "Transform with std::transform:" << result;

I doubt many of you are running around the living room with your arms in the air screaming with joy.

One problem with the above is that you need to declare the result variable by itself and then use std::back_inserter to append to it. Another problem is that you need to call .cbegin() and .cend(), rather than just provide the vector. Finally, I’m sure a few of you are slightly bothered by the standalone toString function, which was what things looked like before C++11 and what lambdas fortunately solved.

Let me show you the above (this time with a lambda), rewritten to use kdalgorithms:

auto toString = [](int i) { return QString::number(i); }; 
auto result = kdalgorithms::transformed(vec, toString); 
qDebug() << "Transform to std::vector:" << result;

Now is a good time for that victory dance. Let me read the code for you:

1. Okay, so there is a lambda here for converting an integer to a string. Well, I’m too important and busy to read the details — next!
2. Aaah…okay, so this is transforming the vector by calling toString on each item.

Done!

You see, that is the beauty of algorithms (besides ensuring that the algorithm is properly implemented and tested) — the code is much easier to read. Heck, if you were really busy, you could have stopped at the word transformed and still got the gist of what is going on.

While the above few statements are true about algorithms in general, my claim is that they are even more so for kdalgorithms. Observe how we cut down on the extra noise:

• We just provide the complete vector, not a pair of iterators. While there indeed are many good use cases for operating on a subset of a container, my guess is that in 97.8% of the cases you execute the algorithms on the full container.
• You get the result returned to you, rather than providing an output iterator (std::back_inserter(result)) to where the data should go.

Okay, Tell Me What’s in the Package…

Sorry, I am not going to list all the available functions. For that, have a look at the documentation.

Let me, however, show you a few examples. For each of the examples, I’ll tell you, below the code, what it does, so you can try to interpret the code first.

Example: Find_if

 
std::vector vec{1, 2, 3, 4, 5};
auto greaterThan = [] (int value) { 
  return [value] (int test) { 
    return test > value; 
  }; 
};
const auto result = kdalgorithms::find_if(vec, greaterThan(2)); 
if (result) 
   std::cout << *result << std::endl; 
else 
   std::cout << "ahh nothing, right\n";

That wasn’t too hard, was it? First, we created a nifty function that returns another function. If you can’t wrap your head around that, it basically just boils down to writing this code in the find_if line:

 
const auto result = kdalgorithms::find_if(vec, [] (int test) { return test > 2; });

The find_if basically searches for the first number in the list that’s greater than 2. However, in contrast to STL algorithms, it doesn’t return an iterator but, rather, an object with an operator bool() so it’s more natural to check if there was a result, and an operator* for getting to the actual value.

See more about find_if in the documentation.

Example: Partitioned

 
const auto& [alive, dead] = 
   kdalgorithms::partitioned<std::unordered_set>(getAllPlayers(), 
                                                 &Player::isAlive);

Simple, still quite a few things to explain.

First, kdalgorithms::partitioned returns a simple struct with two containers in it — one called in, the other called out. Using C++17’s structured binding, I unpack that struct as the value is returned. Had I only had C++14, the code would look like this:

 
const auto result = 
    kdalgorithms::partitioned<std::unordered_set>(getAllPlayers(), &Player::isAlive);
const auto in = result.in;
const auto out = result.out;

Second, the method getAllPlayers() — which honestly only exists in my head — returns a std::vector<Player>. Maybe the players are sorted somehow, but I don’t care about sorting. Instead, the following code might want to do some set operations, so, on the fly, kdalgorithms::partitioned converts the result into two unordered sets. Had I not had that requirement, I could have left out the <std::unordered_set> part and kdalgorithms::partitioned would return a structure containing two vectors.

Finally, what kdalgorithms::partitioned is doing is to splitting the input into two collections — one that contains values that match the given predicate, and one that contains those that don’t (the in‘s and out‘s). As mentioned, the input is a vector of Players and, rather than writing a lambda to call isAlive on each item to decide if they are in or out, I simply provide a pointer to the member function.

In other words, the above code would produce the same result as this:

 
const auto& [alive, dead] = 
   kdalgorithms::partitioned<std::unordered_set>(
      getAllPlayers(), [] (const Player& player) { return player.isAlive(); });

By the way, the syntax &Player::isAlive would be the same whether isAlive is a public function or a public member variable.

Want more examples of partitioned? Head over to the documentation for partitioned.

Example: Searching for Old People

 
std::vector<std::string> names{"Jesper", "Anne Helene", "Louise", "Laura", "Santa"};
std::vector<int> ages{52, 49, 11, 8};

auto olderThan = [](int age) {
   return [age](const auto &tuple) { return std::get<1>(tuple) > age; };
};
auto getName = [](const auto &tuple) { return std::get<0>(tuple); };
auto oldPeople = kdalgorithms::filtered_transformed(kdalgorithms::zip(names, ages),
                                                    getName, olderThan(40));

Ahem! It’s senior citizens, not old people. Besides that, I take it the code reads without any hiccups, right?

Still let me go over it.

The first two lines are just setting up the test data. And I’m sure you are already asking me why I didn’t just have a vector of structs? To that, my answer is simple: Oh for <beep>’s sake please get down from the ivory tower.

We’ve all been in that situation where we have two pieces of data representing different attributes of the same items (here, name and age) but, unfortunately, we’ve had them in two different containers.

Reviewing your code, I’m sure you will find code that smells like this:

 
for (nameIt = names.cbegin(), ageIt = ages.cbegin();
     namesIt != names.cend() && agesIt != ages.cend();
     ++namesIt, ++agesIt) {
  ....
}

That’s where kdalgorithms::zip (which you may get from the file kdalgorithms.zip — okay, I admit that was a bad joke!) comes to the rescue. It takes any number of containers and produces a resulting container of tuples, each containing one item from each container.

The above test data would result in this:

 
std::vector<std::tuple<std::string, int>> resultOfZip{
    {"Jesper", 52},
    {"Anne Helene", 49},
    {"Louise", 11}, 
    {"Laura", 8} 
};

Next, we use filtered_transformed, which, despite its terrible name, does a very common thing:

First, it filters the data (here, it searches for everyone above 40, using the function olderThan(40)) and then transforms those that match (here, it’s calling getName to extract the name from the tuple). The result is a std::vector with two members in it, namely “Jesper” and “Anne Helene” (which, incidentally, is my wife and me — though I’m not saying she’s old!)

Want to learn more about zip or filtered_transformed? <—-Well, there are two links to the documentation.

So, Why Did You Create kdalgorithms?

As previously mentioned, I wanted to showcase algorithms in Qt Widgets and More. Additionally, and maybe most importantly, I wanted to learn much more about template meta programming.

As everyone else in KDAB, I’m entitled to utilizing 10% of my work time for education purposes. So, I decided to play with templates.

So, you might ask, “Is this just a piece of play code for you that you will abandon in no time?”

No! In KDAB, I also wrote my own version of what the rest of the world would think of as SAP — namely, a pretty large and complex piece of software that can tell KDAB everything we want to know about our cashflow, our customers, and even who’s been a bad boy and worked a lot of overtime recently (something we do not allow people to do; we insist that they have a good work/life balance).

What was I talking about? Ahh…right. Yes, in that tool, which is 150,000 lines of code, I am using kdalgorithms intensively –  a word count on kdalgorithms:: reveals almost 500 calls.

So, unless I one day decide that I need a bus full of consultants to redesign KDAB (by introducing SAP), I likely am doomed to support kdalgorithms for a very long time.

Which, now that I think of it, is great, since templates are a lot of fun and I’m sure that, just like 3-dimensional sudokus will delay Alzheimers, so will template meta programming.

Want more? Okay, then — you have to look me in the eyes (aka. watch youtube videos of me). Episode 95 is about kdalgorithms and shows a few different examples. Episodes 96-99 dive into a lot of template meta programming code, with the goal of letting the viewer understand how kdalgorithms::transformed is implemented and, more specifically, optimized for temporaries (that is rvalues) where it can steal the container provided.

Final words: Time to download and provide your feedback on kdalgorithms.

A Special Thanks…

I’d like to bring a special thank you to my coworker, Ivan Čukić, who has been a tremendous help on my journey towards a reborn C++ developer.

Ivan has patiently reviewed all of my pitiful attempts to write template code and continuously pushed me to reach higher.

Besides being a brilliant C++ developer, Ivan also has a good eye for structuring your code for maximum readability. To that end, I can strongly recommend his book on functional programming in C++.