最近在看sgi stl 3.3的代码,写一些感想和要点,就算是做读书笔记吧。
之前关于Concept部分的代码没太关注,仅仅把重点放到数据结构和算法的具体实现上,sgi stl的算法的代码总体感觉冗余的code很多,今天仔细看了其中的一个:
- template <class _ForwardIter>
- bool is_sorted(_ForwardIter __first, _ForwardIter __last)
- {
- __STL_REQUIRES(_ForwardIter, _ForwardIterator);
- __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
- _LessThanComparable);
- if (__first == __last)
- return true;
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
- if (*__next < *__first)
- return false;
- }
- return true;
- }
- template <class _ForwardIter, class _StrictWeakOrdering>
- bool is_sorted(_ForwardIter __first, _ForwardIter __last,
- _StrictWeakOrdering __comp)
- {
- __STL_REQUIRES(_ForwardIter, _ForwardIterator);
- __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool,
- typename iterator_traits<_ForwardIter>::value_type,
- typename iterator_traits<_ForwardIter>::value_type);
- if (__first == __last)
- return true;
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
- if (__comp(*__next, *__first))
- return false;
- }
- return true;
- }
这个is_sorted函并不是C++ standard的一部分,拿它做例子只是因为它简单。
含义很清晰,就是判断[first, last)这个区间内部是否是有序的。第二个版本用户可以自定义比较函数。
为什么sgi stl不基于后者来实现前者呢?我把注意力放到了红色的两行,也就是_LessThanComparable concept的定义和__STL_BINARY_FUNCTION_CHECK的实现。
__STL_REQUIRES的定义:
- #define __STL_REQUIRES(__type_var, __concept) \
- do { \
- void (*__x)( __type_var ) = __concept##_concept_specification< __type_var >\
- ::__concept##_requirement_violation; __x = __x; } while (0)
这个宏通过显式定义模板参数来产生一个具体类型的定义,对于_LessThanComparable这个concept来说,就是定义了_LessThanComparable_concept_specification<__type_var>这个具体类型。
值得一提的是,上述代码仅仅是使编译器产生该类的定义,并对其进行语法检查。编译期就可以将上述的代码优化掉,不会影响运行期的效率。
下面是_LessThanComparable concept的声明:
- /* LessThanComparable Requirements */
- template <class _Type>
- struct _LessThanComparable_concept_specification {
- static void _LessThanComparable_requirement_violation(_Type __a) {
- _STL_ERROR::__less_than_comparable_requirement_violation(__a, __a);
- }
- };
_STL_ERROR::__less_than_comparable_requirement_violation的定义:
- template <class _Type>
- static _Type
- __less_than_comparable_requirement_violation(_Type __a, _Type __b) {
- if (__a < __b || __a > __b || __a <= __b || __a >= __b) return __a;
- return __b;
- }
返回值不重要,关键是类型_Type需要定义以上四种比较运算符。从这个可以看出_LessThanComparable concept的定义式超出了仅仅定义less这样的字面要求。
__STL_BINARY_FUNCTION_CHECK的实现相对简单,仅仅是判定制定的函数/仿函数定义符合后面参数制定的类型,这里就不列出了。
这样看起来,第一个is_sorted可以基于第二个版本实现,大体上是这样:
- template <class ForwardIter>
- bool is_sorted(ForwardIter first, ForwardIter last)
- {
- __STL_REQUIRES(_ForwardIter, _ForwardIterator);
- __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
- _LessThanComparable);
- return is_sorted(first, last, std::less<typename std::iterator_traits<ForwardIter>::value_type>());
- }
阅读(829) | 评论(0) | 转发(0) |