C++0x std::is_sorted - 危ないRiSKのブログ

2009-12-06 (Sun)

■[C++]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;
}