官方bilibiliWindows破解入门Android逆向入门
【网络诊断修复工具】切换到窄版

吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步，快速开始

吾爱破解 - 52pojie.cn»网站 › 【 软件安全 】 › 『编程语言区』 › 【STL】手撕STL系列（三）array
返回列表 发新帖
查看: 929|回复: 0
上一主题 下一主题
收起左侧

[C&C++ 原创] 【STL】手撕STL系列（三）array

  [复制链接]
跳转到指定楼层
楼主
jjjzw 发表于 2025-1-17 17:20 回帖奖励
本帖最后由 jjjzw 于 2025-1-20 20:04 编辑

系列导航

项目地址：https://github.com/Icingworld/WW-STL
仓库代码已经补全，code review会随着系列帖子逐渐完成，欢迎大家关注交流！

序列容器之 array

一、array简介

array 是封装固定大小数组的容器，是 C++11 标准提出的容器。它维护一个 C 风格的数组T[N]作为其唯一非静态数据成员。和数组不同的是，数组会退化成T*用以指向数组的首位地址，但 array 不会。

array 是一个聚合类型，可以聚合初始化（列表初始化的一种）。因此根据聚合体的规定，array 没有构造和析构函数，或者说是隐式的。详情见https://zh.cppreference.com/w/cpp/language/aggregate_initialization。

array 既拥有数组的性能和优点，也集成了 STL 容器在访问、算法上的优点。

int a[3] = {1, 2, 3};                   // C 风格数组

wwstl::array<int, 3> b = {1, 2, 3};     // array

二、array的实现

array 的完整实现位于ww_array.h。

1. array的迭代器

array 的迭代器是一种随机访问迭代器，它维护一个指向 array 底层数组的指针。

这里const_iterator和iterator使用了一个小技巧，阅读代码可以发现，const_iterator中维护的指针并非pointer类型，而是又定义了一个_Ptr类型：

template <class T>
class _array_const_iterator
{
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;
    using self = _array_const_iterator<value_type>;

    using _Ptr = value_type*;   // 底层使用非const指针
};

为什么要这么做呢？首先我们考虑，如果我们使用pointer，那么在const_iterator中维护的就是const value_type * _ptr，这当然是符合语义的。但是在使用iterator时就会出现问题。

对于解引用的两个接口，iterator分别返回reference和pointer类型，这是非 const 的，而底层则维护 const 指针，需要使用const_cast来去除 const 属性，这样的实践并不好，违反了 const 设计的用意，且使得迭代器实现更复杂。

const_iterator同样维护value_type *，而在解引用时，会隐式转换为const value_type *，不会出现问题。唯一需要注意的是，在const_itrator的构造函数中，我们有一个重载：

explicit _array_const_iterator(pointer ptr)
    : _ptr(const_cast<_Ptr>(ptr))
{ // 用指针ptr构造一个迭代器
}

它接受一个const value_type *类型的指针，然后使用const_cast来去除 const 属性，这样在解引用时就不会出现问题。这种情况是少见的，而当我们使用普通的value_type *来构造时，也能够匹配const value_type *。

使用相同的底层指针，我们单独设计const_iterator和iterator的解引用会相当顺畅，但 MSVC 实现为了复用基类的接口，还是使用了const_cast来去除 const 属性，好吧，作者选择借鉴它的做法。

接下来就是迭代器的接口，是简单的指针操作，无需赘述。需要注意的是，MSVC 在实现 STL 时，对代码的复用令作者大开眼界，体现在迭代器的设计中，它尽可能使用复用，绝不写任何重复的代码，以达到更容易维护的目的。

2. array的定义

array 的定义如下：

template <
    class T,
    std::size_t N
> class array;

它接受两个模板参数，第一个模板参数是元素类型，第二个模板参数是元素个数。也就是说，在声明 array 数组时，array 的大小就确定了，这点和 C 风格数组是一致的。

3. array的构造

由于 array 需要符合聚合体的规定，因此它的构造函数、析构函数都是隐式的，且赋值重载也是隐式的。

详情见https://zh.cppreference.com/w/cpp/container/array。

4. array的接口

注意：接口中，与 const 语义有关的重载将不再介绍

  • 元素访问
/**
 * @brief 带越界检查访问指定的元素
 */
reference at(size_type pos)
{
    if (pos >= N) {
        _throw_out_of_range();
    }
    return _data[pos];
}

/**
 * @brief 访问指定的元素
 */
reference operator[](size_type pos)
{
    return _data[pos];
}

/**
 * @brief 访问第一个元素
 */
reference front()
{
    return _data[0];
}

/**
 * @brief 访问最后一个元素
 */
reference back()
{
    return _data[N - 1];
}

/**
 * @brief 直接访问底层连续存储
 */
pointer data()
{
    return _data;
}

其中，_throw_out_of_range()是一个用于抛出异常的内部函数，其定义如下：

[[noreturn]] void _throw_out_of_range() const
{
    throw std::out_of_range("invalid array<T, N> subscript");
}

当我们调用at接口访问容器时，会检测索引是否有效，无效则抛出异常。

  • 迭代器
/**
 * @brief 返回指向起始的迭代器
 */
iterator begin() noexcept
{
    return iterator(_data);
}

/**
 * @brief 返回指向起始的逆向迭代器
 */
reverse_iterator rbegin() noexcept
{
    return reverse_iterator(end());
}

STL 容器中关于迭代器接口的实现大多类似，对于begin()接口，通过指针来构造一个迭代器，然后返回它的拷贝；对于rbegin()接口，则使用一个迭代器end()来构造。关于逆向迭代器的知识，详情见【STL】手撕STL系列（二）迭代器。

  • 容量
/**
 * @brief 检查容器是否为空
 */
constexpr bool empty() const noexcept
{
    return false;
}

/**
 * @brief 返回元素数
 */
constexpr size_type size() const noexcept
{
    return N;
}

/**
 * @brief 返回最大容量
 */
constexpr size_type max_size() const noexcept
{
    return size();
}

关于 array 的容量，由于数组初始化 N 一定是大于0的，所以容器必不为空。那么如果使用模板时传入N = 0怎么办？根据 STL 要求，需要提供一个模板特化的类，来满足这个要求：

template <class T>
class array<T, 0>;

这是一个 array 模板的偏特化，有意思的点在于，维护的是一个T[1]，因为 C++ 不允许声明空数组。它的具体行为见代码，这里不详细介绍。

  • 操作
/**
 * @brief 以指定值填充容器
 */
void fill(const value_type & value)
{
    std::fill_n(_data, N, value);
}

/**
 * @brief 交换内容
 */
void swap(array<T, N> & other) noexcept
{
    std::swap(_data, other._data);
}

array 提供两种操作接口：

一个是fill，调用了标准库算法中的std::fill_n，它能够以指定值从指定位置开始填充指定个数的元素，事实上该函数是一个模板函数，接受迭代器参数，但是原生指针正是一种随机访问迭代器，因此匹配该算法。

另一个是swap，调用标准库算法中的std::swap，它能够交换两个指针的数据，也就是交换 array 的底层数组的内容。

  • 非成员函数
/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> T & get(array<T, N> & a)
{ return a[I]; }

/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> T && get(array<T, N> && a)
{ return std::move(a[I]); }

// 辅助类

template <
    std::size_t I,
    class T
> class tuple_element;

template <
    std::size_t I,
    class T,
    std::size_t N
> class tuple_element<I, array<T, N>>
{
public:
    using type = T;
};

template <class T>
class tuple_size;

template<
    class T,
    std::size_t N
> class tuple_size<array<T, N>> : std::integral_constant<std::size_t, N>
{
};

根据要求，还需要提供一些非成员函数，它们是一系列函数的重载，包括了 STL 通用的比较运算符、交换重载，还有 array 特有的函数，用于提取 array 的数据。

其中，tuple_element用于获取 array 的元素类型，tuple_size用于获取 array 的大小。

三、思考

1. 新特性

C++11 推出了一个名为基于范围的 for 循环的特性，我们常使用它来遍历容器：

for (auto & it : container) {
    // do something
}

这实际上是调用了容器的迭代器接口begin()和end()，因此只要我们的容器完成了迭代器接口的实现，就可以使用这种 for 循环。

完整代码

这里给出作者实现的 array 源码：

#ifndef __WW_ARRAY_H__
#define __WW_ARRAY_H__

#include <stdexcept>
#include "ww_iterator.h"

namespace wwstl
{

/**
 * @brief array常量迭代器类
 */
template <class T>
class _array_const_iterator
{
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;
    using self = _array_const_iterator<value_type>;

    using _Ptr = value_type*;   // 底层使用非const指针

public:
    _Ptr _ptr;  // 指向array的指针

public:
    _array_const_iterator()
        : _ptr(nullptr)
    { // 构造一个空迭代器
    }

    explicit _array_const_iterator(pointer ptr)
        : _ptr(const_cast<_Ptr>(ptr))
    { // 用指针ptr构造一个迭代器
    }

public:
    reference operator*() const
    { return *_ptr; }

    pointer operator->() const
    { return &(operator*()); }

    self & operator++()
    {
        ++_ptr;
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    self & operator--()
    {
        --_ptr;
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        --*this;
        return tmp;
    }

    bool operator==(const self & other) const
    { return _ptr == other._ptr; }

    bool operator!=(const self & other) const
    { return !(*this == other); }

    bool operator<(const self & other) const
    { return _ptr < other._ptr; }

    bool operator>(const self & other) const
    { return other < *this; }

    bool operator<=(const self & other) const
    { return !(other < *this); }

    bool operator>=(const self & other) const
    { return !(*this < other); }

    self & operator+=(const difference_type n)
    {
        _ptr += n;
        return *this;
    }

    self & operator-=(const difference_type n)
    { return *this += -n; }

    self operator+(const difference_type n) const
    {
        self temp = *this;
        return temp += n;
    }

    self operator-(const difference_type n) const
    {
        self temp = *this;
        return temp -= n;
    }

    difference_type operator-(const self & other) const
    { return _ptr - other._ptr; }

    reference operator[](const difference_type n) const
    { return *(*this + n); }
};

/**
 * @brief array非常量迭代器类
 */
template <class T>
class _array_iterator
    : public _array_const_iterator<T>
{
public:
    using base = _array_const_iterator<T>;      // 基类
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;
    using self = _array_iterator<value_type>;

public:
    _array_iterator()
        : base()
    { // 构造一个空迭代器
    }

    explicit _array_iterator(pointer ptr)
        : base(ptr)
    { // 用指针ptr构造一个迭代器
    }

public:
    reference operator*() const
    { return const_cast<reference>(base::operator*()); }

    pointer operator->() const
    { return const_cast<pointer>(base::operator->()); }

    self & operator++()
    {
        ++*(base *)this;
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    self & operator--()
    {
        --*(base *)this;
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        --*this;
        return tmp;
    }

    self & operator+=(difference_type n)
    {
        *(base *)this += n;
        return *this;
    }

    self & operator-=(difference_type n)
    {
        *(base *)this -= n;
        return *this;
    }

    self operator+(difference_type n) const
    {
        self temp = *this;
        return temp += n;
    }

    self operator-(difference_type n) const
    {
        self temp = *this;
        return temp -= n;
    }

    difference_type operator-(const base & other) const
    { return *(base *)this - other; }

    reference operator[](difference_type n) const
    { return *(*this + n); }
};

/**
 * @brief array
 * @link https://zh.cppreference.com/w/cpp/container/array
 */
template <
    class T,
    std::size_t N
> class array
{
public:
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = _array_iterator<value_type>;
    using const_iterator = _array_const_iterator<value_type>;
    using reverse_iterator = mystl::reverse_iterator<iterator>;
    using const_reverse_iterator = mystl::reverse_iterator<const_iterator>;

public:
    value_type _data[N];

public:
    // 元素访问

    /**
     * @brief 带越界检查访问指定的元素
     */
    reference at(size_type pos)
    {
        if (pos >= N) {
            _throw_out_of_range();
        }
        return _data[pos];
    }

    /**
     * @brief 带越界检查访问指定的元素
     */
    const_reference at(size_type pos) const
    {
        if (pos >= N) {
            _throw_out_of_range();
        }
        return _data[pos];
    }

    /**
     * @brief 访问指定的元素
     */
    reference operator[](size_type pos)
    { return _data[pos]; }

    /**
     * @brief 访问指定的元素
     */
    const_reference operator[](size_type pos) const
    { return _data[pos]; }

    /**
     * @brief 访问第一个元素
     */
    reference front()
    { return _data[0]; }

    /**
     * @brief 访问第一个元素
     */
    const_reference front() const
    { return _data[0]; }

    /**
     * @brief 访问最后一个元素
     */
    reference back()
    { return _data[N - 1]; }

    /**
     * @brief 访问最后一个元素
     */
    const_reference back() const
    { return _data[N - 1]; }

    /**
     * @brief 直接访问底层连续存储
     */
    pointer data()
    { return _data; }

    /**
     * @brief 直接访问底层连续存储
     */
    const_pointer data() const
    { return _data; }

    // 迭代器

    /**
     * @brief 返回指向起始的迭代器
     */
    iterator begin() noexcept
    { return iterator(_data); }

    /**
     * @brief 返回指向起始的迭代器
     */
    const_iterator begin() const noexcept
    { return const_iterator(_data); }

    /**
     * @brief 返回指向起始的迭代器
     */
    const_iterator cbegin() const noexcept
    { return begin(); }

    /**
     * @brief 返回指向末尾的迭代器
     */
    iterator end() noexcept
    { return iterator(_data + N); }

    /**
     * @brief 返回指向末尾的迭代器
     */
    const_iterator end() const noexcept
    { return const_iterator(_data + N); }

    /**
     * @brief 返回指向末尾的迭代器
     */
    const_iterator cend() const noexcept
    { return end(); }

    /**
     * @brief 返回指向起始的逆向迭代器
     */
    reverse_iterator rbegin() noexcept
    { return reverse_iterator(end()); }

    /**
     * @brief 返回指向起始的逆向迭代器
     */
    const_reverse_iterator rbegin() const noexcept
    { return const_reverse_iterator(end()); }

    /**
     * @brief 返回指向起始的逆向迭代器
     */
    const_reverse_iterator crbegin() const noexcept
    { return rbegin(); }

    /**
     * @brief 返回指向末尾的逆向迭代器
     */
    reverse_iterator rend() noexcept
    { return reverse_iterator(begin()); }

    /**
     * @brief 返回指向末尾的逆向迭代器
     */
    const_reverse_iterator rend() const noexcept
    { return const_reverse_iterator(begin()); }

    /**
     * @brief 返回指向末尾的逆向迭代器
     */
    const_reverse_iterator crend() const noexcept
    { return rend(); }

    // 容量

    /**
     * @brief 检查容器是否为空
     */
    constexpr bool empty() const noexcept
    { return false; }

    /**
     * @brief 返回元素数
     */
    constexpr size_type size() const noexcept
    { return N; }

    /**
     * @brief 返回最大容量
     */
    constexpr size_type max_size() const noexcept
    { return size(); }

    // 操作

    /**
     * @brief 以指定值填充容器
     */
    void fill(const value_type & value)
    { std::fill_n(_data, N, value); }

    /**
     * @brief 交换内容
     */
    void swap(array<T, N> & other) noexcept
    { std::swap(_data, other._data); }

public:
    /**
     * @brief 抛出out_of_range异常
     */
    [[noreturn]] void _throw_out_of_range() const
    { throw std::out_of_range("invalid array<T, N> subscript"); }
};

// 非成员函数

template <
    class T,
    std::size_t N
> bool operator==(const array<T, N> & a, const array<T, N> & b)
{ return std::equal(a.begin(), a.end(), b.begin(), b.end()); }

template <
    class T,
    std::size_t N
> bool operator!=(const array<T, N> & a, const array<T, N> & b)
{ return !(a == b); }

template <
    class T,
    std::size_t N
> bool operator<(const array<T, N> & a, const array<T, N> & b)
{ return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); }

template <
    class T,
    std::size_t N
> bool operator<=(const array<T, N> & a, const array<T, N> & b)
{ return !(b < a); }

template <
    class T,
    std::size_t N
> bool operator>(const array<T, N> & a, const array<T, N> & b)
{ return b < a; }

template <
    class T,
    std::size_t N
> bool operator>=(const array<T, N> & a, const array<T, N> & b)
{ return !(a < b); }

/**
 * @brief 交换两个array
 */
template <
    class T,
    std::size_t N
> void swap(array<T, N> & a, array<T, N> & b)
{ a.swap(b); }

/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> T & get(array<T, N> & a)
{ return a[I]; }

/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> T && get(array<T, N> && a)
{ return std::move(a[I]); }

/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> const T & get(const array<T, N> & a)
{ return a[I]; }

/**
 * @brief 获取array中第I个元素
 */
template <
    std::size_t I,
    class T,
    std::size_t N
> const T && get(const array<T, N> && a)
{ return std::move(a[I]); }

// 辅助类

template <
    std::size_t I,
    class T
> class tuple_element;

template <
    std::size_t I,
    class T,
    std::size_t N
> class tuple_element<I, array<T, N>>
{
public:
    using type = T;
};

template <class T>
class tuple_size;

template<
    class T,
    std::size_t N
> class tuple_size<array<T, N>> : std::integral_constant<std::size_t, N>
{
};

/**
 * @brief 对空array的特化
 */
template <class T>
class array<T, 0>
{
public:
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = _array_iterator<value_type>;
    using const_iterator = _array_const_iterator<value_type>;
    using reverse_iterator = mystl::reverse_iterator<iterator>;
    using const_reverse_iterator = mystl::reverse_iterator<const_iterator>;

public:
    value_type _data[1];        // 不允许声明一个大小为0的数组

public:
    // 元素访问

    [[noreturn]] reference at(size_type)
    { _throw_out_of_range(); }

    [[noreturn]] const_reference at(size_type) const
    { _throw_out_of_range(); }

    reference operator[](size_type) noexcept
    { return _data[0]; }

    const_reference operator[](size_type) const noexcept
    { return _data[0]; }

    reference front()
    { return _data[0]; }

    const_reference front() const
    { return _data[0]; }

    reference back()
    { return _data[0]; }

    const_reference back() const
    { return _data[0]; }

    pointer data()
    { return nullptr; }

    const_pointer data() const
    { return nullptr; }

    // 迭代器

    iterator begin() noexcept
    { return iterator(); }

    const_iterator begin() const noexcept
    { return const_iterator(); }

    const_iterator cbegin() const noexcept
    { return begin(); }

    iterator end() noexcept
    { return iterator(); }

    const_iterator end() const noexcept
    { return const_iterator(); }

    const_iterator cend() const noexcept
    { return end(); }

    reverse_iterator rbegin() noexcept
    { return reverse_iterator(end()); }

    const_reverse_iterator rbegin() const noexcept
    { return const_reverse_iterator(end()); }

    const_reverse_iterator crbegin() const noexcept
    { return rbegin(); }

    reverse_iterator rend() noexcept
    { return reverse_iterator(begin()); }

    const_reverse_iterator rend() const noexcept
    { return const_reverse_iterator(begin()); }

    const_reverse_iterator crend() const noexcept
    { return rend(); }

    // 容量

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

    constexpr size_type size() const noexcept
    { return 0; }

    constexpr size_type max_size() const noexcept
    { return 0; }

    // 操作

    void fill(const value_type &)
    { // do nothing        
    }

    void swap(const array &)
    { // do nothing
    }

public:
    /**
     * @brief 抛出out_of_range异常
     */
    [[noreturn]] void _throw_out_of_range() const
    { throw std::out_of_range("invalid array<T, 0> subscript"); }
};

} // namespace wwstl

#endif // __WW_ARRAY_H__

免费评分

参与人数 6吾爱币 +12 热心值 +5 收起 理由
苏紫方璇 + 7 + 1 欢迎分析讨论交流，吾爱破解论坛有你更精彩！
Issacclark1 + 1 谢谢@Thanks！
小朋友呢 + 2 + 1 热心回复！
BGDK111 + 1 + 1 谢谢@Thanks！
qmsy273 + 1 我很赞同！
helian147 + 1 + 1 热心回复！

查看全部评分

发帖前要善用【论坛搜索】功能，那里可能会有你要找的答案或者已经有人发布过相同内容了，请勿重复发帖。
回复

举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则


免责声明：
吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如有侵权请邮件与我们联系处理。

Mail To:Service@52pojie.cn

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2025-8-8 15:14

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表