C++ コア ガイドライン:std::array と std::vector は友達です

シーケンシャル コンテナーのユース ケースの 99% では、std::array または std::vector を使用してもまったく問題ありません。何?信じられない場合は、この投稿を読んでください。

わかりました、今日は手短にできます。経験則は次のとおりです。 コンテナに要素を追加するか、コンテナから要素を削除する場合は、std::vector を使用します。そうでない場合は、std::array を使用します。

忙しい場合は読むのをやめて、そうでない場合は続けてください。

詳細

ガイドラインの経験則の理由は次のとおりです:SL.con.2:Prefer using STL vector 別のコンテナを使用する理由がない限り、デフォルトで

std::array と std::vector には次の利点があります:

<オール>
  • 最速の汎用アクセス (ベクトル化に適していることを含むランダム アクセス);
  • 最速のデフォルト アクセス パターン (begin-to-end または end-to-begin はプリフェッチャーに適しています);
  • 最小のスペース オーバーヘッド (連続レイアウトでは要素ごとのオーバーヘッドがなく、キャッシュに適しています)。
  • 3 番目のポイントについては、前回の投稿 C++ Core Guidelines:The Standard Library で既に書きました。インデックス演算子によるランダム アクセスの最初のポイントは明らかです。ですから、権威による証明が嫌いなら、2 番目の点について話させてください。全体像を把握するために、STL の順次コンテナーを次に示します。

    ご覧のとおり、標準テンプレート ライブラリには 5 つの連続したコンテナーがあります。ほとんどの場合、std::vector に要素を追加または削除する必要があるため、ユースケースによっては、std::vector が 95% 適合する場合があります。表にいくつかの補足事項を追加させてください。

    O(i) は、操作の複雑さ (ランタイム) を表します。したがって、O(1) は、コンテナーに対する操作の実行時間が一定であり、コンテナーのサイズに依存しないことを意味します。それとは反対に、O(n) は、ランタイムがコンテナーの要素の数に線形に依存することを意味します。 std::vector または std::array にとってそれはどういう意味ですか。要素のアクセス時間は、std::vector または std::array のサイズとは無関係ですが、k 倍の要素を持つ任意の要素の挿入または削除は k 倍遅くなります。もちろん、変更は std::vector に対してのみ可能です。

    std::array と std::vector は同様のアクセス時間保証を提供しますが、多くの開発者が無視している大きな違いが 1 つあります。通常、std::array はスタック上に作成され、std::vector の要素はヒープ上に作成されます。つまり、std::array は限られた数の要素しか持てませんが、std::vector は無限です。 要素数。

    std::vector の要素へのランダム アクセスは、std::deque の要素へのランダム アクセスと同じ複雑さ O(1) を持っていますが、どちらの操作も同じように高速であるという意味ではありません。この点については後で説明します。

    std::vector および std::deque は、C++11 以降の新しいメソッド shrink_to_fit でサポートされています。通常、std::vector または std:.deque が持つ要素の数 (サイズ) は、メモリが既に予約されている要素の数 (容量) よりも小さくなります。それは単純な理由です。 std::vector または std::deque のサイズは、新しいメモリの高価な割り当てなしで増加できます。新しいメソッド Shrink_to_fit を使用すると、std::vector と std::deque の容量をそのサイズに縮小できます。この呼び出しには拘束力はありません。つまり、ランタイムはそれを無視できます。しかし、一般的なプラットフォームでは、望ましい動作を常に観察しました。

    ダブル (std::list) またはシングル リンク リスト (std::forward_list) への挿入または削除に対する複雑さの保証 O(1) は、反復子が正しい要素を指している場合にのみ保証されます。 std::list と std::forward_list は排他的な保証を提供しますが、これは必要になる場合があります。 std::vector または std::deque を変更すると、反復子が無効になります。これは、std::list または std::forward::list には当てはまりません。

    非常に特別な std::forward_list をシーケンシャル コンテナーとして使用する十分な理由が必要です。 std::forward_list はメモリ要件とパフォーマンスに対して最適化されており、要素の挿入、抽出、または移動が隣接する要素にのみ影響する場合に適用できます。この特別な動作の理由は明らかです。単一のリンクされたリストとして、std::forward_list は前方反復子のみをサポートし、そのサイズさえ知りません。これが、STL の多くのアルゴリズムで std::forward_list を使用できない理由です。

    メモリの予測可能性

    std::vector の要素のアクセス時間と std::deque の要素の O(1) は同じ意味ではありません。これは私の簡単な実験であり、C++ Core Guidelines:The Remaining Rules to Performance の投稿で既に提供しています。これが、説明を非常に短くしている理由です。

    メモリから int を読み取ると、1 つの int のサイズを超えるサイズがメモリから読み取られます。キャッシュ ライン全体がメモリから読み取られ、キャッシュに格納されます。最新のアーキテクチャでは、キャッシュ ラインは通常 64 バイトです。メモリから追加の変数を要求し、この変数が以前のキャッシュにある場合、読み取りはこのキャッシュを直接使用し、操作ははるかに高速になります。

    std::vector、std::deque、std::list、および std::forward_list でこれが何を意味するか見てみましょう。サイズが限られているため、パフォーマンス テストでは意図的に std::array を無視します。

    これがキャッシュラインの理論でした。今、私は興味があります。 std::vector、std::deque、std::list、および std::forward_list からすべての要素を読み取って蓄積することに違いはありますか。小さなプログラムが答えを出すはずです。

    // memoryAcess.cpp
    
    #include <forward_list>
    #include <chrono>
    #include <deque>
    #include <iomanip>
    #include <iostream>
    #include <list>
    #include <string>
    #include <vector>
    #include <numeric>
    #include <random>
    
    const int SIZE = 100'000'000; 
    
    template <typename T>
    void sumUp(T& t, const std::string& cont){ // (6)
     
     std::cout << std::fixed << std::setprecision(10);
    
     auto begin= std::chrono::steady_clock::now();
     std::size_t res = std::accumulate(t.begin(), t.end(), 0LL);
     std::chrono::duration<double> last= std::chrono::steady_clock::now() - begin;
     std::cout << cont << std::endl;
     std::cout << "time: " << last.count() << std::endl;
     std::cout << "res: " << res << std::endl;
     std::cout << std::endl;
     
     std::cout << std::endl;
     
    }
    
    int main(){
     
     std::cout << std::endl;
     
     std::random_device seed; // (1)
     std::mt19937 engine(seed());
     std::uniform_int_distribution<int> dist(0, 100);
     std::vector<int> randNumbers;
     randNumbers.reserve(SIZE);
     for (int i=0; i < SIZE; ++i){
     randNumbers.push_back(dist(engine));
     }
     
     {
     std::vector<int> myVec(randNumbers.begin(), randNumbers.end());
     sumUp(myVec,"std::vector<int>"); // (2)
     }
    
     
     {
     std::deque<int>myDec(randNumbers.begin(), randNumbers.end());
     sumUp(myDec,"std::deque<int>"); // (3)
     }
     
     {
     std::list<int>myList(randNumbers.begin(), randNumbers.end());
     sumUp(myList,"std::list<int>"); // (4)
     }
     
     {
     std::forward_list<int>myForwardList(randNumbers.begin(), randNumbers.end());
     sumUp(myForwardList,"std::forward_list<int>"); // (5)
     } 
     
    }
    

    プログラム memoryAccess.cpp は、0 から 100 (1) までの最初の 1 億個の乱数を作成します。次に、std::vector (2)、std::deque (3)、std::list (4)、および std::forward_list (5) を使用して要素を蓄積します。実際の作業は関数 sumUp (6) で行われます。

    プログラムを最大限に最適化してコンパイルし、Linux と Windows で実行しました。 Linux と Windows の比較には興味がありません。デスクトップ PC とラップトップの比較になるからです。 4 つのコンテナーの読み取りパフォーマンスに興味があります。ここにあります:

    パフォーマンスの比較を理解しやすくするために、ここに図を示します。

    これらのパフォーマンスの数値を過大評価したくはありませんが、重要な観察事項が 1 つあります。コンテナがキャッシュ ラインを認識するほど、要素のアクセス時間は速くなります:std::vector> std::deque> (std::list, std::forward_list)

    次は?

    標準テンプレート ライブラリの連想コンテナについても同様の投稿を書くべきだと思います。私の見解では、それらは C++ コア ガイドラインでは過小評価されています。次の投稿は、std::map や std::unordered_map などの連想コンテナーについてです。


    No