views:

1246

answers:

6

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?

A: 

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

Yuval F
std::copy is probably not the correct choice.
Martin York
+2  A: 

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

Anteru
Since Andrew is trying to construct a new vector, I would recommend "std::vector foo(..." instead of copying with "foo = std::vector(..."
Shmoopty
Yeah, of course, but whether you type std::vector<int> foo = std::vector(...) or std::vector<int> foo (...) should not matter.
Anteru
+7  A: 
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.

Greg Rogers
Makes sense, thanks.
Andrew
+1, also it's O(Y-X), which is less than or equal to O(N) (and in his example much less)
orip
@orip Well, then it's O(N) after all.
Johann Gerell
Its O(N) where N is 1000...
Greg Rogers
+1  A: 

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.

Daniel Spiewak
+5  A: 

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]);
Martin York
Ok, I didn't realize it was that simple to obtain an iterator from an arbitrary vector element.
Andrew
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
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
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
@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<>
Martin York
Yep, pointers aren't necessarily valid std::vector<T>::iterator's but they are valid iterators for an array in continuous storage, which is how it is used.
Greg Rogers
+2  A: 

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.

Eclipse