Bit Focus Blog

Traits in Generic Programming

Posted at 2012-01-10 12:32:17 | Updated at 2018-03-29 00:56:46

Suppose we're going to construct a container, and need combining traits at the compile time. There are some ways to make it, for example, we may use several bools
template <bool AllowDuplicate, bool SortElements, bool CheckOutOfRange>
struct just_another_container;
To use that code will become some sort of nightmare, since every parameter is a bool, if you make a mistake on the order of arguments, you could hardly discover it before the program goes mad.
Another approach is, to merge all bools to a single unsigned, like
template <unsigned Policy>
struct just_another_container;
But that is not good too, since in the first place we have to define some flags
enum {
    SORT_ELE_MASK = 2,
and then to use those flags, say, consider we add an insert interface to the container, which is concerned about whether or not allows duplicated elements in the container, the code may look like
void insert(element_type e)
    _insert<Policy & ALLOW_DUP_MASK>(e);

template <>
void _insert<0>(element_type e);

template <>
void _insert<ALLOW_DUP_MASK>(element_type e);
However unfortunately that won't compile, because C++ forbid specialize template functions (whether partial or not). So, we have to put that _insert into a template struct, like
template <unsigned AllowDuplicate>
struct insert_s
    static void insert(just_a_container& container, element_type& e);

template <>
struct insert_s<ALLOW_DUP_MASK>
    static void insert(just_a_container& container, element_type& e);
That looks really weird, and for struct insert_s, It should be granted public access to just_a_container.
Besides, in the code there would be full of bitwise-and here and there like
void another_member_function()
    element_type ele;
    /* wanna call insert function of policy = Policy */
    insert_s<Policy & ALLOW_DUP_MASK>::insert(*this, ele);
    /* ... */
    find_s<Policy & SORT_ELE_MASK>::insert(*this, ele);
    /* ... */
It requires great carefulness to use such code or the program will become out of control if any & is omitted or wrong flag is used.

But luckily, generice programming gets its own way --- multiple inheritance.
If you hates Object-Oriented programming, don't feel depressive please. This time it's not about polymorphism. It's all traits.

Ok, let's get down to the code. Change just_another_container into
template <typename Policy>
struct just_another_container;
Then define this kinds of empty structures
struct policy_base {};
struct allow_dup : public policy_base {};
struct sort_ele : public policy_base {};
struct check_out_of_range : public policy_base {};
Now we are going to combine all kinds of desired traits by multiple inheritance, like
struct my_policy : public allow_dup, public sort_ele {};
just_another_container<my_policy> my_container;
Then, change insert function signature. This time, function overloading will be our friend.
void insert(element_type e, policy_base);
void insert(element_type e, allow_dup);
According to C++ function overloading rules, a sub-type will be casted to a base type that most close to the parameter type. So if we call insert by passing an instance of my_policy, the overload void insert(element_type e, allow_dup) will be called. For example
void another_member_function()
    element_type ele;
    /* wanna call insert function of policy = my_policy */
    insert(ele, my_policy());
You don't have to worry about the efficiency though there is one more runtime argument, as the compiler will help optimize it.

In STL, each iterator (among std::vector::iterat, std::list::iterator, etc) will have an iterator_category defined, which would be one of the following
InputIterator and OutputIterator are the 2 base types, ForwardIterator inherits both of them, then follows BidirectionalIterator, which inherits ForwardIterator, and the RandomAccessIterator, a sub-class of ForwardIterator.
Some STL algorithm will be concerned about iterator_category, and use it to match the most efficient overload. For example, std::distance will

Post tags:   Generic Programming  Template  C++

Leave a comment:

Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0

. Back to Bit Focus Blog
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site