43

I can't seem to think of a reliable way (that also compacts memory) to remove the first N elements from a std::vector. How would one go about doing that?

Dev Null
  • 4,731
  • 1
  • 30
  • 46
ForeverLearning
  • 6,352
  • 3
  • 27
  • 33
  • 7
    Would changing to a `std::deque` interest you? It's way more efficient for this. – R. Martinho Fernandes Sep 08 '11 at 17:12
  • Never mind! I am having a huge brain freeze today. – ForeverLearning Sep 08 '11 at 17:14
  • @Martinho No :-( Changing it to a deque is a laborious process now. I am wondering if I cannot use std::copy_backward somehow? – ForeverLearning Sep 08 '11 at 17:17
  • What's wrong with `v.erase(v.begin(),v.begin()+N)` ? – n. m. could be an AI Sep 08 '11 at 17:18
  • 3
    @Dilip? Laborious? How so? STL containers are easily swapped by just an single line change, *As long as you are using them correctly*, If you cannot probably you are not using them correctly? – Alok Save Sep 08 '11 at 17:25
  • @n.m. Nothing :-) I am still thawing out my brain – ForeverLearning Sep 08 '11 at 17:37
  • @Als -- its the size of the codebase. It involves modifying parts of code that I don't even own. Things are never so simple. – ForeverLearning Sep 08 '11 at 17:38
  • 3
    @Dilip : Sounds like someone didn't use `typedef` judiciously enough. ;-] – ildjarn Sep 08 '11 at 17:51
  • 1
    You can't typedef away that `std:vector` is contiguous and `std::deque` isn't, which matters a lot when interfacing with legacy code that expects a T*. But for such code, you might be able to not delete the first N elements, and pass `&v[N]` instead. – MSalters Sep 08 '11 at 22:51
  • @Als: Containers are not really that easily swappable. Each of them has very specific characteristics, so either some operations won't compile, or will compile but result in a signifant performance drop (e.g you replace vector with set, but happily keep using std::find). And as MSalters points out, replacing vector with deque may well result in undefined behavior. – visitor Sep 09 '11 at 10:37
  • The caveat "that also compacts memory" is going to be non-portable, because the standard never promises that you can. – Caleth May 29 '19 at 08:18

3 Answers3

46

Use the .erase() method:

// Remove the first N elements, and shift everything else down by N indices
myvec.erase(myvec.begin(), myvec.begin() + N);

This will require copying all of the elements from indices N+1 through the end. If you have a large vector and will be doing this frequently, then use a std::deque instead, which has a more efficient implementation of removing elements from the front.

Adam Rosenfield
  • 390,455
  • 97
  • 512
  • 589
41

Since you mention that you want to compact memory, it would be best to copy everything to a new vector and use the swap idiom.

std::vector<decltype(myvector)::value_type>(myvector.begin()+N, myvector.end()).swap(myvector);
R. Martinho Fernandes
  • 228,013
  • 71
  • 433
  • 510
Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • 9
    Or more succinctly, `std::vector(myvector.begin()+N, myvector.end()).swap(myvector);`. – ildjarn Sep 08 '11 at 17:22
  • @ildjarn, thank you - I knew there was a way to do it with an unnamed temporary but I had a brain freeze. I've updated my answer using your exact text. – Mark Ransom Sep 08 '11 at 17:29
  • @ild: Can you really use the `::` operator with non-types? – fredoverflow Sep 09 '11 at 01:42
  • @FredOverflow, I think he copied that from me. I think you can, but I didn't test it. – Mark Ransom Sep 09 '11 at 01:43
  • @FredOverflow : Mark's correct, I copied it from him and didn't notice. Realistically it would of course be `myvector_t::value_type` or `decltype(myvector)::value_type`. – ildjarn Sep 09 '11 at 01:48
  • 2
    How about the memory allocated by the removed element in contrast to std::vector<>::erase ? – Martin Meeser Mar 14 '13 at 12:27
  • Sometimes a `std::decay_t` is needed. `std::vector::value_type>(myvector.begin()+N, myvector.end()).swap(myvector);` – Zheng Qu Feb 17 '20 at 22:45
13
v.erase( v.begin(), v.size() > N ?  v.begin() + N : v.end() );

Don't forget the check of the size, just in case.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • 1
    @Mooing Duck I missed that. In that case, he'll have to create a new vector: `std::vector( v.begin() + std::min( N, v.size() ). v.end() )` – James Kanze Sep 08 '11 at 17:29