Tag Archives: stl

Using Lambdas in MFC Applications – Part 1: Sorting Arrays

Beginning with Visual Studio 2010 which supports lambda expressions introduced by C++11 standard, you can handily sort an MFC array like in the following example:

Sorting CStringArray by using a lambda expression

Of course, you can write similar code for other types of MFC arrays like CArray, CUIntArray, and so on.
But also you can easily write a kind of “generic lambda” in order to sort any type of MFC arrays.

Using decltype to sort any type of MFC array

That’s pretty cool… However would be nice to be possible to get rid of “wordy” constructions like “decltype(*arr.GetData())” in the lambda’s formal parameters list. Good news! There is a proposal for next C++ standards: using auto type-specifier in order to make generic lambda expressions (which accept any type of arguments). And that is already supported in Visual Studio 2015.

Using generic (polymorphic) lambda expressions

Notes

  • Some people may claim that using MFC collection classes is obsolete and must use STL containers instead. That’s an old subject of arguing but it’s not in scope of this short article.
    It simply presents how to sort MFC arrays by using lambda expressions.

References and related articles

Codexpert – 2014 Articles Summary

Microsoft Libraries

C++ Language

Windows Tips

See also

C++11: Let’s Write a “Hello Lambda!”

A lambda expression (aka lambda function), introduced in C++11 standard, is a simplified notation for defining an anonymous function object. However, its syntax and using may look weird for many people so let’s try to make a simple program to accommodate with it.

Let’s describe each part, in order.

The parts of a lambda expression

  • [] is the lambda introducer that may be empty or may contain a capture list; this part is mandatory for defining a lambda expression;
  • () is a formal parameters list; if it takes no parameters and no specifier like mutable or noexcept has been used, this part is optional;
  • mutable is an optional specifier which indicates that the copies of variables captured by value can be modified inside the lambda body;
  • throw() (or noexcept) is an exception specifier which is also optional;
  • ->void is the return type; it is optional if the compiler can deduce the return type;
  • { std::cout << "Hello Lambda!"; } is the body specifying the code to be executed.
  • finally, we have in our example a function-call operator, (), which is not a part of lambda expression.

Getting rid of optional parts, we can make our program simpler, as follows:

Further, let’s take a little deeper look in the lambda introducer part.

The lambda introducer and the capture list

As already said before, the lambda introducer that may be empty or may contain a capture list. An empty lambda introducer means “no capture is made”. Otherwise, the local variables from the place where lambda is defined can be “captured” (i.e. used in the lambda body) as follows:

  • [=] all local variables are implicitly accessed by value;
  • [&] all local variables are implicitly accessed by reference;
  • [capture_list] a list of variable names to be captured (explicit capture); if a variable name is preceded by & then it is captured by reference; otherwise, it is captured by value;
  • [=, capture_list] all variables which are not in the capture_list are captured by value;
  • [&, capture_list] all variables which are not in the capture_list are captured by reference;

Note that variables captured by value cannot be modified inside the lambda body, except case the mutable specifier has been used.
Now, let’s make our program a little bit more complicated to illustrate the using of capture list and other lambda expression parts.

Notes

  • This article presented just trivial examples, introducing lambda expressions as simple as possible. You can find tens of articles and examples presenting lambdas deeper. See also references and related articles, below.
  • std::function is an STL class that wraps callable objects like functions, lambda expressions and so on.

References and related articles

C++ generic numeric algorithms in header <numeric>

The C++ Standard Library header <numeric> contains several generic numeric algorithms. In this post we take a look at how they can be used for solving real world examples.

Accumulating values

Problem: Given the monthly sales values compute the total sales during a year.

Solution: This is a simple sum that can be computed by iterating over the sales and summing them.

There is an algorithm for that called accumulate. It computes the sum in a given range and the provided initial value. So for our problem this can be put as:

Problem: Given the monthly inflation rates compute the total inflation during a year.

Solution: If the inflation was 10% in January and 20% in February, the inflation at the end of February is not 30% but 32%. The monthly inflation rates must be multiplied. An overloaded accumulate allows to specify a binary operation to be used for accumulating values, instead of operator+. So the solution to our problem could look like this:

Partial accumulations

Problem: Given the monthly sales values compute the accumulated total sales per whole year at the end of each month. In other words show the sales for January, January to February, January to March, … January to December.

Solution: This is again a simple summing operation where in each loop you have a partial sum. s[0] = v[0], s[1] = v[0] + v[1], s[2] = v[0] + v[1] + v[2], etc.

There is an algorithm called partial_sum that does exactly that: it computes the partial sums of the elements in the given range and writes them in a destination range. There are two overloads of it, one using operator+ and one that allows to specify a binary operation.

The content of acc_sales will be {1000, 2500, 4500, 6000, 8000, 9000, 12000, 13500, 14700, 16500, 18700, 20700}.

Sum of products

Problem: Given the values of daily sales in USD compute the total sales in EUR.

Solution: Computing the total sales in USD and then multiplying with the USD/EUR exchange rate is not a correct solution because the exchange rate varies every day. We must compute the daily sales in EUR and then sum those values. That means we need a sum of products.

Another algorithm in the <numeric> header called inner_product does exactly that. It takes two ranges and an initial value and uses operator* to compute the product and operator+ to sum the products.

Problem: Given the monthly budgets and the actual sales over an year count how many times the budget was met or exceeded.

Solution: To count how many times the sales where equal or greater than the budget we have to compare the values in each month and increment a value each time the condition was true.

Instead of coding this explicitly we could use an overload of the inner_product algorithm that takes two additional parameters, both binary operations, for the sum operation and the product operation. For the sum we can use std::plus() and for comparison std::greater_equal() (need to include header <functional>).

The result of the count for the input data is 6.

Adjacent differences

Problem: Given the monthly sales for an year compute the variations (in percentage) between the current and previous monthly sales. If sales in January were 1000 and in February were 1500, then the sales variation for February is 50%.

Solution: We have to iterate through the monthly value and compute (current - prev) / prev for each month. This is an operation applied to adjacent values.

An algorithm called adjacent_difference computes difference between adjacent values in a given ranges and writes them in a destination range. The first element of the input range is copied unmodified to the beginning of the destination range. An overload allows to specify a binary operation to be used instead of operator-.

To solve the proposed problem we call this algorithm on the sales and then remove the first element from the destination range (since it’s just a copy of the sales for the first month). We use a lambda for the binary operation and it simply returns (current - prev) / prev.

The result for the given range (shown with 4 decimals) is {0.5000, 0.3333, -0.2500, 0.3333, -0.5000, 2.0000, -0.5000, -0.2000, 0.5000, 0.2222, -0.0909}.

Assigning algorithms in the C++ Standard Library

The C++ Standard Library provides several algorithms for assigning values to a range (such as a container or a C-array).

fill and fill_n

std::fill assigns a given value to all the elements in a range. It is available in the header <algorithm>. In the following example all elements of a vector of integers are assigned the value 1.

std::fill_n is similar, but instead taking the bounds of a range it takes the beginning and a count and initializes N elements starting from the specified first element. You must make sure that first + count does not exceed the bounds of the range. The following example is an equivalent of the first:

generate and generate_n

These algorithms are similar to the first, but instead of taking a value to assign they take a function and assign the value returned by the function. They are also available in the header <algorithm>.

std::generate assigns the elements in a range the values returned by a function.

In the following example we initialize a vector of 10 elements with random numbers (using a Marsenne twister engine).

The result may look like this:

You can use lambdas as the function whose return value is stored into the range. The following example generates random numbers ranging from 1 to 100 with a uniform distribution.

Result may look like this:

std::generate_n is similar, but instead of taking the limits of the range it takes the beginning and a count and assigns the first N values returned by the function to the range. You must makes sure that first + count does not exceeds the bounds of the range.

In the following example we initialize the elements of a vector with values from 1 to N, where N is the size of the range.

The result is:

iota

std::iota is a new algorithm to C++11. It assigns the elements of a range with sequentially increasing values starting from a given value. The algorithm is available in header <numeric>.

The following example initializes the elements of a vector with values from 1 to N, where N is the size of the range (basically the same thing we did in the last example).

The result is:

Notice that the term iota is taken from the APL programming language and denotes the Greek letter used in various mathematical notations.

Farewell to new and delete

C++11 introduced several smart pointers (residing in the <memory> header):

  • std::shared_ptr: retains shared ownership of an object, that is destroyed when the last shared_ptr that holds a reference to it is destroyed or assigned another pointer.
  • std::unique_ptr: retains sole ownership of an object, that is destroyed when the unique_ptr goes out of scope
  • std::weak_ptr: retains a non-owning reference to an object managed by a shared_ptr. It does not participate in the reference counter of the shared pointer. It is mainly use to break circular dependencies.

While these smart pointers manage resources automatically, so there is no need to delete object explicitly, they still require explicit instantiation with new for the managed resource.

C++11 introduced std::make_shared, a free function that constructs an object and wraps it in a std::shared_ptr object.

C++14 introduces another free function, std::make_unique, that constructs an object and wraps it in a std::unique_ptr object.

With these smart pointer and functions available there is no need any more to use new and delete in your C++ code. Besides avoiding explicit allocation and release these functions have another important advantage: they prevent memory leaks that could happen in the context of function calls. You can read Herb Sutter’s GotW #102: Exception-Safe Function Calls for details about this problem.

C++11: non-member begin() and end()

One of the addition to the C++ 2011 standard that is perhaps not so much popularized is the non-member begin() and end(). In STL all containers have a non-static member begin() and end() methods that return an iterator to the beginning and the end of the container. Therefor iterating over a container could look like this:

The problem here is that not all user-defined containers have begin() and end(), which makes them impossible to use with the STL algorithms or any other user-defined template function that requires iterators. That is even more problematic when using C arrays. For instance, using a C array with a standard algorithm is quite different than using a vector, for instance.

The non-member begin() and end() methods are extensible, in the sense they can be overloaded for any type (including C arrays). Herb Sutter argues in his Elements of Modern C++ Style article that you should always prefer the non-member version. They promote uniformity and consistency and allow for more generic programming.

Always use nonmember begin(x) and end(x) (not x.begin() and x.end()), because begin(x) and end(x) are extensible and can be adapted to work with all container types – even arrays – not just containers that follow the STL style of providing x.begin() and x.end() member functions.

The code above can now look like this:

As for the C array we can overload begin() and end() to look maybe like this:

With this available we can write:

If you’d argue that non-member begin() and end() break the encapsulation then I suggest you read Scott Meyers’ How Non-Member Functions Improve Encapsulation where he explains the opposite.

If you’re writing a function that can be implemented as either a member or as a non-friend non-member, you should prefer to implement it as a non-member function. That decision increases class encapsulation. When you think encapsulation, you should think non-member functions.

There is still one question left: what about the other container functions that return iterators, rbegin(), rend(), cbegin(), cend(), crbegin(), and crend()? Currently they are not implemented as non-member functions. According to Herb Sutter, the omission of cbegin() and cend() was an oversight and it will be fixed.

Additional readings: