C++ Traits
‘C++ Traits’ is an idiom that allows a great level of abstraction at compile time which is normally possible only by a combination of inheritance and composition. It allows an algorithm to change its behavior depending on the object’s traits, i.e., functions and member variables exposed by that object.
What C++ Traits are not?
There is no magic here, only metaprogramming using templates. The compiler doesn’t have any functionality to automatically find out properties of an object and automatically link to the corresponding algorithm. The programmer (still) needs to do that. Traits are an idiom or a way by which you can implement it all so it happens at compile time.
What is Traits idiom?
1. What is Traits
Traits are a bunch of classes that have static public member variables to store information about a different class (O). The consumer (C) of the different class O queries these traits do modify its behavior. Since traits class store static public member variables, they are often implemented as structs. When a variant of O is written by a programmer, the onus of creating the corresponding trait class lies on the programmer.
Traits is written as a templated struct that takes the object type but doesn’t use it. The programmer then writes a specialization of this templated struct for class O and initializes the static public member variables as per the requirement to specify the new behavior.
2. How is Traits class implemented
An algorithm needs to make decisions based on the object properties, so all information about these properties is stored in the traits class. To hide this detail from the user of the algorithm, an intermediatory templated public function (or class) is created that takes object type and then calls a “helper” templated function passing it the object type as well as all of the required traits.
This helper function contains the actual code or implementation of the algorithm. Specialized versions of the helper functions are implemented for each trait that require a change in the algorithm.
3. How Traits work
The client remains oblivious to the traits class. It passes the object of type O to the templated public function/class C, then calls whatever function it wants to call on it. C, in turn, has code to check the traits of O and call appropriate helper function. This call to helper function must be outside of C because a class template cannot have specialized function unless the class itself is specialized.
Overview of C++Traits idiom
Above diagram summarizes the C++ implementation. Now let’s try our hands on some sample code.
Implementing Binary Search Tree using C++ Traits
We will try to implement a Binary Search Tree which can use different types of Nodes. As we know, we can either calculate the depth of a tree every time we need it or store it in the node itself. Similarly, a node can also point to its parent, or not. For simplicity, let’s implement only the first functionality.
We start by defining this as a trait:
|
1 2 3 4 |
template struct NodeTraits { static const bool isStoringDepth = false; }; |
The default is false, but it could very well be true. Remember that specializations will be opposite of default. NOTE: You can also choose to skip specifying the default and move it all in specializations. The downside is that the default trait class won’t show you the complete interface.
Now lets define a default node. Since its trait (isStoringDepth) matches with the default value (false), we may skip writing specialization for it.
|
1 2 3 4 5 6 7 |
class SimpleNode { public: SimpleNode() : left(nullptr), right(nullptr), value(0) {} SimpleNode *left; SimpleNode *right; int value; }; |
Now we will define a new node that internally stores depth. Since it is a departure from the default, we will write a specialization of traits class as well.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class NodeWithDepth { public: NodeWithDepth() : left(nullptr), right(nullptr), value(0), depth(1) {} NodeWithDepth *next; NodeWithDepth *prev; int value; size_t depth; }; // Specialized traits template struct NodeTraits { static const bool isStoringDepth = true; }; |
Now that our node classes and their traits have been defined, lets write a BST class that uses them:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
template class BST { public: BST() : head(nullptr) {} void Add(const int _value) { // Call private function Add<NodeTraits::isStoringDepth>(&head, _value); } private: Node *head; template void Add(Node **, const int); // We will implement this later }; |
The behavior of Add() function depends on whether we want to store depth or not. If the node doesn’t store depth, Add() will only add a new node. If node stores depth, Add() will need to update the depth field of all the parent nodes leading up to the newly inserted one. For this reason, we have templated the Add() function. Note that the template takes a trait, not a Node. This allows us to write new Node classes without changing the BST class itself, and this is where the need for traits idiom is fully justified.
Now we will write two helper functions implementing each of these algorithms:
|
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 |
// Default implementation template struct BSTHelper { static void Add(Node **_head, int _value) { if (*_head == nullptr) { auto *node = new Node(); node->value = _value; *_head = node; } else { if ((*_head)->value < _value) { BSTHelper<Node, isStoringDepth>::Add(&((*_head)->right), _value); } else { BSTHelper<Node, isStoringDepth>::Add(&((*_head)->left), _value); } } } }; // Specialized implementation when isStoringDepth is true template struct BSTHelper<Node, true> { static void Add(Node **_head, int _value) { if (*_head == nullptr) { auto *node = new Node(); node->value = _value; *_head = node; } else { if ((*_head)->value < _value) { BSTHelper<Node, isStoringDepth>::Add(&((*_head)->right), _value); (*_head)->depth = (*_head)->right->depth + 1; } else { BSTHelper<Node, isStoringDepth>::Add(&((*_head)->left), _value); (*_head)->depth = (*_head)->left->depth + 1; } } } }; |
NOTE: The helper functions are implemented inside a templated class BSTHelper. This is just to keep the global namespace clean.
Now we can use these helper functions to implement the private Add() function of BST class:
|
1 2 3 4 5 |
template template void BST::Add(Node **_head, int _value) { BSTHelper<Node, isStoringDepth>::Add(_head, _value); } |
The client is not bothered by all the complexity hidden behind templates and multiple structs. The use is simple:
|
1 2 3 4 |
BST bst1; bst1.Add(42); BST bst2; bst2.Add(42); |
Tomorrow the client can implement a new node class, define its traits and BST code wouldn’t need to change even though it is all linked together at compile time. No need for virtual tables and no need to create pointers.
References:
- An introduction to C++ Traits, Thaddaeus Frogley
- C++: Type Traits [PDF], Ben Artin
- A sample implementation of Binary Search Tree using C++ Traits
