c++ - ベクトルからサブベクトルを抽出する最良の方法は?

Question

size の (としましょう) があるとしstd::vectorます。X から Y までの要素のコピー (0 <= X <= Y <= N-1) で構成される新しいベクトルを作成する最も簡単な方法は何ですか? たとえば、size のベクトルを通過します。myVecNmyVec [100000]myVec [100999]150000

これがベクトルで効率的に実行できない場合、代わりに使用すべき別の STL データ型はありますか?

score 430 · Accepted Answer

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

新しいベクトルを作成するのは O(N) 操作ですが、実際にはこれより良い方法はありません。

score 102 · Accepted Answer

ベクトルコンストラクターを使用するだけです。

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);

score 29 · Accepted Answer

std::vector<T>(input_iterator, input_iterator)、あなたの場合foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);、たとえばここを参照してください

score 11 · Accepted Answer

両方が変更されない場合 (アイテムの追加/削除はありません - スレッド化の問題に注意を払う限り、既存のアイテムの変更は問題ありません)、単純に and を渡しdata.begin() + 100000、それらが小さいベクトルのandであるdata.begin() + 101000ふりをすることができます。begin()end()

または、ベクトルストレージは連続していることが保証されているため、単純に 1000 項目の配列を渡すことができます。

T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;

これらの手法は両方とも一定の時間がかかりますが、データの長さが増加しないことが必要であり、再割り当てがトリガーされます。

score 6 · Accepted Answer

型とは何かについては言及しstd::vector<...> myVecませんでしたが、ポインターを含まない単純な型または構造体/クラスであり、最高の効率が必要な場合は、直接メモリコピーを実行できます (これは、他の回答が提供されています）。この場合std::vector<type> myVecのの一般的な例を次に示します。typeint

typedef int type; //choose your custom type/struct/class
int iFirst = 100000; //first index to copy
int iLast = 101000; //last index + 1
int iLen = iLast - iFirst;
std::vector<type> newVec;
newVec.resize(iLen); //pre-allocate the space needed to write the data directly
memcpy(&newVec[0], &myVec[iFirst], iLen*sizeof(type)); //write directly to destination buffer from source buffer

score 5 · Accepted Answer

あなたはただ使うことができますinsert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);

score 3 · Accepted Answer

M がサブベクトルのサイズである場合、O(M) パフォーマンスでSTL コピーを使用できます。

score 1 · Accepted Answer

線形時間ではないコレクションを投影する唯一の方法は、遅延して行うことです。結果の「ベクトル」は、実際には元のコレクションに委譲するサブタイプです。たとえば、Scala のList#subseqメソッドは一定時間でサブシーケンスを作成します。ただし、これは、コレクションが不変であり、基になる言語がガベージコレクションをサポートしている場合にのみ機能します。

c++ - ベクトルからサブベクトルを抽出する最良の方法は?

15 に答える 15

Related

Reference