Imperative collection algorithms

Did you ever write…

std::vector<int> v;

...

for (auto i = v.begin(); i != v.end(); ++i) {
    if (someCondition(*i)) {
        doSomething(*i);
    }
}

Kinda irratating… Thanks to templatious, you can replace v.begin() and v.end() calls with:

...

for (auto i = SA::begin(v); i != SA::end(v); ++i) {
    if (someCondition(*i)) {
        doSomething(*i);
    }
}

All for now folks!

… Just kidding. Templatious library has a functional collection manipulation api. It is similar to Macromoft MILQ, however - it should work with any collection as long as it specializes CollectionAdapter interface. Tasks that were once tedious can be simplified.

Here's a one way to rewrite the upper boilerplate expression:

auto filt = SF::filter(v,someCondition);
SM::forEach(filt,doSomething);

someCondition in this context can be anything that can be called with an int as an argument (including const int&, int&, int&& and plain int) and return boolean indicating whether we want something in our filter or not. This can range from plain C pointer to a function, to arbitrary object that overloads () operator or a lambda expression.

Now, one thing to note is that someCondition is stored with a storage policy. Meaning, if you supply rvalue reference of some object it will be stored as a copy constructed with rvalue constructor, if you supply lvalue reference it will be stored as lvalue reference for minimum copying.

Now, there's a new collection created that is called a filt. Surprise, surprise, it is another collection. Meaning, whatever functions in templatious library could work with vector can also very likely work with the created filter.

I can hear some C++ programmer screaming “HOW IS THE VECTOR STORED?” and indeed, if I say to you as a copy I will get burned to the stake. But it's not, filt actually has just a reference to the original vector so there's no copying at all in that little code block. However, if we passed rvalue reference to the filter function then it will be copied using rvalue constructor, and we're safe again!

In the end, we traverse the filter with SM::forEach loop and it contains only values we specified in condition.

Kinda nice, can we use this in more serious manipulation? Oh yes we can. There are more templatious functions that do similar things as filter:

SF::filter // - filter collection
SF::select // - transform collection
SF::range  // - select range from collection
// (from 3rd to 7th element for example)
SF::skip   // - skip elements in collection
// (get every 2nd element for example)

Now, using these functions, let's do some arbitrary task:
There's a collection with elements from 1 to 100. We need elements bigger than 50, of the resulting collection we need from 17th until 37th elements and out of these take every 3rd element and remove these elements from the original collection.

Let's see how it's done!

std::vector<int> v; // contains 1 .. 100

...

auto col =
    SF::skip(
        SF::range(
            SF::filter(
                v,
                [](int i) { return i > 50; }
            ),
        17,37),
    3);

SA::clear(col);

That was tough! Typing examples letter by letter from bachelor graduation thesis is hard…

Anyway, this code does what the task requires. I guess you noticed, that since we have a reference to the original vector rather than it's copy we can affect it's elements. While we cleared the handle with reference, original vector was relieved of elements belonging to it's handle.

Now, C++ programmers tend not to like smoke and mirror's. How is it done? For all we know we could have called “erase” on vector iterators one by one which would be n squared complexity.

Templatious is smarter than that. Collection adapter has a boolean value called “floating_iterator”. This simply is a value that indicates what happens when we remove one iterator from collection. Are other iterators affected by that? Are other iterators not affected by that?

In short, std::vector iterator is floating, because if we remove first element from vector, the iterator that was pointing to the second element will now point to third, third element iterator will point to fourth and so on… Iterator of std::list on the other hand is not a floating iterator, because if we remove first element from std::list all the existing iterators of std::list will still point to the same elements they did before the removal.

So, what happened when we cleared the filter handle? A simple algorithm that works similarly to std::remove_if was used. The elements that belong to the filter were empty holes in the vector, and vector just copied back elements to cover the holes and shorten in size.

Even if it's efficient, it assumes one thing:

  • Elements of vector are copyable (either by const T& copy constructor or T&& rvalue copy constructor)

Had this been something like std::list elements would simply be erased out of collection one by one calling SA::erase on their iterators.

Even if we can clear the entire filter we can't clear single iterators of a filter because… Well, it complicates things nearly to the “why she might be upset” level.

Anyway, we have left out another tough guy in the block - SF::select. This is quite similar to select in sql statement. That is, if we get a pod, we can select an int from that pod and communicate with it as if it was a collection.

struct SomePod {
    SomePod() : a(0), b(0), c(0) {}

    int a;
    float b;
    char c;
};

std::vector< SomePod > pv;
TEMPLATIOUS_REPEAT( 100 ) {
    SA::add(pv,SomePod());
}

// pv now contains 100 SomePod's
// with default values

auto sel = SF::select< char& >(pv,
    [](SomePod& p) -> char& { return p.c; });

SM::set('7',sel);

// pv pods now have '7' for their char value.

This also simply contains a handle rather than copying collection. When you use function like TEMPLATIOUS_FOREACH on every iteration a function that transforms one value to another is called. So, if it is a CPU intensive function it may slow down traversal every time you need to traverse it.

This can be freely combined with the rest of the functions like SF::filter, SF::skip etc. to create complex queries.

But wait, there's more!

For the functional guys who think that holding references to vectors instead of a copy is a blasphemy, there's a little for you too. If you add magical letter 'C' to end of every function you get a copy instead of a reference. So, if you do a complex operation on some ints and you want to avoid copy whenever you can but receive copy in the end - you can do that!

Let's demonstrate it with a magical query.

Get every 7th element of a vector, get even numbers, multiply them by 7 and return a copy of it as doubles.

std::vector< int > a;

...
auto result =
    SF::selectC<double>(
        SF::filter(
            SF::skip(a,7),
            [](int i) { return i % 2 == 0; }
        ),
        [](int i) { return i * 7; }
    );

// type of result - std::vector<double>

So, the main thing to notice here is we used SF::selectC rather than SF::select. This returns a copy, by default it is std::vector. However, if you're on the magical days of the month where you sympathize for the list you can write:

auto result =
    SF::selectC<double,std::list>(
        ...

Yes, if you're the one of the million you can specify allocator also… (doesn't matter if collection doesn't support custom allocators).

auto result =
    SF::selectC<double,std::list,std::allocator>(
        ...

Ever thought of sorting arbitrary elements in a collection? Not that you will ever need to, but now you can!

std::list<int> l;
SA::add(l,7,6,5,4,3,2,1);

auto skipper = SF::skip(l,2);
SM::sort(skipper);

// l now contains 1,6,3,4,5,2,7

(custom comparator also available)