乐趣区

关于c++:超详细STL之array容器使用及实现原理解析

阐明一下,我用的是 gcc7.1.0 编译器,规范库源代码也是这个版本的。

本篇文章讲述 STL 中 array 的应用及原理。

导读

array 其实是一个固定大小的数组,元素类型及大小在申明的时候指定,原型如下:

template<typename _Tp, std::size_t _Nm>
    struct array
    {...};

有些书上说 array 也是一个 class,然而我这个版本看到的是 struct,不过没有关系,除了一些轻微的方面,struct 和 class 并无太大的区别,这里能够看到 array 其实就是一个模板类。

array 的初步应用

应用 array 要蕴含头文件<array>,并申明 std 命名空间才可应用。

如下是一个简略的案例:

#include <array>
#include <iostream>

int main()
{std::array<int,5> a = {1,2,3,4,5};
    for(auto i:a)
    {std::cout << "value is" << i << std::endl;}
    return 0;
}

fill()和 swap()的应用

先看下他们的原型,如下:

//fill 函数是把以后 array 外面所有元素都填充为入参__u
void fill(const value_type& __u);
//swap 是替换两个 array 数据
void swap(array& __other) noexcept(_AT_Type::_Is_nothrow_swappable::value);

看一下应用案例:

#include <array>
#include <iostream>

int main()
{
    std::array<int,5> arr1;
    arr1.fill(5);
    for(auto i:arr1)
    {std::cout << "arr1 value is" << i << std::endl;}
    std::array<int,5> arr2 = {1,2,3,4,5};
    arr2.swap(arr1);
    for(auto i:arr1)
    {std::cout << "arr1 value is" << i << std::endl;}
    for(auto i:arr2)
    {std::cout << "arr2 value is" << i << std::endl;}
    return 0;
}

这里要留神的一个点是,arr1 和 arr2 的元素类型和大小都必须要完全一致,才能够应用 swap 函数,因为应用 swap 的前提就是类型要完全一致,而 array 容器的类型是包含两个模板参数:元素类型和元素个数,如果不统一,编译时没有方法通过的。

迭代器函数

// 这里 value_type 就是定义一个 array 时指定的元素类型,比方在下面的例子中,它就是 int 类型
typedef value_type*                        iterator;
typedef const value_type*                  const_iterator;
// 返回一个指向以后 array 的第一个元素的可读可写的迭代器
_GLIBCXX17_CONSTEXPR iterator
begin() noexcept
{return iterator(data()); }
// 返回一个指向以后 array 的第一个元素的只读迭代器
_GLIBCXX17_CONSTEXPR const_iterator
begin() const noexcept
{return const_iterator(data()); }
// 返回一个指向以后 array 的最初一个元素的下一个地位的可读可写迭代器
_GLIBCXX17_CONSTEXPR iterator
end() noexcept
{return iterator(data() + _Nm); }
// 返回一个指向以后 array 的最初一个元素的下一个地位的只读迭代器
_GLIBCXX17_CONSTEXPR const_iterator
end() const noexcept
{return const_iterator(data() + _Nm); }
// 返回一个指向以后 array 的最初一个元素的下一个地位的可读可写反转迭代器,也就是指向最初一个元素
_GLIBCXX17_CONSTEXPR reverse_iterator
rbegin() noexcept
{return reverse_iterator(end()); }
// 返回一个指向以后 array 的最初一个元素的只读迭代器
_GLIBCXX17_CONSTEXPR const_reverse_iterator
rbegin() const noexcept
{return const_reverse_iterator(end()); }
// 返回一个指向以后 array 的第一个元素的前一个地位的可读可写的迭代器
_GLIBCXX17_CONSTEXPR reverse_iterator
rend() noexcept
{return reverse_iterator(begin()); }
// 返回一个指向以后 array 的第一个元素的前一个地位的只读迭代器
_GLIBCXX17_CONSTEXPR const_reverse_iterator
rend() const noexcept
{return const_reverse_iterator(begin()); }

// 以下四个迭代器其实与下面的统一,只是它都是只读迭代器
_GLIBCXX17_CONSTEXPR const_iterator
cbegin() const noexcept
{return const_iterator(data()); }

_GLIBCXX17_CONSTEXPR const_iterator
cend() const noexcept
{return const_iterator(data() + _Nm); }

_GLIBCXX17_CONSTEXPR const_reverse_iterator
crbegin() const noexcept
{return const_reverse_iterator(end()); }

_GLIBCXX17_CONSTEXPR const_reverse_iterator
crend() const noexcept
{return const_reverse_iterator(begin()); }

在这一堆迭代器函数外面有两点须要留神:

  • 一是同样的函数能够返回可读可写和只读两种,比方 begin,同样的函数名和参数,只是返回类型和 const 属性不一样;
  • 二是反转迭代器反转一下其实是指向以后地位的前一个元素的迭代器,也就是说除了地位反转了,其实方向也反转了;

为了防止混同,应用的时候,如果要可读可写,就间接应用 begin,要只读就应用 cbegin,要反转的话,就应用 rbegin。

应用案例如下:

#include <iostream>
#include <array>
using namespace std;

int main()
{array<int,5> a = {1,2,3,4,5};
    array<int,5>::iterator ite1 = a.begin();
    array<int,5>::const_iterator ite2 = a.begin();
    auto ite3 = a.rbegin();
    *ite1 = 3;
    cout << *ite1 << endl;
    //*ite2 = 4; // 这里不行,说向只读地位写数据
    cout << *ite2 << endl;
    cout << *ite3 << endl;
 
    return 0;
}

从这里能够看进去,编译器应该是依据右边变量的类型来决定到底要调用哪个函数的。而 *ite3 这里输入了 5,阐明在 rbegin 反转了地位和方向。

size、max_size、empty 函数

函数原型如下:

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

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

constexpr bool
empty() const noexcept { return size() == 0; }

_Nm 是在申明一个 array 的时候就固定的数值,标示它的元素个数,因为 array 是容量固定的容器,所以它的 size()=max_size(),当 empty 返回为真的时候则阐明该容器一个元素都没有。

下标 [] 及 at 函数

还是看一下原型:

// 重载了 operator[]当前容许咱们像应用数组一样应用 array
_GLIBCXX17_CONSTEXPR reference
operator[](size_type __n) noexcept
{return _AT_Type::_S_ref(_M_elems, __n); }

constexpr const_reference
operator[](size_type __n) const noexcept
{return _AT_Type::_S_ref(_M_elems, __n); }

_GLIBCXX17_CONSTEXPR reference
at(size_type __n)
{if (__n >= _Nm)
std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu)"
                ">= _Nm (which is %zu)"),
            __n, _Nm);
return _AT_Type::_S_ref(_M_elems, __n);
}

constexpr const_reference
at(size_type __n) const
{
// Result of conditional expression must be an lvalue so use
// boolean ? lvalue : (throw-expr, lvalue)
return __n < _Nm ? _AT_Type::_S_ref(_M_elems, __n)
: (std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu)"
                   ">= _Nm (which is %zu)"),
               __n, _Nm),
 _AT_Type::_S_ref(_M_elems, 0));
}

重载符函数 operator[]和 at 函数都实现了两个,与下面的迭代器一样,依据左值判断具体调用哪一个函数。

依据代码实现看,其实 [] 和 at 实现一样,只不过下标 [] 如果取了不在容器范畴内数据,不会抛出谬误,而 at 函数则会,看上面代码:

#include <iostream>
#include <array>
using namespace std;

int main()
{array<int,5> a= {1,2,3,4,5};
    cout << a[6];// 这里不会报错
    //cout << a.at(6);// 此处会报错:terminate called after throwing an instance of 'std::out_of_range'
    a[3] = 100;
    cout << "a[3]=" << a[3] << endl;
    return 0;
}

所以应用的时候,如能确定不会超出容器范畴,则能够应用[],否则倡议应用 at,避免出现一些莫名其妙的问题。

另外因为 [] 和 at 返回返回的都是援用,所以咱们能够间接通过这两种形式去批改 array 中元素的值。

front、back、data 函数

array 容器是不存在 push 之类往里面写数据的函数的,因为它容量固定,但它也提供了从头和尾取数据的函数:

_GLIBCXX17_CONSTEXPR reference
front() noexcept
{return *begin(); }

constexpr const_reference
front() const noexcept
{return _AT_Type::_S_ref(_M_elems, 0); }

_GLIBCXX17_CONSTEXPR reference
back() noexcept
{return _Nm ? *(end() - 1) : *end();}

constexpr const_reference
back() const noexcept
{return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1)
       : _AT_Type::_S_ref(_M_elems, 0);
}

_GLIBCXX17_CONSTEXPR pointer
data() noexcept
{return _AT_Type::_S_ptr(_M_elems); }

_GLIBCXX17_CONSTEXPR const_pointer
data() const noexcept
{return _AT_Type::_S_ptr(_M_elems); }

其实认真看就会发现,front 和 back 返回的就是援用,与下标和 at 类型统一,而 data 返回的则是指针与迭代器应用统一,所以他们的应用能够参考下面的代码,这里就不再具体阐明了。

array 的实现原理

咱们后面说了 array 是一个容量大小固定的数组,那么它是怎么实现的呢?

咱们看一下,array 头文件外面是这样定义的,如下:

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

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

  static constexpr _Tp*
  _S_ptr(const _Type& __t) noexcept
  {return const_cast<_Tp*>(__t); }
};
template<typename _Tp, std::size_t _Nm>
struct array
{
    ......
    // 这里对类型取别名
    typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
    typename _AT_Type::_Type                         _M_elems;
    ......
};

能够看进去_M_elems 是一个依据咱们指定元素个数定义的数组,而元素类型和元素个数都是依据咱们申明 array 对象时模板实参决定的,而返回援用还是指针则是依据 _S_ref_S_ptr这两个动态成员函数来决定的。

array 说白了,就是在一个固定大小的数组根底上进行了一些封装,且应用了模板,让咱们能够灵便定义各种类型的数组,既然是数组,那必然是一段间断的地址空间,对于一段间断的地址空间,不论是获取数据还是批改数据都能够在常量复杂度下实现,所以 array 效率也还不错。而相比于一般的数组,因为 array 做了封装,只能通过它提供的接口去操作数组,又保障了肯定的安全性,所以如果想应用固定大小的数组,举荐应用 array 呀。

如果我的文章对你有用,麻烦点个赞呗。

退出移动版