Jak działa kategoria iteratora w C++?

Question

Próbowałem zrozumieć wdrażanie iteracyjnej, a podczas zabawy ze źródła, widziałem to stwierdzenie:

typedef output_iterator_tag iterator_category; 

ja nie rozumiem, jak ta praca typedef w klasie? Jaki jest efekt uboczny? Czy ktoś może mnie przez to przechodzić?

Answer 1

Musisz przeczytać ogólne programowanie, ponieważ prawdopodobnie nie dostaniesz tej odpowiedzi.

"Wyjście Iterator" to koncepcja, którą niektóre iteratory pasują do siebie. Każdy iterator będący realizacją tej koncepcji ma pewną funkcjonalność z tym związaną. To coś w rodzaju dziedzictwa, ale tak nie jest.

C++ nie ma niczego takiego, co reprezentuje pojęcia (było proponowanym dodatkiem do C++ 0x, ale nie udało się go utworzyć). W związku z tym potrzebujemy różnych konstrukcji szablonów, aby umożliwić skojarzenie "tagu" z typem iteratora. Przez skojarzenie typu output_iterator_tag z iteratorem twierdzimy, że nasz typ iteratora realizuje koncepcję OutputIterator.

Jest to bardzo ważne, gdy próbujesz napisać algorytmy, które są tak zoptymalizowane, jak to możliwe, a także ogólne. Na przykład, sortowanie z iteratorem, które może być zwiększane lub zmniejszane o dowolną wartość (inną niż 1 innymi słowy) jest bardziej wydajne niż sortowanie, które nie ma tej możliwości. Ponadto, aby uzyskać nowy iterator, odległość X od innej może wymagać różnych operacji w zależności od możliwości iteratora. Aby napisać taki algorytm, należy użyć "wysyłania znaczników". Aby wyjaśnić to dokładniej, oto implementacja (untested) std :: advance, która działa zarówno z iteratorami, które mają operatora + = i tymi, które mają tylko operatora ++ i jest tak szybki jak to możliwe w obu wersjach.

template < typename RandomAccessIterator > 
RandomAccessIterator advance(RandomAccessIterator it 
          , int amount 
          , random_access_iterator_tag) 
{ return it + amount; } 

template < typename ForwardIterator > 
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag) 
{ 
    for (;amount; --amount) ++it; 
    return it; 
} 

template < typename Iterator > 
Iterator advance(Iterator it, int amount) 
{ 
    typedef typename std::iterator_traits<Iterator>::iterator_tag tag; 
    advance(it, amount, tag()); 
} 

To z pamięci, więc pewnie usiane błędami (prawdopodobnie mają kilka typów źle parzyste) ... ale to jest pomysł. Znaczniki iteracyjne są typami, które są puste, a także dziedziczą od siebie dokładnie w ten sam sposób, w jaki koncepcje zawężają się wzajemnie. Na przykład, iterator dostępu losowego IS jest iteratorem forward. Tak więc random_access_iterator_tag jest pochodną parametru forward_iterator_tag. Ze względu na to, że reguły przeciążania funkcji przechodzą do parametru random_access_iterator_tag, funkcja rozróżnia tę wersję funkcji zamiast parametru forward_iterator_tag.

Ponownie, przeczytaj na temat programowania ogólnego. Konieczne jest wykorzystanie pełnej mocy C++.

Aha, wreszcie ... Typedef znajduje się w definicji klasy iteratora, ponieważ jest to miłe, wygodne miejsce na umieszczenie go. Domyślne iterator_traits może go tam szukać. Będziesz chciał użyć iterator_traits zamiast tej definicji, ponieważ surowe wskaźniki również są iteratorami i nie mogą mieć wewnętrznych typów.

Answer 2

output_iterator_tag jest pustą klasą. Jego celem jest umożliwienie algorytmom identyfikacji ogólnych klasyfikacji iteratorów, które są zgodne z określonymi regułami i zapewniają określone operatory. Umożliwia to algorytmom zapewnienie bardziej wyspecjalizowanej implementacji danego algorytmu w określonych warunkach. „Std :: odległość”

Na przykład w nagłówku VS2010 jest "algorytm zawiera dwie implementacje w zależności od«iterator_category»typedef'd w iteratorów przekazanych w.

std :: odległość wymaga tylko iterator wejściowy w celu obliczenia odległości między dwoma iteratorami, ale obliczenie odpowiedzi może wymagać liniowego czasu "O (n)".

Jeśli jednak kompilator stwierdzi, że używany jest iterator dostępu swobodnego, może skorzystać z operatora odejmowania w celu obliczenia odległości w stałym czasie "O (1)".

Polecam oglądając film Stephana T. Lavaveja video, w którym opisuje on cechy typowe i ich zastosowania w Bibliotece szablonów standardowych.