Showing posts with label lambda. Show all posts
Showing posts with label lambda. Show all posts

CodeEval Prefix Expressions

The CodeEval problem #7 asks us to write a toy calculator for simple arithmetic expressions written in Polish notation. We expect only addictions, multipications, and divisions. And no inner expressions are allowed, meaning that we can safely expect to have in input firstly all the operators then operands, as integer numbers. We should give an integer answer, even though the internal process should keep correctly track of real numbers generated by divisions.

As sample we are given a unique case, that I converted in a python test:
def test_provided_1(self):
    self.assertEqual(20, solution('* + 2 3 4'))
Since we have only to deal with binary operations, we can use the clever trick of starting from the middle of the input, were we can find the first operand, moving to the left to get the list of operators and to the right for the other operands. This lead naturally to think using zip() a python implementation:
i = len(data) // 2  # 1
result = float(data[i])  # 2
for op, value in zip(reversed(data[0:i]), data[i + 1:]):  # 3
    # ...
1. Getting the central element index in the input data list.
2. Convert the first value to real number, so that floating point arithmetic is applied to the expression.
3. I zip together the left and right part of the input data. First part reversed, so that I start to center and move to the edges fetching elements.

Now, what I should do in the loop. As C programmer my instinct went to a switch on the operators, to detect which operation I have to apply. But Python has no switch, so I had to think to something smarter. I put in a dictionary the mapping between each operator and the actual piece of code I need to run in that context, in form of a lambda function, and then I simply have to lookup in it to have the job done:
mapping = {'+': lambda r, v: r + v, '*': lambda r, v: r * v, '/': lambda r, v: r / v}

# ...

for # ...
    result = mapping[op](result, int(value))
Then, after the for loop, I just have to cast the result to integer and return its value.

On GitHub you can see the unit test and the full python script.

Go to the full post

Functional interfaces

In Java everything that is not a primitive is an object. OK, but what about functions? Introducing a support for functional programming in Java 8 led to the need of give an answer to this question, and the designers decided to use the ad-hoc solution of functional interfaces.

A functional interface is a Java interface that has only one abstract method. It is a good idea to annotate it as FunctionalInterface so that it's clear what it is mean for, and let the compiler to check if it is alright. However it is not mandatory.

We can define and use any interface we like for use it in this way, but we should save to ourselves, and to our code clients, some pain using when possible the standard one, define in the java.util.function package.

Let's see a few examples.

Predicate

The predicate functional interface is defined as:
@FunctionalInterface
public interface Predicate<T> {
    boolean test(T t);

    // ...
}
I can use it if I have to write a method filter() that gets in input a list of data and filter them accordingly some requirements decided by the user.
public static <T> List<T> filter(List<T> data, Predicate<T> p) { // 1
    List<T> results = new ArrayList<>();
    for (T t: data) { // 2
        if (p.test(t)) {
            results.add(t);
        }
    }
    return results;
}
1. It takes as input a list of T and a predicate on T.
2. For each element in the list, if it pass the test defined by the caller, I add it to the list I return.

Here is a piece of code that uses the filter() method:
List<String> result = FunctionalInterfaces.filter(Arrays.asList("", "x", ""), (s) -> !s.isEmpty());
I create a list of strings and I pass it to filter() alongside a lambda function, that has to match with the expected Predicate, so the lambada input has to be a String - I could state it explicitly, but I can also leave it implicit - and it should return a boolean.
The result is a list containing just one string, namely "x".

Consumer

It is defined as:
@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);

    // ...
}

Here I use it in a forEach() method that let the user specify what it should do with each element of a List:
public static <T> void forEach(List<T> data, Consumer<T> c) {
    for(T t: data) {
        c.accept(t);
    }
}
I use this forEach() to keep calculate the length of all the strings in a list:
List<String> data = Arrays.asList("Functional", "Interfaces", "in", "Java 8");
consumed = 0;
FunctionalInterfaces.forEach(data, (s) -> consumed += s.length());
assertThat(consumed, is(28));
Again, note that here the type of the lambda parameter s is inferred from T, type of the list passed to forEach() and used to determine the actual Consumer functional interface to which the lambda should refer to.
Interesting to note how the consumed variable is captured by the lambda without the need of any explicit action by programmer. This mechanism works fine only for non-local variables. Local variables can be captured only if final (at least effectively so).

Function
@FunctionalInterface
public interface Function<T, R> {
    R apply(T t);

    // ...
}

This map() method maps objects of a given type to another one, delegating to the caller the job of specifying how to do the conversion.
public static <T, R> List<R> map(List<T> data, Function<T, R> f) {
    List<R> result = new ArrayList<>();
    for(T t: data) {
        result.add(f.apply(t));
    }
    return result;
}

I use it here to convert a list of strings in a list of integers:
List<String> data = Arrays.asList("Functional", "Interfaces", "in", "Java 8");
List<Integer> result = FunctionalInterfaces.map(data, (s) -> s.length());
The compiler does a lot of job for us here. Since map() is templatized by T, the template type of the input list, and R, from the returned list, it figures out that s, passed to the lambda, is a String, so it should return an object of the class returned by the String method lenght(), that is an int, boxed to Integer.

IntBinaryOperator
@FunctionalInterface
public interface IntBinaryOperator {
    int applyAsInt(int left, int right);
}
In the example for Function, boxing the integers was an expected behavior. We need them as objects since we want them in a collection.
Other times, boxing and unboxing could be just a useless cost that we could avoid using a special functional interface like this one, that works with lambdas working on primitives.

This combine() method works on primitive integers and don't want to pay any extra costs for objects
public static int combine(int[] data, IntBinaryOperator op) {
    if(data == null || data.length != 2) {
        return 0;            
    }
    return op.applyAsInt(data[0], data[1]);
}

I could use it to decide dinamically what kind of operation applying to a couple of integers, accordingly to the lambda passed.
int result = FunctionalInterfaces.combine(new int[] {6, 7}, (a, b) -> a * b);

Supplier

@FunctionalInterface
public interface Supplier<T> {
    T get();
}

We don't have anything to pass to the lambda, and we blindly let it to create an object of the specified type.
public static <T> T aFactory(Supplier<T> s) {
    return s.get();
}

Here is a trivial example:
String result = FunctionalInterfaces.aFactory(() -> "Hello");

I pushed to GitHub a class FunctionalInterfaces with the static method having a reference to functional interfaces as parameter and a JUnit tester that shows how I called them.

Reference: Java 8 in action, section 3.4 Using functional interfaces.

Go to the full post

Execute around pattern and try-with-resources

Say that you have to implement in Java 8 a functionality where there is a lot of boilerplate. Instead of duplicating code in sibling methods, we can try to create a single method where the changing behavior is passed by parameter as a lambda function.

Reduced to the minimal term, here is the example of a method that we could refactor using the execute around pattern. The code is made more interesting by using the try-with-resources statement available in Java since version 7.
public static String processFileLimited(String filename) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) { // 1
        return br.readLine(); // 2
    }
}
1. We try to create a BufferedReader. At the end of the block, even in case of an exception, Java takes care of closing the resource. Neat.
2. This is the behavior we want to be parametrized.

Lambda is here our friend. Only a minor nuisance, we can't use a standard functional interface because here we should let our lambdas throw an IO exception, and in Java this should specified in the method signature.
@FunctionalInterface
public interface BufferedReaderProcessor {
    public String process(BufferedReader br) throws IOException;
}
Given this interface, we can refactor the above method in this way:
public static String processFile(String filename, BufferedReaderProcessor p) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
        return p.process(br);
    }
}
The boilerplate is there unchanged, the actual behavior has been externalized. It should be user resposibility to provide something sensed to be done in. Here is a couple of different ways processFile() could be called:
ExecuteAround.processFile(FNAME, (BufferedReader b) -> b.readLine());
ExecuteAround.processFile(FNAME, (BufferedReader b) -> b.readLine() + '-' + b.readLine());
As second parameter, I pass a lambda that in its body uses the BufferedReader to perform its job. A string is (implicitly) returned.

I have divided the code between the actual ExecuteAround class and its unit test. You can find both on GitHub.

Code and ideas are based on Java 8 in action, section 3.3 Putting lambdas into practice: the execute around pattern.

Go to the full post

Filtering apples with Predicate and lambdas

We have to write a apple filtering Java method that, given in input a string describing a list of apples, preceded by a flag that tell us how to filter them, gives as output the filtered apples.

Even if just two ways of filtering have to be implemented, we should design a solution that could be easily extended to support many unforeseen other filters.

Here is a few test cases that I have written to better explain the problem.
@Test
public void testSolutionByColor() {
    assertThat(AppleFilter.solution("color:80 green|155 green|120 red"), is("80 green|155 green"));
}

@Test
public void testSolutionByMissingColor() {
    assertThat(AppleFilter.solution("color:80 blue|155 yellow|120 red").length(), is(0));
}

@Test
public void testSolutionByWeight() {
    assertThat(AppleFilter.solution("weight:80 green|155 green|120 red"), is("155 green"));
}
Each apple is represented by its color and weight, blank separated. A pipe is used as separator between apples. There are just two filtering way currently, color, that let's us select just the green apples, and weight, that select only the apples heavier than 150.

The point of this exercise is in using a few Java 8 features, namely the Predicate functional interface and lambda functions.

The core of the algorithm is this filter method:
private static List<Apple> filter(List<Apple> apples, Predicate<Apple> p) {
    List<Apple> result = new ArrayList<>();
    for (Apple apple : apples) {
        if (p.test(apple)) {
            result.add(apple);
        }
    }
    return result;
}
Given a list of apples and a predicate on apples, each apple in the list is tested against the predicate. If the test is passed, the apple is added to a new list that is returned by the method.

Here is how I decide which predicate to use, given that data[0] is a String containing the selector as extracted from the input parameter.
Predicate<Apple> p = data[0].equals("color") ?
    (Apple a) -> a.color.equals("green") :
    (Apple a) -> a.weight > 150;
I store in the predicate p a lambda function that has as input an apple and return a boolean, accordingly to the kind of filtering I want to perform. Here I assume only two kind filtering could be performed, however is easy to extend, and make more robust, this piece of code.

The rest of the code I have written is all about converting raw data to objects and back from objects to a string formatted as required by the user. There is some interesting stuff there, too.

I used the String split() method to split the input string. Nothing much to say on it when the separator is a colon or a blank, however we should remember that it is a regular expression, so we have to pay attention to correctly escape it when a special character, like a pipe, is passed it. So, to split the list of apples I write:
data[1].split("\\|")
For the other way round, I used the static String join() method, that joins an iterable on a give character sequence. There is a caveat here, too. The iterable has to be a generic based on CharSequence, quite a nuisance. Libraries as Guava and Apache Commons provide smarter functions, however, if we want to keep our code free from third-party code, we need to use some workaround, like:
List<Apple> selected = filter(apples, p);
List<String> result = new ArrayList<>(selected.size());
for (Apple a : selected) {
    result.add(a.toString());
}
return String.join("|", result);

I have conceived this problem as a way to work with the information provided by the authors when reading Java 8 in action, chapter one. If you have this book at hand, you are going to find in section 1.2 Functions in Java code very similar to the one I used above.

I have create a repository on GitHub where I plan to push all the code I write related to this book. You can see the code above in the Java source AppleFilter class and in the JUnit AppleFilterTest.

Go to the full post

CodeEval knight moves

Given the position of a knight on the chessboard, return all its possible moves. In alphabetical order.

You could solve this problem as a CodeEval easy challenge.

It came natural to me to solve it in a functional way, still writing C++11 code.

My solution function would put the result in a string using a local lambda function:
std::string result;

auto push_back = [&result] (char x, char y)
{
  result.push_back(x);
  result.push_back(y);
  result.push_back(' ');
};
Nothing of much interest here. My push_back() lambda captures the result string, and push back to it its parameters, adding a blank at the end as separator for the possible next element.

More interesting this other lambda. It captures the string passed as input parameter, that would contain the current knight position in a format like "g2", and the above defined push_back lambda. As parameter it gets the column where I want to move the knight and how many squares I could move up or down:
auto add = [&input, &push_back](char x, int step)
{
  if (input[1] > '0' + step)
    push_back(x, input[1] - step);
  if (input[1] < '9' - step)
    push_back(x, input[1] + step);
};
If the knight does not fall off the chessboard, I push back the resulting positions using the push_back lambda. Now I just have to call add() for each meaningful column. I can do that in this way:
char x = input[0];
if (x > 'b')
  add(x - 2, 1);
if (x > 'a')
  add(x - 1, 2);
if (x < 'h')
  add(x + 1, 2);
if (x < 'g')
  add(x + 2, 1);
Just for readability, I introduced the x variable that should contain the name of the column where the knight is placed. If it is to the right of the 'b' column, I could move two steps to the left, and then call the add() lambda to verify if it could be moved one square more up or down. And so on. Full C++ code is available on github. As well as a few test cases.

Go to the full post

Selecting the longest lines

We have in input a few strings, we want to output a given number of them, ordered by their size.

This is such a simple problem that I couldn't think of any interesting test case about. You can find it in the CodeEval open challenge under the name Longest Lines.

At its core, the solution to this problem is nothing more than a couple of C++ statements.

Assuming the number of lines we want to output is stored in an int variable named nr, and the vector of strings named lines keep the data, it is just a matter of sort the vector by lines size and return its first nr elements:
std::sort(lines.begin(), lines.end(), StringSizeCmp());
for(int i = 0; i < nr; ++i)
  std::cout << lines[i] << std::endl;
Right. But I forgot to tell you who is that StringSizeCmp guy. It is a simple functor that defines how sort() should decide which element comes first:
struct StringSizeCmp : public std::binary_function<std::string, std::string, bool>
{
  bool operator()(const std::string& lhs, const std::string& rhs) const
  {
    return lhs.size() > rhs.size();
  }
};
As clearly stated by inheritance, StringSizeCmp is a binary function that gets a couple of strings in and gives a boolean out. The comparison is here solved accordingly to the input sizes.

C++11 makes it even simpler, by means of lambda function. We could combine the predicate definition and its usage in a single line:
std::sort(lines.begin(), lines.end(),
    [](const std::string& lhs, const std::string& rhs) {
  return lhs.size() > rhs.size();
});

Go to the full post

Another asynchronous wait on a steady timer

This is a new version of an oldish Boost ASIO example of mine about asynchronously waiting on a timer, keeping advantage of C++11 features. If you are looking for something simpler, there's another post on the same matter but more focused on the bare ASIO functionality. Or you could go straight to the original source, the official tutorial on Boost.

Five years later, I found out that this post requires some adjustments. You could follow the link to its March 2018 version.

The main function of this example is spawning a new thread, that runs a function that does something indefinitely. But before creating the new thread, it would set an asynchronous timer, calling a function on its expiration that would cause the runner to terminate.

It makes sense to encapsulate both function in a single class, like this:
class MyJob
{
private:
    MyJob(const MyJob&) = delete; // 1
    const MyJob& operator=(const MyJob& ) = delete;

    std::mutex mx_; // 2
    bool expired_;
public:
    MyJob() : expired_(false) {}

    void log(const char* message) // 3
    {
        std::unique_lock<std::mutex> lock(mx_);
        std::cout << message << std::endl;
    }

    void timeout() // 4
    {
        expired_ = true;
        log("Timeout!");
    }

    void operator()() // 5
    {
        for(int i = 0; !expired_; ++i)
        {
            std::ostringstream os;
            os << '[' << i << ']';

            log(os.str().c_str());
            std::this_thread::sleep_for(std::chrono::seconds(1));
        }
    }
};
1. I don't want an object of this class to be copyable, we'll see later why. So I remove from this class interface copy constructor and assignment operator, using the C++11 equals-delete marker.
2. There are two threads insisting on a shared resource (the standard output console), a mutex is needed to rule its access.
3. The shared resource is used in this function only. A lock on the member mutex takes care of protecting it.
4. When the timer expires, it is going to call this method.
5. This function contains the job that is going to run in another thread. Nothing fancy, actually. Just a forever loop with some logging and sleeping. The timeout is going to change the loop control variable, so that we can have a way out.

This is the user code for the class described above:
boost::asio::io_service io; // 1
boost::asio::steady_timer timer(io, std::chrono::seconds(3)); // 2

MyJob job; // 3
timer.async_wait([&job](const boost::system::error_code&) {
  job.timeout();
}); // 4

std::thread thread(std::ref(job)); // 5
io.run();
thread.join();
1. An ASIO I/O service is created.
2. I create a steady timer (that is just like an old deadline timer, but uses the C++11 chrono functionality) on the I/O service object.
3. An object that describes the job I want to run in another thread is instantiated.
4. When the timer expires, the passed lambda function is executed. It is an asynchronous call, so it returns immediately the control, that passed to the next instruction (5). The lambda would call the timeout() method on the job object, that has been captured by reference. Having defined the MyJob class as non-copyable, forgetting the ampersand, passing the job by value, results in a compiler error. Here I don't care about the error code parameter, that is set by ASIO to say if the timer has expired correctly or with an error. I just stop the job running. In a real-life usage a check would be expected.
5. Before running the I/O service, I create a thread on our job - again passed by reference, as the std::ref() shows. Again, trying to pass it by value would result in compiler errors.

Full C++ code for this example is on Github.

Go to the full post

Waiting for C++0x for each

Among the many useful stuff we are going to have at hand with the new shiny C++0x standard, there is also a new way of looping, the so called "for each" loop. If you use other languages (as Java or Perl, just to make a couple of names) that is no news at all and, actually, the standard C++ for each remembers them closely, expecially the Java "enhanced loop", as they call it.

For what I can see, there is only an issue with the C++0x for each: currently it is not available. At least, if you are not using the GNU compiler.

If you are not in the GNU club, you still have at least a couple of alternatives, non-standard implementation provided by Boost and Microsoft. I won't suggest you to use them, but you could see them in the code you are working with.

Say that we have a vector of integer, like this:
std::vector<int> vi;
vi.reserve(10);

for(int i = 0; i < 10; ++i)
vi.push_back(i);

And we want to print all its elements on one line, using a blank as a delimiter.

A classic way of doing that is looping with a for from zero to the size of the vector:
for(size_t i = 0; i < vi.size(); ++i)
std::cout << i << ' ';
std::cout << std::endl;

There's nothing wrong with this solution, but it is not much expressive of what we are about to do: we want print any single value of the vector. It could be said louder.

If we are working with Visual C++, we can say it using the Microsoft propertary version of for each:
for each(const int& i in vi)
std::cout << i << ' ';
std::cout << std::endl;

In this way we are saying explicitely we are doing our job for each the elements of our vector - but we are saying it in a non-portable way. So, better to avoid it.

A portable way of doing the same is using the BOOST_FOREACH macro:
BOOST_FOREACH(const int& i, vi)
std::cout << i << ' ';
std::cout << std::endl;

The boost libraries are available for a vast number of C++ compilers, so portability shouldn't be an issue. On the other hand, this is not standard, and someone (me included) doesn't like that much using a macro, when an alternative is given.

And a good alternative is provided by the standard algorithm for_each - better if coupled with a lambda function:
std::for_each(vi.begin(), vi.end(), [] (const int& i) {std::cout << i << ' ';} );
std::cout << std::endl;

Admittedly, if you are not acquainted with lambda functions, this piece of code is not exactely so readable as the previous for each versions but, well, it is so cool. And it says exactely what we are going to do. We can read it in this way: for each element in the interval from begin to end of the vector vi, execute the lambda function that takes as input the element currently fetched and output it, followed by a blank, to the console.

But, do we really need to perform a for loop? In this specific case, a natural way of implementing a solution would require us calling the standard algorithm copy, using an ostream_iterator as destination:
std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

Isn't that a beauty?

Go to the full post

Standard algorithms are cool

Using standard algorithms our code gets easier to read, write, and modify. And even better if we throw in lambda functions. Here we are seeing an example showing how std::transform() looks better than a for loop.

We have to write a piece of code that gets in input an array of doubles and puts them, increased by 42 and keeping their order, at the beginning of a deque.

Let's say this is the array of doubles:

const int DIM = 10;
double data[DIM] = { 0.23, 1.54, 2.44, 3.45, 4.98, 5.93, 6.34, 7.28, 8.58, 9.41 };
dump(data, data+DIM);

And this is the deque:

std::deque<double> d;
d.push_back(999); // this should stay at the end

We can't use push_back(), because the element(s) already in the deque should be kept at the end of it. We can't use push_front() because we would get the unrequired special effect of reversing the data order. We should use insert().

Here is a "classical" solution to our problem, by for loop:

std::deque<double>::iterator pos = d.begin();
for(int i = 0; i < DIM; ++i)
pos = d.insert(pos, data[i] + 42) + 1;

We need to refresh our current position (pos iterator) after the call to insert(), since it invalidates its old value, and we increase it to avoid falling back in the push_front() behaviour.

Once one is accustomed to the standard transform() algorithm, this version of the same code looks clearer:

std::transform(data, data + DIM, inserter(d, d.begin()),
std::bind2nd(std::plus<double>(), 42));

Actually, there are a few features that could look surprising, at first. Maybe you need to get acquainted to inserters, to the binders, or to the standard functor. But after a while all of this would look natural to you.

Moreover, we could avoid using a binder and the plus functor here, if we use a lambda function instead - that makes the code even more clear:

std::transform(data, data + DIM, inserter(d, d.begin()),
[] (double v) { return v + 42; } );

Item 43 of Effective STL, one of the Effective C++ book series by Scott Meyers, is about standard algorithm as a way of writing better C++ code.

Go to the full post

Using std::for_each() instead of for loop

The standard algorithm for_each() is usually more efficent and less error prone than a classical for loop. And after a while it gets more natural to use.

The major nuisance in using for_each(), at least from my point of view, is that we have often to adapt the function we call in it by mem_fun() or mem_fun_ref(). Luckly, lambda function makes it easier for us.

For this example we are about to use this pretty nonsensical class:

class I43
{
private:
const int value_;
public:
I43(int value) : value_(value) {}

int getValue() const { return value_; }

void doSomething() const
{
std::cout << "Doing something on " << value_ << std::endl;
}
};
std::ostream& operator<<(std::ostream& os, const I43& i)
{
return os << i.getValue();
}

The "put to" overload on ostream makes our new class ready to be used for our simple printing utility function.

As usual, let's create some data to work with:

std::vector<I43> vi;
vi.reserve(10);
for(int i = 0; i < 10; ++i)
vi.push_back(i);
dump(vi);

Notice that we push an integer in the vector but, since the underlying vector type is I43, and the I43 ctor having int ad argument is not explicit, our friendly compiler automatically creates an I43 object for us, and put it in the vector.

If we didn't like having an automatic conversion from int to I43 we would have written the constructor in this way:
explicit I43(int value) : value_(value) {}
But we didn't, so our code works fine.

Now we want to call the doSomething() method for each element in the vector. A common approach to this task results in a for using an iterator as loop variable:

typedef std::vector<I43>::iterator IT;
for(IT it = vi.begin(); it != vi.end(); ++it)
it->doSomething();

Using the standard algorithm for_each() is usually considered a better approach:
std::for_each(vi.begin(), vi.end(), std::mem_fun_ref(&I43::doSomething));
Problem is that we have to use a notation that is a bit clumsy. We specify the address of the member function we want to call, then we adapt it to for_each() using std::mem_fun_ref().

A lambda function makes the code a bit more concise and readable:
std::for_each(vi.begin(), vi.end(), [] (I43 i) { i.doSomething(); });

Item 43 of Effective STL, one of the Effective C++ book series by Scott Meyers, says a lot more about why for_each() is better than a for loop

Go to the full post

std::is_partitioned() and std::partition_point()

The C++0x standard has made easier working with partitioning. Now we have a standard function, is_partitioned(), to check if an interval in a container is partitioned against a predicate, and another one, partition_point() that returns an iterator to the first element out of the first group

As we can expect, partition_point() assumes the elements have been already partitioned by the passed predicate.

We are going to test these features on this container:

std::vector<int> vi;
vi.reserve(10);
for(int i = 0; i < 10; ++i)
vi.push_back(i);
dump(vi);

We need a predicate for partitioning the container, say, in even and odd elements. Best choice is a lambda fuction, being the test so easy, but we need to store the function in a local variable, since we have to reuse it a couple of times. The explicit way of doing that is using a function object (declared in the standard functional include file):
std::function<bool (int)> isEven = [] (int i) -> bool { return i%2 == 0; };
But if we want to save some typing we could use the autodetecting type deducing, by the auto keyword, and not specify the lambda return type - letting the compiler deducing it from the code, too:
auto isEven = [] (int i) { return i%2 == 0; };
We are paying our lazyness (and the concision/readability of the produced code) with less control on what we are writing - it is a choice that you have to take.

In any case, now we can test if our sequence is partitioned in even/odd elements:

if(std::is_partitioned(vi.begin(), vi.end(), isEven))
std::cout << "I don't expect this" << std::endl;

After typedeffing the iterator on our vector:
typedef std::vector<int>::iterator IT;
we partition the sequence, and test it again, this time for getting a positive result. Notice the paranoid check on the partitioning result. In this case is just overkilling, but I put it there as I would do in production code:

IT pivot = std::partition(vi.begin(), vi.end(), isEven);
if(std::is_partitioned(vi.begin(), vi.end(), isEven))
{
std::cout << "Now the container is partitioned: ";
dump(vi);
if(pivot != vi.end())
std::cout << "Second group starts at: " << *pivot << std::endl;
}

Now that the sequence is partitioned, we can get its partition point. Actually, here this is not useful at all, since that is the iterator we get back from partition(). But OK, this is just an example:

IT ppoint = std::partition_point(vi.begin(), vi.end(), isEven);
if(ppoint != vi.end())
std::cout << "Partition point is: " << *ppoint << std::endl;

Go to the full post

std::copy_if

With C++0x std::copy_if() is finally here, hurray! But, what if your compiler does not support yet the new standard? You have to write it yourself.

Good news is that the code is quite simple:

template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator my_copy_if(InputIterator begin, InputIterator end, OutputIterator to, Predicate p)
{
while(begin != end)
{
if(p(*begin))
*to++ = *begin;
++begin;
}
return to;
}

Let's see it at work, because it is a good reason to see copy_if, a back_inserter and a lambda function in the same line.

As usual, first step is about setting up the input data:

std::vector<int> vi;
vi.reserve(10);
for(int i = 0; i < 10; ++i)
vi.push_back(i);
dump(vi);

An then let's copy only the even elements:

std::vector<int> vo;
std::copy_if(vi.begin(), vi.end(), std::back_inserter(vo),
[] (int i) -> bool { return i %2 == 0; });
dump(vo);

Here I used the standard copy_if() - using our version won't change the test code.

Why copy_if() has to be written how we see it, and more info on the matter in Item 36 of Effective STL, one of the Effective C++ book series by Scott Meyers.

Go to the full post

Pointer in container and erase-remove idiom

We know that using raw pointers in a standard container is a pain in the neck. But we now we can use instead smart pointers, as the shared_ptr originally provided by Boost, and now available as part of the C++0x standard.

With smart pointers there is no special issue, we barely use the erase-remove idiom as we already know it.

But there is some interest in this post, because we are about to use a lambda function and improve again our simple dump function, to let it deal with pointers.

Firstly, we write a class that we are about to use dinamically:

class Simple
{
private:
const int value_;
bool valid_;
public:
Simple(int value) : value_(value), valid_(true) {}

bool isValid() const { return valid_; }
void setValid(bool valid) { valid_ = valid; } const

int getValue() const { return value_; }
};

Then we write a variation on our function for dumping elements in a container, specific for pointers management:

template <typename T, typename InputIterator>
void dumpPtr(InputIterator begin, InputIterator end,
std::ostream& os = std::cout, const char* const delimiter = " ")
{
std::for_each(begin, end, [&] (T t) { os << *t << delimiter; } );
os << std::endl;
}

It doesn't change much, actually, from the previous version. We just acknowledge that we have to do with a pointer, and dereference it on usage.

We should remember to write an overload for the "put to" operator, so that we can output Simple objects:

std::ostream& operator<<(std::ostream& os, const Simple& s)
{
return os << s.getValue() << " (" << s.isValid() << ')';
}

We are going to work with shared pointers to Simple objects. A typedef is going to be useful:
typedef std::shared_ptr<Simple> SPS;
Given all this, we create a vector of smart pointers to Simple, put some data in it, and mark as not valid a few items:

std::vector<SPS> vss;
vss.reserve(10);
for(int i = 0; i < 10; ++i)
vss.push_back(SPS(new Simple(i)));

vss[2]->setValid(false);
vss[5]->setValid(false);
vss[8]->setValid(false);

dumpPtr<SPS>(vss.begin(), vss.end());

And now the fun stuff:

vss.erase(std::remove_if(vss.begin(), vss.end(),
[] (SPS s) -> bool { return s->isValid() == false; }), vss.end());

It is just a line of code, but it is quite dense.

We use the remove_if() standard algorithm using as a predicate a lambda function (notice the "arrow" notation to specify its return type) that works on each smart pointer in the passed range. The returned iterator from remove_if() is used as beginning of the sequence that has to be erased from the vector.

More info on this issue in Item 33 of Effective STL, one of the Effective C++ book series by Scott Meyers.

Go to the full post

Printing map not using ostream_iterator

My simple dumping function for containers has a few limitations, the worst of them probably is that it doesn't work for maps.

The fact is maps are based on std::pair, no "put to" operator on ostream is defined for it in the std namespace, but ostream_iterator really needs it there to do its job.

So I have taken a different approach. Instead of using the standard copy() algorithm coupled with ostream_iterator, I'm using here for_each() and I'll add a local "put to" operarator definition for my pair.

Here is my new version of the function:

template <typename InputIterator>
inline void dump(std::ostream& os, InputIterator begin, InputIterator end,
const char* const delimiter = " ")
{
typedef std::iterator_traits<InputIterator>::value_type T;
std::for_each(begin, end, [&] (T t) { os << t << delimiter; } );
}

I have used a lambda function to keep the code sleek and compact. If you compiler does not allow lambda yet, you can use the boost implementation.

The overload for "normal usage" on standard output has not changed:

template <typename InputIterator>
inline void dump(InputIterator begin, InputIterator end)
{
dump(std::cout, begin, end);
std::cout << std::endl;
}

As also the overload for dumping all the items in the container stays the same:

template <typename Container>
inline void dump(const Container& c) { dump(c.begin(), c.end()); }

Given this new version of dump(), I define a map and a operator "put to" working for its undelying pair:

typedef std::map<int, int> MII;
typedef MII::value_type MII_VT;
std::ostream& operator<<(std::ostream& s, const MII_VT& p)
{
return s << '(' << p.first << ", " << p.second << ')';
}

And here is a sample code for testing:

MII mii;
for(int i = 0; i < 10; ++i)
mii[i] = i * i;

dump(mii);

Go to the full post

boost::lambda::placeholder and more

The C++0x simplify a lot the usage of the lambda expression still, if you are using a compiler that does not support it yet, it useful to know a couple of tricks that could help us in keeping the code more readable.

For instance, using constant_type<>::type could we define constant to be used in our expression, besides, we see here also how to redefine the name for the placeholders:

#include <iostream>
#include <vector>
#include <algorithm>

#include "boost/lambda/lambda.hpp"
#include "boost/lambda/bind.hpp"
#include "boost/function.hpp"

using std::cout;
using std::endl;

namespace
{
template <typename T, typename Operation>
void for_all(T& t, Operation op) { std::for_each(t.begin(), t.end(), op); }

template<typename T>
void lambdaBoost(const T& t)
{
using namespace boost::lambda;

constant_type<char>::type space = constant(' ');
boost::lambda::placeholder1_type _;

boost::function<void(T::value_type)> f = cout << _ << space;
for_all(t, f);
cout << endl;
}

template<typename T>
void lambda0x(const T& t)
{
auto f = [] (T::value_type x) { cout << x << ' '; } ;
for_all(t, f);
cout << endl;
}
}

void lambda04()
{
std::vector<int> v;
for(int i = 0; i < 5; ++i)
v.push_back(i);

lambdaBoost(v);
lambda0x(v);
}


For more information on boost lambda you could read "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book.

Go to the full post

The use of ret in a boost lambda expression

Another nuisance in the usage of the boost lambda expression is that the compiler could be get confused in the translating of the expression and can't get the correct return type from a token. The more annoying fact in this is that we get an error message that is incredibly long and quite difficult to understand. But at least we should find out that the problem comes from a 'sig' symbol and from deducing argument types.

The problem could look obscure, at least the first time, but the solution is easy: just explicitly tell the compiler the return type it should expect using the ret<>() function, or its shortcut bind<>().

The good news is that this problem is no more, when using the C++0x implementation.

Let's see an example:

#include <iostream>

#include "boost/lambda/lambda.hpp"
#include "boost/lambda/bind.hpp"

using namespace boost::lambda;

using std::cout;
using std::endl;

class Doubler
{
public:
int operator()(int i) const { return i*2; }
};

void lambda03()
{
Doubler d;

// this doesn't work:
//(cout << _1 << " * 2 = " << (bind(d, _1)) << '\n')(12);

(cout << _1 << " * 2 = " << (ret<int>(bind(d, _1))) << '\n')(12);
(cout << _1 << " * 2 = " << (bind<int>(d, _1)) << '\n')(12);

[d] (int j) { cout << j << " * 2 = " << d(j) << endl; } (12);
}

The commented boost lambda expression just does not compile. We should help the compiler to figure out the type returned by the token involving the binding to the Doubler functor, using what it is showed in the next line, by the ret<>() function or, more concisely, we could use the bind<>() function, that combines binding to the return value identification.

And, when we can, using the C++0x implementation could save us a lot of head scratching.

More information on boost lambda and ret<> in "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book.

Go to the full post

Constants inside a lambda expression

Using constants inside a boost lambda expression is a kind a nuisance. And also calling a member for a variable passed to the lambda expression is not so smooth as it could be.

This is not an issue anymore, if you are lucky enough to use a compiler that supports the C++0x TR1. But if this is not the case, well, just be patient.

Here is an example that shows the difference between the two implementations:

#include <iostream>
#include <string>
#include <map>
#include <algorithm>

#include "boost/lambda/lambda.hpp"
#include "boost/lambda/bind.hpp"

using std::cout;
using std::endl;

namespace
{
typedef std::map<int, std::string> AMap;

void lambdaBoost(const AMap& aMap)
{
using namespace boost::lambda;

cout << "boost lambda nullary functor: constant()\n";
for_each(aMap.begin(), aMap.end(),
cout << constant("key = ") << bind(&AMap::value_type::first, _1)
<< ", value = " << bind(&AMap::value_type::second, _1) << '\n');

// Print the size and max_size of the container
(cout << "size is = " << bind(&AMap::size, _1)
<< "\nmax_size is = " << bind(&AMap::max_size, _1) << '\n')(aMap);
}

void lambdaOx(const AMap& aMap)
{
cout << endl << "C++0x lambda makes it easier" << endl;
typedef AMap::value_type AMType;
auto f1 = [] (AMType at) { cout << "key = " << at.first << ", value = " << at.second << endl; };
for_each(aMap.begin(), aMap.end(), f1);

[aMap] { cout << "size is = " << aMap.size() << endl << "max_size is = " << aMap.max_size() << endl; } ();
}
}

void lambda02()
{
AMap aMap;
aMap[3] = "Less than pi";
aMap[42] = "You tell me";
aMap[0] = "Nothing, if you ask me";

lambdaBoost(aMap);
lambdaOx(aMap);
}

As we see, the boost implementation of lambda requires our collaboration, since we have to use the constant() function to mark at least the first string used in the expression as a constant, and we should explicitly bind() the variable to access a member of it.

The code is based on an example provided by "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book. An interesting reading indeed.

Go to the full post

The lambda expression

A lambda expression is a sort of function, that is declared in the body of another function and that could also be used in a boost::function (and even a std::function, if your compiler already support the C++0x TR1 ).

Here is a simple example that shows how to use a lambda expression, alone and in combination with function, using the boost libraries:

#include <iostream>

#include "boost/lambda/lambda.hpp"
#include "boost/function.hpp"

using namespace boost::lambda;
using std::cout;
using std::endl;

void boostLambda()
{
cout << "boost::lambda says hello ..." << endl;

(cout << _1 << " " << _3 << " " << _2 << "!\n") ("Hello", "friend", "my");

boost::function<void(int,int,int)> f =
cout << _1 << "*" << _2 << "+" << _3 << " = " << _1*_2+_3 << "\n";

f(1, 2, 3);
f(3, 2, 1);
}

The boost implementation is a bit different from the standard one, but it works just in the same way:

#include <iostream>
#include <functional>

using std::cout;
using std::endl;

void stdLambda()
{
cout << endl << "C++0x lambda says hello ..." << endl;

[] (char* a, char* b, char* c) { cout << a << ' ' << c << ' ' << b << '!' << endl; }("Hello", "friend", "my");

std::function<void(int,int,int)> f =
[] (int a, int b, int c) {cout << a << "*" << b << "+" << c << " = " << a*b+c << endl;};

f(1, 2, 3);
f(3, 2, 1);
}

The standard implementation is a bit more verbose than the boost one or we could say that the standard way is a bit more explicit.

In my opinion the standard version is more readable, but this is just a matter of taste.

The code is based on an example provided by "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book. An interesting reading indeed.

Go to the full post

std::transform

If we want to apply the same change to all the elements in a sequence, it is nice to use the std::transform algorithm. As usual, we pass to it a predicate that is delegate to perform the actual change.

If the transformation is not banal we usually write a functor to store the rule that has to be applied. At least, that's what we did when there was no boost or C++0x available.

In the example we see how to implement the transformation "increase the value by ten, than reduce the result by 5%" using boost::bind, and then with the C++0x lambda.

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>
#include <iterator>

#include "boost/bind.hpp"

using namespace std;

namespace
{
template<class T>
void dump(list<T>& lst)
{
copy(lst.begin(), lst.end(), ostream_iterator(cout, " "));
cout << endl;
}

void init(list<double>& lst)
{
lst.clear();
lst.push_back(10.0);
lst.push_back(100.0);
lst.push_back(1000.0);
dump(lst);
}
}


void bind05()
{
list<double> values;

init(values);
auto fb = boost::bind(multiplies<double>(), 0.95, boost::bind(plus<double>(), _1, 10));
transform(values.begin(), values.end(), values.begin(), fb);
dump(values);

init(values);
auto fl = [](double d) { return (d + 10) * 0.95; };
transform(values.begin(), values.end(), values.begin(), fl);

dump(values);
}

Why using boost::bind when with C++0x lambda the code is so straigthforward? Well, maybe when you have to use a compiler that does not support C++0x yet.

The code is based on an example provided by "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book. An interesting reading indeed.

Go to the full post

std::count_if and std::find_if

Another place where it comes handy to use boost::bind or the lambda expression is as predicate of the conditional version for the STL algorithms count_if and find_if.

We use count_if when we want to get the number of elements in a sequence that respect a clause we specify; find_if is used to find the fist element in a sequence matching our requirements.

Without using boost or C++11 we should define a functor to specify the behavior that we are interested in. As we can see in this example, the new techniques make the code cleaner and more readable:

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <iterator>

#include "boost/bind.hpp"

using namespace std;

namespace
{
   template<class T>
   void dump(vector<T>& vec)
   {
      copy(vec.begin(), vec.end(), ostream_iterator<T>(cout, " "));
      cout << endl;
   }
}

void bind04()
{
   vector<int> vec;

   vec.push_back(12);
   vec.push_back(7);
   vec.push_back(4);
   vec.push_back(10);
   dump(vec);

   cout << endl << "Using boost::bind" << endl;

   cout << "Counting elements in (5, 10]: ";

   // 1
   auto fb = boost::bind(logical_and<bool>(),
   boost::bind(greater<int>(), _1, 5),
   boost::bind(less_equal<int>(), _1, 10));
   int count = count_if(vec.begin(), vec.end(), fb);
   cout << "found " << count << " items" << endl;

   cout << "Getting first element in (5, 10]: ";
   vector<int>::iterator it = find_if(vec.begin(), vec.end(), fb);
   if(it != vec.end())
      cout << *it << endl;

   cout << endl << "Same, but using lambda expressions" << endl;

   cout << "Counting elements in (5, 10]: ";

   // 2
   auto fl = [](int x){ return x > 5 && x <= 10; };
   count = count_if(vec.begin(), vec.end(), fl);
   cout << "found " << count << " items" << endl;

   cout << "Getting first element in (5, 10]: ";
   it = find_if(vec.begin(), vec.end(), fl);
   if (it != vec.end())
      cout << *it << endl;
}
1. since we use the same predicate a couple of times it's a good idea storing it in a local variable (here using the cool C++11 'auto' keyword to save the time from figuring out the correct type definition for the predicate). The construct is a bit verbose, but should be clear enough in its sense: we are looking for a value in the interval (5, 10]; count_if will count all the elements in the sequence respecting this rule; find_if will return the iterator to the first element for which that is valid - or end() if no one will do.
2. it is so much cleaner implementing the same functionality using the C++11 lambda syntax.

The code is based on an example provided by "Beyond the C++ Standard Library: An Introduction to Boost", by Björn Karlsson, an Addison Wesley Professional book. An interesting reading indeed.

Go to the full post