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

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?

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;.

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.

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.

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.

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.

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.

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.

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()); 
}