[C++] Tuples From Scratch

Find this example here on compiler explorer.

In my last article I started with typelists and what they are. In this one we'll continue with tuples. We'll create a tuple from scratch and demonstrate the basic idea of it.

In general, the term "tuple" is an ordered list or sequence of elements. And this is exactly what they are in C++. The basic usage with std::tuple is like this:

std::tuple<int, double, std::string> foo(99, 3.14, "hello tuple"); 

And this is just a list which holds an int, a double and a std::string without dedicated names. You can access the values by their indices and a get function, swap them, etc.

But first things first and start creating our tuple class. We'll use namespace cwt to avoid redundancy with the standard library.

Note: The implementation of std::tuple is more complex with this one. This is just a demonstartion to understand the idea behind tuples.

cwt::tuple

With typelist we used to access the types by Head and the rest by Tail... and the same approach we're using with tuples.

// primary template
template<typename... Types>
class tuple;

// template class with Head and Tail
template<typename Head, typename... Tail>
class tuple<Head, Tail...>
{
private:
    // member declaration
    Head m_head;
    tuple<Tail...> m_tail;
public:
    // constructors to create tuples with values
    tuple() = default;
    tuple(const Head& head, const Tail&... tail) : m_head(head), m_tail(tail...) {}
    tuple(const Head& head, const tuple<Tail...>& tail) : m_head(head), m_tail(tail) {}

    // getters and setters for their members
    Head& get_head() {return m_head;}
    const Head& get_head() const {return m_head;}
    tuple<Tail...>& get_tail() {return m_tail;}
    const tuple<Tail...>& get_tail() const {return m_tail;}
};

// an empty tuple
template<>
class tuple<> {};

So this means we hold the first element as Head and then we hold the remaining elements in another tuple<Tail...> until no more elements left.

If we now compare this class with the foo from above, we technically would have something which holds three values and has getters and setters to it. But a tuple should be generic and variable in it's size. Therefore we store them just like a typelist with a Head and their Tail.... But we need something to access each member specifically.

Get A Tuple-Value By Index

In the standard library the get function is not a class method, but in the boost::tuple I think it is. I honestly don't know the reason, but lets create a regular get function.

Since we don't have specific names for the members, aside from Head and Tail... we need to iterate through all.

// tuple_get with static apply function
// 1. the template parameter represents the index we want
template<unsigned N>
struct tuple_get
{
    template<typename Head, typename... Tail>
    static auto apply(const tuple<Head, Tail...>& t)
    {
        // 2. we call recursively apply where we leave out Head
        return tuple_get<N-1>::apply(t.get_tail());
    }
};

// 3. until we reach 0 where we access the head
template<>
struct tuple_get<0>
{
    template<typename Head, typename... Tail>
    static const Head& apply(const tuple<Head, Tail...>& t)
    {
        return t.get_head();
    }
};

// 4. the getter which we'll call
// "Types" will be deduced by the compiler since we pass tuple<Types...> as function argument
template<unsigned N, typename... Types>
auto get(const tuple<Types...>& t) 
{
    return tuple_get<N>::apply(t);
}

// ... 

// 5. usage could be like this:
int main() 
{
    using namespace cwt;
    tuple<int, double, std::string> t(99, 2.45, "hello tuple!");
    
    std::cout << get<0>(t) << '\n'; // prints 99
    std::cout << get<1>(t) << '\n'; // prints 2.45
    std::cout << get<2>(t) << '\n'; // "hello tuple!"
}

Iterating Through Tuples

Let's iterate through our tuple and to demonstrate this we'll create a simple print function. Note, there is an optional is_first which is by default true and by all recursive calls then false. With this we can identify the first element and print a beginning "tuples :".

// 1. provide print_tuple for an empty tuple or after the last element
void print_tuple(std::ostream& os, const tuple<>&, bool is_first = true)
{
    os << (is_first ? "tuple: " : " done"); 
}

// 2. print_tuple for tuples with elements
template<typename Head, typename... Tail>
void print_tuple(std::ostream& os, const tuple<Head, Tail...>& t, bool is_first = true)
{
    os << (is_first ? "tuple: " : " "); 
    // 3. print head
    os << t.get_head();
    // 4. call print_tuple another time and leave out head
    print_tuple(os, t.get_tail(), false);
}

// 5. overide << operator 
template<typename... Types>
std::ostream& operator<< (std::ostream& os, const tuple<Types...>& t)
{
    print_tuple(os, t);
    return os;
}

// ... 

// 6. example usage:
int main ()
{
    using namespace cwt;
    tuple<int, double, std::string> t(99, 2.45, "hello tuple!");
    std::cout << t << '\n';
}

push_front, pop_front and push_back

The basic idea to implement push_front, pop_front and push_back comes close to the implementation for typelists. For push_front we had these class templates and the according alias:

namespace details {
    // class template for pop front
    template<typename List>
    struct pop_front;

    // partial specialization for pop front
    template<typename Head, typename... Tail>
    struct pop_front<typelist<Head, Tail...>>
    {
        using Type = typelist<Tail...>; // we create a new typelist without Head
    };
}
// pop_front_t alias to access the type of pop_front
template<typename List>
using pop_front_t = typename details::pop_front<List>::Type;

And now we partial specialize the class templates for tuples:

namespace details {
    // partial specialization for accessing front
    template<typename Head, typename... Tail>
    struct front<tuple<Head, Tail...>>
    {
        using Type = Head;
    };

    // partial specialization for pop_front
    template<typename Head, typename... Tail>
    struct pop_front<tuple<Head, Tail...>>
    {
        // here we are creating a new tuple where Head is left out
        using Type = tuple<Tail...>;
    }; 

    // partial specialization for push_front 
    template<typename... Types, typename Element>
    struct push_front<tuple<Types...>, Element>
    {
        // here we are creating a new tuple where Head is the new added Element
        using Type = tuple<Element, Types...>;
    };

    // partial specialization for push_back 
    template<typename... Types, typename Element>
    struct push_back<tuple<Types...>, Element>
    {
        // here we are creating a new tuple where Head is the new added Element
        using Type = tuple<Types..., Element>;
    };
}

And with the partial specialization we can now implement our functions which we can use to modify tuples:

// pushing new value V to the front 
template<typename... Types, typename V>
// returning push_front_t, the alias for the just created push_front specialization
push_front_t<tuple<Types...>, V> 
push_front(const tuple<Types...>& t, const V& value)
{
    return push_front_t<tuple<Types...>, V>(value, t);
}

// pop front from tuple
template<typename... Types>
pop_front_t<tuple<Types...>> // same as with push_front
pop_front(const tuple<Types...>& t)
{
    return t.get_tail();
}

// push back V to an empty tuple
template<typename V>
// push_back for empty tuples where we have only V inside the tuple
tuple<V> push_back(const tuple<>&, const V& value)
{
    return tuple<V>(value);
}

// push back V to a tuple recursively
template<typename Head, typename... Tail, typename V>
// push_back for tuples where we create a new tuple with trailing new value V
tuple<Head, Tail..., V>
push_back(const tuple<Head, Tail...>& t, const V& value)
{
    return tuple<Head, Tail..., V>(t.get_head(), push_back(t.get_tail(), value));
}

Finally, let's use this functions:

int main ()
{
    using namespace cwt;
    tuple<int, double, std::string> t(99, 2.45, "hello tuple!");

    auto t1 = pop_front(t);
    std::cout << t1 << '\n'; // tuple: 2.45 hello tuple! done

    auto t2 = push_front(t, std::string("a beginning string"));
    std::cout << t2 << '\n'; // tuple: a beginning string 99 2.45 hello tuple! done

    auto t3 = push_back(t, std::string("a trailing string"));
    std::cout << t3 << '\n'; // tuple: 99 2.45 hello tuple! a trailing string done

    // or with an dedicated alias
    using AnotherTuple = push_back_t<decltype(t), bool>;
    AnotherTuple t4(get<0>(t), get<1>(t), get<2>(t), true);
    std::cout << t4 << '\n'; // tuple: 99 2.45 hello tuple! 1 done

    return 0;
}

Conclusion

I added this example to the typelist example, here on compiler explorer.

With breaking down tuples I understood tuples way better and in the next article I will start to implement Lua bindings so we can access Lua variables in an easy way.

So far, that's it for now.

Best Thomas