3

Vector back() メソッドが反復子の観点から実装されているのはなぜですか

reference back()
{   // return last element of mutable sequence
    return (*(end() - 1));
}

のようなものではなく...

return (*(_Myfirst + size()));

この質問の背景:

私は最近、一部のレガシー コード (アロケータの実装) の最適化に取り組んでおり、かなりの時間が に費やされていることに気付きましたstd::vector::back()。したがって、さまざまなコレクション（Vector vs List vs Deque）を使用していくつかの実験を行いback()ましたが、基本的にはコレクション内の最後の要素を取得しているためvector::back()、vector[size()-1]

これは私がテストに使用したコードです:

#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <boost/timer/timer.hpp>

int RandomNumber () { return (rand()%100); }



void doVector( std::vector<int>& test_vec )
{
    std::cout << "vect back() = " << test_vec.back() << std::endl;
    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_vec.back();
    }
}

void doVector2( std::vector<int>& test_vec )
{
    std::cout << "vect [size()-1] = " << test_vec[test_vec.size()-1] << std::endl;
    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_vec[test_vec.size()-1];
    }

}


void doList( std::vector<int>& test_vec )
{
    std::list<int> test_list(test_vec.begin(),test_vec.end());
    std::cout << "list back() = " << test_list.back() << std::endl;

    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_list.back();
    }

}

void doDeque( std::vector<int>& test_vec )
{
    std::deque<int> test_deq(test_vec.begin(),test_vec.end());
    std::cout << "Deque back() = " << test_deq.back() << std::endl;

    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_deq.back();
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> test_vec(100);
    std::generate(test_vec.begin(), test_vec.end(), RandomNumber );

    doVector(test_vec);
    doVector2(test_vec);
    doList(test_vec);
    doDeque(test_vec);
}

結果は次のとおりです。

デバッグをオンにして、リリース時間の最適化を秒単位でオフにしたため、結果を削除しました。

明らかに、vect[ size() - 1] を使用することで大幅に利益が得られます。さらに、front() よりも vect[0] を使用することで利益も得られます。私は自分自身をベクトルに縛り付けていることを認識していますが、短期的にはそれが私の選択した方向です (クイックウィン)。しかし、それは私に考えさせられました - なぜ front() と back() のベクトル実装は内部で非効率的な実装を使用するのですか?

vect back() = 41 0.183862 秒の壁、0.171601 秒のユーザー + 0.000000 秒のシステム = 0.171601 秒の CPU (93.3%)

vect [size()-1] = 41 0.416969 秒の壁、0.421203 秒のユーザー + 0.000000 秒のシステム = 0.421203 秒の CPU (101.0%)

list back() = 41 0.079119 秒の壁、0.078001 秒のユーザー + 0.000000 秒のシステム = 0.078001 秒の CPU (98.6%)

Deque back() = 41 0.186574 秒の壁、0.187201 秒のユーザー + 0.000000 秒のシステム = 0.187201 秒の CPU (100.3%)

明らかに、分析を行ったときに間違った結果を見ていました。これは、実装の選択を完全に裏付けているためです。この編集の前にこれを見た人には申し訳ありません.....

4

2 に答える 2

4

C ++仕様は、実装ではなくセマンティクスを定義します。std::vector<T, A>::back()仕様が示唆するものとは異なる実装を使用して実装された実装で重要な場合、実装は正しいことを実行する必要があります。明らかに、それでも正しいセマンティクスを提供する必要があります。

それが指定されている基本的な理由は、おそらく元の実装に由来します。のイテレータタイプstd::vector<T, A>は単なるaでしたT*（さまざまな理由でファッショナブルになったものですが、これはまだ有効な実装です）。最近std::vector<T, A>の実装では、ポインターに単純なラッパーを使用する傾向があります。

とはいえ、適切なコンパイラの場合、実際に表示されるオーバーヘッドは最適化する必要があります。どの最適化フラグを使用しましたか？

于 2012-10-28T19:09:34.547 に答える
1

あなたの質問から、デバッグを使用している_Myfirst + size()と思いますが、テストにビルドを使用していると確信していますか?ビルドのデバッグでは余分な時間がかかりますが、モードでは両方に同じ時間がかかります(少なくとも私のマシンでは を使用)MSVCiteratorreleasedebugiteratorreleaseMSVC 2010

于 2012-10-28T19:13:22.743 に答える