9.1.01_vector(ベクトル)

12782 ワード
vector(ベクトル)
C++のデータ構造で、正確にはクラスです.それは1つの動的な配列に相当して、プログラマーが自分の必要な配列の規模がどれだけ大きいかを知ることができない時、それを使って問題を解決して最大の節約空間の目的を達成することができます.
1.ファイルの内容:
まず、プログラムの先頭に#includeを追加して必要なクラスファイルvectorを含め、必ずusing namespace stdを追加します.
#include 
#include 

using namespace std;

2.変数宣言:
  • 例:1次元の配列に代わるintベクトルを宣言する:vectora;(int配列a[]が宣言され、サイズが指定されていないため、動的に削除を追加できます).
  • 例:2次元配列の代わりにvectorを用いた.実際には1次元配列ベクトルを宣言すればよいが、1つの配列の名前は実際にはそのヘッダアドレスを表すので、1つのアドレスのベクトルを宣言すればよい.すなわち、vector>a.は3次元配列の代わりにベクトルを理想的に使用するのと同じであり、vector>aである.さらに上へこのように押す.
    • //     
vector  a;
//   
vector  b;
//   
vector  c;

    3.具体的な使い方及び関数呼び出し:
    3.1関数リスト
    メソッド名|説明--|push_back|配列の最後にデータpopを追加back|配列の最後のデータatを削除|番号付け位置を取得するデータbegin|は、容器の最初の要素end|を指す反復器iteratorを返し、容器の最後の要素の次の位置front|配列ヘッダを取得する参照back|は配列の最後のユニットの参照max_を取得するsize|得られるvectorの最大サイズは、現在のvectorが割り当てたサイズsize|現在使用されているデータのサイズresize|現在使用されているデータのサイズを変更し、現在使用されているデータより大きい場合、デフォルト値reserve|現在のvecotrに割り当てられたスペースのサイズを変更erase|ポインタが指すデータ項目clear|を削除現在のvectorrbegin|をクリア|逆順序反復器reverse_を返すiterator、コンテナの最後の要素rend|を指す逆反復器reverse_を返します.iteratorは、容器cの最初の要素の前の位置empty|を指し、vectorが空のswap|であるか否かを判断し、別のvectorとデータを交換する
    3.2参照コード
  • 基本用法:
    •     int b = 5;
    a.push_back(b);
    a.push_back(8);
    a.push_back(10);
    a.push_back(22);
    cout << "a's capacity : " << a.capacity() << endl;
    cout << "a[0] : " << a[0] << endl;
    cout << "--------------------------------" << endl << endl;
  • 印刷vectorのすべての数字
    • p_vec(vector  *vec)
{
    cout << "vec's capacity : " << vec->capacity() << endl;
    cout << "vec's size : " << vec->size() << endl;
    
    //    
    vector::iterator iter = vec->begin();  
    while (iter != vec->end())  
    {
        cout << *iter << "\t";
        iter++;
    }
    
//    //    
//  for(vector::iterator iter=vec->begin(); iter!=vec->end(); iter++)
//  {
//      cout << *iter ;
//  }

    cout << endl << endl; 
}
  • 詳細実装
    •     dump_vec(&a);
    
    cout << "a.push_back(2)" << endl;
    a.push_back(2);
    dump_vec(&a);
    
    cout << "a.pop_back()" << endl;
    a.pop_back();
    dump_vec(&a);
    
    cout << "a.at(0): " << a.at(0) << endl; 
    cout << "a.back(): " << a.back() << endl; 
    cout << "a.front(): " << a.front() << endl; 
    cout << endl;
    
    cout << "a.max_size(): " << a.max_size() << endl; 
    cout << "a.capacity(): " << a.capacity() << endl; 
    cout << "a.size(): " << a.size() << endl; 
    cout << endl;

    cout << "a.resize(2)" << endl;
    a.resize(2);
    dump_vec(&a);
    
    cout << "a.resize(4)" << endl;
    a.resize(4);
    dump_vec(&a);
    
    cout << "a.resize(9)" << endl;
    a.resize(9);
    dump_vec(&a);
    
    cout << "a.reserve(6)" << endl;
    a.reserve(6);
    dump_vec(&a);
    
    cout << "a.reserve(10)" << endl;
    a.reserve(10);
    dump_vec(&a);
    
    //a.insert(pos,elem);   pos      elem  
    cout << "a.insert(a.begin() + 4, 9)" << endl;
    //       ，  vector capacity          
    vector::iterator pos = a.begin() + 3;
    for(int i=0; i<3; i++)
    {   
        pos = a.begin() + 3;
        a.insert(pos + i, 9);
    }
    dump_vec(&a);
    
    //a.erase(beg,end)-  [beg,end)      
    cout << "a.erase(pos)" << endl;
    a.erase(pos);
    dump_vec(&a);
    
    cout << "a.erase(pos, pos+2)" << endl;
    a.erase(pos, pos+2);
    dump_vec(&a);
    
    //a.rbegin()          ，     c       
    //a.rend()          ，     c           
    cout << "a.rbegan() & a.rend()" << endl;
    for(vector::reverse_iterator r_iter=a.rbegin(); r_iter!=a.rend(); r_iter++)
    {
        cout << *r_iter << "\t";
    }
    cout << endl;
    dump_vec(&a);
    
    //a.swap(b)     vector    
    vector  m;
    m.push_back(1);
    m.push_back(2);
    m.swap(a);
    dump_vec(&a);
    
    //a.empty()   vector    
    cout << "a.empty() : " << a.empty() << endl;
    cout << endl;
    
    //a.clear()      vector
    cout << "a.clear()" << endl;
    a.clear();
    cout << "a.empty() : " << a.empty() << endl;

    4.メモリ管理と効率
    4.1 reserve()関数を用いて容量サイズを事前に設定し、複数回の容量拡張による効率低下を回避
    STL(Standard Template Library標準テンプレートライブラリ)コンテナについて、最も称賛される特性の1つは、それらの最大サイズを超えない限り、あなたが入れたデータを収容するのに十分な大きさに自動的に増加することです.(この最大値を知るには、max_sizeというメンバー関数を呼び出すだけです.)
    vectorとstringについては,より多くの空間が必要であればreallocのような考え方でサイズを大きくする.vectorコンテナはランダムアクセスをサポートするため,効率を向上させるために内部で動的配列を用いて実現される.reserve()によって特定のサイズが申請されると、常に指数境界によって内部バッファが増大する.
    Insertまたはpush_を行う場合backなどの要素を増やす操作では,このとき動的配列のメモリが足りない場合は,現在の大きさの1.5~2倍の新しいメモリ領域を動的に再割り当てし,元の配列の内容をコピーする.したがって、一般的には、アクセス速度は一般配列と同じであり、再割り当てが発生した場合にのみパフォーマンスが低下します.上のコードが教えてくれたように.
    pop_back操作の場合、capacityはvector容器の要素が減少したために低下することはなく、操作前のサイズを維持します.vectorコンテナでは、push_を行う必要があるデータが大量にある場合backは、reserve()関数を使用して容量サイズを事前に設定する必要があります.そうしないと、容量拡張操作が多く発生し、効率が低下します.
    reserveメンバー関数を使用すると、必要な再割り当ての回数を最小限に抑えることができ、真の割り当てのオーバーヘッドと反復器/ポインタ/参照の失効を回避できます.しかし、reserveがなぜそうできるのかを説明する前に、時々困惑する4つの関連メンバー関数を簡単に紹介します.標準コンテナでは、vectorとstringだけがこれらの関数をすべて提供します.
  • size()は、容器にどれだけの要素があるかを教えてくれます.コンテナが収容する要素にどれだけのメモリが割り当てられているかは教えてくれません.
  • capacity()は、コンテナが割り当てられたメモリにどれだけの要素を収容できるかを示します.それは、コンテナがそのメモリにどれだけの要素を収容できるかであり、どれだけの要素を収容できるかではありません.vectorまたはstringにどれだけ消費されていないメモリがあるかを知りたい場合は、capacity()からsize()を減算する必要があります.sizeとcapacityが同じ値を返すと、コンテナに空き容量がなくなり、次の挿入(insertやpush_backなど)によって上記の再割り当てステップが開始されます.
  • resize(Container::size_type n)強制的に容器をn個の要素を収容するように変更した.resizeを呼び出すとsizeはnを返します.nが現在のサイズより小さい場合、コンテナの末尾の要素は破棄されます.nが現在のサイズより大きい場合、新しいデフォルト構造の要素がコンテナの末尾に追加されます.nが現在の容量より大きい場合、要素が追加される前に再割り当てが発生します.
  • reserve(Container::size_type n)は、容器の容量を少なくともnに変更することを強制し、提供されるnは現在のサイズより小さくない.これは、容量が増加する必要があるため、一般に再割り当てを強制する.(nが現在の容量より小さい場合、vectorはそれを無視し、この呼び出しは何もせず、stringはその容量をsize()とnの大きな数に減らす可能性がありますが、stringのサイズは変わりません.私の経験では、reserveを使用して1つのstringから余分な容量を修正するのは一般的に「交換テクニック」を使用するよりも、条項17のテーマです.)

    • このプロフィールでは、エレメントを挿入する必要があり、コンテナの容量が不足している場合に再割り当てが発生することを示しています.(メンテナンスされた元のメモリの割り当てと回収、オブジェクトのコピーと分析、反復器、ポインタ、参照の失効を含む).したがって、再割り当てを回避する鍵はreserveを使用してコンテナの容量をできるだけ早く十分に大きく設定することであり、コンテナが構築された後に立刻することが望ましい.
    たとえば、1～1000の値を収容するvectorを構築したいとします.reserveは使用されていません.このようにすることができます.
    vector v;
for (int i = 1; i <= 1000; ++i)
{ 
 v.push_back(i);
}

    ほとんどのSTLインプリメンテーションでは、このコードはループ中に2〜10回再割り当てされます.(10という数はおかしくありません.vectorは再割り当てが発生したときに容量を2倍にするのが一般的で、1000は約2^10に等しいことを覚えておいてください.)
    コードをreserveに変更し、これを入手します.
    vector v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i)
{
  v.push_back(i);
}

    これは、ループで再割り当ては発生しません.
    サイズと容量の関係では、vectorまたはstringの再割り当てがいつ挿入されるかを予言できます.また、コンテナへの反復器、ポインタ、参照がいつ挿入されるかを予言できます.例えば、このコードを与えると、
    string s;
...
if (s.size() < s.capacity()) 
{
  s.push_back('x');
}

    push_backの呼び出しは、stringの容量がそのサイズより大きいことを保証するため、このstringを指す反復器、ポインタ、または参照を失効させない.push_を実行しない場合back、コードはstringの任意の位置でinsertを行い、挿入中に再割り当てが発生しないことを保証することができますが、string挿入に伴う反復器の失効の一般的なルールと一致し、挿入位置からstringの最後までの反復器/ポインタ/リードはすべて失効します.
    本条項の主旨に戻ると、通常、reserveを使用して不要な再割り当てを回避する場合が2つあります.
  • の最初の使用可能な状況は、容器に最後に現れる要素がどれくらいあるかを正確にまたはほぼ知っている場合です.そうすると、上のvectorコードのように、reserveの適切な数の空間を繰り上げるだけです.
  • の2つ目のケースは、必要な最大のスペースを保持し、完全なデータを追加すると、余分な容量を修正することです.

    • 4.2「交換テクニック」を使用してvector過剰空間/メモリを修正
    最大の容量から現在必要な容量に減らす方法があります.このように容量を減少する方法は、「適切に収縮する(shrink to fit)」と呼ばれることが多い.この方法は、vector(ivec)という文を1つだけ必要とする.swap(ivec);
    式vector(ivec)は、ivecのコピーである一時的なvectorを確立します.vectorのコピー構造関数がこの仕事をしました.ただし、vectorのコピーコンストラクション関数は、コピーされた要素に必要なメモリのみを割り当てるため、この一時vectorには余分な容量はありません.次に、一時vectorとivecにデータを交換させます.このとき、ivecは一時変数のトリミングされた容量しかありませんが、この一時変数はivecで使用されていなかった過剰容量を持っています.ここで(この文の最後)、一時vectorは破棄されるため、以前のivecで使用していたメモリが解放され、適切に縮小されます.
    4.3 STL Vectorのメモリをswapで強制的に解放する
    template < class T> void ClearVector( vector& v )
{ 
    vector vtTemp;
    vtTemp.swap( v );
}

    次のようになります.
    vector v ;
v.push_back(1);
v.push_back(3);
v.push_back(2);
v.push_back(4);
vector().swap(v);

//
v.swap(vector()); 

//    { }  tmp  { }     
{ std::vector tmp = v;   v.swap(tmp);   };

    5.Vectorメモリ管理メンバー関数の動作テスト
    C++STLのvectorは広く使われていますが、メモリの管理モデルについては様々な推測があります.次に、インスタンスコードテストでメモリの管理方法を理解します.テストコードは以下の通りです.
    #include 
#include 
using namespace std;

int main()
{
    vector iVec;
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //0   ，      0

    iVec.push_back(1);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //1   ，      1

    iVec.push_back(2);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //2   ，      2

    iVec.push_back(3);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //3   ，      4

    iVec.push_back(4);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //4   ，      4

    iVec.push_back(5);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //5   ，      8

    iVec.push_back(6);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //6   ，      8

    iVec.push_back(7);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //7   ，      8

    iVec.push_back(8);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //8   ，      8

    iVec.push_back(9);
    cout << "      : " << iVec.size() << endl;
    cout << "      : " << iVec.capacity() << endl; //9   ，      16
    /* vs2005/8          ，1.5   
       9        9 
       10      13
    */

    /*   effective stl        swap() */
    cout << "  vector     : " << iVec.size() << endl;
    cout << "  vector     : " << iVec.capacity() << endl;
    vector(iVec).swap(iVec);

    cout << "   vector       : " 
        << (vector(iVec)).size() << endl;
    cout << "   vector       : " 
        << (vector(iVec)).capacity() << endl;
    cout << "   ，  vector     : " << iVec.size() << endl;
    cout << "   ，  vector     : " << iVec.capacity() << endl;

    return 0;
}

    6.vectorの他のメンバー関数
  • c.assign(beg,end):[beg;end)区間のデータをcに割り当てる.
  • c.assign(n,elem):n個のelemのコピーをcに割り当てます.
  • get_allocator:コンストラクション関数を使用してコピーを返します.
  • c.~vector():すべてのデータを破棄し、メモリを解放します.

    • 7.備考:vectorの使用中のいくつかの問題について、ここで説明します.
  • このときbに対して別途値を付与場合はa[0]の値
    • に影響しない.
    vector  a;
int b = 5;
a.push_back(b);

    aベクトルに押し込む値はbの値、すなわちa[0]=bであり、このときa[0]とbは2つの異なるアドレスに格納.したがって、bの値を変更してもa[0]には影響しない.
  • このとき出力値は、b配列の初期化が始まる値ではなく、予測できない値である.
    • vector  a;
int *b;
b = new int[4];
b[0]=0;
b[1]=1;
b[2]=2;
a.push_back(b);
delete b;  //  b     
for(int i=0 ; i <3 ; i++)
{
   cout<

    一つのアドレス(ポインタ)をベクトルa,すなわちa[0]=bに押し込むので、bを解放するアドレスもa[0]のアドレスを解放するので、a[0]配列に格納数値も分からない.
    OSI基本参照モデル
    コンストラクション関数初期化リストのメンバー変数を初期化する必要がある場合