|
The power of typelists applied to multiple-key sorts.
July 01, 2003
URL:http://www.drdobbs.com/using-a-typelist-to-create-a-flexible-co/184401667
This paper describes the class order_by that performs a compound sort on a container of objects according to one or more attributes. To provide flexibility, I'll use a typelist to represent the desired sort order. This technique allows the user to supply multiple comparison-function objects to specify the compound sort order while retaining compile-time type checking.
SELECT * FROM PERSON ORDER BY ID SELECT * FROM PERSON ORDER BY LAST, FIRST, ID SELECT * FROM PERSON ORDER BY STATE, ZIP, LAST, FIRST, IDThis last example retrieves the data such that it is sorted by state, then each record with the same state is sorted by zip, each with the same state and zip is sorted by last name, and so on. This is known as a "compound sort."
Retrieving the data set presorted from the database works fine in many cases, but not when the same data needs to be resorted multiple times. In the case where many clients need to receive the same data set in multiple unique formats, it becomes necessary to perform the same query multiple times just to get the various sort orders.
The class order_by provides this functionality for containers of objects where the concept of "less than" applies to multiple attributes. For example, a person object exists that contains the data members first, last, middle, state, zip, and id. A set of less_than function objects also exists, each taking two arguments of type person const & and each examining one particular data attribute. (Refer to Listing 1 for a contrived example.)
The order_by constructor can receive two random access iterators into a container of person objects and sort the collection in any desired order (see examples above).Using this class, a data set can be retrieved in only one call to the database and then presented in many different ways.
An alternate approach to using the order_by object is to use a set of function objects that perform the less_than operation on multiple attributes at once. For example, each of the following function objects may be written for a class with three attributes: first, last, id.
less_first less_first_last less_first_last_id
less_last less_last_first less_first_id_last
less_ssn less_first_id less_last_first_id
less_id_first less_last_id_first
less_last_id less_id_first_last
less_id_last less_id_last_first
Any of these compound-comparison function objects can be passed as a third argument
to the standard sort function, resulting in the desired order. (Listing
2 shows an implementation of struct less_last_first_id and its usage.)
However, there are two problems with this approach:
One obvious motivation for this rule is that the comparison function objects can take advantage of a friend declaration to save at least two calls to public member access functions (see the text box titled "Friendship"). But more important than the efficiency issue is the presentation of a single coherent interface to the class. A function that compares two objects of a class by one specific attribute must model a unique concept. By not placing the comparison function objects in the same translation unit, you are allowing a user to define their own varieties and possibly cause the class to behave in unpredictable ways.
Since the comparison function objects must reside in the same header as the class definition, any modification to this file causes all translation units that depend on this class to be recompiled and retested. It is unlikely that the designer of the class is going to know all of the sorting permutations that future users are ever going to require, and it is equally unrealistic for the class designer to include all possible compound-sorting permutations in the file. Therefore, the project using standard sort with compound function objects (Listing 2) has established a fragile dependency by placing a component that is likely to change above more stable components in the dependency graph. [2]
The order_by object allows a class with multiple comparable attributes to define only the comparison function objects that correspond to these attributes. This decouples the class from the sorting requirements of future users.
A typelist is a template struct containing two typedefs: Head and Tail (Listing 3). A typelist does not have any data members or member functions. Its only purpose is to provide the alternate type names for the two template parameters. Since a typelist is itself a type, the Tail type of a typelist can be another typelist (Figures 1a, 1b, and 1c). In this way, a typelist is chained together like a compile-time singly linked list of types. An empty struct NullType is used to indicate the end of a list.
The class order_by provides a mechanism to apply the comparison function objects in a typelist to subsequent subsets of the data to achieve the desired compound sort. (Refer to the order_by.h in Listing 4.)
The order_by object gets the type of the container holding the objects and the typelist of comparison-function objects as template parameters. The length of the typelist is determined using the Typelist::Length [3] template construct and is stored in the enum n. Since this occurs at compile time, n can be used in turn as a template parameter for the next instantiation of class order_by. The type of the comparison function at the current offset in the typelist is typedef'd to comp_type using the Typelist::TypeAt [3] template construct. This is used to call the standard sort function on the range specified by the constructor arguments. The comp_type is also used with the standard equal_range function to determine the subsets of the container (differentiated by the attribute associated with comp_type).
(Again in English.) The order_by function first sorts the entire container using the first comparison function object. The code then enters a while loop where the container is broken up into subsets of equal items based on this comparison type. A new order_by object is created receiving the subset of items and the index of the next function object. This order_by object knows nothing of the previous object and thinks that it has received the entire container and the first comparison function object. This occurs in classic "recursive style" until there are no more function objects by which to sort, and all of the equal ranges in the outermost container are sorted.
The instantiation of the subsequent order_by objects uses the expression ((i+1==n)?(0xFFFF):(i+1)) as the third integral template parameter. This indicates that the next typelist index is to be used unless it would be past the end of the typelist, in which case, a marker value is substituted. This is possible because i and n are compile-time constants and operator ?:, unlike an if-then-else statement, is also evaluated at compile time. The marker integer is used as the partial specialization of the order_by class template to end the template recursion.
I refer to the cascading function calls as "recursive style" out of convenience only. Although one function calling itself looks like classic recursion, this case is different because it is a constructor. The only true recursion that is taking place is in the compile-time recursive template instantiation of the various versions of the order_by class (one distinct order_by object for each item in the Typelist). The calls appear to be recursive in the code, but in reality, they are simply calls made between the template instantiations of the order_by objects.
The effect of instantiating an order_by object with a typelist containing four types is to create four order_by objects that call each other's constructors in the order determined by the typelist.
If a separate typelist needs to be created for each compound-sorting permutation, why bother using a typelist solution at all? The answer is in the dependency relationships. The code that defines the various typelists may need to be modified each time a new compound sort is required by a user, but this code does not have to reside in the file containing the comparison function objects and class definition. This code can be isolated from the other modules, and, therefore, the source of instability is isolated from the highly depended-upon components.
Figure 2a shows the dependency graph of a project using a sort_logic component. The person.h in this project contains multiple-compound comparison function objects and uses the standard sort function to perform the sorting (as shown in Listing 2). The sort_logic component collects the runtime information and calls the sort function, depending on which type of sorting is required. (This may occur by reading a list of client options from a database, getting a user's preferences from a cookie, and so on.) The person object is fairly ubiquitous and many components in the project depend on it. In this case, when a user of the sort_logic component needs to account for a new type of sorting, the person.h file must be modified. This necessitates the recompilation and retesting of all dependent components (A, B, and C).
Figure 2b shows the dependency graph of a project that uses the order_by object for compound sorting. A new component person_sel has been added that contains the known sorting requirements (Please refer to Listing 5). In each case block, the construction of object o sorts the container according to the Typelist provided as its second template parameter. The sort_logic component works as it did before: collecting the runtime information and calling the proper sort. However, in this case, the person component only contains one comparison-function object per attribute and has no knowledge of any of the sorting requirements. When a new compound sort is needed, only the person_sel.h file is modified and all of the other components that have included the person.h do not know or care.
In this way, the characteristic of the project that is most likely to change is isolated from the component that needs to be the most stable.
The use of typelist allows for the best of both worlds: the flexibility of using unknown numbers of unknown types and the desirability of compile-time type checking.
[2] R.C. Martin, "Large-scale Stability," C++ Report, 9(2), pp. 54-60, February 1997.
[3] Andrei Alexandrescu. Modern C++ Design. (Addison-Wesley, 2001).
Figure 1a: Typelist containing one type
Figure 1b: Typelist containing two types
Figure 1c: Typelist containing three types
Figure 2a: Project using compound-comparison function objects
Figure 2b: Project using class order_by
Listing 1: Class person with comparison function objects
//person.h
#ifndef __PERSON_H__
#define __PERSON_H__
#include <string>
class person
{
public:
//constructors and access functions
private:
std::string first_;
std::string last_;
unsigned long id_;
//...
friend struct less_first;
friend struct less_last;
friend struct less_id;
//...
};
struct less_first
{
bool operator()(person const &lh, person const &rh) const
{return lh.first_ < rh.first_;}
};
struct less_last
{
bool operator()(person const &lh, person const &rh) const
{return lh.last_ < rh.last_;}
};
struct less_id
{
bool operator()(person const &lh, person const &rh) const
{return lh.id_ < rh.id_;}
};
//...
#endif
Listing 2: Definition and usage of a compound-comparison function object
//in person.h
struct less_last_first_id
{
bool operator()(person const &lh, person const &rh) const
{return ((lh.last_ < rh.last_)?(true):
((lh.last_ > rh.last_)?(false):
((lh.first_ < rh.first_)?(true):
((lh.first_ > rh.first_)?(false):
((lh.id_ < rh.id_)?(true):
((lh.id_ > rh.id_)?(false):
(false)))))));}
};
//usage
std::sort(people.begin(), people.end(), less_last_first_id());
Listing 3: Typelist definition
template<class T, class U>
struct Typelist
{
typedef T Head;
typedef U Tail;
};
Listing 4: Class order_by implementation
//order_by.h
#ifndef __ORDER_BY_H__
#define __ORDER_BY_H__
#include <algorithm>
#include <iterator>
#include <Typelist.h>
template <typename CONT, typename TLIST, int i = 0>
class order_by
{
private:
typedef typename CONT::iterator iter;
enum{n = Loki::TL::Length<TLIST>::value};
typedef typename Loki::TL::TypeAt<TLIST, i>::Result
comp_type;
public:
order_by(iter begin, iter end)
{
std::sort(begin, end, comp_type());
pair<iter, iter> range;
while(true)
{
range = std::equal_range(begin, end, *begin, comp_type());
if(range.first == end)
return;
order_by<CONT, TLIST, ((i+1==n)?(0xFFFF):(i+1))>
o(range.first, range.second);
begin = range.second;
}
}
};
//specialized object to end template recursion
template <typename CONT, typename TLIST>
class order_by<CONT, TLIST, 0xFFFF>
{
private:
typedef typename CONT::iterator iter;
public:
order_by(iter begin, iter end){}
};
#endif
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.