C++ STL笔记03-std::array数组

动手实现C++ STL容器。本节介绍std::array的常见用法和实现。

std::array用法

std::array是C++标准库中的一个容器，用于表示一个固定大小的数组。它的用法与C中内置数组的用法基本一致，但还具有许多STL容器的优点：

固定大小：std::array的大小在创建时确定，不能在运行时改变；
范围检查：std::array在访问元素时会进行边界检查，防止越界访问；
迭代器：可以使用迭代器来遍历std::array中的元素，使其与其他STL容器兼容；
大小信息：可以通过size()方法获取数组的大小；
支持STL算法：很多STL算法可以直接应用在std::array上。

创建并访问std::array元素可以参考如下代码：

#include <iostream>
#include <array>

int main()
{
    std::array<int, 5> MyArray = {1, 2, 3, 4, 5};
    
    // 访问元素
    std::cout << "First element: " << MyArray[0] << std::endl;

    // 获取数组大小
    std::cout << "Array size: " << MyArray.size() << std::endl;

    // 使用迭代器遍历数组
    for (const auto& element : MyArray) {
        std::cout << element << " ";
    }

    return 0;
}

运行上面的代码可以得到如下结果：

First element: 1
Array size: 5
1 2 3 4 5 

Array实现

接下来我们从零开始实现一个类似于标准库中std::array的数组Array。

模板定义

首先是模板定义，在创建Array时我们需要指定两个模板参数：元素类型_Tp以及数组大小_N，然后再Array内部创建一个数组_M_element[_N]存储实际的元素：

template <class _Tp, size_t _N>
struct Array {
    _Tp _M_element[_N];
}

访问元素

为了使Array能像通常的数组一样进行访问，我们需要重载[]运算符：

template <class _Tp, size_t _N>
struct Array {
    ...
    _Tp &operator[] (size_t __i) noexcept {
        return _M_element[__i];
    }

    _Tp const &operator[](size_t __i) const noexcept {
        return _M_elements[__i];
    }
}

这里需要说明的是很多情况下[]运算符需要返回一个左值从而允许我们对Array中的元素进行赋值，因此它的第一个版本返回类型是一个左值引用。而[]运算符的第二个版本返回的则是const左值引用，它不允许对Array内部的元素进行修改。在很多只需要对数组进行遍历的情况下，它会避免拷贝操作从而有更好的性能。对于这种情况还需要在函数的后面再添加一个const表示我们不会对Array进行修改。

使用[]运算符访问数组的一个缺陷在于它可能会出现访问越界的情况，因此更合理的方式是通过at()函数来进行访问。at()函数会首先检查索引的大小，只有数组大小范围内的索引才会进行访问，否则抛出异常：

#define _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, __n) throw std::runtime_error("out of range at index " + std::to_string(__i) + ", size " + std::to_string(__n))


template <class _Tp, size_t _N>
struct Array {
    ...
    _Tp &at(size_t __i) {
        if (__i >= _N) [[__unlikely__]]
            _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, _N);
        return _M_elements[__i];
    }

    _Tp const &at(size_t __i) const {
        if (__i >= _N) [[__unlikely__]]
            _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, _N);
        return _M_elements[__i];
    }
}

数组大小

Array允许我们访问当前数组的大小以及数组是否非空：

template <class _Tp, size_t _N>
struct Array {
    ...
    static constexpr bool empty() noexcept {
        return false;
    }

    static constexpr size_t size() noexcept {
        return _N;
    }

    static constexpr size_t max_size() noexcept {
        return _N;
    }
}

这里需要说明的是Array的大小以及是否非空实际上在数组创建时就可以得到了，因此我们使用constexpr关键字将函数的返回值声明为编译期常量。这允许在编译时确定这些值，而不是在运行时进行计算，从而提高性能。

迭代器

Array的一个重要特性在于它支持迭代器，使得我们可以使用标准的迭代器接口来访问和遍历数组中的元素。为了支持迭代器，我们首先需要定义begin()和end()函数来返回数组的首尾：

template <class _Tp, size_t _N>
struct Array {
    ...
    _Tp const *cbegin() const noexcept {
        return _M_elements;
    }

    _Tp const *cend() const noexcept {
        return _M_elements + _N;
    }

    _Tp const *begin() const noexcept {
        return _M_elements;
    }

    _Tp const *end() const noexcept {
        return _M_elements + _N;
    }

    _Tp *begin() noexcept {
        return _M_elements;
    }

    _Tp *end() noexcept {
        return _M_elements + _N;
    }
}

同时，我们需要添加一些类型别名以便于迭代器访问：

template <class _Tp, size_t _N>
struct Array {
    using value_type      = _Tp;
    using pointer         = _Tp *;
    using const_pointer   = _Tp const *;
    using reference       = _Tp &;
    using const_reference = _Tp const &;
    using iterator        = _Tp *;
    using const_iterator  = _Tp const *;
    ...
}

对于反向迭代器，我们这里直接调用std::make_reverse_iterator来实现：

template <class _Tp, size_t _N>
struct Array {
    using reverse_iterator       = std::reverse_iterator<_Tp *>;
    using const_reverse_iterator = std::reverse_iterator<_Tp const *>;
    ...

    std::reverse_iterator<_Tp const *> crbegin() const noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp const *> crend() const noexcept {
        return std::make_reverse_iterator(_M_elements);
    }

    std::reverse_iterator<_Tp const *> rbegin() const noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp const *> rend() const noexcept {
        return std::make_reverse_iterator(_M_elements);
    }

    std::reverse_iterator<_Tp *> rbegin() noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp *> rend() noexcept {
        return std::make_reverse_iterator(_M_elements);
    }
}

其它成员函数

Array的一些其它常用成员函数可以参考如下实现：

template <class _Tp, size_t _N>
struct Array {
    ...
    void fill(_Tp const &__val) noexcept(std::is_nothrow_copy_assignable_v<_Tp>) {
        for (size_t __i = 0; __i < _N; __i++) {
            _M_elements[__i] = __val;
        }
    }

    void swap(Array &__that) noexcept(std::is_nothrow_swappable_v<_Tp>) {
        for (size_t __i = 0; __i < _N; __i++) {
            std::swap(_M_elements[__i], __that._M_elements[__i]);
        }
    }

    _Tp &front() noexcept {
        return _M_elements[0];
    }

    _Tp const &front() const noexcept {
        return _M_elements[0];
    }

    _Tp &back() noexcept {
        return _M_elements[_N - 1];
    }

    _Tp const &back() const noexcept {
        return _M_elements[_N - 1];
    }

    _Tp const *cdata() const noexcept {
        return _M_elements;
    }

    _Tp const *data() const noexcept {
        return _M_elements;
    }

    _Tp *data() noexcept {
        return _M_elements;
    }
    ...
}

除此之外，为了便于创建Array我们还可以利用模板参数推导来省去指定元素类型以及数组大小的过程：

template <class _Tp, class ..._Ts>
Array(_Tp, _Ts...) -> Array<_Tp, 1 + sizeof...(_Ts)>;

空数组

当数组大小N = 0时数组本身不具有任何意义，但仍然可以通过编译。这里我们需要引入一个模板特化来进行处理：

#if defined(_MSC_VER)
#define _LIBPENGCXX_UNREACHABLE() __assume(0)
#elif defined(__clang__)
#define _LIBPENGCXX_UNREACHABLE() __builtin_unreachable()
#elif defined(__GNUC__)
#define _LIBPENGCXX_UNREACHABLE() __builtin_unreachable()
#else
#define _LIBPENGCXX_UNREACHABLE() do {} while (1)
#endif


template <class _Tp>
struct Array<_Tp, 0> {
    using value_type = _Tp;
    using pointer = _Tp *;
    using const_pointer = _Tp const *;
    using reference = _Tp &;
    using const_reference = _Tp const &;
    using iterator = _Tp *;
    using const_iterator = _Tp const *;
    using reverse_iterator = _Tp *;
    using const_reverse_iterator = _Tp const *;

    _Tp &operator[](size_t __i) noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &operator[](size_t __i) const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp &at(size_t __i) {
        _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, 0);
    }

    _Tp const &at(size_t __i) const {
        _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, 0);
    }

    void fill(_Tp const &) noexcept {
    }

    void swap(Array &) noexcept {
    }

    _Tp &front() noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &front() const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp &back() noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &back() const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    static constexpr bool empty() noexcept {
        return true;
    }

    static constexpr size_t size() noexcept {
        return 0;
    }

    static constexpr size_t max_size() noexcept {
        return 0;
    }

    _Tp const *cdata() const noexcept {
        return nullptr;
    }

    _Tp const *data() const noexcept {
        return nullptr;
    }

    _Tp *data() noexcept {
        return nullptr;
    }

    _Tp const *cbegin() const noexcept {
        return nullptr;
    }

    _Tp const *cend() const noexcept {
        return nullptr;
    }

    _Tp const *begin() const noexcept {
        return nullptr;
    }

    _Tp const *end() const noexcept {
        return nullptr;
    }

    _Tp *begin() noexcept {
        return nullptr;
    }

    _Tp *end() noexcept {
        return nullptr;
    }

    _Tp const *crbegin() const noexcept {
        return nullptr;
    }

    _Tp const *crend() const noexcept {
        return nullptr;
    }

    _Tp const *rbegin() const noexcept {
        return nullptr;
    }

    _Tp const *rend() const noexcept {
        return nullptr;
    }

    _Tp *rbegin() noexcept {
        return nullptr;
    }

    _Tp *rend() noexcept {
        return nullptr;
    }
};

完整实现

总结一下，整个Array的代码可以参考如下：

#pragma once

#include <cstddef> // size_t
#include <stdexcept> // std::runtime_error
#include <string> // std::to_string
#include <iterator> // std::reverse_iterator

// C++ 标准规定：单下划线+大写字母（_Identifier）或 双下划线+小写字母（__identifier）的标识符是保留字。理论上用户不得使用，只允许标准库和编译器使用。此处小彭老师打算只在最简单的 array 容器中严格服从一下这个规则作为演示，正经标准库里的代码都是这样的（为避免和用户定义的符号产生冲突），此后其他容器的课程都会用日常的写法，不给同学平添阅读难度

#define _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, __n) throw std::runtime_error("out of range at index " + std::to_string(__i) + ", size " + std::to_string(__n))

#if defined(_MSC_VER)
#define _LIBPENGCXX_UNREACHABLE() __assume(0)
#elif defined(__clang__)
#define _LIBPENGCXX_UNREACHABLE() __builtin_unreachable()
#elif defined(__GNUC__)
#define _LIBPENGCXX_UNREACHABLE() __builtin_unreachable()
#else
#define _LIBPENGCXX_UNREACHABLE() do {} while (1)
#endif

template <class _Tp, size_t _N>
struct Array {
    using value_type = _Tp;
    using pointer = _Tp *;
    using const_pointer = _Tp const *;
    using reference = _Tp &;
    using const_reference = _Tp const &;
    using iterator = _Tp *;
    using const_iterator = _Tp const *;
    using reverse_iterator = std::reverse_iterator<_Tp *>;
    using const_reverse_iterator = std::reverse_iterator<_Tp const *>;

    _Tp _M_elements[_N];

    _Tp &operator[](size_t __i) noexcept {
        return _M_elements[__i];
    }

    _Tp const &operator[](size_t __i) const noexcept {
        return _M_elements[__i];
    }

    _Tp &at(size_t __i) {
        if (__i >= _N) [[__unlikely__]]
            _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, _N);
        return _M_elements[__i];
    }

    _Tp const &at(size_t __i) const {
        if (__i >= _N) [[__unlikely__]]
            _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, _N);
        return _M_elements[__i];
    }

    void fill(_Tp const &__val) noexcept(std::is_nothrow_copy_assignable_v<_Tp>) {
        for (size_t __i = 0; __i < _N; __i++) {
            _M_elements[__i] = __val;
        }
    }

    void swap(Array &__that) noexcept(std::is_nothrow_swappable_v<_Tp>) {
        for (size_t __i = 0; __i < _N; __i++) {
            std::swap(_M_elements[__i], __that._M_elements[__i]);
        }
    }

    _Tp &front() noexcept {
        return _M_elements[0];
    }

    _Tp const &front() const noexcept {
        return _M_elements[0];
    }

    _Tp &back() noexcept {
        return _M_elements[_N - 1];
    }

    _Tp const &back() const noexcept {
        return _M_elements[_N - 1];
    }

    static constexpr bool empty() noexcept {
        return false;
    }

    static constexpr size_t size() noexcept {
        return _N;
    }

    static constexpr size_t max_size() noexcept {
        return _N;
    }

    _Tp const *cdata() const noexcept {
        return _M_elements;
    }

    _Tp const *data() const noexcept {
        return _M_elements;
    }

    _Tp *data() noexcept {
        return _M_elements;
    }

    _Tp const *cbegin() const noexcept {
        return _M_elements;
    }

    _Tp const *cend() const noexcept {
        return _M_elements + _N;
    }

    _Tp const *begin() const noexcept {
        return _M_elements;
    }

    _Tp const *end() const noexcept {
        return _M_elements + _N;
    }

    _Tp *begin() noexcept {
        return _M_elements;
    }

    _Tp *end() noexcept {
        return _M_elements + _N;
    }

    std::reverse_iterator<_Tp const *> crbegin() const noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp const *> crend() const noexcept {
        return std::make_reverse_iterator(_M_elements);
    }

    std::reverse_iterator<_Tp const *> rbegin() const noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp const *> rend() const noexcept {
        return std::make_reverse_iterator(_M_elements);
    }

    std::reverse_iterator<_Tp *> rbegin() noexcept {
        return std::make_reverse_iterator(_M_elements + _N);
    }

    std::reverse_iterator<_Tp *> rend() noexcept {
        return std::make_reverse_iterator(_M_elements);
    }
};

template <class _Tp>
struct Array<_Tp, 0> {
    using value_type = _Tp;
    using pointer = _Tp *;
    using const_pointer = _Tp const *;
    using reference = _Tp &;
    using const_reference = _Tp const &;
    using iterator = _Tp *;
    using const_iterator = _Tp const *;
    using reverse_iterator = _Tp *;
    using const_reverse_iterator = _Tp const *;

    _Tp &operator[](size_t __i) noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &operator[](size_t __i) const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp &at(size_t __i) {
        _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, 0);
    }

    _Tp const &at(size_t __i) const {
        _LIBPENGCXX_THROW_OUT_OF_RANGE(__i, 0);
    }

    void fill(_Tp const &) noexcept {
    }

    void swap(Array &) noexcept {
    }

    _Tp &front() noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &front() const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp &back() noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    _Tp const &back() const noexcept {
        _LIBPENGCXX_UNREACHABLE();
    }

    static constexpr bool empty() noexcept {
        return true;
    }

    static constexpr size_t size() noexcept {
        return 0;
    }

    static constexpr size_t max_size() noexcept {
        return 0;
    }

    _Tp const *cdata() const noexcept {
        return nullptr;
    }

    _Tp const *data() const noexcept {
        return nullptr;
    }

    _Tp *data() noexcept {
        return nullptr;
    }

    _Tp const *cbegin() const noexcept {
        return nullptr;
    }

    _Tp const *cend() const noexcept {
        return nullptr;
    }

    _Tp const *begin() const noexcept {
        return nullptr;
    }

    _Tp const *end() const noexcept {
        return nullptr;
    }

    _Tp *begin() noexcept {
        return nullptr;
    }

    _Tp *end() noexcept {
        return nullptr;
    }

    _Tp const *crbegin() const noexcept {
        return nullptr;
    }

    _Tp const *crend() const noexcept {
        return nullptr;
    }

    _Tp const *rbegin() const noexcept {
        return nullptr;
    }

    _Tp const *rend() const noexcept {
        return nullptr;
    }

    _Tp *rbegin() noexcept {
        return nullptr;
    }

    _Tp *rend() noexcept {
        return nullptr;
    }
};


template <class _Tp, class ..._Ts>
Array(_Tp, _Ts...) -> Array<_Tp, 1 + sizeof...(_Ts)>;

Reference

PREVIOUSstd::unique_ptr

NEXTstd::vector