Эффективно переместить нижнюю четверть вектора в верхнюю?

Question

Учитывая вектор со 100 элементами, я хочу переместить элементы с 75 по 100 вперед, чтобы 75 было массивом [0], 76 - массивом [1] и 1 - массивом [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 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);

}

Скомпилировано с GCC 4.6.1 с -std=c++0x -O3 -s -march=native -flto -DMETHOD=???, после повторных запусков я получаю следующие результаты:

[ Редактировать : добавлены отчеты valgrind.]

Метод 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 примерно в шесть раз быстрее, чем две другие.)

Исходя из этого, я буду придерживаться своего мнения о том, что реализация стандартной библиотеки будет хорошим выбором, и вам понадобятся очень веские причины для предпочтения ручного решения.

Answer 3

В зависимости от вашего сценария вы также можете использовать больший буфер и изменять только смещение. Это подходит, например, для потоковой передачи данных:

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

Преимущество этого метода в том, что он не копирует данные и, следовательно, работает быстрее.

Answer 4

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