unordered_map cbegin()+ number //常量复杂度?

问题描述 投票:1回答:1

正如标题所说,我知道unbedered_map的cbegin()具有恒定的复杂性,但是是常量复杂度的迭代器的迭代。例如:cbegin()++; cbegin()+ 10; cbegin()+ i; CEND() - ;这些都是o(1)???

c++ dictionary iterator complexity-theory unordered
1个回答
1
投票

24.2.1 [iterator.requirements.general]

所有迭代器类别仅需要在恒定时间内(摊销)可以为给定类别实现的那些函数。因此,迭代器的需求表没有复杂性列。

这的第一部分可能有些令人困惑,但它说的并不是所有迭代器类型都支持所有操作(即,没有使用前向迭代器的随机访问);但那些定义的功能,他们总是have amortized constant complexity。该标准没有明确指定每个迭代器方法的复杂性;它似乎表明,在本节中,定义的那些迭代器方法必须具有分摊的常量复杂性。

© www.soinside.com 2019 - 2024. All rights reserved.