Какой самый эффективный способ получить индекс итератора std :: vector?

Question

Я перебираю вектор и мне нужен индекс, на который сейчас указывает итератор. AFAIK это можно сделать двумя способами:

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

Каковы плюсы и минусы этих методов?

Answer 1

Я бы предпочел it - vec.begin() точно по противоположной причине, заданной Навином: так что не будет компилироваться, если вы измените вектор в список. Если вы будете делать это во время каждой итерации, вы легко сможете превратить алгоритм 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, ваш алгоритм будет поддерживать гораздо более широкий класс итераторов: входные итераторы.

Конечно, вычисление distance для итераторов без произвольного доступа является в общем случае неэффективной операцией (хотя, опять же, для произвольных итераторов это так же эффективно, как вычитание). Вы сами решаете, имеет ли ваш алгоритм смысл для итераторов без произвольного доступа, с точки зрения эффективности. Если результирующая потеря эффективности опустошает вас до такой степени, что делает ваш алгоритм совершенно бесполезным, тогда вам лучше придерживаться вычитания, что запрещает неэффективное использование и вынуждает пользователя искать альтернативные решения для других типов итераторов. Если эффективность с итераторами без произвольного доступа все еще находится в пригодном для использования диапазоне, то вам следует использовать distance и задокументировать тот факт, что алгоритм работает лучше с итераторами с произвольным доступом.

Answer 6

Согласно http://www.cplusplus.com/reference/std/iterator/distance/,, поскольку vec.begin() является итератором с произвольным доступом , метод расстояния использует оператор -.

Таким образом, ответ с точки зрения производительности тот же, но, возможно, использование distance() легче понять, если кому-то придется читать и понимать ваш код.

Answer 7

Я бы использовал вариант - только для std::vector - довольно ясно, что имеется в виду, и простота операции (которая не превышает вычитание указателя) выражается синтаксисом (distance с другой стороны, звучит как пифагор в первом чтении, не так ли?).Как указывает UncleBen, - также действует как статическое утверждение в случае, если vector случайно изменено на list.

Также я думаю, что это гораздо более распространено - хотя чисел для этого нет,Основной аргумент: it - vec.begin() короче в исходном коде - меньше печатной работы, меньше занимаемого места.Поскольку ясно, что правильный ответ на ваш вопрос сводится к вкусу, это может также быть действительным аргументом.