SGI STL笔记（Concept的使用）

最近在看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>());
}