• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

超细化STL中数组容器的使用和实现原理分析

超细化STL中数组容器的使用和实现原理分析

浏览次数:
评论次数:
编辑: 乐咏
信息来源: 51CTO博客
更新日期: 2021-06-11 01:09:23
摘要

超详细STL之array容器使用及实现原理解析,说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。本篇文章讲述STL中array的使用及原理。导读array其实是一个固定大小的数组,元素类型及大小在声明的时候指定,原型如下:template<typename_Tp,std::size_t_Nm>structarray{...};有些书上说array也是一个class,

  • 资讯详情

解释一下,我用的是gcc7.1.0编译器,标准库的源代码也是这个版本。

本文介绍了数组在STL中的使用和原理。

导读

数组实际上是一个固定大小的数组。声明时指定元素类型和大小。原型如下:

templatetypename _Tp,std:size _ t _ Nm

结构数组

{

.

};

有的书上说数组也是一个类,但是我在这个版本里看到的是struct,但是没关系。除了一些细微的方面,struct和class没有太大区别。这里我们可以看到数组实际上是一个模板类。

array的初步使用

要使用数组,必须包含头文件数组并声明标准命名空间,然后才能使用它。

下面是一个简单的例子:

#包含数组

#包含iostream

int main()

{

std:arrayint,5 a={1,2,3,4,5 };

for(auto i:a)

{

std:cout '值为' i std:endl

}

返回0;

}

fill()和swap()的使用

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

//fill函数是将当前数组中的所有元素填充为参数_ _ u。

void fill(const value _ type _ _ u);

//交换是交换两个数组数据

void swap(array _ _ other)no except(_ AT _ Type : _ Is _ northrow _ swapp able : value);

看看这个用例:

#包含数组

#包含iostream

int main()

{

std:arrayint,5 arr1

arr 1 . fill(5);

for(auto i:arr1)

{

std:cout 'arr1值为' i std:endl

}

std:arrayint,5 arr2={1,2,3,4,5 };

arr 2 . swap(arr 1);

for(auto i:arr1)

{

std:cout 'arr1值为' i std:endl

}

for(auto i:arr2)

{

std:cout 'arr2值为' i std:endl

}

返回0;

}

这里需要注意的一点是,arr1和arr2的元素类型和大小必须完全一致才能使用swap函数,因为使用swap的前提是类型必须完全一致,数组容器的类型包含两个模板参数:元素类型和元素编号,如果不一致就不能在编译时传递。

迭代器函数

//这里value_type是定义数组时指定的元素类型。例如,在上面的示例中,它是int类型

typedef value_type*迭代器;

typedef const value _ type * const _ iterator;

//返回一个可读写的迭代器,指向当前数组的第一个元素

_ GLIBCXX17 _ CONSTEXPR迭代器

begin() noexcept

{ return iterator(data());}

//返回指向当前数组第一个元素的只读迭代器

_ GLIBCXX17 _ CONSTEXPR const迭代器

begin() const noexcept

{ return const _ iterator(data());}

//返回一个可读可写的迭代器,指向当前数组最后一个元素的下一个位置

_ GLIBCXX17 _ CONSTEXPR迭代器

end() noexcept

{ return iterator(data()_ Nm);}

//返回一个只读迭代器,指向当前数组最后一个元素的下一个位置

_ GLIBCXX17 _ CONSTEXPR const迭代器

end() const noexcept

{ return const _ iterator(data()_ Nm);}

//返回一个可读可写的反向迭代器,指向当前数组最后一个元素的下一个位置,即指向最后一个元素

_ GLIBCXX17 _ CONSTEXPR reverse迭代器

rbegin() noexce

pt { 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呀。

标签: STL array
为什么这个算法执行时间这么长?
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多