C++,std :: list的左/右旋转

Question

有没有办法如何使用std::rotate列表

std::list<int> v = { 0,7, 1,2 };

因为这些左/右旋转

std::rotate(v.begin(), v.begin() + 1, v.end());
std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());

为矢量工作？

std::vector<int> v = { 0, 7, 1, 2 };

一种可能的方法是将列表复制到向量

std::vector<int> u{ std::begin(v), std::end(v) };

反之亦然,但我发现它太"冗长"......直接轮换列表会导致以下错误:

Error   C2672   'std::rotate': no matching overloaded function found    
Error   C2676   binary '+':  std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator

谢谢你的帮助.

Answer 1

您无法添加到std::list迭代器,因为它不是随机访问.但你可以增加它.那就是std::next对你有用的东西:

void rot_slow( std::list<Item>& seq )
{
    std::rotate( seq.begin(), next( seq.begin() ), seq.end() );
}

但是,这个逻辑std::rotate使用O(n)交换操作.

这是不必要的低效率.如果要旋转列表中O(n²)复杂度的所有项目.它很快变得很慢.

而只是拼接列表末尾的第一个项目:

void rot_fast( std::list<Item>& seq )
{
    seq.splice( seq.end(), seq, seq.begin() );
}

这使用0项交换,O(1)复杂度.

Answer 2

调用的唯一语法问题

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

是std::list迭代器不模拟随机访问迭代器而是双向迭代器.因此,您不能向它们添加或从中减去积分值.相反,称std::rotate这样的

std::rotate(v.begin(), std::next(v.begin()), v.end());
std::rotate(v.rbegin(), std::next(v.rbegin()), v.rend());

在这里,std::next增加你的迭代器,无论它满足什么概念.这就是为什么有时候首先使用它(在你的情况下,当使用a时std::vector)更好,因为它增加了一个间接级别,而不是someIterator + 1硬连接随机访问要求.