Take the 2-minute tour ×

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?

share|improve this question

9 Answers 9

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

It's an O(N) operation to construct the new vector, but there isn't really a better way.

share|improve this answer
Makes sense, thanks. –  Andrew Jan 7 '09 at 20:01
+1, also it's O(Y-X), which is less than or equal to O(N) (and in his example much less) –  orip Jan 7 '09 at 21:53
@orip Well, then it's O(N) after all. –  Johann Gerell Jan 8 '09 at 7:56
Its O(N) where N is 1000... –  Greg Rogers Jan 8 '09 at 20:02
@GregRogers: It doesn't make sense to use the big-O notation where N is a specific number. Big-O communicates the rate of growth with respect to how N changes. Johann: It's best not to use one variable name in two ways. We'd normally say either O(Y-X), or we'd say O(Z) where Z=Y-X. –  Mooing Duck Sep 11 '13 at 17:51

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]);
share|improve this answer
Ok, I didn't realize it was that simple to obtain an iterator from an arbitrary vector element. –  Andrew Jan 7 '09 at 19:58
Well, you actually get pointers to the elements, which in most cases are equivalent to iterators. However, I assume that they won't be checked like iterators when you have a checked-iterators implementation. Could be some magic I'm unaware of though that makes that work too... –  Niklas Jan 7 '09 at 20:56
Taking the address of those vector elements is an unportable hack that will break if the vector storage is not in fact contiguous. Use begin() + 100000 etc. –  j_random_hacker Jan 8 '09 at 6:29
My bad, apparently the standard guarantees that vector storage is contiguous. Nevertheless it's bad practice to work with addresses like this as it is certainly not guaranteed to work for all containers supporting random access, while begin() + 100000 is. –  j_random_hacker Jan 8 '09 at 6:36
@j_random_hacker: Sorry have to disagree. The STL specification for std::vector was explicitly changed to support this type of procedure. Also a pointer is valid type of iterator. Look up iterator_traits<> –  Loki Astari Jan 8 '09 at 7:35

std::vector(input_iterator, input_iterator), in your case foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, see for example here

share|improve this answer
Since Andrew is trying to construct a new vector, I would recommend "std::vector foo(..." instead of copying with "foo = std::vector(..." –  Drew Dormann Jan 7 '09 at 19:34
Yeah, of course, but whether you type std::vector<int> foo = std::vector(...) or std::vector<int> foo (...) should not matter. –  Anteru Jan 7 '09 at 20:06

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.

share|improve this answer
This is also good if you want the original vector and the subvector to be linked. –  PyRulez Mar 1 at 19:38

You can get the first iterator using begin, and advance it by whatever amount you need:

vector<int> sub(advance(begin(myVec), 100000),
                advance(begin(myVec), 101000));
share|improve this 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.

share|improve this answer
in c++ way to do that would be to have vector of shared_ptr to X instead of vector of X and then copy SPs, but unfortunately I dont think that is faster because atomic operation involved with cpying SP. Or the original vector could be a const shared_ptr of vector instead and you just take reference to subrange in it. ofc you dont need to make it a shared_ptr of vector but then you have lifetime problems... all this is off top of my head, could be wrong... –  NoSenseEtAl Oct 22 '13 at 14:30

Ok. This is a pretty old discussion. But I just discovered something neat:

slice_array - Could this be a fast alternative ? I have not tested it.

share|improve this answer
No, since this for valarray's, not vectors –  nbubis Sep 25 '13 at 2:08
@nbubis: True. But considering that the OP is open to other STLs, would you think that slice_array (using valarray) is not an efficient alternative ? –  user2000581 Sep 25 '13 at 9:53

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

Then pass the pointer p and a len to anything needing a subvector.

notelen must be!! len < myVec.size()-start

share|improve this answer

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

share|improve this answer
std::copy is probably not the correct choice. –  Loki Astari Jan 7 '09 at 19:23

Your Answer


