STL-tuple源码阅读

2022-07-13 约 4557 字预计阅读 10 分钟

std::tuple是C++11开始支持的一个编译期确定长度的, 可支持任意参数类型的容器, 相当于是std::pair的扩展, 平常只使用过它, 却没有了解其实现原理.

Class template std::tuple is a fixed-size collection of heterogeneous values. It is a generalization of std::pair.

TinyTuple

我们先来实现一个简易版的std::tuple - TinyTuple, 支持任意参数类型和get<N>方法(先不考虑get<Type>).

遇到的第一个问题是, 如何将任意数量的, 不同参数类型的值打包起来? 一种想法是, 用一块动态内存来存, 每输入一个参数var, 动态内存就扩大sizeof(var), 然后记下当前位置. 在获取的时候, 根据N就能确定内存的位置, 不过这时候用户还需要输入数据类型才能正确获取值, get接口可能就变成了get<N, Type>, 相当于是一个array any了. 能不能省略Type输入呢? 参考我们上一篇STL-any源码阅读, 是不是用一个类似AnyData的模板类来保存数据类型? 可能不太好使, 因为get方法不带type类型的话, AnyData似乎也束手无策(对应的问题是, 返回值如何统一?).

std::tuple是借助"继承可变参模板类"来实现的, 看看简化版的TinyTuple如何实现:

定义如下:

1
2
template <typename ...Tps>
class TinyTuple;

现在"偏特化"模板, 提取第一个参数的类型, 并以此递归下去:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
template <typename Tp, typename ...Tps>
class TinyTuple<Tp, Tps...> : public TinyTuple<Tps...>
{
public:
    TinyTuple(const Tp& val, Tps&& ...params) : TinyTuple<Tps...>(std::forward<Tps>(params)...)
    {
        value = val;
    }

    Tp get_value() const
    {
        return value;
    }
private:
    Tp value;
};

注意到构造函数TinyTuple(Tp && val, Tps && ...params) : TinyTuple<Tps...>(std::forward<Tps>(params)...)的原地构造是递归的, 在函数体内部才赋值当前值, 因此TinyTuple参数的初始化(复制)顺序是从右往左的.

参数为空就是递归的终止条件:

1
2
3
4
template <>
class TinyTuple <>
{
};

对于一个实例TinyTuple<Type1, Type2, ..., TypeN> tuple(var1, var2, ..., varN)可以得到其内存排列如下:

https://bu.dusays.com/2022/10/23/635554d29ba1f.png — TinyTuple内存排列

以上, 我们将TinyTuple的值和类型保存了下来, 如何获取值呢?

注意到, 我们实例化的TinyTuple对象, 实际上是一个子类. 如下:

1
TinyTuple<Type1, Type2, ..., TypeN> tuple(var1, var2, ..., varN);

其父类类型是:

1
2
3
4
TinyTuple<Type2, ..., TypeN>
TinyTuple<..., TypeN>
...
TinyTuple<TypeN>

因此, 可以向上转换成对应的父类, 该父类的value成员就是我们需要获取的值. 那么可以定义如下接口:

1
2
3
4
5
6
template<size_t N, typename ...Tps>
auto get(const TinyTuple<Tps...> &ttuple)
{
    using tuple_t = Elements<N, Tps...>::tuple_t;
    return static_cast<const tuple_t &>(ttuple).get_value();
}

通过Elements<N, Tps...>可以获取第N阶父类的类型. 然后将tuple转换成对应父类类型访问value即可.

Elements的实现方法类似TinyTuple, 不过是通过N递归来获取第N阶父类类型:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
template <size_t N, typename ...Tps>
struct Elements;

template <size_t N>
struct Elements<N> {
    static_assert(N > 0, "Index overflow");
};

template <size_t N, typename Tp, typename ...Tps>
struct Elements<N, Tp, Tps...> : public Elements <N - 1, Tps...>{
};

template <typename Tp, typename ...Tps>
struct Elements<0, Tp, Tps...>
{
    using tuple_t = TinyTuple<Tp, Tps...>;
};

那么, 可以这样使用:

1
2
3
4
5
6
7
8
int main() {
    TinyTuple<int, char, double, const char*> ttuple{1, 'a', 0.2, "abc"};

    std::cout << get<0>(ttuple) << std::endl;
    std::cout << get<1>(ttuple) << std::endl;
    std::cout << get<2>(ttuple) << std::endl;
    std::cout << get<3>(ttuple) << std::endl;
}

完整代码: https://gcc.godbolt.org/z/v3bYnxWrP

std::tuple

std::tuple的实现比以上的TinyTuple复杂得多, 但是核心思想还是类似的, std::tuple的类间关系如下:

https://bu.dusays.com/2022/10/23/635554d3599b9.png — std::tuple 继承关系

_Head 和 _Head_base

最底层部分是_Head这个"类", _Head是什么? 我们看下面的定义就可以知道了, _Head会是用户需要存储的一种类型:

1
2
3
4
5
template<size_t _Idx, typename _Head>
struct _Head_base<_Idx, _Head, true>
{
    //...
}

比如std::tuple<int, double>, 那么_Head就是int和double.

_Head_base和_Head的关系有两种实现方法, 一种是is a, 一种是use a, 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// is a
template<size_t _Idx, typename _Head>
struct _Head_base<_Idx, _Head, true>
: public _Head
{
    //...
}

// use a
template<size_t _Idx, typename _Head>
struct _Head_base<_Idx, _Head, true>
{
    //...
    [[__no_unique_address__]] _Head _M_head_impl;
}

以use a关系为例, _Head_base偏特化了两个实现, 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
template<size_t _Idx, typename _Head>
struct _Head_base<_Idx, _Head, true>
{
    //...
    [[__no_unique_address__]] _Head _M_head_impl;
}

template<size_t _Idx, typename _Head>
struct _Head_base<_Idx, _Head, false>
{
    //...
    _Head _M_head_impl;
};

以上两个模板在实现上没有任何区别, 仅成员变量_M_head_impl的声明不同. 那么, 现在需要关注__no_unique_address__属性是什么意思. __no_unique_address__属性如其字面意思, 描述的是它修饰的东西没有独立的地址. 比如对一个空类, 一般来说会占用1B空间, 但是经过__no_unique_address__修饰后, 可以不占用额外的地址空间(0B). 什么时候会选中这个属性? 这时候需要关注_Head_base的第三个模板参数什么时候会特化为true, 什么时候特化为false.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
template<typename _Tp>
struct __is_empty_non_tuple : is_empty<_Tp> { };

// Using EBO for elements that are tuples causes ambiguous base errors.
template<typename _El0, typename... _El>
struct __is_empty_non_tuple<tuple<_El0, _El...>> : false_type { };

// Use the Empty Base-class Optimization for empty, non-final types.
template<typename _Tp>
using __empty_not_final
= __conditional_t<__is_final(_Tp), false_type,
            __is_empty_non_tuple<_Tp>>;

template<size_t _Idx, typename _Head,
    bool = __empty_not_final<_Head>::value>
struct _Head_base;

如上, _Head_base的第三个模板参数特化为false的情况有:

_Head是用final修饰的类
_Head是tuple类型
_Head不是empty的

_Head_base的第三个模板参数特化为true的情况有:

_Head没有用final修饰并且不是tuple类型, 并且是empty的

is_empty描述如下:

If T is an empty type (that is, a non-union class type with no non-static data members other than bit-fields of size 0, no virtual functions, no virtual base classes, and no non-empty base classes), provides the member constant value equal to true. For any other type, value is false.

以上, 我认为偏特化两种_Head_base的作用是为了将少无用内存的消耗.

_Tuple_impl

_Tuple_impl是做可变参模板递归的类, 其实现类似于TinyTuple, 定义如下:

1
2
template<size_t _Idx, typename... _Elements>
struct _Tuple_impl;

偏特化为两个实现, 一个是通俗的递归过程:

1
2
3
4
template<size_t _Idx, typename _Head, typename... _Tail>
struct _Tuple_impl<_Idx, _Head, _Tail...>
: public _Tuple_impl<_Idx + 1, _Tail...>,
    private _Head_base<_Idx, _Head>

一个是递归终止过程:

1
2
3
template<size_t _Idx, typename _Head>
struct _Tuple_impl<_Idx, _Head>
: private _Head_base<_Idx, _Head>

递归的_Tuple_impl如何实现的? 先来关注其构造函数:

1
2
3
4
5
6
7
8
9
typedef _Tuple_impl<_Idx + 1, _Tail...> _Inherited;
typedef _Head_base<_Idx, _Head> _Base;

//...

explicit constexpr
_Tuple_impl(const _Head& __head, const _Tail&... __tail)
: _Inherited(__tail...), _Base(__head)
{ }

同TinyTuple的内存排列, _Tuple_impl的排列也是从右往左的元素按照地址从高到低排列.

如何获取元素呢? _Tuple_impl充分借用了父子类的特性, 很值得学习和实践:

1
2
3
4
5
static constexpr const _Head&
_M_head(const _Tuple_impl& __t) noexcept { return _Base::_M_head(__t); }

static constexpr const _Inherited&
_M_tail(const _Tuple_impl& __t) noexcept { return __t; }

_M_head可以获取tuple元素的值, _M_tail可以获取余下的"队列".

怎么做到的? 因为_Base::_M_head会将_Tuple_impl向上转换为_Head_base类, 这也是_Tuple_impl的父类. _M_tail则是通过返回值的类型, 将_Tuple_impl转换为_Inherited这个父类, 因此可以拿到余下的元素类. 递归终止类的实现类似, 此处就不继续看了.

这里涉及到多继承向上转换的隐式过程, 如下demo来验证:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

class B1 {
public:
    int val1;
};
class B2 {
public:
    int val2;
};

class D : public B1, public B2 {};

int main() {
    D d;
    B1 &b1 = d;
    B2 &b2 = d;

    std::cout << &b1 << "  " << &b2 << std::endl;
}

输出是0x7fff2ac0bf38 0x7fff2ac0bf3c, b1和b2是不同的内存区域, 差值是4B, b2在高地址, b1在低地址, 实际上在编译期就已经计算好两个base的偏移了, 他们的内存布局就对应着相应的Base类的内存布局.

tuple

以上我们学习了三个数据类型, 最基础的是Head, 它表示的是用户需要的元素的类型, 比如int, double一类；然后是Head_base, 相当于是Head的封装, 与Head一般是use的关系. 再是_Tuple_impl, 这是一个变参模板递归的类, 采用双继承的结构, 一个父类是自身的递归类, 一个是 Head_base类. 接下来就看看tuple类型, tuple有几种特化类型, 如下:

基础类型:

1
2
3
4
5
template<typename... _Elements>
class tuple : public _Tuple_impl<0, _Elements...>
{
    //...
}

空数据:

1
2
template<>
class tuple<>

2个元素的tuple:

1
2
template<typename _T1, typename _T2>
class tuple<_T1, _T2> : public _Tuple_impl<0, _T1, _T2>

因为有_Tuple_impl的辅助, tuple的实现就不需要关系数据如何保存了, tuple类更多的是关心如何构造, 如何复制之类, 暂时就不展开看了.

get

访问tuple元素的方法之一是通过get方法, 一般接口如下, 我们需要关注两个实现__tuple_element_t和__get_helper.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
template<size_t __i, typename... _Elements>
constexpr const __tuple_element_t<__i, tuple<_Elements...>>&
get(const tuple<_Elements...>& __t) noexcept
{ return std::__get_helper<__i>(__t); }

template<size_t __i, typename... _Elements>
constexpr const __tuple_element_t<__i, tuple<_Elements...>>&&
get(const tuple<_Elements...>&& __t) noexcept
{
    typedef __tuple_element_t<__i, tuple<_Elements...>> __element_type;
    return std::forward<const __element_type>(std::__get_helper<__i>(__t));
}

__tuple_element_t的实现见cppreference-tuple_element, 和TinyTuple中Elements的实现基本一致, 这里也不展开了. 最终是通过__get_helper获取元素的, 实现如下:

1
2
3
4
template<size_t __i, typename _Head, typename... _Tail>
constexpr const _Head&
__get_helper(const _Tuple_impl<__i, _Head, _Tail...>& __t) noexcept
{ return _Tuple_impl<__i, _Head, _Tail...>::_M_head(__t); }

这里的trick也比较有意思, 虽然 std::__get_helper<__i>(__t)传入的参数是"最"子类tuple, 但是__get_helper接收的是某个父类_Tuple_impl作为形参, 这时候size_t __i这个模板参数就起到作用了, 因为__get_helper<__i>可以直接匹配对应的_Tuple_impl类型, tuple作为__get_helper的参数入参后, 就会匹配并转换成_Tuple_impl<__i, _Head, _Tail...>父类, 然后通过_M_head接口获取元素的值即可.

在C++14后, get还支持将类型作为模板参数, 比如get<int>(tuple), 可以想想怎么实现. 比如参考Elements的做法, 将tuple的类型列表展开后, 匹配到对应的类型就返回对应的index, 一种实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
template <size_t N, typename Tp, typename Head, typename ...Tps>
constexpr size_t ElementsIndex()
{
    if constexpr (std::is_same<Tp, Head>::value)
        return N;
    else
        return ElementsIndex<N + 1, Tp, Tps...>();
}

template <size_t N, typename Tp, typename Head>
constexpr size_t ElementsIndex()
{
    if constexpr (std::is_same<Tp, Head>::value)
        return N;
    static_assert(std::is_same<Tp, Head>::value, "No Matched Type");
}

将这个更新加在TinyTuple可以扩展get方法, 如下使用:

1
2
3
4
5
6
std::cout << get<0>(ttuple) << std::endl;
std::cout << get<1>(ttuple) << std::endl;
std::cout << get<2>(ttuple) << std::endl;
std::cout << get<3>(ttuple) << std::endl;
std::cout << get<char>(ttuple) << std::endl;
std::cout << get<double>(ttuple) << std::endl;

在gcc是这样实现的:

1
2
3
4
5
6
7
8
9
template <typename _Tp, typename... _Types>
constexpr const _Tp&
get(const tuple<_Types...>& __t) noexcept
{
    constexpr size_t __idx = __find_uniq_type_in_pack<_Tp, _Types...>();
    static_assert(__idx < sizeof...(_Types),
    "the type T in std::get<T> must occur exactly once in the tuple");
    return std::__get_helper<__idx>(__t);
}

关注__find_uniq_type_in_pack:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
template<typename _Tp, typename... _Types>
constexpr size_t
__find_uniq_type_in_pack()
{
    constexpr size_t __sz = sizeof...(_Types);
    constexpr bool __found[__sz] = { __is_same(_Tp, _Types) ... };
    size_t __n = __sz;
    for (size_t __i = 0; __i < __sz; ++__i)
{
    if (__found[__i])
    {
        if (__n < __sz) // more than one _Tp found
    return __sz;
        __n = __i;
    }
}
    return __n;
}

此处对变参模板使用得很灵活, __is_same(_Tp, _Types) ...用法值得学习(相当于一个参数固定, 另一个参数是可变参).

tie

tuple的另一个功能是支持解包, 通过tie实现. tie怎么做的? 先看看源码:

1
2
3
4
template<typename... _Elements>
constexpr tuple<_Elements&...>
tie(_Elements&... __args) noexcept
{ return tuple<_Elements&...>(__args...); }

相当于是返回了一个类型是引用类型的tuple, 那么我们可以给TinyTuple加上类似的功能, 其中的tie实现如下:

1
2
3
4
5
template<typename ...Tps>
TinyTuple<Tps &...> tie(Tps &...args)
{
    return TinyTuple<Tps &...>(args...);
}

需要再实现TinyTuple的赋值操作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
template<typename...> friend class TinyTuple;

template <typename Head, typename ...Args>
TinyTuple<Tp, Tps...> &operator=(const TinyTuple<Head, Args...> &t)
{
    this->value = t.value;
    TinyTuple<Tps...>(*this) = TinyTuple<Args...>(t);

    return *this;
}

此处的TinyTuple<Tps...>(*this) = TinyTuple<Args...>(t);不需要递归终止条件, 因为最终的TinyTuple<Tps...>会退化为TinyTuple<>. 那么, 在TinyTuple里面可以这样使用tie:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int p1;
char p2;
double p3;
const char* p4;
tie(p1, p2, p3, p4) = ttuple;

std::cout << p1 << std::endl;
std::cout << p2 << std::endl;
std::cout << p3 << std::endl;
std::cout << p4 << std::endl;