1.range的概念
“Ranges”实际上可理解为一个接口规范(C++20中的concept),它针对集合,提供begin()和end()两个方法,返回一个指示类(iterator),然后就可以枚举集合中的所有元素。由此,以前标准库中所有的容器类都满足range定义。
(注:集合应包括数组、链表等“一维”结构类型,也应该包括矩阵、树等“二维”结构类型,现在的range因有先后顺序的概念,因而在逻辑上是线性结构)。
按照一个集合可以进行如何枚举,有下面的特征:
将以前的容器类按照上面的标准进行分类如下:
另外,如果按读与写进行分类,可有input_range和output_range。集合不同,与之相关的iterator也不同(见下面描述)。
2.iterator category
iterator是集合访问的“指示器”,正是通过它才能访问某个特定元素和如何访问集合元素。根据集合的不同,iterator也不同,目前有6种iterator类型。
- input iterator:只能向前移动,每次只能移动一步,只读且只能读一次它指向的东西。它以一个输入文件中的 read pointer为原型, istream_iterator 就是这一种类的典型代表。
- output iterator:只能向前移动,每次只能移动一步,只写且只能写一次它指向的东西。它以一个输出文件中的 write pointer为原型,ostream_iterator是这一种类的典型代表。
- forward iterator:在 input和 output iterator基础上,加上可以多次读写它指向的东西,即可用于 multi-pass 运算。单向访问数据结构的iterator都可属于此类。
- bidirectional iterator:在 forward iterator基础上,加上和向前一样的向后移动的能力。双向链表以及可以双向访问的set,map等的iterator都属于此类。
- random access iterator:在bidirectional iterator基础上,加上了 "iterator arithmetic"(“迭代器运算”)的能力,即在常量时间里向前或者向后跳转一个任意的距离,有点类似于指针运算。random access iterator是以pointer(指针)为原型的,vector,deque 和 string 的 iterator属于此类。
- contiguous iterator:在random access iterator基础上,要求元素的存储区域是连续的,即要求std::pointer_from(i) == std::addressof(*i)及std::pointer_from(i + n) == std::pointer_from(i) + n。contiguous iterator是以数组为原型的,vector, string的 iterator属于此类,但deque的iterator通常不是。
下图是关于几类iterator的描述(来自于网络)。
3.range的意义
Range概念的出现,感觉上把集合类(容器类)的概念更抽象化(学术化)了,ranges库中有许多concept,从外部access的角度,对以前的各种容器类/枚举类进行了划分,概念化后,对容器类的扩展和自定义都有帮助。
另外,STL在使用上,大致有两个不方便,一是大量应用iterator,二是集合操作写法不直观(简洁)。
Iterator主要有两个作用:用于移动元素的指示位置(操作符:+,-,++,--)和得到元素内容(操作符:->,*),如果不是适用于集合整体,必须用iterator指明范围,因此集合操作中存在大量iterator,当然,还有一种办法是构造一个子集,然后将操作施加于子集。
有了各种range::view的操作后,就不需iterator了,从这个意义上讲,range的一个作用可以隐藏iterator。
4. ADL(Argument-dependent lookup)
ADL(Argument-dependent lookup)的意思是当编译器对无限定域的函数调用进行名字查找时,除了当前名字空间域以外,也会把函数参数类型所处的名字空间加入查找的范围,最明显的例子如在一个命名空间中,重载了符号+,我们在使用这个+重载函数时,可以不指定其所在的命名空间,编译器会自动给我们加上:using XXX。
namespace NA
{
class number
{
public:
number() {};
};
void doit(number& one)
{
std::cout<<"NA doit "<<std::endl;
}
}
namespace NB
{
class number
{
public:
number() {};
};
void doit(number& one)
{
std::cout<<"NB doit "<<std::endl;
}
}
int main()
{
NA::number aa;
doit(aa); // invoke NA::doit()
NB::number bb;
doit(bb); // invoke NN::doit()
}
上面例子中的number类和doit函数完全相同,main中调用doit时并没有指定namespace,而靠的是其参数的namespace找到NA或NB。
5.定制点对象Customization point object(CPO)
ranges库中有许多被称为“定制点对象Customization point object)”的类(函数),如range:begin等。所谓Customization point object,顾名思义,是库的编写者为扩展库的适用范围,将某个接口开放出来,使用者可以按规则进行自定义,即“框架”由库提供,“实现”由使用者提供,最终的代码中库通过Customization point来调用使用者的代码,二者完美结合。例如类中虚函数其实就可以看作是一种Customization point。将std::range:begin等写成定制点对象方式,无非想让其更加generic。
函数的转发调用,也是一种实现CP的方法,例如上面的begin,最简单的实现示意如下:
auto range::begin(T a, Args…)
{
return a.begin(Args…)
}
但是作为库的话,就不能如上面那么简单了。下面这个例子是2014年Eric Niebler博文(https://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/)中提供的一个CPO的例子,大概是现在range::begin的一个简化示意,稍有改动。
namespace mystd
{
namespace __detail
{
// define begin for arrays
template<class T, size_t N>
constexpr T* begin(T (&a)[N]) noexcept
{
return a;
}
// Define begin for containers (trailing return type needed for SFINAE)
template<class _RangeLike>
constexpr auto begin(_RangeLike && rng) //->decltype(std::forward<_RangeLike>(rng).begin())
{
return std::forward<_RangeLike>(rng).begin();
}
struct __begin_fn
{
template<class R>
constexpr auto operator()(R && rng) const //-> decltype(begin(std::forward<R>(rng)))
{
return begin(std::forward<R>(rng));
}
};
}
// To avoid ODR violations:
template<class T>
struct __static_const
{
static constexpr T value{};
};
template<class T>
constexpr T __static_const<T>::value;
// std::begin is a global function object!
namespace
{
constexpr auto const & begin =
__static_const<__detail::__begin_fn>::value;
}
}
namespace NS {
struct S {};
void * begin( S & s ) {std::cout<<"here"; return nullptr;}
}
int main()
{
NS::S s;
void*p = mystd::begin(s); // calls NS::begin(s)
}
这个例子有点晦涩,可作为参考,结果是,虽然看起来调用的是mystd空间中的begin,其实是调用NS中的begin。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)