Deque удаляет элементы спереди и кладет их сзади - PullRequest
Новая
       8

Deque удаляет элементы спереди и кладет их сзади

0 голосов
/ 08 ноября 2018

У меня есть объект deque типа int с большим количеством элементов, и моя задача состоит в том, чтобы получить все элементы из первой половины очереди, поместить их сзади и удалить эти элементы спереди: например, [1, 2,3,4,5] станет [3,4,5,1,2]. В настоящее время код, который делает это: 

for(int i=0;i<myDeque.size()/2;i++)
{
        int a=myDeque.front();
        myDeque.pop_front();
        myDeque.push_back(a);
}

Есть ли способ оптимизировать этот процесс?

1 Ответ

0 голосов
/ 09 ноября 2018

Вы можете использовать std :: rotate следующим образом: 

   std::rotate( myDeque.begin(), myDeque.begin() + dequeSize/2, myDeque.end());

Полный тест: 

#include <iostream>
#include <chrono>
#include <deque>
#include <algorithm> // std::rotate


void printDequeBegin(const std::deque<int>& aDeque)
{
   auto d {aDeque.cbegin()};
   auto i {0};
   while (i < 10 && d != aDeque.cend())
   {
      std::cout << *d++ << " ";
      ++i; 
   }
   std::cout << "\n";
}


int main()
{

   const int dequeSize { 9000000 };
   std::deque<int> myDeque;

   for (int i = 0; i < dequeSize; )
   {
      myDeque.push_back(++i);
   }

   printDequeBegin(myDeque);

   auto start {std::chrono::system_clock::now()};

   std::rotate( myDeque.begin(), myDeque.begin() + dequeSize/2, myDeque.end()); 

   auto end {std::chrono::system_clock::now()};

   auto ms {std::chrono::duration_cast<std::chrono::milliseconds>(end-start)};
   std::cout << ms.count() << " ms\n";

   printDequeBegin(myDeque);

   return 0;
}

Выход: 

1 2 3 4 5 6 7 8 9 10 
326 ms
4500001 4500002 4500003 4500004 4500005 4500006 4500007 4500008 4500009 4500010
...