C++ STL Source Code Analysis: tr1 and std array

Table of Contents

C++ STL Source Code Analysis: tr1 and std array

0. Introduction

The source code analysis is based on version gcc4.9.1.

C++ tr1, short for Technical Report 1, is the first extension to the C++ standard library. It is expected to be included in the upcoming C++ standard version, C++0x, along with some extensions to the language itself. tr1 includes long-awaited features such as smart pointers, regular expressions, and other support for generic programming. At the drafting stage, the namespace for newly added classes and templates is std::tr1.

1. std::tr1::array

Usage:

#include <tr1/array>
std::tr1::array<int, 10> a;

The array in tr1 is relatively simple, mimicking the language's native arrays and supporting iterator operations, allowing it to invoke algorithms like other containers. There are no constructors or destructors for array in tr1. Iterators directly use the type passed in for definition as pointers.

Let's take a brief look at the source code of this static array array:

template<typename _Tp, std::size_t _Nm>
struct array
{
    typedef _Tp                     value_type;
    typedef value_type&             reference;
    typedef const value_type&       const_reference;
    typedef value_type*             iterator;
    typedef const value_type*       const_iterator;
    typedef std::size_t             size_type;
    typedef std::ptrdiff_t          difference_type;
    typedef std::reverse_iterator<iterator>           reverse_iterator;
    typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
}

It uses reverse_iterator for the rbegin and rend operations. Although it appears to have one iterator, there are actually two: iterator, which directly uses the type passed in for definition as a pointer.

It can be compared to the forward and reverse iterators in a vector.

It's worth noting that in tr1::array, support for passing a size of 0 is allowed. For example, if we use:

std::tr1::array<int, 0> a;

For such usage, it corresponds to:

// Support for zero-sized arrays mandatory.
value_type _M_instance[_Nm ? _Nm : 1];

Based on the passed size, if it's not 0, it's the passed size; otherwise, it's 1.

2. std::array

Usage:

std::array<int, 10> a;

The array in std contains:

Comparison between tr1 and std array:

template<typename _Tp, std::size_t _Nm>
struct array
{
    typedef _Tp                     value_type;
    typedef value_type*             pointer;
    typedef const value_type*       const_pointer;
    typedef value_type&             reference;
    typedef const value_type&       const_reference;
    typedef value_type*             iterator;
    typedef const value_type*       const_iterator;
    typedef std::size_t             size_type;
    typedef std::ptrdiff_t          difference_type;
    typedef std::reverse_iterator<iterator>           reverse_iterator;
    typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;

    // Support for zero-sized arrays mandatory.
    typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;    // # define _GLIBCXX_STD_C std
    typename _AT_Type::_Type                         _M_elems;
}

There are two noteworthy points inside the array:

// Support for zero-sized arrays mandatory.
typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;    // # define _GLIBCXX_STD_C std
typename _AT_Type::_Type                         _M_elems;

Looking for __array_traits in the source code:

template<typename _Tp, std::size_t _Nm>
struct __array_traits
{
    typedef _Tp _Type[_Nm];

    static constexpr _Tp&
    _S_ref(const _Type& __t, std::size_t __n) noexcept
    { return const_cast<_Tp&>(__t[__n]); }
};

The two lines above can be understood as follows:

typedef _Tp _Type[100];
typedef _Type _M_elems;  // An array containing 100 elements.

When writing actual code, if we want to define an array, we can do it like this:

int a[100];
// or
typedef int T[100];
typedef T a;

Regarding handling the passed size, it's more complex compared to tr1. It uses template partial specialization to handle the case when the size passed is 0.

template<typename _Tp, std::size_t _Nm>
struct __array_traits
{
    typedef _Tp _Type[_Nm];

    static constexpr _Tp&
    _S_ref(const _Type& __t, std::size_t __n) noexcept
    { return const_cast<_Tp&>(__t[__n]); }
};

template<typename _Tp>
struct __array_traits<_Tp, 0>
{
    struct _Type { };

    static constexpr _Tp&
    _S_ref(const _Type&, std::size_t) noexcept
    { return *static_cast<_Tp*>(nullptr); }
};