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

439

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

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

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

cairol
источник

Ответы:

558

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

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

Примечание: itэто общее имя для итератора контейнера std::container_type::iterator it;.

Дядя Бен
источник
3
Согласовано. Я бы сказал, что знак минус лучше, но было бы лучше сохранить счетчик второго цикла, чем использовать std :: distance, именно потому, что эта функция может быть медленной.
Стивен Судит
28
что за хрень it?
Штейнфельд
32
@ Штайнфельд это итератор. std::container_type::iterator it;
Мэтт Мансон
2
Добавление счетчика второго цикла является настолько очевидным решением, что я смущен, я не думал об этом.
Мордред
3
@Swapnil, потому std::listчто не предлагает прямой доступ к элементам по их положению, поэтому, если вы не можете этого сделать list[5], вы не сможете этого сделать list.begin() + 5.
Хосе Томас Тосино
135

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

Нэвин
источник
50
Когда вы используете контейнер без итераторов произвольного доступа, лучше не вычислять такие расстояния, потому что они неэффективны
Эли Бендерский,
6
@Eli: Я согласен с этим, но в очень особом случае, если это действительно необходимо, тогда этот код будет работать.
Навин
9
Я думаю, что код должен быть изменен в любом случае, если контейнер изменится - иметь названную переменную std :: list vec- плохая новость. Если код был переписан так, чтобы он был универсальным, принимая тип контейнера в качестве параметра шаблона, тогда мы можем (и должны) поговорить об обработке итераторов без произвольного доступа ;-)
Стив Джессоп,
1
И специализация для определенных контейнеров.
ScaryAardvark
19
@SteveJessop: Именование вектора vecтоже довольно плохая новость.
Река Там
74

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

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

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

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

jalf
источник
1
Я был в грязи в прошлом. Использование std :: distance на двух итераторах std :: map и ожидание того, что оно будет O (N).
ScaryAardvark
6
@ScaryAardvark: Разве вы не предполагаете, что он будет O (1)?
2010 года
12

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

Эли Бендерский
источник
19
Более понятно использовать вычитание, чтобы найти расстояние, чем буквально использовать слово distance?
Трэвис Гокель
4
@ Travis, для меня это так. Это вопрос вкуса и обычая. Мы говорим, it++а не что-то вроде std::increment(it), не так ли? Разве это не считается менее понятным?
Эли Бендерский
3
++Оператор определяется как часть STL последовательностей , как , как мы увеличиваем итератор. std::distanceвычисляет количество элементов между первым и последним элементом. Тот факт, что -оператор работает, просто совпадение.
Трэвис Гокель
3
@MSalters: и все же мы используем ++ :-)
Эли Бендерский
10

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

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

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

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

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

Муравей
источник
4

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

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

Stéphane
источник
3

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

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

Александр Гесслер
источник
0

Вот пример, чтобы найти «все» вхождения 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()); 
}
Срикант Баттхула
источник