Jaki jest najskuteczniejszy sposób uzyskania indeksu iteratora std :: vector?

439

Iteruję nad wektorem i potrzebuję indeksu, na który obecnie wskazuje iterator. AFAIK można to zrobić na dwa sposoby:

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

Jakie są zalety i wady tych metod?

Kair
źródło

Odpowiedzi:

558

Wolałbym it - vec.begin()dokładnie z przeciwnego powodu podanego przez Naveen: więc nie skompilowałby się, gdyby zmienić wektor na listę. Jeśli zrobisz to podczas każdej iteracji, możesz łatwo przekształcić algorytm O (n) w algorytm O (n ^ 2).

Inną opcją, jeśli nie przeskakujesz w kontenerze podczas iteracji, byłoby zachowanie indeksu jako drugiego licznika pętli.

Uwaga: itJest to wspólna nazwa dla iteratora pojemnika std::container_type::iterator it;.

Wujek Ben
źródło
3
Zgoda. Powiedziałbym, że znak minus jest najlepszy, ale lepiej byłoby zachować drugi licznik pętli niż używać std :: distance, właśnie dlatego, że ta funkcja może być wolna.
Steven Sudit,
28
co do cholery jest it?
Steinfeld,
32
@ Steinfeld to iterator. std::container_type::iterator it;
Matt Munson,
2
Dodanie drugiego licznika pętli jest tak oczywistym rozwiązaniem, że wstydzę się, że o tym nie pomyślałem.
Mordred,
3
@ Swapnil, ponieważ std::listnie oferuje bezpośredniego dostępu do elementów według ich pozycji, więc jeśli nie możesz tego zrobić list[5], nie powinieneś być w stanie tego zrobić list.begin() + 5.
José Tomás Tocino,
135

Wolę, std::distance(vec.begin(), it)ponieważ pozwoli mi to zmienić kontener bez żadnych zmian kodu. Na przykład, jeśli zdecydujesz się użyć std::listzamiast tego, std::vectorktóry nie zapewnia iteratora o dostępie swobodnym, Twój kod nadal będzie się kompilował. Ponieważ std :: distance wybiera optymalną metodę w zależności od cech iteratora, nie zmniejszysz wydajności.

Naveen
źródło
50
Kiedy używasz kontenera bez iteratorów o dostępie swobodnym, najlepiej nie obliczać takich odległości, ponieważ jest to nieefektywne
Eli Bendersky
6
@Eli: Zgadzam się z tym, ale w bardzo szczególnym przypadku, jeśli jest to naprawdę wymagane, kod nadal będzie działał.
Naveen
9
Myślę, że kod powinien zostać zmieniony, jeśli kontener się zmieni - posiadanie nazwanej zmiennej std :: list vecto złe wieści. Jeśli kod zostałby ponownie napisany, aby był ogólny, biorąc pod uwagę typ kontenera jako parametr szablonu, wtedy możemy (i powinniśmy) mówić o obsłudze iteratorów bez dostępu losowego ;-)
Steve Jessop
1
I specjalizacja dla niektórych pojemników.
ScaryAardvark
19
@SteveJessop: Posiadanie wektora o nazwie vecjest również złą wiadomością.
Rzeka Tam
74

Jak pokazali UncleBens i Naveen, istnieją dobre powody dla obu. To, które z nich jest „lepsze”, zależy od tego, jakie zachowanie chcesz: czy chcesz zagwarantować zachowanie w czasie stałym, czy też chcesz, aby w razie potrzeby wrócił do czasu liniowego?

it - vec.begin()zajmuje stały czas, ale operator -jest definiowany tylko w iteratorach o swobodnym dostępie, więc kod nie kompiluje się na przykład z iteratorami list.

std::distance(vec.begin(), it) działa dla wszystkich typów iteratorów, ale będzie działać tylko w trybie ciągłym, jeśli zostanie zastosowany w iteratorach o dostępie swobodnym.

Żadne z nich nie jest „lepsze”. Użyj tego, który robi to, czego potrzebujesz.

jalf
źródło
1
Wpadłem na to w przeszłości. Użycie std :: distance na dwóch iteratorach std :: map i oczekiwanie, że będzie to O (N).
ScaryAardvark
6
@ ScaryAardvark: Czy nie masz na myśli oczekiwać, że będzie to O (1)?
czerwiec
12

Podoba mi się ten:, it - vec.begin()ponieważ dla mnie wyraźnie mówi „odległość od początku”. Dzięki iteratorom jesteśmy przyzwyczajeni do myślenia w kategoriach arytmetyki, więc -znak jest tutaj najwyraźniejszym wskaźnikiem.

Eli Bendersky
źródło
19
Czy łatwiej jest zastosować odejmowanie, aby znaleźć odległość, niż dosłownie słowo distance?
Travis Gockel
4
@Travis, dla mnie to jest. To kwestia gustu i zwyczaju. Mówimyit++ a nie coś takiego std::increment(it), prawda? Czy nie byłoby to również mniej jasne?
Eli Bendersky
3
++Operator jest zdefiniowany jako część sekwencji STL jak jak przyrost iteracyjnej. std::distanceoblicza liczbę elementów między pierwszym a ostatnim elementem. Fakt, że- operator działa, jest jedynie zbiegiem okoliczności.
Travis Gockel
3
@MSalters: a jednak używamy ++ :-)
Eli Bendersky
10

Jeśli jesteś już ograniczony / sztywno swój algorytm za pomocą std::vector::iteratora std::vector::iteratortylko, że nie ma znaczenia, która metoda będzie skończyć użyciu. Twój algorytm jest już skonkretyzowany poza punktem, w którym wybór jednego z nich może mieć znaczenie. Oboje robią dokładnie to samo. To tylko kwestia osobistych preferencji. Osobiście użyłbym wyraźnego odejmowania.

Jeśli natomiast chcesz zachować wyższy stopień ogólności w swoim algorytmie, a mianowicie, aby umożliwić możliwość zastosowania go w przyszłości w innym typie iteratora, najlepsza metoda zależy od twoich zamiarów . To zależy od tego, jak restrykcyjny chcesz być w odniesieniu do typu iteratora, którego możesz tutaj użyć.

  • Jeśli użyjesz jawnego odejmowania, twój algorytm będzie ograniczony do raczej wąskiej klasy iteratorów: iteratorów o swobodnym dostępie. (Z tego teraz otrzymujesz std::vector)

  • Jeśli używasz distance, twój algorytm będzie obsługiwał znacznie szerszą klasę iteratorów: iteratory wejściowe.

Oczywiście obliczanie distancedla iteratorów bez dostępu losowego jest na ogół nieefektywną operacją (podczas gdy dla tych z dostępem losowym jest równie wydajne jak odejmowanie). To Ty decydujesz, czy Twój algorytm ma sens dla iteratorów bez dostępu losowego, pod względem wydajności. Jeśli wynikająca z tego utrata wydajności jest tak druzgocąca, że ​​algorytm staje się całkowicie bezużyteczny, należy lepiej trzymać się odejmowania, tym samym zakazując nieefektywnych zastosowań i zmuszając użytkownika do poszukiwania alternatywnych rozwiązań dla innych typów iteratorów. Jeśli wydajność z iteratorami nieposiadającymi losowego dostępu jest nadal w użytecznym zakresie, powinieneś użyć distancei udokumentować fakt, że algorytm działa lepiej z iteratorami o swobodnym dostępie.

Mrówka
źródło
4

Według http://www.cplusplus.com/reference/std/iterator/distance/ , ponieważ vec.begin()jest to iterator o dostępie swobodnym , metoda odległości wykorzystuje -operatora.

Odpowiedź jest więc taka sama z punktu widzenia wydajności, ale być może korzystanie z niej distance()jest łatwiejsze do zrozumienia, jeśli ktoś będzie musiał przeczytać i zrozumieć Twój kod.

Stéphane
źródło
3

Użyłbym tego -wariantu std::vectortylko - jest całkiem jasne, co to znaczy, a prostota operacji (która nie jest niczym więcej niż odejmowaniem wskaźnika) jest wyrażona przez składnię ( distancez drugiej strony brzmi jak pitagoras na pierwsze czytanie, prawda?). Jak wskazuje UncleBen, -działa również jako twierdzenie statyczne na wypadek vectorprzypadkowej zmiany na list.

Myślę też, że jest to o wiele bardziej powszechne - nie ma jednak liczb, aby to udowodnić. Główny argument: it - vec.begin()jest krótszy w kodzie źródłowym - mniej pracy na pisaniu, mniej miejsca. Ponieważ jasne jest, że właściwa odpowiedź na twoje pytanie sprowadza się do gustu, może to być również uzasadniony argument.

Alexander Gessler
źródło
0

Oto przykład, aby znaleźć „wszystkie” wystąpienia 10 wraz z indeksem. Pomyślałem, że to pomoże.

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()); 
}
Srikanth Batthula
źródło