C++，left/right 旋转 std::list

Question

有什么方法可以将 std::rotate 用于列表

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

因为这些 left/right 旋转

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) };

反之亦然但我也发现了"lengthy"...直接旋转列表会导致以下错误：

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::rotate(v.begin(), v.begin() + 1, v.end());

是 std::list 迭代器不建模 random access iterators but bidirectional iterators。因此，您不能对它们添加或减去整数值 to/from。相反，像这样调用 std::rotate

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

此处，std::next 递增您的迭代器，无论它满足什么概念。这就是为什么有时最好首先使用它（在你的情况下，当使用 std::vector 时），因为它增加了一个间接级别，而不是 someIterator + 1，你硬连接随机访问要求。

Answer 2

您不能添加到 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) 复杂度。

C++，left/right 旋转 std::list

C++, left/right rotation of std::list

c++

algorithm

list

vector

rotation