When did you read “The C++ programming language” by Bjarne Stroustrup? In chapter 22 a situation is discussed where one may want to avoid extra temporaries, copying and loops (22.4.7). So now I want to present a little more complicated version of such situation.
Consider we have some class, which has an operator+ member, which takes as an argument another instance of the same class, thus we can add as many terms as we want. For built-in types, or some simple user-defined types, this kind of expressions will create temporaries for each pair of terms, i.e. we can imagine the expression a1 + a2 + a3 + a4 + … as ((…(a1 + a2) + a3) + a4) + …, so for each pair of parentheses a temporary will be created during the evaluation of the whole expression. For complex types, whose operator+ consists of many calls of other functions, maybe loops, the evaluation of this expression will cost really much. And both the number of temporaries and the time taken depends on the number of terms added. So in current article I want to describe a technique this problem can be solved with.
The main type (class) I will consider throughout the article is MySet, which is a template class and represents a set of elements of template type. The ‘+’ operator should unite given sets.
template <typename T>
class MySet
{
public:
MySet() {}
MySet(const T& elem)
{
m_elements.insert(elem);
}
template <typename Iterator>
MySet(const Iterator& begin,
const Iterator& end)
{
m_elements.insert(begin, end);
}
void addElement(const T& elem)
{
m_elements.insert(elem);
}
void removeElement(const T& elem)
{
m_elements.erase(elem);
}
private:
std::set<T> m_elements;
};
To be able to add objects of type MySet<T> we need the operator+ to be defined:
template <typename T>
const MySet<T> operator+(const MySet<T>& first, const MySet<T>& second);
Now we’ve got the abovementioned problem which we need to avoid. We can create an auxiliary class which will just keep the references as described in “The C++ programming language” - 22.4.7. Whoever is not familiar with the Stroustrup’s suggestion I will tell briefly. A class is created which has two reference members, which refer to two terms of an expression, and has a simple constructor which just initializes the references:
template <class T>
struct Temp
{
const MySet<T>& t1;
const MySet<T>& t2;
Temp(const MySet<T>& arg1, const MySet<T>& arg2)
: t1(arg1), t2(arg2)
{ // nothing to do here }
};
But how do we know how many terms will contain the final expression. We do not, indeed. So we need a way to generalize the number of terms. For that purpose we can consider the sum of terms as a sum of all the terms but the rightmost and a separate rightmost set, so any expression contains only two terms in this comprehension. So in our case the reference keeper should be a template either:
template <typename LeftTerm, typename RightTerm>
struct TempUnion
{
const LeftTerm& l_;
const RightTerm& r_;
TempUnion(const LeftTerm& left,
const RightTerm& right)
: l_(left), r_(right)
{
}
};
Now we can represent the sum of two MySet’s as TempUnion<MySet<T>, MySet<T> >, sum of three terms as TempUnion<TempUnion<MySet<T>, MySet<T> >, MySet<T> >, and so on. As to operator+ for MySet’s, it should just construct a TempUnion instance and return. But for this we need a common interface/approach to both MySet and TempUnion of any “depth”. Here we take advantage of CRTP pattern to support static (compile-time) polymorphism:
template <typename T>
struct Wrapper
{
const T& get() const
{
return static_cast<const T&>(*this);
}
};
We should not forget to inherit both MySet and TempUnion from Wrapper with the derived type as template argument:
template <typename T>
class MySet : public Wrapper<MySet<T> >
{ ...
template <typename LeftTerm, typename RightTerm>
struct TempUnion : public Wrapper<TempUnion<LeftTerm, RightTerm> >
{ ...
MySet should also be able to be constructed from the TempUnion, so that the outermost TempUnion is converted to MySet when assigned to the latter. Thus, we need a constructor, preliminary of this prototype:
template <typename LeftTerm, typename RightTerm>
MySet(const TempUnion<LeftTerm, RightTerm>& un);
Seems everything is already done, but… how do we know how many sets do we have to unite, when all we have got is one object of TempUnion<…> type? So we need a mechanism to count the sets and also find out references to real objects to be able to collect their elements (m_elements). Another helper class is meant to work this out:
template <typename LeftTerm, typename RightTerm>
struct SetOfSets<TempUnion<LeftTerm, RightTerm> >
{
// recursive template instantiantion
static const int size = 1 + SetOfSets<LeftTerm>::size;
};
We know that the right term is always a single set, so we can calculate the number of sets just adding 1 for the rightmost set and using recursive instantiation for the rest of the sum as a LeftTerm. We need a terminating condition, and it is easy to guess - for a single set the number should be 1:
template <typename Term>
struct SetOfSets
{
static const int size = 1;
};
Actually this is more general (not specialized template) than the previous specialization, so this should come before. Now we can calculate the number of sets in an expression, in our terms, in a TempUnion<…> object. We can collect the pointers of sets using the same recursive instantiation approach: (using the same struct)
template <typename Term>
struct SetOfSets
{
static const int size = 1;
template <typename T>
inline static void getSets(const MySet<T>** sets, const Term& t)
{
*sets = static_cast<const MySet<T>*>(&t);
}
};
template <typename LeftTerm, typename RightTerm>
struct SetOfSets<TempUnion<LeftTerm, RightTerm> >
{
static const int size = 1 + SetOfSets<LeftTerm>::size;
template <typename T>
inline static void getSets(const MySet<T>** sets,
const TempUnion<LeftTerm, RightTerm>& un)
{
SetOfSets<LeftTerm>::getSets(sets, un.l_);
*(sets + size - 1) = static_cast<const MySet<T>*>(&un.r_);
}
};
Almost done! We have to write the operator= and the constructor for MySet, taking a TempUnion. So the final code for all this stuff follows:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
template <typename Term>
struct SetOfSets;
template <typename T>
struct Wrapper
{
const T& get() const
{
return static_cast<const T&>(*this);
}
};
template <typename LeftTerm, typename RightTerm>
struct TempUnion;
template <typename T>
class MySet : public Wrapper<MySet<T> >
{
public:
MySet() {}
MySet(const T& elem)
{
m_elements.insert(elem);
}
template <typename Iterator>
MySet(const Iterator& begin,
const Iterator& end)
{
m_elements.insert(begin, end);
}
void addElement(const T& elem)
{
m_elements.insert(elem);
}
void removeElement(const T& elem)
{
m_elements.erase(elem);
}
template <typename LeftTerm, typename RightTerm>
MySet(const TempUnion<LeftTerm, RightTerm>& un)
{
operator=(un);
}
template <typename LeftTerm, typename RightTerm>
const MySet& operator=(const TempUnion<LeftTerm, RightTerm>& un);
void dump()
{
std::copy(m_elements.begin(), m_elements.end(),
std::ostream_iterator<T>(std::cout, " "));
std::cout << std::endl;
}
private:
std::set<T> m_elements;
};
template <typename T>
template<typename LeftTerm, typename RightTerm>
const MySet<T>& MySet<T>::operator=(const TempUnion<LeftTerm, RightTerm>& un)
{
const int count = SetOfSets<TempUnion<LeftTerm, RightTerm> >::size;
const MySet<T>* sets[count];
SetOfSets<TempUnion<LeftTerm, RightTerm> >::getSets(sets, un);
m_elements.clear();
for (int i = 0; i < count; ++i)
{
const std::set<T>& elems = sets[i]->m_elements;
m_elements.insert(elems.begin(), elems.end());
}
return *this;
}
template <typename LeftTerm, typename RightTerm>
struct TempUnion : public Wrapper<TempUnion<LeftTerm, RightTerm> >
{
const LeftTerm& l_;
const RightTerm& r_;
TempUnion(const LeftTerm& left,
const RightTerm& right)
: l_(left), r_(right)
{
}
};
template <typename LeftTerm, typename RightTerm>
inline const TempUnion<LeftTerm, RightTerm>
operator+(const Wrapper<LeftTerm>& s1, const Wrapper<RightTerm>& s2)
{
return TempUnion<LeftTerm, RightTerm>(s1.get(), s2.get());
}
template <typename Term>
struct SetOfSets
{
static const int size = 1;
template <typename T>
inline static void getSets(const MySet<T>** sets, const Term& t)
{
*sets = static_cast<const MySet<T>*>(&t);
}
};
template <typename LeftTerm, typename RightTerm>
struct SetOfSets<TempUnion<LeftTerm, RightTerm> >
{
static const int size = 1 + SetOfSets<LeftTerm>::size;
template <typename T>
inline static void getSets(const MySet<T>** sets,
const TempUnion<LeftTerm, RightTerm>& un)
{
SetOfSets<LeftTerm>::getSets(sets, un.l_);
*(sets + size - 1) = static_cast<const MySet<T>*>(&un.r_);
}
};
int main()
{
MySet<int> s1(1), s2(2), s3(3), s4(4), s5(5), s6(6), s7(7), s8;
s8 = s1 + s2 + s3 + s4 + s5 + s6 + s7;
s8.dump();
std::cout << "the end" << std::endl;
return 0;
}
Thus, s8 is constructed from an object of type TempUnion<TempUnion<…4 more times…<MySet<T>, MySet<T> >, MySet<T> > and the latter is “constructed” at compile time. Here we did not get rid of loops, as we need to run through all elements of all sets, which, generally, are of different sizes.
I hope this post will be useful for some people, I myself admired a lot when learned this kind of stuff first time. Please feel free to comment or ask questions. Thanks for your time.
