c++ - 双端队列从前面删除元素并将它们放在后面

Question

我有一个 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);
}

有没有办法优化这个过程？

Answer 1

您可以像这样使用 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