More C++ Idioms/Boost mutant

Boost mutant
edit

Intent edit

Reorder the data members of a plain old data (POD) type when all members are of the same type, without physically reorganizing or copying the data items.

Also Known As edit

Motivation edit

The need of this idiom is best motivated using Boost's Bimap.[1] Boost.Bimap is a bidirectional maps library for C++. In bimap<X,Y>, values of types X and Y can both serve as keys. The implementation of such a data structure can be optimized using the boost mutant idiom.

Solution and Sample Code edit

Boost mutant idiom makes use of reinterpret_cast and depends heavily on the assumption that the memory layouts of two different structures with identical data members (types and order) are interchangeable. Although the C++ standard does not guarantee this property, virtually all the compilers satisfy it. Moreover, the mutant idiom is standard if only POD types are used.[2] The following example shows how the boost mutant idiom works.

template <class Pair>
struct Reverse
{
    typedef typename Pair::first_type  second_type;
    typedef typename Pair::second_type first_type;
    second_type second;
    first_type first;
};

template <class Pair>
Reverse<Pair> & mutate(Pair & p)
{
  return reinterpret_cast<Reverse<Pair> &>(p);
}

int main(void)
{
  std::pair<double, int> p(1.34, 5);
  std::cout << "p.first = " << p.first 
            << ", p.second = "  << p.second << std::endl
            << "mutate(p).first = " << mutate(p).first 
            << ", mutate(p).second = "  << mutate(p).second << std::endl;
}

Given a std::pair<X,Y> object of POD data members only, the layout of the Reverse<std::pair<X,Y>> is identical to that of pair's on most compilers. The Reverse template reverses the names of the data members without physically reversing the data. A helper mutate function is used to easily construct a Reverse<Pair> reference, which can be considered as a view over the original pair object. The output of the above program confirms that the reverse view can be obtained without reorganizing data:

p.first = 1.34, p.second = 5
mutate(p).first = 5, mutate(p).second = 1.34

Known Uses edit

Related Idioms edit

References edit

  1. Capeletto, Matias. "Boost.Bimap".
  2. http://beta.boost.org/doc/libs/1_43_0/libs/bimap/test/test_mutant.cpp