Suppose I have a std::vector (let's call it myVec) of size N. What's the simplest way to construct a new vector consisting of a copy of elements X through Y, where 0 <= X <= Y <= N-1? For example, myVec [100000] through myVec [100999] in a vector of size 150000.
If this cannot be done efficiently with a vector, is there another STL datatype that I should use instead?
You can use STL copy with O(M) performance when M is the size of the subvector.
You could just use insert
vector<type> myVec { n_elements };
vector<type> newVec;
newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Yet another option:
Useful for instance when moving between a thrust::device_vector and a thrust::host_vector, where you cannot use the constructor.
std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));
Should also be complexity O(N)
You could combine this with top anwer code
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));
Just use the vector constructor.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
You didn't mention what type std::vector<...> myVec is, but if it's a simple type or struct/class that doesn't include pointers, and you want the best efficiency, then you can do a direct memory copy (which I think will be faster than the other answers provided). Here is a general example for std::vector<type> myVec where type in this case is 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
The only way to project a collection that is not linear time is to do so lazily, where the resulting "vector" is actually a subtype which delegates to the original collection. For example, Scala's List#subseq method create a sub-sequence in constant time. However, this only works if the collection is immutable and if the underlying language sports garbage collection.
You didn't mention what type std::vector<...> myVec is, but if it's a simple type or struct/class that doesn't include pointers, and you want the best efficiency, then you can do a direct memory copy (which I think will be faster than the other answers provided). Here is a general example for std::vector<type> myVec where type in this case is 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
Copy elements from one vector to another easily
In this example, I am using a vector of pairs to make it easy to understand
`
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)]
'
As you can see you can easily copy elements from one vector to another, if you want to copy elements from index 10 to 16 for example then we would use
vector<pair<int, int> > a(v.begin()+10, v.begin+16);
and if you want elements from index 10 to some index from end, then in that case
vector<pair<int, int> > a(v.begin()+10, v.end()-5);
hope this helps, just remember in the last case v.end()-5 > v.begin()+10
std::vector<T>(input_iterator, input_iterator), in your case foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, see for example here
The only way to project a collection that is not linear time is to do so lazily, where the resulting "vector" is actually a subtype which delegates to the original collection. For example, Scala's List#subseq method create a sub-sequence in constant time. However, this only works if the collection is immutable and if the underlying language sports garbage collection.
You can use STL copy with O(M) performance when M is the size of the subvector.
Maybe the array_view/span in the GSL library is a good option.
Here is also a single file implementation: array_view.
std::vector<T>(input_iterator, input_iterator), in your case foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, see for example here
If both are not going to be modified (no adding/deleting items - modifying existing ones is fine as long as you pay heed to threading issues), you can simply pass around data.begin() + 100000 and data.begin() + 101000, and pretend that they are the begin() and end() of a smaller vector.
Or, since vector storage is guaranteed to be contiguous, you can simply pass around a 1000 item array:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Both these techniques take constant time, but require that the length of data doesn't increase, triggering a reallocation.
Maybe the array_view/span in the GSL library is a good option.
Here is also a single file implementation: array_view.
If both are not going to be modified (no adding/deleting items - modifying existing ones is fine as long as you pay heed to threading issues), you can simply pass around data.begin() + 100000 and data.begin() + 101000, and pretend that they are the begin() and end() of a smaller vector.
Or, since vector storage is guaranteed to be contiguous, you can simply pass around a 1000 item array:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Both these techniques take constant time, but require that the length of data doesn't increase, triggering a reallocation.
The only way to project a collection that is not linear time is to do so lazily, where the resulting "vector" is actually a subtype which delegates to the original collection. For example, Scala's List#subseq method create a sub-sequence in constant time. However, this only works if the collection is immutable and if the underlying language sports garbage collection.
These days, we use spans! So you would write:
#include <gsl/span>
...
auto start_pos = 100000;
auto length = 1000;
auto span_of_myvec = gsl::make_span(myvec);
auto my_subspan = span_of_myvec.subspan(start_pos, length);
to get a span of 1000 elements of the same type as myvec's. Or a more terse form:
auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);
(but I don't like this as much, since the meaning of each numeric argument is not entirely clear; and it gets worse if the length and start_pos are of the same order of magnitude.)
Anyway, remember that this is not a copy, it's just a view of the data in the vector, so be careful. If you want an actual copy, you could do:
std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());
Notes:
gsl stands for Guidelines Support Library. For more information about gsl, see: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.gsl implementations . For example: https://github.com/martinmoene/gsl-litespan. You would use std::span and #include <span> rather than #include <gsl/span>.std::vector has a gazillion constructors, it's super-easy to fall into one you didn't intend to use, so be careful.Just use the vector constructor.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
Posting this late just for others..I bet the first coder is done by now. For simple datatypes no copy is needed, just revert to good old C code methods.
std::vector <int> myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;
Then pass the pointer p and a len to anything needing a subvector.
notelen must be!! len < myVec.size()-start
Just use the vector constructor.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
You could just use insert
vector<type> myVec { n_elements };
vector<type> newVec;
newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Posting this late just for others..I bet the first coder is done by now. For simple datatypes no copy is needed, just revert to good old C code methods.
std::vector <int> myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;
Then pass the pointer p and a len to anything needing a subvector.
notelen must be!! len < myVec.size()-start
If both are not going to be modified (no adding/deleting items - modifying existing ones is fine as long as you pay heed to threading issues), you can simply pass around data.begin() + 100000 and data.begin() + 101000, and pretend that they are the begin() and end() of a smaller vector.
Or, since vector storage is guaranteed to be contiguous, you can simply pass around a 1000 item array:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Both these techniques take constant time, but require that the length of data doesn't increase, triggering a reallocation.
The only way to project a collection that is not linear time is to do so lazily, where the resulting "vector" is actually a subtype which delegates to the original collection. For example, Scala's List#subseq method create a sub-sequence in constant time. However, this only works if the collection is immutable and if the underlying language sports garbage collection.
Just use the vector constructor.
std::vector<int> data();
// Load Z elements into data so that Z > Y > X
std::vector<int> sub(&data[100000],&data[101000]);
If both are not going to be modified (no adding/deleting items - modifying existing ones is fine as long as you pay heed to threading issues), you can simply pass around data.begin() + 100000 and data.begin() + 101000, and pretend that they are the begin() and end() of a smaller vector.
Or, since vector storage is guaranteed to be contiguous, you can simply pass around a 1000 item array:
T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;
Both these techniques take constant time, but require that the length of data doesn't increase, triggering a reallocation.
This discussion is pretty old, but the simplest one isn't mentioned yet, with list-initialization:
vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};
It requires c++11 or above.
Example usage:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> big_vector = {5,12,4,6,7,8,9,9,31,1,1,5,76,78,8};
vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};
cout << "Big vector: ";
for_each(big_vector.begin(), big_vector.end(),[](int number){cout << number << ";";});
cout << endl << "Subvector: ";
for_each(subvector.begin(), subvector.end(),[](int number){cout << number << ";";});
cout << endl;
}
Result:
Big vector: 5;12;4;6;7;8;9;9;31;1;1;5;76;78;8;
Subvector: 6;7;8;9;9;31;1;1;5;76;
Copy elements from one vector to another easily
In this example, I am using a vector of pairs to make it easy to understand
`
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)]
'
As you can see you can easily copy elements from one vector to another, if you want to copy elements from index 10 to 16 for example then we would use
vector<pair<int, int> > a(v.begin()+10, v.begin+16);
and if you want elements from index 10 to some index from end, then in that case
vector<pair<int, int> > a(v.begin()+10, v.end()-5);
hope this helps, just remember in the last case v.end()-5 > v.begin()+10
You can use STL copy with O(M) performance when M is the size of the subvector.
Yet another option:
Useful for instance when moving between a thrust::device_vector and a thrust::host_vector, where you cannot use the constructor.
std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));
Should also be complexity O(N)
You could combine this with top anwer code
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));
std::vector<T>(input_iterator, input_iterator), in your case foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, see for example here
These days, we use spans! So you would write:
#include <gsl/span>
...
auto start_pos = 100000;
auto length = 1000;
auto span_of_myvec = gsl::make_span(myvec);
auto my_subspan = span_of_myvec.subspan(start_pos, length);
to get a span of 1000 elements of the same type as myvec's. Or a more terse form:
auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);
(but I don't like this as much, since the meaning of each numeric argument is not entirely clear; and it gets worse if the length and start_pos are of the same order of magnitude.)
Anyway, remember that this is not a copy, it's just a view of the data in the vector, so be careful. If you want an actual copy, you could do:
std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());
Notes:
gsl stands for Guidelines Support Library. For more information about gsl, see: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.gsl implementations . For example: https://github.com/martinmoene/gsl-litespan. You would use std::span and #include <span> rather than #include <gsl/span>.std::vector has a gazillion constructors, it's super-easy to fall into one you didn't intend to use, so be careful.This discussion is pretty old, but the simplest one isn't mentioned yet, with list-initialization:
vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};
It requires c++11 or above.
Example usage:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> big_vector = {5,12,4,6,7,8,9,9,31,1,1,5,76,78,8};
vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};
cout << "Big vector: ";
for_each(big_vector.begin(), big_vector.end(),[](int number){cout << number << ";";});
cout << endl << "Subvector: ";
for_each(subvector.begin(), subvector.end(),[](int number){cout << number << ";";});
cout << endl;
}
Result:
Big vector: 5;12;4;6;7;8;9;9;31;1;1;5;76;78;8;
Subvector: 6;7;8;9;9;31;1;1;5;76;
std::vector<T>(input_iterator, input_iterator), in your case foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, see for example here
Source: Stackoverflow.com