Best way to extract a subvector from a vector

Question

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  lt   X  lt   Y  lt   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

User · Answer

You can use STL copy with O M  performance when M is the size of the subvector

User · Answer

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 lt T gt  newVector  newVector reserve 1000   std  copy n  amp vec 100000   1000  std  back inserter newVector      Should also be complexity O N   You could combine this with top anwer code  vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  std  copy first  last  std  back inserter newVector

User · Answer

Maybe the array view span in the GSL library is a good option   Here is also a single file implementation  array view

User · Answer

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    amp 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

User · Answer

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

User · Answer

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    amp 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

User · Answer

You didn t mention what type std  vector lt     gt  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 lt type gt  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 lt type gt  newVec  newVec resize iLen     pre-allocate the space needed to write the data directly memcpy  amp newVec 0    amp myVec iFirst   iLen sizeof type      write directly to destination buffer from source buffer

User · Answer

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  lt int gt    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  lt  myVec size  -start

User · Answer

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    amp 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

User · Answer

vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  vector lt T gt  newVec first  last     It s an O N  operation to construct the new vector  but there isn t really a better way

User · Answer

You can use STL copy with O M  performance when M is the size of the subvector

User · Answer

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 lt pair lt int  int gt   gt  v n      we want half of elements in vector a and another half in vector b vector lt pair lt lli  lli gt   gt  a v begin   v begin   n 2   vector lt pair lt lli  lli gt   gt  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 lt pair lt int  int gt   gt  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 lt pair lt int  int gt   gt  a v begin   10  v end  -5     hope this helps  just remember in the last case v end  -5  gt  v begin   10

User · Answer

You can use STL copy with O M  performance when M is the size of the subvector

User · Answer

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

User · Answer

You could just use insert  vector lt type gt  myVec   n elements     vector lt type gt  newVec   newVec insert newVec begin    myVec begin     X  myVec begin     Y

User · Answer

Just use the vector constructor   std  vector lt int gt    data       Load Z elements into data so that Z  gt  Y  gt  X  std  vector lt int gt    sub  amp data 100000   amp data 101000

User · Answer

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  lt int gt    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  lt  myVec size  -start

User · Answer

You didn t mention what type std  vector lt     gt  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 lt type gt  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 lt type gt  newVec  newVec resize iLen     pre-allocate the space needed to write the data directly memcpy  amp newVec 0    amp myVec iFirst   iLen sizeof type      write directly to destination buffer from source buffer

User · Answer

vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  vector lt T gt  newVec first  last     It s an O N  operation to construct the new vector  but there isn t really a better way

User · Answer

You can use STL copy with O M  performance when M is the size of the subvector

User · Answer

Maybe the array view span in the GSL library is a good option   Here is also a single file implementation  array view

User · Answer

This discussion is pretty old  but the simplest one isn t mentioned yet  with list-initialization     vector lt int gt  subvector    big vector begin     3  big vector end   - 2      It requires c  11 or above    Example usage     include  lt iostream gt   include  lt vector gt   include  lt algorithm gt   using namespace std   int main         vector lt int gt  big vector    5 12 4 6 7 8 9 9 31 1 1 5 76 78 8       vector lt int gt  subvector    big vector begin     3  big vector end   - 2        cout  lt  lt   Big vector         for each big vector begin    big vector end      int number  cout  lt  lt  number  lt  lt              cout  lt  lt  endl  lt  lt   Subvector         for each subvector begin    subvector end      int number  cout  lt  lt  number  lt  lt              cout  lt  lt  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

User · Answer

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

User · Answer

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

User · Answer

std  vector lt T gt  input iterator  input iterator   in your case foo   std  vector lt T gt  myVec begin      100000  myVec begin      150000    see for example here

User · Answer

These days  we use spans  So you would write   include  lt gsl span gt       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 lt T gt  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  There are several gsl implementations   For example  https   github com martinmoene gsl-lite C  20 provides an implementation of span  You would use std  span and  include  lt span gt  rather than  include  lt gsl span gt   For more information about spans  see  What is a  quot span quot  and when should I use one  std  vector has a gazillion constructors  it s super-easy to fall into one you didn t intend to use  so be careful

User · Answer

std  vector lt T gt  input iterator  input iterator   in your case foo   std  vector lt T gt  myVec begin      100000  myVec begin      150000    see for example here

User · Answer

std  vector lt T gt  input iterator  input iterator   in your case foo   std  vector lt T gt  myVec begin      100000  myVec begin      150000    see for example here

User · Answer

These days  we use spans  So you would write   include  lt gsl span gt       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 lt T gt  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  There are several gsl implementations   For example  https   github com martinmoene gsl-lite C  20 provides an implementation of span  You would use std  span and  include  lt span gt  rather than  include  lt gsl span gt   For more information about spans  see  What is a  quot span quot  and when should I use one  std  vector has a gazillion constructors  it s super-easy to fall into one you didn t intend to use  so be careful

User · Answer

Just use the vector constructor   std  vector lt int gt    data       Load Z elements into data so that Z  gt  Y  gt  X  std  vector lt int gt    sub  amp data 100000   amp data 101000

User · Answer

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    amp 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

User · Answer

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 lt T gt  newVector  newVector reserve 1000   std  copy n  amp vec 100000   1000  std  back inserter newVector      Should also be complexity O N   You could combine this with top anwer code  vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  std  copy first  last  std  back inserter newVector

User · Answer

Just use the vector constructor   std  vector lt int gt    data       Load Z elements into data so that Z  gt  Y  gt  X  std  vector lt int gt    sub  amp data 100000   amp data 101000

User · Answer

This discussion is pretty old  but the simplest one isn t mentioned yet  with list-initialization     vector lt int gt  subvector    big vector begin     3  big vector end   - 2      It requires c  11 or above    Example usage     include  lt iostream gt   include  lt vector gt   include  lt algorithm gt   using namespace std   int main         vector lt int gt  big vector    5 12 4 6 7 8 9 9 31 1 1 5 76 78 8       vector lt int gt  subvector    big vector begin     3  big vector end   - 2        cout  lt  lt   Big vector         for each big vector begin    big vector end      int number  cout  lt  lt  number  lt  lt              cout  lt  lt  endl  lt  lt   Subvector         for each subvector begin    subvector end      int number  cout  lt  lt  number  lt  lt              cout  lt  lt  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

User · Answer

vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  vector lt T gt  newVec first  last     It s an O N  operation to construct the new vector  but there isn t really a better way

User · Answer

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 lt pair lt int  int gt   gt  v n      we want half of elements in vector a and another half in vector b vector lt pair lt lli  lli gt   gt  a v begin   v begin   n 2   vector lt pair lt lli  lli gt   gt  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 lt pair lt int  int gt   gt  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 lt pair lt int  int gt   gt  a v begin   10  v end  -5     hope this helps  just remember in the last case v end  -5  gt  v begin   10

User · Answer

Just use the vector constructor   std  vector lt int gt    data       Load Z elements into data so that Z  gt  Y  gt  X  std  vector lt int gt    sub  amp data 100000   amp data 101000

User · Answer

vector lt T gt   const iterator first   myVec begin     100000  vector lt T gt   const iterator last   myVec begin     101000  vector lt T gt  newVec first  last     It s an O N  operation to construct the new vector  but there isn t really a better way

User · Answer

You could just use insert  vector lt type gt  myVec   n elements     vector lt type gt  newVec   newVec insert newVec begin    myVec begin     X  myVec begin     Y

User · Answer

std  vector lt T gt  input iterator  input iterator   in your case foo   std  vector lt T gt  myVec begin      100000  myVec begin      150000    see for example here

[c++] Best way to extract a subvector from a vector?

Examples related to c++

Examples related to stl

Examples related to vector

Examples related to range