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





by index (7)


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

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

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

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

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




Мне нравится этот: it - vec.begin() , потому что для меня это четко говорит «расстояние от начала». С итераторами мы привыкли думать с точки зрения арифметики, поэтому знак - это самый яркий показатель.




Как показали UncleBens и Naveen, для обоих есть веские причины. Какой из них «лучше» зависит от того, какое поведение вы хотите: хотите ли вы гарантировать постоянное поведение, или вы хотите, чтобы он вернулся к линейному времени, когда это необходимо?

it - vec.begin() принимает постоянное время, но operator - определяется только на итераторах произвольного доступа, поэтому код вообще не будет компилироваться с итераторами списков.

std::distance(vec.begin(), it) работает для всех типов итераторов, но будет работать только в постоянном режиме, если используется для итераторов произвольного доступа.

Ни один из них не «лучше». Используйте тот, который делает то, что вам нужно.




Я бы предпочел it - vec.begin() именно по той противоположной причине, которую дал Naveen: поэтому он не будет компилироваться, если вы измените вектор на список. Если вы делаете это на каждой итерации, вы можете легко превратить алгоритм O (n) в алгоритм O (n ^ 2).

Другой вариант, если вы не прыгаете в контейнере во время итерации, будет поддерживать индекс как второй счетчик циклов.




Я бы предпочел std::distance(vec.begin(), it) как это позволит мне изменить контейнер без каких-либо изменений кода. Например, если вы решили использовать std::list вместо std::vector который не предоставляет итератор произвольного доступа, ваш код все равно будет компилироваться. Поскольку std :: distance выбирает оптимальный метод, зависящий от характеристик итератора, вы также не будете иметь ухудшения производительности.




Если вы уже ограничены / жестко закодированы ваш алгоритм использования только std::vector::iterator и std::vector::iterator , на самом деле не имеет значения, какой метод вы в конечном итоге используете. Ваш алгоритм уже конкретизирован за пределами того места, где выбор одного из других может иметь какое-либо значение. Они оба делают то же самое. Это только вопрос личных предпочтений. Я лично использовал бы явное вычитание.

Если, с другой стороны, вы хотите сохранить более высокую степень общности в своем алгоритме, а именно, чтобы позволить возможность, что когда-нибудь в будущем она может быть применена к другому типу итератора, тогда лучший способ зависит от вашего намерения , Это зависит от того, насколько ограничительным вы хотите быть в отношении типа итератора, который можно использовать здесь.

  • Если вы используете явное вычитание, ваш алгоритм будет ограничен довольно узким классом итераторов: итераторы с произвольным доступом. (Это то, что вы получаете теперь из std::vector )

  • Если вы используете distance , ваш алгоритм будет поддерживать гораздо более широкий класс итераторов: входные итераторы.

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




К сожалению, даже ваш «расточительный» код неверен. EPSILON - это наименьшее значение, которое можно добавить в 1.0 и изменить его значение. Значение 1.0 очень важно - при добавлении в EPSILON большее число не изменяется. Теперь вы можете масштабировать это значение до чисел, которые вы сравниваете, чтобы определить, являются ли они разными или нет. Правильное выражение для сравнения двух удвоений:

if (fabs(a - b) <= DBL_EPSILON * fmax(fabs(a), fabs(b)))
{
    // ...
}

Это как минимум. В общем, однако, вы хотели бы учитывать шум в ваших расчетах и ​​игнорировать несколько наименее значимых бит, поэтому более реалистичное сравнение будет выглядеть следующим образом:

if (fabs(a - b) <= 16 * DBL_EPSILON * fmax(fabs(a), fabs(b)))
{
    // ...
}

Если эффективность сравнения очень важна для вас, и вы знаете диапазон своих значений, то вместо этого вы должны использовать числа с фиксированной точкой.





c++ iterator coding-style