15

STL の多くのテンプレート アルゴリズムで、引数が参照ではなく値で渡されるのはなぜだろうか。<iterator> ヘッダーの例を次に示します。

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last);

この関数に 2 つの反復子を渡すと、それらがコピーされます。私の素朴な考えでは、イテレータ オブジェクトのコピーを避けるために、これらのイテレータを const-reference で渡す方がよいでしょう。

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (const InputIterator &first, const InputIterator &last);

イテレータは一般に非常に小さなオブジェクトであり、それらのコピーは高価ではないと言えます。それでもなお、安価なコピーは、まったくコピーしないよりも高価になります。

では、STL バージョンで反復子が値渡しされる理由は何ですか?

ありがとうございました!

4

4 に答える 4

14

私の頭に浮かんだことconstで、参照の内容に反することの1つは、イテレータを使用するときに変更する必要があることです。

別の実装の詳細は、イテレータが実際にはポインタとして実装されているだけである可能性があります。ほとんどの場合、参照も同様です。ポインターを値で渡す場合は、一度コピーしますが、必要な場合にのみ逆参照します。ただし、反復子ポインター自体が参照ポインターによって渡される場合は、反復子を取得するために、最初に参照ポインターを逆参照する必要があり、反復子にアクセスするたびにこれを実行する必要があります。それは余計です。

于 2013-08-01T09:57:12.987 に答える
6

stdイテレータの概念は、ポインタの一般化です。コンテナーの反復子は、std通常、単一のポインターを構成する型として実装されます。ポインターと同じくらい安価にコピーできる引数の型の場合、引数を参照で渡すと、値で渡すよりもコストがかかります。オブジェクトの値を使用する前に、オブジェクトへの参照を逆参照する必要があります。詳細については、この回答を参照してください。

ほとんどすべてのstdアルゴリズムはイテレータのコピーを作成する必要があるため、最高のパフォーマンスを得るためには、イテレータを安価にコピーできることがすでに不可欠です。このため、参照渡しよりも値渡しの方がはるかにコストがかかるイテレータを見つけることは非常にまれです。

および他の多くのアルゴリズムの場合、std::distanceアルゴリズム全体が非常に単純であるため、コンパイラによって呼び出しがインライン化される可能性が非常に高くなります。呼び出しがインライン化されている場合、引数が参照渡しか値渡しかは関係ありません。[インライン関数呼び出しはインライン関数宣言と同じではないことに注意してください!]

イテレータが参照渡しよりも値渡しの方がコストがかかり、関数呼び出しがインライン化されていない場合、右辺値参照によってイテレータを渡すための引数を作成できます。このようなまれなケースでのパフォーマンスの向上は、おそらく追加の複雑さに見合うものではありません。

于 2013-08-01T10:09:34.027 に答える
2

ほとんどのアルゴリズムは引数を変更します。たとえば、distance次のように実装できます1 :

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last) {
    typename iterator_traits<InputIterator>::difference_type result{};
    while (first++ != last)
        ++result;
    return result;
}

first参照として渡すと、明らかにこれは機能しませんconst

constまた、ほとんどの呼び出しコンテキストでは呼び出し元のオブジェクトを変更できないため (たとえば、関数に結果を渡す場合) 、非参照として渡す場合も機能しませんcontainer.begin()

もちろん、参照渡し、関数constでコピーを作成してから変更することもできます。その時点で、私たちはまったく何も得られなかったでしょう。

C++ 標準の推奨事項であるイテレータはコピーが安価な軽量の型である必要があるため、値で渡す方が簡単で、ほとんどの場合より効率的です。

それでもなお、安価なコピーは、まったくコピーしないよりも高価になります。

違います。また、参照をコピーする必要があります (インライン化されていない関数呼び出しの場合、参照はポインターとして実装されます)。そして、オーバーヘッドも追加するそのポインターを逆参照する必要があります。多くの場合、ポインターをコピーするのと同じくらい安価であり、間接参照のオーバーヘッドが発生しないストレート コピーと比較して。


1もちろん、実際の実装は、ランダム アクセス イテレータが線形ではなく一定のランタイムを持つように最適化されます。上記の実装は説明のみを目的としています。

于 2013-08-02T10:01:19.840 に答える