私はC++ランドのC/Pythonプログラマーであり、初めてSTLを使用しています。
Pythonでは、リストを別のリストで拡張するには、次の.extend方法を使用します。
>>> v = [1, 2, 3]
>>> v_prime = [4, 5, 6]
>>> v.extend(v_prime)
>>> print(v)
[1, 2, 3, 4, 5, 6]
私は現在、このアルゴリズムアプローチを使用してC++でベクトルを拡張しています。
v.resize(v.size() + v_prime.size());
copy(v_prime.begin(), v_prime.end(), v.rbegin());
これはベクトルを拡張する標準的な方法ですか、それとも私が見逃しているより簡単な方法がありますか？
ここから
// reserve() is optional - just to improve performance
v.reserve(v.size() + distance(v_prime.begin(),v_prime.end()));
v.insert(v.end(),v_prime.begin(),v_prime.end());
copy(v_prime.begin(), v_prime.end(), back_inserter(v));
There are multiple ways to achieve your target.
std::vector::insert
The vector can be extended by inserting new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted. You can follow one of below approaches. The second version uses C++11 and it can be considered as a more generic answer, as b could also be an array.
a.insert(a.end(), b.begin(), b.end());
a.insert(std::end(a), std::begin(b), std::end(b));
Sometimes in usage it is a best practice to use reserve function before using std::vector::insert. std::vector::reserve function increases the capacity of the container to a value that's greater or equal to new_cap. If new_cap is greater than the current capacity(), new storage is allocated, otherwise the method does nothing.
a.reserve(a.size() + distance(b.begin(), b.end()));
Use of reserve function is not required but may be advisable. And it is best practive to use reserve if you are repeatedly inserting into a vector for which you know the final size, and that size is large. Otherwise, it is better to let the STL grow your vector as needed.
std::copy
std::copy is the second option that you can consider to achieve your target. This function copies the elements in the range (first,last) into the range beginning at result.
std::copy (b.begin(), b.end(), std::back_inserter(a));
However use of std::copy is slower than use of std::vector::insert(), because std::copy() can't reserve enough space before-hand (it doesn't have access to the vector itself, only to an iterator which has), while std::vector::insert(), being a member function, can. Due to that std::copy is indeed slower than using std::vector::insert. Most of the people, over use std::copy without knowing this scenario.
boost::push_back
The third option that you can consider is the use of boost's push_back function.
boost::push_back(a, b);
C++14 では、関数の 2 つの異なるバリアントが必要でしたextend。そのうちの 1 つは、追加されるベクトルの各要素の移動セマンティクスをサポートしていました。
vecはあなたのv、そしてextあなたのv_primeです。
/**
* Extend a vector with elements, without destroying source one.
*/
template<typename T>
void vector_extend(std::vector<T> &vec, const std::vector<T> &ext) {
vec.reserve(vec.size() + ext.size());
vec.insert(std::end(vec), std::begin(ext), std::end(ext));
}
/**
* Extend a vector with elements with move semantics.
*/
template<typename T>
void vector_extend(std::vector<T> &vec, std::vector<T> &&ext) {
if (vec.empty()) {
vec = std::move(ext);
}
else {
vec.reserve(vec.size() + ext.size());
std::move(std::begin(ext), std::end(ext), std::back_inserter(vec));
ext.clear();
}
}
次の構文のみを使用してください。
a.insert(a.end(), b.begin(), b.end());
自分が何をしているのかを理解していない限り、Reserve\Resize は使用しないでください。
予約は、サイズの指数関数的な増加を必ずしも割り当てるとは限らないため、大きなオーバーヘッドを引き起こす可能性があるため、予約ごとに O(n) 時間が発生する可能性があります。
これは、1 回だけ実行する場合はそれほどコストがかからない可能性があり、実際には、そのような場合に時間とメモリの効率が向上する可能性があります。一方、比較的小さな配列でこの方法で配列を拡張し続けると、非常に非効率的であることがわかります。次の例は、10,000 倍の時間増加を引き起こす単純な使用ミスを示しています。
例：
#include <vector>
#include <iostream>
#include <chrono>
int main() {
std::vector<int> a, b(50);
auto t1 = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 5e4; i++) {
a.reserve(a.size() + b.size()); // line in question.
a.insert(a.end(), b.begin(), b.end());
}
auto t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>( t2 - t1 ).count();
std::cout << 1.0 * duration / 1e9;
return 0;
}
//run time complexity speed up
//with reserve 114.558 s O(N) x1
//without reserve 0.012 s O(N^2) x10000 (~O(N/50))
gcc 17、Intel i5 で -O3 を指定してコンパイル。