Dun*_*eal 4 c++ stl std data-structures
我正在尝试找到a中的最大值std::map,这将是树中的最后一个节点(因为std::map键已排序).
Cppref说std::map.end()是恒定的时间.但是要获得最大的密钥,我必须得到这个迭代器的先前值,即*std::prev(std::map.end()).
该操作的时间复杂度是多少？
我明白这应该相当于--std::map.end(),但我不知道该操作的成本.
使用std::map::rbegin()替代,其中:
返回指向容器中最后一个元素的反向迭代器(即,它的反向开始).
和:
复杂
不变.
最后一个字听起来像是你耳朵里的音乐.
std::prev(std::map.end())是恒定的复杂性.
而且,您对等效性的理解是错误的.
来自std::prev笔记:
虽然表达式
--c.end()经常编译,但不能保证这样做:c.end()是一个rvalue表达式,并且没有迭代器要求指定rvalue的减量保证可以工作.特别是,当迭代器作为指针实现,--c.end()并不能编译,而std::prev(c.end())做.
在任何方向上前进都是前进的数量是线性的(在你的情况下是一个,所以我们可以称之为恒定时间),但你不需要这样做.只需使用rbegin()哪个是最后一个元素的迭代器.
std::prev虽然不等同于--std::map.end()后者,但后者并不能保证做任何有用的事情.查看std::prev文档.