c++ vector迭代器下标 - 什么是获得std :: vector迭代器索引的最有效方法?




4 Answers

我更喜欢it - vec.begin()恰恰是出于Naveen给出的相反原因:所以如果将向量更改为列表, 它将不会编译。 如果你在每次迭代过程中都这么做,那么你很容易就会把O(n)算法变成O(n ^ 2)算法。

另一种选择是,如果你在迭代过程中没有在容器中跳转,那么将索引保存为第二个循环计数器。

vector索引 c++索引

我遍历一个向量并需要迭代器当前指向的索引。 AFAIK这可以通过两种方式完成:

  • it - vec.begin()
  • std::distance(vec.begin(), it)

这些方法的优点和缺点是什么?




正如UncleBens和Naveen所表明的那样,这两者都有很好的理由。 哪一个“更好”取决于你想要的行为:你想保证恒定时间的行为,还是希望在必要时回到线性时间?

it - vec.begin()需要一定的时间,但operator -只是在随机访问迭代器上定义的,所以例如代码根本无法用列表迭代器进行编译。

std::distance(vec.begin(), it)适用于所有迭代器类型,但是如果在随机访问迭代器上使用,则只会是一个常量操作。

两者都不是“更好”。 使用你需要的那个。




如果您已经将算法限制/硬编码为仅使用std::vector::iteratorstd::vector::iterator ,则最终使用哪种方法并不重要。 你的算法已经具体化,超越了选择其中一个可以产生任何不同的点。 他们都做同样的事情。 这只是个人喜好的问题。 我会亲自使用明确的减法。

另一方面,如果您希望在算法中保留更高的通用性,即允许将来某一天它可能应用于其他迭代器类型的可能性,那么最好的方法取决于您的意图。 这取决于你想在这里可以使用的迭代器类型方面有多严格。

  • 如果你使用显式减法,你的算法将被限制在一个相当狭窄的迭代器类中:随机访问迭代器。 (这是你现在从std::vector

  • 如果你使用distance ,你的算法将支持更广泛的迭代器类:输入迭代器。

当然,计算非随机访问迭代器的距离一般情况下是低效率的操作(而对于随机访问迭代器来说,其效率与减法效率一样)。 由您决定您的算法对于非随机访问迭代器是否有意义 ,效率明智。 由此导致的效率损失对于使算法完全无用而言具有破坏性,那么您应该更好地坚持减法,从而禁止低效率的使用并迫使用户为其他迭代类型寻求替代解决方案。 如果非随机访问迭代器的效率仍处于可用范围内,那么应该使用distance并记录该算法与随机访问迭代器更好地工作的事实。




我只使用std::vector变量 - 它很清楚是什么意思,并且操作的简单性(它不过是一个指针减法)用语法表示( distance ,在另一侧,一读时听起来像毕达哥拉斯,不是吗?)。 正如UncleBen指出的那样-vector被意外更改为list情况下,它也充当静态断言。

另外我认为它更常见 - 没有数字可以证明它。 主要论点: it - vec.begin()在源代码中更短 - 更少的打字工作,更少的空间消耗。 很显然,对你的问题的正确答案归结为一个品味问题,这可能是一个有效的论点。




Related