C++,STD的左/右旋转::列表

调用的唯一语法问题

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

是吗 std::list 迭代器不建模 random access iterators 但是 bidirectional iterators . 因此,不能对它们加上或减去整数值。相反,打电话 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

你不能添加到 std::list 迭代器,因为它不是随机访问。但是你可以增加它。那就是 std::next 为您服务:

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

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

那是不必要的低效。如果你想在列表中的所有项之间进行旋转,那么这就非常复杂了。它很快变得很慢。

相反,只需在列表末尾拼接第一项:

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

这使用0项交换,O(1)复杂性。