C++ 获取 std::vector 迭代器索引的最有效方法是什么？

What is the most effective way to get the index of an iterator of an std::vector?

提问by cairol

I'm iterating over a vector and need the index the iterator is currently pointing at. AFAIK this can be done in two ways:

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

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

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

What are the pros and cons of these methods?

这些方法的优缺点是什么？

回答by UncleBens

I would prefer it - vec.begin()precisely for the opposite reason given by Naveen: so it wouldn'tcompile if you change the vector into a list. If you do this during every iteration, you could easily end up turning an O(n) algorithm into an O(n^2) algorithm.

我更喜欢it - vec.begin()Naveen 给出的相反原因：因此，如果将向量更改为列表，它将无法编译。如果您在每次迭代中都这样做，您很容易最终将 O(n) 算法转换为 O(n^2) 算法。

Another option, if you don't jump around in the container during iteration, would be to keep the index as a second loop counter.

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

Note: itis a common name for a container iterator,std::container_type::iterator it;.

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

回答by Naveen

I would prefer std::distance(vec.begin(), it)as it will allow me to change the container without any code changes. For example, if you decide to use std::listinstead of std::vectorwhich doesn't provide a random access iterator your code will still compile. Since std::distance picks up the optimal method depending on iterator traits you'll not have any performance degradation either.

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

回答by jalf

As UncleBens and Naveen have shown, there are good reasons for both. Which one is "better" depends on what behavior you want: Do you want to guarantee constant-time behavior, or do you want it to fall back to linear time when necessary?

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

it - vec.begin()takes constant time, but the operator -is only defined on random access iterators, so the code won't compile at all with list iterators, for example.

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

std::distance(vec.begin(), it)works for all iterator types, but will only be a constant-time operation if used on random access iterators.

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

Neither one is "better". Use the one that does what you need.

没有一个是“更好的”。使用可以满足您需求的那个。

回答by Eli Bendersky

I like this one: it - vec.begin(), because to me it clearly says "distance from beginning". With iterators we're used to thinking in terms of arithmetic, so the -sign is the clearest indicator here.

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

回答by AnT

If you are already restricted/hardcoded your algorithm to using a std::vector::iteratorand std::vector::iteratoronly, it doesn't really matter which method you will end up using. Your algorithm is already concretized beyond the point where choosing one of the other can make any difference. They both do exactly the same thing. It is just a matter of personal preference. I would personally use explicit subtraction.

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

If, on the other hand, you want to retain a higher degree of generality in your algorithm, namely, to allow the possibility that some day in the future it might be applied to some other iterator type, then the best method depends on your intent. It depends on how restrictive you want to be with regard to the iterator type that can be used here.

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

• If you use the explicit subtraction, your algorithm will be restricted to a rather narrow class of iterators: random-access iterators. (This is what you get now from std::vector)

• If you use distance, your algorithm will support a much wider class of iterators: input iterators.

• 如果您使用显式减法，您的算法将被限制为相当窄的一类迭代器：随机访问迭代器。（这就是你现在得到的std::vector）

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

Of course, calculating distancefor non-random-access iterators is in general case an inefficient operation (while, again, for random-access ones it is as efficient as subtraction). It is up to you to decide whether your algorithm makes sensefor non-random-access iterators, efficiency-wise. It the resultant loss in efficiency is devastating to the point of making your algorithm completely useless, then you should better stick to subtraction, thus prohibiting the inefficient uses and forcing the user to seek alternative solutions for other iterator types. If the efficiency with non-random-access iterators is still in usable range, then you should use distanceand document the fact that the algorithm works better with random-access iterators.

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

回答by Stéphane

According to http://www.cplusplus.com/reference/std/iterator/distance/, since vec.begin()is a random accessiterator, the distance method uses the -operator.

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

So the answer is, from a performance point of view, it is the same, but maybe using distance()is easier to understand if anybody would have to read and understand your code.

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

回答by Alexander Gessler

I'd use the -variant for std::vectoronly - it's pretty clear what is meant, and the simplicity of the operation (which isn't more than a pointer subtraction) is expressed by the syntax (distance, on the other side, sounds like pythagoras on the first reading, doesn't it?). As UncleBen points out, -also acts as a static assertion in case vectoris accidentially changed to list.

我只会将-变体用于std::vector- 它的含义很清楚，并且操作的简单性（不超过指针减法）由语法表达（distance，另一方面，听起来像毕达哥拉斯初读，不是吗？）。正如 UncleBen 指出的那样，-也可以作为静态断言，以防vector意外更改为list.

Also I think it is much more common - have no numbers to prove it, though. Master argument: it - vec.begin()is shorter in source code - less typing work, less space consumed. As it's clear that the right answer to your question boils down to be a matter of taste, this can alsobe a valid argument.

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

回答by Srikanth Batthula

Here is an example to find "all" occurrences of 10 along with the index. Thought this would be of some help.

这是一个示例，用于查找“所有”出现的 10 次以及索引。认为这会有所帮助。

void _find_all_test()
{
    vector<int> ints;
    int val;
    while(cin >> val) ints.push_back(val);

    vector<int>::iterator it;
    it = ints.begin();
    int count = ints.size();
    do
    {
        it = find(it,ints.end(), 10);//assuming 10 as search element
        cout << *it << " found at index " << count -(ints.end() - it) << endl;
    }while(++it != ints.end()); 
}