ベクトルからサブベクトルを抽出する最良の方法は?
質問
サイズstd::vector
のmyVec
(N
と呼びましょう)があるとします。 0 <!> lt; = X <!> lt; = Y <!> lt; = N-1の要素XからYのコピーで構成される新しいベクトルを構築する最も簡単な方法は何ですか?たとえば、サイズmyVec [100000]
のベクターのmyVec [100999]
から150000
まで。
ベクターでこれを効率的に実行できない場合、代わりに使用する必要がある別のSTLデータ型はありますか?
解決
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);
新しいベクトルを作成するのはO(N)操作ですが、実際にはこれ以上の方法はありません。
他のヒント
ベクトルコンストラクターを使用するだけです。
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
std::vector(input_iterator, input_iterator)
、あなたのケースではfoo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);
、たとえばこちら
最近では、span
sを使用しています!したがって、次のように記述します。
#include <gsl/span>
...
auto start_pos = 100000;
auto length = 1000;
auto my_subspan = gsl::make_span(myvec).subspan(start_pos, length);
は、myvec
と同じタイプの1000個の要素のスパンを取得します。さて、これはベクター内のデータのコピーではなく、単なるビューですので、注意してください。実際のコピーが必要な場合は、次を実行できます。
std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());
注:
-
gsl
は、ガイドラインサポートライブラリの略です。std::span
の詳細については、次を参照してください: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library 。 -
#include <span>
の1つの実装については、次を参照してください: https://github.com/Microsoft/GSL - C ++ 20は、
#include <gsl/span>
の実装を提供します。std::vector
ではなく<=>と<=>を使用します。 - スパンの詳細については、次を参照してください: What <!> quot; span <!> quot;いつ使うべきですか?
- <=>には膨大な数のコンストラクタがあり、使用するつもりがなかったコンストラクタに陥りやすいので注意してください。
両方が変更されない場合(アイテムの追加/削除なし-既存のアイテムの変更は、スレッドの問題に注意を払う限り問題ありません)、単にdata.begin() + 100000
とdata.begin() + 101000
を回して、それを装うことができますそれらは、より小さいベクトルのbegin()
およびend()
です。
または、ベクトルストレージは連続していることが保証されているため、単純に1000アイテムの配列を渡すことができます:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
これらの手法はどちらも一定の時間を要しますが、データの長さが増加しないことを要求し、再割り当てをトリガーします。
std::vector<...> myVec
型については言及しませんでしたが、ポインターを含まない単純な型または構造体/クラスであり、最高の効率が必要な場合は、直接メモリコピーを実行できます(これは、提供される他の回答よりも高速になると思います)。 std::vector<type> myVec
の一般的な例を次に示します。この場合のtype
はint
です。
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
STLコピーは、Mサブベクトルのサイズです。
線形時間ではないコレクションを投影する唯一の方法は、結果の<!> quot; vector <!> quot;実際には、元のコレクションに委任するサブタイプです。たとえば、ScalaのList#subseq
メソッドは、一定の時間でサブシーケンスを作成します。ただし、これは、コレクションが不変であり、基礎となる言語がガベージコレクションをサポートしている場合にのみ機能します。
わかりました。これはかなり古い議論です。しかし、私はちょうど素敵な何かを発見しました:
slice_array -これは高速な代替手段でしょうか?テストしていません。
他の人のためだけにこれを遅く投稿します。最初のコーダーはもう終わりです。 単純なデータ型の場合、コピーは不要です。古き良きCコードメソッドに戻してください。
std::vector <int> myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;
次に、サブベクトルを必要とするものにポインターpとlenを渡します。
notelenは!! len < myVec.size()-start
array_view / span は、GSLライブラリの適切なオプションです。
単一ファイルの実装もここにあります: array_view 。
要素をあるベクターから別のベクターに簡単にコピーする
この例では、ペアのベクトルを使用して理解しやすくしています
`
vector<pair<int, int> > v(n);
//we want half of elements in vector a and another half in vector b
vector<pair<lli, lli> > a(v.begin(),v.begin()+n/2);
vector<pair<lli, lli> > b(v.begin()+n/2, v.end());
//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
//then a = [(1, 2), (2, 3)]
//and b = [(3, 4), (4, 5), (5, 6)]
//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
//then a = [(1, 2), (2, 3), (3, 4)]
//and b = [(4, 5), (5, 6), (6, 7)]
'
ご覧のように、あるベクトルから別のベクトルに要素を簡単にコピーできます。たとえば、インデックス10から16に要素をコピーする場合は、次を使用します
vector<pair<int, int> > a(v.begin()+10, v.begin+16);
そして、インデックス10から最後からインデックスまでの要素が必要な場合、その場合
vector<pair<int, int> > a(v.begin()+10, v.end()-5);
これが役立つことを願って、最後のケースで覚えておいてくださいv.end()-5 > v.begin()+10
さらに別のオプション:
たとえば、コンストラクタを使用できないthrust::device_vector
とthrust::host_vector
の間を移動する場合に便利です。
std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));
複雑さもO(N)でなければなりません
これをトップアンワーコードと組み合わせることができます
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));
単にinsert
vector<type> myVec { n_elements };
vector<type> newVec;
newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);