9

私は最近、無料の関数を好み、イテレータを明示的にコピーおよびインクリメント/デクリメントすることを好むようになりましstd::nextたstd::prev。現在、非常に特殊なケースで奇妙な動作が見られます。それをわかりやすく説明する助けをいただければ幸いです。

boost::any_range一部の で動作する補間/補外関数がありX_typeます。範囲型の完全な定義は次のとおりです。

boost::any_range <
    const X_type,
    boost::random_access_traversal_tag,
    const X_type,
    std::ptrdiff_t
>

はany_range、この特定のケースでは、iterator_range保持する 2 つのポインタからに割り当てられます。これは、 の領域の約半分のビューconst X_typeとして機能します。X_typedata()vector<char>

MSVC 2010 でアプリケーションをコンパイルすると、すべて正常に動作します。MinGW g++ 4.7.0 で同じコードをコンパイルすると、ある特定の場所でハングしているように見えました。

// Previously ensured conditions:
// 1) xrange is nonempty;
// 2) yrange is the same size as xrange.

auto x_equal_or_greater =
    std::lower_bound(std::begin(xrange),std::end(xrange),xval);

if (x_equal_or_greater == std::end(xrange))
{
    return *yit_from_xit(std::prev(x_equal_or_greater),xrange,yrange);
}

gdb のコードをステップ実行すると、単一のstd::prev呼び出しから戻るのに非常に長い時間がかかっただけで、動けなくなっていないことがわかりました。libstdc++ ではstd::advance、最終的には+=演算子の観点から実装されています。

return行を次のように置き換えるだけです。

auto xprev=x_equal_or_greater;
--xprev;
return *yit_from_xit(xprev,xrange,yrange);

パフォーマンスは再び素晴らしく、実質的に遅延はありません。

型が消去されたイテレータ ( のイテレータ) を使用することのオーバーヘッドは認識していますany_rangeが、それでも、上記の 2 つのケースは実際にそのような異なるコストを負担することになっていますか? それとも私は何か間違ったことをしていますか？

4

1 に答える 1

4

さて、SplinterOfChaos のコメントに返信した後、私は何かに気づきました。問題は、any_range の使用にあります。特に、3 番目の引数は、参照引数が であることを示しますconst int。ブースト イテレータ ファサードでは、参照が実際の参照ではない場合、 を使用するかstd::input_iterator_tag、または STL と同等のタグを提供しません。

厳密に言えば、順方向、双方向、およびランダムアクセスのすべての STL イテレータは、参照型に実際の参照を使用する必要があるという事実に関係しています。C++11 標準の 24.2.5 から:

クラスまたは組み込み型 X は、次の場合に前方反復子の要件を満たします。

— X は入力反復子 (24.2.3) の要件を満たします。

— X は DefaultConstructible 要件 (17.6.3.1) を満たします。

— X が変更可能な反復子の場合、参照は T への参照です。X が定数反復子の場合、参照は const T への参照です。

— 表 109 の式が有効であり、示されたセマンティクスを持っている。

— タイプ X のオブジェクトは、以下で説明するマルチパス保証を提供します。

この場合、std::input_iterator_tagその を照会すると whenが返されるiterator_categoryため、呼び出しがUndefined Behaviorstd::prev()に移行します。

いずれにせよ、解決策は (可能であれば) の使用をboost::any_range次のように変更することです。

  boost::any_range <
        const X_type,
        boost::random_access_traversal_tag,
        const X_type&,
        std::ptrdiff_t
    >

これにより、iterator_categoryofが発生しstd::random_access_iterator_tag、最初に期待したとおりに操作が実行されます。

于 2012-11-06T22:53:29.977 に答える