Variadic typedefs, or "Bimaps done the C++0x way"

Question

Short question: Can I typedef a variadic argument pack? I need template <typename ...T> struct Forward { typedef T... args; };.

---

Long version:

I was thinking about reimplementing the excellent boost bimap in C++0x. Recall that a bimap of two types S and T is a std::set of relations between S x and T y. The objects themselves are stored in two independent internal containers, and the relations track the associated iterators I suppose; both types can serve as keys via "left" and "right" lookup. Depending on the choice of internal containers, values may be unique or not, e.g. if the left container is a set and the right container is a multiset, then one x can map to many different ys, and right lookup gives an equal-range. Popular internal containers are set, multiset, vector and list, and maybe the unordered_* versions too.

So we need a type which accepts two containers as template parameters:

class Bimap<S, T, std::set, std::multiset>

But we must accept that the containers can take arbitrary many arguments, so we need to pass all those, too. If we just needed one set of variadic arguments, it wouldn't be a problem, since we could pass those directly. But now we need two sets of arguments, so I want to write a forwarder, to be used like so:

Bimap<int, int, std::set, std::set, Forward<std::less<int>, MyAllocator>, Forward<std::greater<int>, YourAllocator>> x;

Here's the template I came up with:

#include <set>
#include <cstdint>

template <typename ...Args>
struct Forward
{
  typedef Args... args; // Problem here!!
  static const std::size_t size = sizeof...(Args);
};

template <typename S, typename T,
          template <typename ...SArgs> class SCont,
          template <typename ...TArgs> class TCont,
          typename SForward = Forward<>, typename TForward = Forward<>>
class Bimap
{
  typedef SCont<S, typename SForward::args> left_type;
  typedef TCont<T, typename TForward::args> right_type;

  template <typename LeftIt, typename RightIt> struct Relation; // to be implemented

  typedef Relation<typename left_type::const_iterator, typename right_type::const_iterator> relation_type;

};


int main()
{
  Bimap<int, int, std::set, std::set, Forward<std::less<int>>, Forward<std::greater<int>>> x;
}

Unfortunately, in the indicated line in Forward I cannot figure out how to typedef the parameter pack! (The commented line gives a compiler error.)

[I suppose I could go for a lazy version Bimap<std::set<int, MyPred>, std::multiset<char, YourPred>> x; and extract the types via LeftCont::value_type and RightCont::value_type, but I thought it'd be nicer if I could make the key types my primary template arguments and allow defaulting to std::set containers.]

Thigpen

Answer 1

You can achieve what you want by encapsulating the variadic argument pack in a tuple and later using the following two helper template structs to forward the actual variadic arguments:

template<typename PackR, typename PackL>
struct cat;

template<typename ...R, typename ...L>
struct cat<std::tuple<R...>, std::tuple<L...>>
{
        typedef std::tuple<R..., L...> type;
};

and

template<typename Pack, template<typename ...T> class Receiver>
struct Unpack;

template<typename ...Args, template<typename ...T> class Receiver>
struct Unpack<std::tuple<Args...>, Receiver>
{
        typedef Receiver<Args...> type;
};

your code sample would look like this:

#include <set>
#include <cstdint>
#include <tuple>

template<typename PackR, typename PackL>
struct Cat;

template<typename ...R, typename ...L>
struct Cat<std::tuple<R...>, std::tuple<L...>>
{
        typedef std::tuple<R..., L...> type;
};

template<typename Pack, template<typename ...T> class Receiver>
struct Unpack;

template<typename ...Args, template<typename ...T> class Receiver>
struct Unpack<std::tuple<Args...>, Receiver>
{
        typedef Receiver<Args...> type;
};

template<typename ...Args>
struct Forward
{    
        //typedef Args... args; // Problem here!!
        typedef std::tuple<Args...> args; // Workaround

        static const std::size_t size = sizeof...(Args);
};

template<typename S, typename T, 
        template<typename ...SArgs> class SCont, 
        template<typename ...TArgs> class TCont, 
        typename SForward = Forward<> ,
        typename TForward = Forward<>>
class Bimap
{
        //typedef SCont<S, typename SForward::args> left_type;
        //typedef TCont<T, typename TForward::args> right_type;
        typedef typename Unpack<typename Cat<std::tuple<S>, typename SForward::args>::type, SCont>::type left_type; //Workaround
        typedef typename Unpack<typename Cat<std::tuple<T>, typename TForward::args>::type, TCont>::type right_type; //Workaround

        template<typename LeftIt, typename RightIt> struct Relation; // to be implemented

        typedef Relation<typename left_type::const_iterator, typename right_type::const_iterator> relation_type;

};

int main()
{
    Bimap<int, int, std::set, std::set, Forward<std::less<int>> , Forward<std::greater<int>>> x;
}

which compiles just fine under gcc 4.6.0

Markup

Wow, excellent! I didn't realize you can have variadic arguments followed by other arguments in a template. Very nice! – Thigpen

Answer 2

You can typedef a tuple. However, I wouldn't know how to then get the types back out again.

The easiest thing to do would be to just accept two full types.

Nuremberg

Yeah, that'd be easy, but somehow not very elegant. For instance, I'd like to be able to give defaults like Bimap<int, int>. In the laziest case I'd just use Boost.Bimap ;-) – Thigpen