is_sorted --sortの事後条件--

というわけで,ここまで長々訳の分からないことを書いておきながら,結論は至ってシンプルです.自前のfor文回すのが一番楽ですが,ここはあえて既存のアルゴリズムでやってみました.

template
inline
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred)
{
  ForwardIterator it(first);
  return equal(++first, last, it, std::not2(pred));
}

上のコードはcomp.lang.c++で書かれていたものを若干変更したものです.predがadaptableであることを要求しているのが唯一残念なところです.equalの使い方が本来期待されている使い方と異なっていますが,規格書読む限りはこれも正しい使い方であると思われます.ただし2つのiterator範囲がoverlapするので,equalが本来要求しているInputIteratorではなく,ForwardIteratorが必要になります.というかこのequalの使い方は結構( ・∀・)つ〃∩ ヘェーヘェーヘェーな感じ.
1つだけ注意として,Strict Weak Orderの否定が何を意味するかですが,上の議論から「!(a < b)」は「a > b または a <> b」を表すことになります.そしてこのequalは結局,隣接する要素a, b(要素の順序はこの順とする)において「a < b または a <> b が成り立つ」ということを確認しています.これがsortの事後条件をきちんと確認していることは上の議論のとおりです.
最後に余計ながら,自分が考えたコードを示しておきます.

template
inline
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred)
{
  return std::adjacent_find(
    first, last, 
    boost::lambda::bind(pred, boost::lambda::_2, boost::lambda::_1)) 
      == last;
}

lambda::bind持ち出していますが,やっていることは非常に単純です.ちなみにこのコードはequalによるis_sortedのコードとまったく等価です(一見しただけでは分かりにくいですが).
後,他にiteratorを逆回しにしてアルゴリズムに突っ込むコードもありましたが,iteratorに対する要求がForwardからBidirectionalになってしまうので避けました.