Move bottom quarter of a vector to the top efficiently?

Given a vector with 100 elements, I want to move elements 75 to 100 to the front so that 75 is array[0], 76 is array[1] and 1 is arra开发者_开发问答y[25].

Thanks

Your description sounds like you need std::rotate:

std::rotate(v.begin(), v.begin() + 75, v.end());

Pardon the additional answer, but I thought this'd best be kept separate from my original answer.

Intrigued by another poster's boasts of being able to outwit the C++ standard library, I put it to the test with this program, which implements the other poster's algorithms:

#include <vector>
#include <algorithm>
#include <cstdio>
#include <ctime>

const std::size_t size = 25000000;
std::time_t t1, t2, t3, t4;

int main()
{
  t1 = clock();
  std::puts("Allocating...\n");

  std::vector<int> v;
  v.reserve(size);

  t2 = clock();
  std::puts("Filling...\n");

  for (std::size_t i = 0; i != size; ++i)
    v.push_back(i);

  t3 = clock();
  std::puts("Rotating...\n");

#if METHOD == 1
  // Method 1: rotate
  std::rotate(v.begin(), v.begin() + 3*size/4, v.end());
#elif METHOD == 2
  // Method 2: insert at front plus erase
  v.insert(v.begin(), &v[3*size/4], &v[size]);   // ouch, UB
  v.erase(v.begin() + size, v.end());
#elif METHOD == 3
  // Method 3: second vector
  std::vector<int> temp(&v[3*size/4], &v[size]); // ouch, UB
  v.erase(v.begin() + 3*size/4, v.end());
  v.insert(v.begin(), temp.begin(), temp.end());
#endif

  t4 = clock();

  std::puts("Done.\n");

  std::printf("Results: Allocating: %lu ms\nFilling:   %lu ms\nRotating:  %lu ms\n",
              (t2-t1)*1000/CLOCKS_PER_SEC, (t3-t2)*1000/CLOCKS_PER_SEC, (t4-t3)*1000/CLOCKS_PER_SEC);

}

Compiled with GCC 4.6.1 with -std=c++0x -O3 -s -march=native -flto -DMETHOD=???, I get the following results, after repeated runs:

[Edit: Added valgrind reports.]

Method 1:

Results: Allocating: 0 ms
Filling:   210 ms
Rotating:  140 ms

total heap usage: 1 allocs, 1 frees, 100,000,000 bytes allocated

Method 2:

Results: Allocating: 0 ms
Filling:   200 ms
Rotating:  230 ms

total heap usage: 2 allocs, 2 frees, 125,000,000 bytes allocated

Method 3:

Results: Allocating: 0 ms
Filling:   210 ms
Rotating:  160 ms

total heap usage: 2 allocs, 2 frees, 300,000,000 bytes allocated

(Valgrind reports were obtained separately from the timing. Running under valgrind, the rotate version is about six times faster than the other two.)

Based on this I will stand by my opinion that the standard library implementation will be a good first choice, and you will need very strong reasons for preferring a hand-rolled solution.

my_vector w(v.begin() + 75, v.end());
v.resize(75);
v.insert(0, w.begin(), w.end());

Depending on your scenario, you can also use a larger buffer and only change the offset. This is suitable for example, for streaming data:

// C++
enum { kBufferSize = 1024 * 1024 }; // 1MB

char* buffer = new char[kBufferSize];

char* ptr = &buffer[0];
size_t frameSize = 100;

while(someCondition) {
    processFrame(ptr, frameSize);
    ptr += 75; // move the pointer
    // after the first loop, ptr[0] will point to buffer[75] and so on
}

This method has the advantage that it does not copy data and thus, is faster.