std::distance 相对于减法迭代器有什么好处？

Question

我正在迭代一个向量，并且需要迭代器当前指向的索引。以下方法有何优缺点？

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

Answer 1

我更喜欢 it - vec.begin() ，正是出于 Naveen 给出的相反原因：所以如果将向量更改为列表，它不会编译。如果在每次迭代期间都执行此操作，则很容易将 O(n) 算法转变为 O(n^2) 算法。

如果您在迭代期间不在容器中跳转，另一种选择是将索引保留为第二个循环计数器。

注意：it 是容器迭代器的通用名称，std::container_type::iterator it;。

Answer 2

我更喜欢 std::distance(vec.begin(), it) ，因为它允许我在不更改任何代码的情况下更改容器。例如，如果您决定使用 std::list 而不是 std::vector，它不提供随机访问迭代器，您的代码仍将编译。由于 std::distance 根据迭代器特征选择最佳方法，因此您也不会出现任何性能下降。

Answer 3

正如 UncleBens 和 Naveen 所表明的那样，两者都有充分的理由。哪一个“更好”取决于您想要什么行为：您想要保证恒定时间行为，还是希望它在必要时回退到线性时间？

it - vec.begin() 需要恒定时间，但 operator - 仅在随机访问迭代器上定义，因此代码根本无法使用列表迭代器进行编译，例如。

std::distance(vec.begin(), it) 适用于所有迭代器类型，但如果用于随机访问迭代器，则只能是常量时间操作。

两者都不是“更好”。使用能满足您需要的产品。

Answer 4

我喜欢这个：it - vec.begin()，因为对我来说它清楚地表明了“距起点的距离”。对于迭代器，我们习惯于用算术来思考，因此 - 符号是这里最清晰的指示符。

Answer 5

如果您已经将算法限制/硬编码为仅使用 std::vector::iterator 和 std::vector::iterator，那么使用哪个并不重要您最终将使用的方法。您的算法已经具体化，超出了选择其中之一可以产生任何影响的程度。他们都做完全相同的事情。这只是个人喜好问题。我个人会使用显式减法。

另一方面，如果您希望在算法中保留更高程度的通用性，即允许将来有一天它可能应用于其他迭代器类型，那么最好的方法取决于您的意图。这取决于您希望对此处可以使用的迭代器类型进行多大的限制。

• 如果您使用显式减法，您的算法将仅限于相当狭窄的迭代器类别：随机访问迭代器。 （这就是您现在从 std::vector 获得的结果）

• 如果您使用 distance，您的算法将支持更广泛的迭代器类别：输入迭代器。< /p>

当然，计算非随机访问迭代器的距离在一般情况下是低效的操作（而对于随机访问迭代器来说，它与减法一样有效）。从效率角度来看，您的算法对于非随机访问迭代器是否有意义取决于您。如果由此产生的效率损失是毁灭性的，以至于使您的算法完全无用，那么您应该更好地坚持使用减法，从而禁止低效的使用并迫使用户寻找其他迭代器类型的替代解决方案。如果非随机访问迭代器的效率仍在可用范围内，那么您应该使用距离并记录该算法在随机访问迭代器上效果更好的事实。

Answer 6

根据 http://www.cplusplus.com/reference/std/iterator/distance/ ，由于vec.begin()是一个随机访问迭代器，距离方法使用-运算符。

所以答案是，从性能的角度来看，它是相同的，但如果有人必须阅读和理解您的代码，那么使用 distance() 可能更容易理解。

Answer 7

我只会将 - 变体用于 std::vector - 它的含义非常清楚，并且操作简单（只不过是一个指针减法）由语法表达（距离，另一方面，乍一看听起来像毕达哥拉斯，不是吗？）。正如 UncleBen 指出的，- 还可以充当静态断言，以防 vector 意外更改为 list。

而且我认为这种情况更为常见——不过没有数据可以证明这一点。主要论点：it - vec.begin() 源代码更短 - 更少的打字工作，更少的空间消耗。很明显，您的问题的正确答案归根结底是一个品味问题，这也是一个有效的论点。

Answer 8

我刚刚发现这个： https://greek0.net/boost-range/boost -adaptors-indexed.html

    for (const auto & element : str | boost::adaptors::indexed(0)) {
        std::cout << element.index()
                  << " : "
                  << element.value()
                  << std::endl;
    }

Answer 9

除了 int float string 等之外，在使用 diff 时，您还可以将额外的数据放入 .second 中。类型如：

std::map<unsigned long long int, glm::ivec2> voxels_corners;
std::map<unsigned long long int, glm::ivec2>::iterator it_corners;

或

struct voxel_map {
    int x,i;
};

std::map<unsigned long long int, voxel_map> voxels_corners;
std::map<unsigned long long int, voxel_map>::iterator it_corners;

当

long long unsigned int index_first=some_key; // llu in this case...
int i=0;
voxels_corners.insert(std::make_pair(index_first,glm::ivec2(1,i++)));

或

long long unsigned int index_first=some_key;
int index_counter=0;
voxel_map one;
one.x=1;
one.i=index_counter++;

voxels_corners.insert(std::make_pair(index_first,one));

使用正确类型 || 时结构中，您可以在 .second 中放置任何内容，包括在执行插入时递增的索引号。

而不是

it_corners - _corners.begin()

或

std::distance(it_corners.begin(), it_corners)

当

it_corners = voxels_corners.find(index_first+bdif_x+x_z);

在索引之后很简单：

int vertice_index = it_corners->second.y;

使用 glm::ivec2 类型

或

int vertice_index = it_corners->second.i;

结构数据类型时