C++のvectorクラスの使い方と特性を深く理解する
5406 ワード
//
template < class T, class Alloc = allocator > class vector;
ベクトル(Vector)は、ダイナミックサイズ配列をカプセル化したシーケンシャルコンテナである.他のタイプのコンテナと同様に、さまざまなタイプのオブジェクトを格納できます.ベクトルは任意のタイプの動的配列を格納できると簡単に考えられる.
vectorクラスは、stringクラスと同様にvectorクラスが標準C++とともに導入された標準ライブラリの一部であり、vectorを使用するには関連するヘッダファイルを含む必要があります.
#include
容量特性:
1.シーケンス
シーケンスコンテナの要素は、厳密な線形シーケンスでソートされます.対応する要素には、要素のシーケンス内の位置からアクセスできます.
2.動的配列
シーケンス内の任意の要素への迅速な直接アクセスをサポートし、ポインタの計算によってもこの操作を行うことができます.操作は、シーケンスの最後に要素を比較的迅速に追加/削除する操作を提供します.
3.メモリディスペンサを感知できる(Allocator-aware)
コンテナは、メモリディスペンサオブジェクトを使用して、ストレージ要件を動的に処理します.
次の操作を行います.
vectorを使用するには,いわゆる配列習慣とSTL習慣の2つの異なる形式がある.
一、配列慣用法1.既知の長さのvectorを定義します.
vector< int > ivec( 10 ); // int ia[ 10 ];
ivec[インデックス番号]で要素にアクセスできます
if(ivec.empty()を用いて空か否かを判断する、ivec.size()は要素の個数を判断する.
2.vectorの要素はそのタイプに関連するデフォルト値に初期化されます.算術とポインタタイプのデフォルト値は0です.classタイプの場合、デフォルト値はこのようなデフォルト構造関数を呼び出すことで得ることができます.また、vector
組み込み配列の場合、配列の要素を定数値のセットに明示的に初期化できます.たとえば、次のようにします.
int ia[ 6 ] = { -2, -1, 0, 1, 2, 1024 };
同様の方法でvectorを明示的に初期化することはできませんが、vectorを既存の配列のすべてまたは一部に初期化することができます.vectorを初期化するために使用する配列の開始アドレスと配列の最下位要素の次の位置を指定するだけで実現できます.たとえば、次のようになります.
// ia 6 ivec
vector< int > ivec( ia, ia+6 );
ivecに渡された2つのポインタは、オブジェクトの値を初期化するための範囲をマークし、2番目のポインタは常にコピーする末尾要素の次の位置を指し、マークされた要素範囲は配列のサブセットであってもよい.たとえば、次のようにします.
// 3 ia[2], ia[3], ia[4]
vector< int > ivec( &ia[ 2 ], &ia[ 5 ] );
3.内蔵配列とは異なるvectorを別のvectorによって初期化したり、別のvectorに与えたりすることができる.
vector< string > svec;
void init_and_assign()
{
// vector vector
vector< string > user_names( svec );
// ...
// vector vector
svec = user_names;
}
二、STL習慣用法STL 9ではvectorの習慣用法が全く異なる.既知のサイズのvectorを定義するのではなく、空のvector vector
1.インデックス要素ではなくvectorに要素を挿入し、push_などの要素に値を割り当てます.back()操作は、vectorの後ろに要素を挿入するwhileループが標準入力から文字列シーケンスを読み込み、vectorに1つの文字列を挿入するたびに
string word;
while ( cin >> word ) {
text.push_back( word );
// ...
}
要素へのアクセスを反復するには、下付きオペレータを使用しますが
cout << "words read are:
";
for ( int ix = 0; ix < text.size(); ++ix )
cout << text[ ix ] << ' ';
cout << endl;
しかし、より典型的な方法はvectorオペレーションセットのbegin()とend()を使用して返される反復器iteratorペアです.
cout << "words read are:
";
for ( vector::iterator it = text.begin();
it != text.end(); ++it )
cout << *it << ' ';
cout << endl
iteratorは標準ライブラリのクラスで、ポインタの機能を備えています.
*it;
反復器に対して参照を解除し、その指向する実際のオブジェクトにアクセスします.
++it;
反復器itを前に移動して次の要素を指す
2.この2つの習慣的な使い方を混用しないように注意しましょう.例えば、次の定義です.
vector< int > ivec;
空のvectorを定義してこのような文を書きます
ivec[ 0 ] = 1024;
エラーです.ivecには最初の要素がないため、vectorにすでに存在する要素size()操作をインデックスしてvectorに含まれる要素の個数を返すしかありません.
3.同様に、vectorを所定のサイズで定義する場合、例えば、
vector ia( 10 );
いずれの挿入操作も、既存の要素を上書きするのではなくvectorのサイズを大きくします.これは明らかに見えますが、次のエラーは初心者には珍しくありません.
const int size = 7;
int ia[ size ] = { 0, 1, 1, 2, 3, 5, 8 };
vector< int > ivec( size );
for ( int ix = 0; ix < size; ++ix )
ivec.push_back( ia[ ix ]);
プログラム終了時にivecには14個の要素が含まれ,iaの要素は8番目の要素から挿入される.
ベクトルでは、すべての要素が連続的に格納されていることを深く理解します.すなわち,各要素に反復器(Iterators)でアクセスできるだけでなく,要素へのポインタにオフセットを加えてアクセスできる.また、任意の関数にベクトルの要素のポインタを渡すと、このポインタは配列内の要素を指していると直接考えられることを意味する.ベクトル内部のストレージ調整は自動的に処理され、必要に応じて拡張または圧縮されます.通常、ベクトルは静的配列(Static arrays)よりも多くの記憶領域を占有します.これは、追加のメモリが将来増加する部分で使用されるためです.そのため、要素を挿入するとき、ベクトルはあまり頻繁にメモリを再割り当てする必要はありません.現在の最大容量は、関数capacity()でクエリーできます.追加のメモリはshrink_を呼び出すことができます.to_fit()関数はオペレーティングシステムに返されます.ベクトルオブジェクトのシーケンスの長さが長くなると、現在のストレージ容量の上限を超えると、内部に配列が再割り当てされ、要素が順次コピーされます.その他の挿入および削除操作により、シーケンス内の要素の一部のメモリアドレスが変更されます.上記のすべての場合、シーケンス内の変更された部分を指す反復器または参照は無効になります.メモリ再割り当てが発生しない場合、ポイントを挿入または削除する前に要素を指す反復器または参照のみが有効になります.
標準ライブラリでは、メモリの使用量と再割り当てにかかるパフォーマンスをバランスさせるために、異なる成長ポリシーを実行できます.いずれの場合も、再割り当てメモリのサイズは指数関数的に増加する必要があります.このようにしてこそ、ベクトルの最後に要素を1つずつ挿入するのに要する時間複雑度を全体的に一定値に割り当てることができます.
メモリの再割り当ては、パフォーマンスにとって高コストの操作です.ベクトルを使用する前に要素の数がわかる場合は、reserve()でメモリ再割り当てを除去できます.
ベクトルは、シーケンスの最後に一定の時間を費やす挿入および要素の削除をサポートします.ベクトルの中間に要素を挿入または削除するには、線形の時間が必要です.シーケンスの開始または未終了への要素の挿入および削除のみに関連する場合、std::dequeコンテナのパフォーマンスは大幅に向上します.シーケンス内の任意の位置への挿入および削除操作に関連する場合、std::listコンテナの性能は大幅に向上します.一般的なアルゴリズムの複雑さ(パフォーマンス関連)は次のとおりです.