とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

C++0x std::is_sorted

VC++2008 の is_sorted は効率わるくね?というエントリ。
algorithm ファイル内に is_sorted があります。以下実装引用

template<class _FwdIt> inline
	bool is_sorted(_FwdIt _First, _FwdIt _Last)
	{	// test is range is ordered by operator<
	_DEBUG_RANGE(_First, _Last);
	for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
		if (_DEBUG_LT(*_Next, *_First))
			return (false);
	return (true);
	}

for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)

この強調部分,ループのたびに比較する必要あるのでしょうか?
私が(上のコードに気付く前に)実装してたコードはこんなの。

template<class ForwardIterator> inline
 bool is_sorted(ForwardIterator first, ForwardIterator last)
{
 if(first != last){
  for(ForwardIterator next = first;; ++first){
   if(++next == last)break;
   if(*next < *first)return false;
  }
 }
 return true;
}

最初の一回だけ first != last の比較してます。これだとバグることあるのかな…。自信ないー。