c++ - C++,std::list 的左/右旋转
问题描述
有什么办法可以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
谢谢你的帮助。
解决方案
您不能添加到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) 复杂度。
推荐阅读
- javascript - 逐渐静音/取消静音视频的音频
- java - 使用 IAuthenticationProvider 进行身份验证
- asp.net - 没有后端的 Windows 身份验证?
- java - Spring Boot mvnw 无法编译代码成功 test-compiled
- python - 运行 python 应用程序并从目录中的不同路径导入模块
- typescript - 打字稿:从联合中的所有接口中省略一个属性,但保留联合结构
- autohotkey - 问题返回正确的鼠标线
- javascript - 从 K6 模拟每个 VU 的浏览器缓存以进行负载测试
- reactjs - 如何在子组件的子组件中更改 this.state 的属性值
- nativescript-angular - Mediafilepicker 视频文件选择(在应用程序上显示视频)