有效地将向量的底部四分之一移动到顶部

Question

给定一个有100个元素的向量，我想把元素75到100移到前面，这样75是array[0]， 76是array[1]， 1是array[25]。

谢谢

Answer 1

您的描述听起来像是需要std::rotate:

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

Answer 2

请原谅我的额外回答，但我认为这最好与我原来的回答分开。

被另一个发布者吹嘘自己能够战胜c++标准库所吸引，我用这个程序来测试它，它实现了另一个发布者的算法:

#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 msnFilling:   %lu msnRotating:  %lu msn",
              (t2-t1)*1000/CLOCKS_PER_SEC, (t3-t2)*1000/CLOCKS_PER_SEC, (t4-t3)*1000/CLOCKS_PER_SEC);
}

使用GCC 4.6.1与-std=c++0x -O3 -s -march=native -flto -DMETHOD=???编译，经过反复运行，我得到以下结果:

[Edit: add valgrind reports.]

方法1:

Results: Allocating: 0 ms
Filling:   210 ms
Rotating:  140 ms
total heap usage: 1 allocs, 1 frees, 100,000,000 bytes allocated

方法2:

Results: Allocating: 0 ms
Filling:   200 ms
Rotating:  230 ms
total heap usage: 2 allocs, 2 frees, 125,000,000 bytes allocated

方法3:

Results: Allocating: 0 ms
Filling:   210 ms
Rotating:  160 ms
total heap usage: 2 allocs, 2 frees, 300,000,000 bytes allocated

(Valgrind报告是与计时分开获得的。在valgrind下运行，rotate版本比其他两个版本快6倍。

基于此，我将坚持我的观点，即标准库实现将是一个很好的首选，您将需要非常有力的理由来偏好手工编写的解决方案。

Answer 3

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

Answer 4

根据您的场景，您还可以使用更大的缓冲区并仅更改偏移量。这适用于流数据:

// 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
}

此方法的优点是不复制数据，因此速度更快。