Contents
Introduction
Are you interested in a convenient tool which facilitates the use of generic C++ programing for processing or storing custom data types? Have you ever tried to use any of the notable std::sort, std::merge or std::lower_bound STL [1] algorithms for processing custom structures or classes? Have you ever tried to use STL associative containers, like the std::set or the std::map, for storing your own data types? Or maybe, do you feel that the implementation of the function objects, (functors) the lambda expressions, or the custom C++ operators should be less tedious, cumbersome and error-prone?
If your answer to any of the above questions is positive, chances are that this article will interest you. The purpose of this article is to present the Online Generic Data Ordering Wizard and demonstrate how this tool can make the ordering of custom data much more convenient in generic C++ programming, by easily creating specialized C++ function objects, lambda expressions and custom C++ operators. All these will be discussed in the next paragraphs from a very practical point of view and with the use of simple examples, while the theoretical and technical details will be kept to the minimum necessary for clarity.
Abstract
The C++ compilers do not automatically handle the ordering of custom classes or structures, while at the same time, data ordering is widely used by a plethora of generic C++ components (i.e. template classes, structures and functions). Therefore, many generic C++ components, including some of the most notable STL algorithms and containers, often fail to work with user-made classes or structures out-of-the-box, because they cannot order this kind of data without additional programming effort. The typical solution for these issues is to create an adequate function object (functor), lambda function or custom operator and use it to assist the generic code in ordering the particular custom data type. However, the manual creation of these functors, lambdas and custom operators is a rather cumbersome, tedious and relatively error-prone programming task.
Recognizing that this situation actually prevents the software developers from fully exploiting the benefits of generic C++ programming, I have decided to implement the Online Generic Data Ordering Wizard presented in this article. Interestingly enough, this tool can simplify the previously cumbersome and error-prone generic data ordering so much, that most data ordering tasks in generic C++ programming can now become as easy as filling a three-field form. At the same time, this tool allows us to enjoy the benefits of some very useful functors, lambdas and custom operators, without having to worry about their (rather cumbersome) implementation and without investing time in learning and mastering them.
What can this wizard do for us?
The Online Generic Data Ordering Wizard is meant to be a practical tool for C++ developers. The mission of this tool is to help us with practical problems in generic C++ programing and to make some programing tasks much easier than they used to be. Hence, in order to realize what this wizard can do for us, it is essential to understand the nature of the problems which this wizard is designed to handle and to also understand how exactly this tool can help the C++ developers to overcome these problems in practice.
What is the problem with generic data ordering?
Most of the times in C++, it is fairly easy and straightforward to use template functions and classes, like the STL algorithms and containers, for processing or storing standard data types, such as integers, doubles or std::string objects. For instance in the following example #1 you can see how easy it is to create std::set containers for storing standard C++ data values and also how equally easy it is to use std::sort for sorting standard C++ data values contained in a std::vector. The example code is expected to compile without errors in any decent C++ compiler, as you can verify by clicking the corresponding compile link.
Example #1: Ordering standard C++ values [compile]
#include <vector>
#include <string>
#include <set>
#include <algorithm>
int main()
{
std::vector<int> v1;
std::sort(v1.begin(), v1.end());
std::vector<double> v2;
std::sort(v2.begin(), v2.end());
std::vector<std::string> v3;
std::sort(v3.begin(), v3.end());
std::set<int> s1;
s1.find(int());
std::set<double> s2;
s2.find(double());
std::set<std::string> s3;
s3.find(std::string());
return 0;
}
However things become much more difficult, when we start using generic code for processing or storing custom structures and classes. Namely, it is not possible to just replace the standard data types of the previous example with custom types, even as simple as the point struct of the next example, and expect that the code will still continue to work like before! On the contrary, STL will be much less friendly to this point structure, than it previously was to the standard C++ data types. In the example #2 bellow, the "straightforward" attempts to create and use a std::set<point> container and also to sort the elements of a std::vector<point> container with the std::sort algorithm will both fail to compile, as you can verify by clicking the corresponding compile link.
Example #2: Ordering a custom structure [compile]
#include <vector>
#include <set>
#include <algorithm>
struct point {
int x, y;
};
int main()
{
std::vector<point> v;
std::sort(v.begin(), v.end());
std::set<point> s;
s.find(point());
return 0;
}
What went wrong in the example #2 above is that the implementation code of the std::set and std::sort templates has attempted to order point structures using the less-than (<) operator and has failed to compile because there was no less-than (<) operator defined for our point structure. In essence, this is just an instance of a very common data ordering problem in generic C++ programming, which is related to the availability of the less-than (<) operator. Namely, many generic C++ components like the std::set and the std::sort, by default rely on the less-than (<) operator for ordering generic data, but at the same time the structures and classes in C++ cannot be compared via the less-than (<) operator, unless we have explicitly defined and implemented this operator for them. Consequently, it is quite usual and common for the C++ developers to face difficulties and complications, when using generic code which directly or indirectly orders custom structures or classes. And eventually these difficulties and complications often prevent the software developers from fully exploiting the benefits of generic C++ programming.
| |
Put more formally, many generic C++ components (such as the std::set and std::sort) have less-than-comparable [2] type requirements, meaning that they are designed to work with data types which model the less-than-comparable concept. [2,3] However, the C++ classes and structures are not less-than-comparable types by default and this fact makes the generic components with less-than-comparable requirements (like the std::set and std::sort) incompatible with most custom data-types.
|
How exactly can this wizard help us?
The Online Generic Data Ordering Wizard has been designed to help us overcome most of the difficulties and complications, which the ordering of custom data types can cause in generic C++ programming. This wizard can make generic data ordering much easier and safer, by offering an extremely easy creation of three alternative solutions for ordering custom structures and classes in generic C++ programming: A strict-weak-ordering functor, a strict-weak-ordering lambda function and a custom less-than (<) operator.
For instance, in the following examples 3, 4 & 5 you can see how each of these three solutions, which the wizard provides, can effectively eliminate the problems we previously had with our point structures. Using any of these approaches is adequate enough to allow us both to store our custom point structures in a std::set container and also to sort the elements of a std::vector<point> container with std::sort. You are welcome to test the wizard solutions against a real C++ compiler, by clicking the corresponding compile links.
Example #3: The Strict-Weak-Ordering Functor solution [compile]
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
struct point {
int x, y;
};
struct point_functor
: public std::binary_function<point, point, bool>
{
bool operator() (const point &left, const point &right) const
{
if (left.x == right.x)
return (left.y < right.y);
else
return (left.x < right.x);
}
};
int main()
{
std::vector<point> v;
std::sort(v.begin(), v.end(), point_functor());
std::set<point, point_functor> s;
s.find(point());
return 0;
}
Example #4: The Strict-Weak-Ordering Lambda solution [compile]
#include <vector>
#include <set>
#include <algorithm>
struct point {
int x, y;
};
int main()
{
auto point_lambda = [] (const point &left, const point &right) -> bool
{
if (left.x == right.x)
return (left.y < right.y);
else
return (left.x < right.x);
};
std::vector<point> v;
std::sort(v.begin(), v.end(), point_lambda);
std::set<point, decltype(point_lambda)> s(point_lambda);
s.find(point());
return 0;
}
Example #5: The Less-Than (<) Operator solution [compile]
#include <vector>
#include <set>
#include <algorithm>
struct point {
int x, y;
};
inline bool operator< (const point &left, const point &right)
{
if (left.x == right.x)
return (left.y < right.y);
else
return (left.x < right.x);
}
int main()
{
std::vector<point> v;
std::sort(v.begin(), v.end());
std::set<point> s;
s.find(point());
return 0;
}
How useful can this wizard be in practice?
I expect that the Online Generic Data Ordering Wizard will be quite useful for many C++ developers, because I believe that many C++ developers frequently need to use generic code which orders custom data-types and also because it is very convenient to let the wizard handle these data ordering tasks. In the following paragraphs I will try to explain the reasons why I feel this way about this wizard.
How often do we need to order custom data?
The need for ordering data values is very frequent in software development and generic C++ programming is no exception to this trend. For instance, if we take a look at the following Table #1, we will clearly see that a plethora of STL algorithms and containers need to order generic data in order to work. But its not just the number of these algorithms and containers which is noteworthy, even more important is the fact that the Table #1 actually contains some of the most notable and useful STL components, such as all sorting, merging, heap and binary-searching STL algorithms and all the associative STL containers as well!
| Table #1: STL components which need to order generic data
|
| Sorting algorithms | sort, stable_sort, partial_sort, partial_sort_copy, nth_element |
|---|
| Binary searching algorithms | lower_bound, upper_bound, equal_range, binary_search |
|---|
| Merging algorithms | merge, inplace_merge |
|---|
| Set algorithms on sorted ranges | includes, set_union, set_intersection, set_difference, set_symmetric_difference |
|---|
| Heap algorithms | push_heap, pop_heap, make_heap, sort_heap |
|---|
| Min/max algorithms | min, max, min_element, max_element |
|---|
| Other algorithms | lexicographical_compare, next_permutation, prev_permutation |
|---|
| Sorted associative containers | set, map, multiset, multimap |
|---|
|
The extensive use of data ordering in STL is just a reflection of what actually happens in generic C++ programming in general. Most generic C++ libraries are expected to use data ordering extensively, either directly in their own code, or indirectly by using STL algorithms and containers which in turn need to order generic data. At the same time the user-made structures and classes also play a very important role in C++, and it is no coincidence that C++ was originally named C with Classes. Consequently, there can be a little doubt that, as long as a C++ developer is frequently using STL or other generic C++ libraries, chances are that this developer will often need to use generic code which orders custom data.
Taking the above discussion into account, it is not hard to imagine that a tool which can make generic data ordering much easier than it normally is, can in fact become a quite useful tool for many C++ developers. And this is exactly what the Online Generic Data Ordering Wizard aims to become: A useful online tool, which can frequently make generic C++ programming more convenient and easy for as many C++ developers as possible.
How convenient is it to let the wizard handle the data ordering?
Since there is often a need for ordering custom structures and classes in C++, it is normal to expect that we already have workable solutions for accomplishing these relatively frequent tasks. In fact the solutions that the Online Generic Data Ordering Wizard is producing are neither new nor essentially different, compared to the solutions which the most competent C++ developers already create by hand. And obviously, it is perfectly feasible to write manually the same code that the wizard is producing and have exactly the same functionality, without using the wizard at all! However, we will now see that using the wizard is far more convenient and easy, than writing manually the code required for handling these issues.
To make this discussion more concrete, lets take a closer look at the code snippet bellow, where you can see exactly the same strict-weak-ordering functor implementation we have already used in the example #3, stripped down from any additional example code. The strict-weak-ordering functor is the most effective, generic and versatile among the solutions which can be used for handing generic data ordering, but does the functor implementation bellow seem intuitive enough to you? Is it a piece of code that you could comfortable write whenever necessary? According to my experience, most C++ developers find this functor coding tedious and non-intuitive, to say the least. Some of them even find this kind of coding very ugly and often avoid it altogether!
#include <functional> //Header file requirement
struct point_functor
: public std::binary_function<point, point, bool>
{
bool operator()(const point &left, const point &right) const
{
if (left.x == right.x)
return (left.y < right.y);
else
return (left.x < right.x);
}
};
Moreover, besides being ugly, tedious and cumbersome, the coding of a strict-weak-ordering functor can be a relatively error-prone task as well, since there are several tricky issues involved in the creation of this functor. Namely, in the following list you can see three important issues that require our special attention during a strict-weak-ordering functor implementation:
- A correct strict-weak-ordering functor implementation should carefully respect the strict-weak-ordering concept [4] in its every detail. For example, although the we can replace the less-than (
<) operator with greater-than (>) operator in the above functor implementation, the use of a less-than-or-equal (<=), or greater-than-or-equal (>=) operator is completely prohibited. - The strict-weak-ordering functor performance can be greatly affected when its parameters are not being passed by reference, since the functor implementation is usually so lightweight that the performance cost of passing a structure or class by value can become very significant.
- The strict-weak-ordering functor should be derived from the
std::binary_function base struct, [5] in order to be correctly adaptable. [6] Unfortunately, the correct choice of the std::binary_function template parameters, is neither intuitive nor well documented.
In stark contrast to the above complexities the Online Generic Data Ordering Wizard offers a super easy, simultaneous creation of a strict-weak-ordering functor, a strict-weak-ordering lambda function and a custom operator, in a blink of an eye. As shown in the picture bellow, the only actions the programmer has to do when using this wizard, is to fill three simple fields in the wizard form and afterwards to choose which among the three available solutions he or she prefers the most. And being a simple HTML page, as far as the client-side is concerned, this wizard requires no installation, works in all modern operating systems, with any modern web-browser and is always one click away, as long as you are online.
The evident convenience which this tool offers, as far as generic data ordering is concerned, is a strong indication for me that the wizard will be quite useful for many C++ developers. But of course, you don't actually need to rely on what I am saying regarding the convenience or usefulness of this tool. On the contrary, you are encouraged to visit the Online Generic Data Ordering Wizard web-page and try the wizard online to see for yourself!
More about the wizard solutions
We have already mentioned that the Online Generic Data Ordering Wizard offers three alternative solutions for ordering custom structures and classes in generic C++ programming: A strict-weak-ordering functor, a strict-weak-ordering lambda function and a custom less-than (<) operator. Lets now discuss some interesting and potentially useful details regarding these three solutions.
The Strict-Weak-Ordering Functor solution
The strict-weak-ordering functor is the most effective, generic and versatile solution you can possibly use for ordering custom data in generic C++ programming and this is the approach I personal recommend for almost every case. Particularly if you are unsure of which approach to choose, or if you want to avoid unpleasant surprises, this is certainly the right choice for you.
The Strict-Weak-Ordering Lambda solution
Compared to the strict-weak-ordering functor, the strict-weak-ordering lambda requires slightly less complex and less cumbersome coding when manually implemented. However this advantage is completely irrelevant when both the functor and the lambda are simultaneously created by the Online Generic Data Ordering Wizard. Furthermore, the lambda solution can be somewhat more elegant and readable than an equivalent functor, particularly when used with template functions. But at the same time, the strict-weak-ordering lambdas are less flexible than the strict-weak-ordering functors, are not adaptable [6] and can only work with compilers that conform with the new C++11 standard standard. Consequently, my recommendation for the time being is to generally prefer the strict-weak-ordering functors, instead of the strict-weak-ordering lambdas.
The Less-Than (<) Operator solution
The less-than (<) operator solution differs a lot from the other two wizard solutions, in the sense that instead of adding extra functionality to the generic component we need to use, it actually adds new characteristics to the data we need to process. This is why in my opinion, the less-than (<) operator is the most inflexible, restrictive and problematic among the solutions which the wizard has to offer. One important problem with this approach, is that it does not allow the ordering of the same data in more than one way, meaning that it will make it very difficult for us to choose at runtime between several ordering methods.
Furthermore, in practice it is often not appropriate to change the characteristics of our data, just because somewhere in our code we need a specific type of ordering. For instance, if we need to order our data in a way that differs from the default ascending ordering, then we will be forced to implement a rather unconventional and counterintuitive less-than (<) operator. This counterintuitive operator in turn, will very likely cause undesirable side-effects in other parts of our program, or even to other developers who happen to use this particular data structure. Hence considering all the above, I would not recommend the less-than (<) operator approach for ordering custom data, unless you have very good reasons to choose it.
Other possible uses of the wizard
The Online Generic Data Ordering Wizard has been designed mainly for handling the ordering of custom structures and classes in generic C++ programming. However, this does not mean that it cannot also be useful with standard C++ classes, such as the std::string or the std::vector. Of course, since these standard classes have already the less-than (<) operator defined for them, there is practically no sense in using this wizard, unless we need a non-standard type of ordering, which the default less-than (<) operator cannot offer to us.
To be more concrete, let's suppose for example that we need to sort the elements of a std::vector of std::string objects. (i.e. a vector<string> container) The default behavior of the std::sort would be to sort these strings alphabetically, since the less-than (<) operator of the std::string performs a lexicographic comparison. However, what if we need to sort the items of this vector in the ascending order of their size? (i.e. according to the number of their letters) In this case we will have to use a strict-weak-ordering functor or lambda to sort our data and it would be definitely a good idea to let the wizard implement these functors and lambdas for us!
In case we use the Online Generic Data Ordering Wizard to sort our std::string data according to their size, we just need to got to the wizard page, fill the thee fields of the wizard form with rather obvious values [size_sorter / std::string / size()], and then press the create button. The next step will be to utilize the code created by the wizard in conjunction with your own code, like I did in the Example #6 bellow. (As usually, by clicking the compile link, you can see exactly how the example #6 builds and runs)
Example #6: Ordering strings by size [compile]
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
typedef std::vector<std::string> string_vector;
struct size_sorter
: public std::binary_function<std::string, std::string, bool>
{
bool operator() (const std::string &left, const std::string &right) const
{
return (left.size() < right.size());
}
};
void test_functor_solution(string_vector sv)
{
std::sort(sv.begin(), sv.end(), size_sorter());
std::copy(sv.begin(), sv.end(), std::ostream_iterator<std::string>(std::cout, " "));
}
void test_lambda_solution(string_vector sv)
{
std::sort(sv.begin(), sv.end(),
[] (const std::string &left, const std::string &right) -> bool
{
return (left.size() < right.size());
}
);
std::copy(sv.begin(), sv.end(), std::ostream_iterator<std::string>(std::cout, " "));
}
int main()
{
string_vector test_data;
test_data.push_back("george");
test_data.push_back("nick");
test_data.push_back("peter");
test_functor_solution(test_data);
std::cout << std::endl;
test_lambda_solution(test_data);
return 0;
}
Wizard limitations
Like most tools, the Online Generic Data Ordering Wizard has also its limitations. Namely, the code created by this wizard is specifically designed to handle the comparison of class and struct objects and can only do that by comparing up to four of their public member variables or methods. In addition, all member variables and methods used in this comparison should be comparable via the less-than (<) operator.
Furthermore, even though we have seen that the Online Generic Data Ordering Wizard can relieve us from some cumbersome and error-prone coding, it still cannot guarantee the correct compilation and execution of the code it produces. The wizard does not perform any syntax checking on its resulting code and it certainly has no way of knowing whether its code will be compatible with the rest of our code. It all depends on the parameters we provide in the wizard form. However, by using this wizard we will most probably avoid many mistakes, which are very likely to happen when writing strict-weak-ordering functors, strict-weak-ordering lambdas or less-than (<) operator by hand.
The wizard implementation
From the implementation point of view, the Online Generic Data Ordering Wizard is just a simple PHP-5 web application. My primary design goals when creating this web application, were to make it convenient and practical in every aspect that matters. Namely, I wanted this tool to be useful, very easy to use, and to require as little as possible from its user or its administrator.
On the server-side I have just used plain and simple PHP-5, with no additional CMS [7] dependencies (like droupal, Joomla or WordPress). By having no additional dependencies than simply PHP-5, the portability and the ease of installation are maximized, while at the same time the hosting cost is expected to be as low as possible.
On the client-side the Online Generic Data Ordering Wizard only requires from its user a web-browser which can render simple HTML/CSS. There are no requirements for things like Javascript, cookies, Flash, etc. Consequently, the wizard is expected to work in any modern operating system, with any modern web-browser and chances are that it will also be able to work nicely in some old or restricted configurations and environments as well. As a proof of concept, I have even tried and succeeded to use this wizard from inside a terminal emulator, via the ELinks [8] console-based browser, like you can see in the picture bellow, although I would not recommend this usage style to most users.
Last but not least, the Online Generic Data Ordering Wizard is an open source project and all its implementation code can be found in the online-programming-utils [9] Google Code [10] project, licensed under the Apache 2.0 license [11]. Hence, you are free to modify or extend this wizard-tool in any way you wish. In case you do any of the above, please consider that by letting me know about it, you will make a fellow programmer extremely happy!
Revision History
- 1 June 2013
- Initial release
References
