The purpose of this post is to show and explain a bit more about the practical usage of C++ “lambda power”. This time in developing a light, fully functional, fast, and hopefully not that often seen, matrix creation utility. Functional programming style.
GitHub gist is here. The previous post with another very interesting matrix variation is here.
Update 2021 MAR: The gist version 6 is a major update. Matrix related code does not use the std:: lib any more.
Before we proceed: I do know about Expression Templates and few other optimization techniques. Alas. I do consider them overkill in this context. Another reason for the existence of this post and code is the search for simplicity made possible by C++ lambdas.
This is the core API of your API
You are preparing a “matrix something something” library. Some game, uni project, PhD project or similar. Let’s say some matrix operations for your specific needs. Thus I assume you do understand why the core of your library should be something a bit better than T[rows][cols]. I am assuming you need a quick and easy to use, but fully functional, core of your matrix API. The one you can use straight away and concentrate on the functionality you need to provide. The core API where you actually contain the functionality of keeping the matrices and making them available.
Usage of my single function API is simple.
|
1 2 3 4 5 6 7 8 |
// int 3x3 matrix // static version // this is compile time // arguments are: type, width, height constexpr auto matrix_= dbj_mx_make_stack(int, 3, 3); // int 3x3 dynamic matrix auto matrix_= dbj_mx_make_heap(int, 3, 3 ); |
You need to preserve those matrix dimensions. Changing the cell value is simple.
|
1 2 |
// change the value through one function API matrix_(1, 1) = 42 ; |
The same call is used to both change the value of a matrix cell, or get to the value of the cell.
|
1 2 3 |
// obtain the cell value auto cell_val = matrix(1,1); assert( cell_val, 42 ); |
The whole API is just one function with two arguments: row and column ordinal. How is matrix actually created, is it on the stack or on the heap, you do not need to know, Just use it as the core of your matrix API.
So. Why is “my” solution good? Because it is simple, it is standard C++ and completely decoupled from the std lib. This means the two std lib array and vector are replaced with extremely simple code developed “in house”. This in turn means this matrix solution can be used in mission-critical or embedded or IOT runtime environments.
Let us first study the obvious alternatives. Perhaps they are good enough?
The full std:: lib way
Stack means small(er) matrices, with nothing to worry about, regarding freeing the memory used by the matrix. Also, one can create and use those 2D arrays at compile time.
Let start with using C++ std:: lib types. For the stack-based matrix, we shall use std::array.
Note: coding style in this part is a bit pedestrian. That is deliberate, it helps to understand.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <array> using std::array; // matrix template (alias) template< typename T, size_t width, size_t height > using mtx_stack = array< array<T, width > , height >; // matrix type using mtxint_3_2 = mtx_stack<int,3,2>; // matrix instance + initialization constexpr mtxint_3_2 mx_1{ array{1,2,3} , array{4,5,6} }; // row 0 compile time values static_assert( mx_1[0][0] == 1 ); static_assert( mx_1[0][1] == 2 ); static_assert( mx_1[0][2] == 3 ); // row 1 compile time values static_assert( mx_1[1][0] == 4 ); static_assert( mx_1[1][1] == 5 ); static_assert( mx_1[1][2] == 6 ); |
Above is somewhat equal to int mx_1[2][3]. But here we use std::array as one very handy and simple std type, for generic stack-based 2D arrays of type T. And unlike native arrays, std::array instances can be moved, can be used with standard templates and algorithms easily.
Heap-based standard solution
Heap is for much larger run-time matrices. But. With the added issue of memory fragmentation. And strict run-time usage. No, compile-time speed.
At first thought, for the heap-based array I decided to use (also c++17 standard) std::unique_ptr<T[]>, basically a smart pointer to an array. Here is a basic, complex but workable solution.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <memory> using std::unique_ptr; /* Example -- height : 2, width: 3 2 rows 3 columns +----+ +----+----+----+ | 0 +---> | 0 | 1 | 2 | +----+ +----+----+----+ | 1 +---> | 0 | 1 | 2 | +----+ +----+----+----+ */ // heap array template (alias) template<typename T> using heap_rows = unique_ptr<T[]>; // heap matrix template (alias) template< typename T > using mtx_heap = unique_ptr< // array of rows heap_rows<T>[] >; // heap matrix type using mtxh_int = mtx_heap<int>; // creation has to be runtime mtxh_int make_mtxh_int_3_2( ) { using std::make_unique; // make rows array auto rows_arr = make_unique< heap_rows<int>[] >( 2 /*height of two rows*/ ); // each element of array of rows is pointing to array of values const int width = 3; rows_arr[0] = make_unique< int[] >(width); rows_arr[1] = make_unique< int[] >(width); // unique ptr can move return rows_arr; } static auto use_mtxh_int_3_2 = []() { mtxh_int mtxh_3_2 = make_mtxh_int_3_2(); // row 0 mtxh_3_2[0][0] = 1; mtxh_3_2[0][1] = 2; mtxh_3_2[0][2] = 3; // row 1 mtxh_3_2[1][0] = 4; mtxh_3_2[1][1] = 5; mtxh_3_2[1][2] = 6; return true; }(); |
First to note: I made the wrong choice here. The std::vector<T> is a (much) more elaborate type, but crucially, with the added benefit of giving to the whole mechanism, the crucial ability to be both copied and moved around. Also, the above can be expanded, made more complex, and involved; if for example, we extend the functionality in order to create a heap-based matrix of any size, or we can create a structure around this core, etc. Or we can think of:
The Alternative
In any case, I am sure you will agree, that is not a very simple looking code. To use it you probably just have to believe, I know what I am doing and that will all work in all sorts of applications you might have.
I somehow do not subscribe to that point of view. Standard C++, 17 and beyond have rapidly increased in complexity. In my opinion, unwarranted complexity. Those two solutions so far, just look too complex to me.
Armed with the C++ core language “Lambda Expressions” feature, and two small, “base” functions, I might be so bold to present all you need to create and use standard C++ std lib 2D arrays in a very FP fashion.
All the std lib usage is nicely hidden (aka encapsulated) and decoupled inside two tiny lambdas. Without your code knowing or worrying are you on the stack or on the heap. Besides you of course knowing the unique limitations of both kinds of memory.
Without further cogitations, here is the front of the mechanism:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
template< typename T, size_t rows, size_t cols, typename F > /* potentially constexpr function */ inline constexpr /* return type is lambda*/ auto mx( /* argument is a callable object that has to generate memory block, big enough to store T[rows x cols] made on stack or on heap result has to be movable F type has to be moveable and copyable and has to have indexing operator '[]' */ F source_ ) { /* return a lambda */ return[ /* make a call to hand over the array memory and make 'arry' member, available inside lambda note that we copy the result to 'arry' with '=' yet another lambda feature */ arry = source_() ] /* lambda is always to be called with row and col of the matrix stored in the member 'arry' */ (size_t row_, size_t col_) /* this lambda is potentially compile time and returned type is mutable reference to type T */ mutable->T& { assert(row_ < rows); assert(col_ < cols); /* we use a single contiguous memory block to represent 2D matrix to return a single element we use the formula as bellow */ return arry[row_ * rows + col_]; }; } // mx |
Please take your time, going through the code above. It is really packed with a lot of modern C++. Showing the “power of lambda”.
NOTE (2021 MAR): As we explained above code is available as the GIST is in version 6.0.0. It is probably faster and simpler because it does not use std::array or std::vector. Thus it can be used in “no exceptions, no streams, no RTTI” projects. That of course does not mean this code is somehow inferior. Please read on.
What surprises most readers, is the capture statement of the lambda above: [ arry = source_() ]. That is a legal C++. Lambda capture statement is how users pass lambda object constructor arguments, and name members to be used inside the lambda.
Above we are saying: the result of the call source_() will be copied to the member arry upon constructing the lambda object. Watch carefully. The synopsis of the function object generated by the compiler to implement that lambda is approximately this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
``` // not legal C++ lambda __some_uid_123_ { size_t rows_{/* take from the closure */}; size_t cols_{/* take from the closure */}; // the array memory T arry_[] {} ; // constructor __some_uid_123_ () { __copy_to( arry, source_() ) ; } // this is what users see and use as closure T & operator () (size_t row_, size_t col_) { assert(row_ < rows); assert(col_ < cols); return arry[row_ * rows_ + col_]; } } ; ``` |
The key point of the above is: when implemented that lambda represents the so-called “local class”. Let us repeat once more: We return the instance of a local class when returning lambda from inside a function. Here is the solution from above this time with no comments:
|
1 2 3 4 5 6 7 8 9 10 11 |
template< typename T, size_t rows, size_t cols, typename F > inline constexpr auto mx(F source_) noexcept { return[arry = source_()] (size_t row_, size_t col_) mutable->T& { assert(row_ <= rows); assert(col_ <= cols); return arry[row_ * rows + col_]; }; } // mx |
And that is the secret sauce. This gives us the greatest degree of encapsulation and decoupling. We use the inner lambda returned on the first call of the outer function. Inner lambda has access to the closure where it was born. Most importantly to the memory block given to the constructor of the closure where our matrix lambda was born.
|
1 2 3 |
// arry is array // kept inside the lambda return arry[row_ * rows + col_]; |
Above we do return one arry element by reference. And that lambda is “mutable” which is yet another, secret sauce.
API Sampling
How do we use this in practice? Provided we all understand why is it done as it is. First the inevitable macros. We actually used them at the beginning of this post, without telling you.
|
1 2 3 4 5 6 7 8 9 10 11 |
// T is the type, R is rows, C is columns // use the function K as the argument to the // mx< T, R * C> // K is one of the two array memory providers #define dbj_mx_make(T, R, C, K) mx<T, R, C>(K<T, R * C>) // us the first macro and use the heap arr making function #define dbj_mx_make_heap(T,R,C) dbj_mx_make(T, R, C, arr_heap) // use the first macro and use the stack arr making function #define dbj_mx_make_stack(T,R,C) dbj_mx_make(T, R, C, arr_stack) |
As in the gist provided, for the above macros, we need two tiny functions to provide 2D arrays allocated on the stack or on the heap. arr_stack and arr_heap.
|
1 2 3 4 5 6 7 8 9 10 11 |
// make 1D array on the stack template< typename T, size_t len_ > inline constexpr auto arr_stack() { return std::array<T, len_>{ {}}; } // make 1D array on the heap template< typename T, size_t len_ > inline auto arr_heap() { return std::vector<T>(len_); } |
Above we have completely encapsulated the mechanism of making arrays and thus decoupled the solution from this mechanism completely.
The commonality of actual types returned above is: operator [ ] (aka indexing) operator and the ability of both to be moved and copied. In case you want to replace them with something else you might fancy in order not to depend on the std lib at all.
Functional programming
The type of the C++ lambda is irrelevant, its functionality is what matters. This is a simple and single API for both 2D array types: stack and heap. Now you can write matrix manipulation functions that are completely decoupled from matrix creation issues.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// receive the matrix 'as a function' by value inline auto changer = []( // pass by value auto matrix_, size_t row_, size_t col_, auto value_) { // on the matrix given, change the cell required matrix_(row_, col_) = value_; // return again by value return matrix_; }; // print the matrix inline auto printer = []( // pass by value auto matrix_, size_t width_, size_t height_) -> void { using namespace std; for (size_t row_ = 0; row_ < width_; row_++) { cout << endl << "{"; for (size_t col_ = 0; col_ < height_; col_++) { // here we use the matrix, again through one function call cout << setw(3) << matrix_(row_, col_) << " "; } cout << "}" << endl; } cout << endl; }; |
We simply have a matrix completely encapsulated in a function. The full test, again in an FP style is at the bottom of that gist, already mentioned.
I think this is one very small but useful utility. Showing a lot of good sides of a mixture of modern C++ and functional programming. All simply enabled with lambdas aka closures.
Usability
Using this mechanism we do “carry around” our matrices. Wherever we can copy or move the lambda instance we will take the access of the 2Darray kept inside it. I think you might have already noticed that.
This is giving the ability to pass these matrices by value and also return them by value. And it all “just works”. Thanks to lambda implementation and thanks to a few key points of this design.
You will quickly find out, to actually use this API, FP style is the best fit. As in the examples above. Which does not mean the OOP style is excluded. It is only, this solution is not suited for OOP. As it is not simple to keep lambda as a member in a class.
Finally
Several measures can be added to stop the abuse, but as it is, this utility can be used in very real, demanding projects. Also, both std::array and std::vector,quality alternative implementations can be found on the net. That is in case your code is running in mission-critical environments.
