Różnice między wybraną wersją a wersją aktualną.
— |
reverse_reverse_copy [2009/04/29 00:00] (aktualna) mfrancis utworzono |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
+ | ====== Algorytm reverse & reverse_copy ====== | ||
+ | Zaliczane są do rodziny algorytmów **mutujących** biblioteki standardowej C++.\\ | ||
+ | |||
+ | == reverse == | ||
+ | * odwraca kolejność elementów wewnątrz podanego zakresu\\ | ||
+ | * //std::list// udostępnia funkcję składową //reverse//, oferującą lepszą wydajność | ||
+ | (modyfikowane są jedynie powiązania wskaźników wewnątrz listy) | ||
+ | |||
+ | == reverse_copy == | ||
+ | * odwraca kolejność elementów podczas kopiowania z zakresu źródłowego\\ | ||
+ | |||
+ | ===== Nagłówek ===== | ||
+ | <code cpp> | ||
+ | #include <algorithm> | ||
+ | </code> | ||
+ | dla iteratorów wstawiających: | ||
+ | <code cpp> | ||
+ | #include <iterator> | ||
+ | </code> | ||
+ | ===== Definicje ===== | ||
+ | == reverse == | ||
+ | <code cpp> | ||
+ | template <class BidirectionalIterator> | ||
+ | void reverse ( BidirectionalIterator first, BidirectionalIterator last ) | ||
+ | { | ||
+ | while ((first!=last)&&(first!=--last)) | ||
+ | swap (*first++,*last); | ||
+ | } | ||
+ | </code> | ||
+ | == reverse_copy == | ||
+ | <code cpp> | ||
+ | template <class BidirectionalIterator, class OutputIterator> | ||
+ | OutputIterator reverse_copy ( BidirectionalIterator first, | ||
+ | BidirectionalIterator last, OutputIterator result ) | ||
+ | { | ||
+ | while (first!=last) *result++ = *--last; | ||
+ | return result; | ||
+ | } | ||
+ | </code> | ||
+ | ===== Parametry ===== | ||
+ | == reverse == | ||
+ | <code> | ||
+ | first - początek zakresu źródłowego | ||
+ | last - koniec zakresu źródłowego | ||
+ | </code> | ||
+ | == reverse_copy == | ||
+ | <code> | ||
+ | first - początek zakresu źródłowego | ||
+ | last - koniec zakresu źródłowego | ||
+ | result - iterator wyjściowy wskazujący miejsce zapisu | ||
+ | </code> | ||
+ | |||
+ | ===== Wartość zwracana ===== | ||
+ | == reverse == | ||
+ | <code> | ||
+ | brak | ||
+ | </code> | ||
+ | == reverse_copy == | ||
+ | <code> | ||
+ | pozycja za ostatnim elementem w kolekcji docelowej: | ||
+ | result + (last - first) | ||
+ | </code> | ||
+ | |||
+ | ===== Warunki użycia ===== | ||
+ | * zakres [first, last) jest prawidłowy\\ | ||
+ | * //reverse_copy//: w kontenerze docelowym zapewniona jest odpowiednio duża ilość miejsca lub używane są iteratory wstawiające\\ | ||
+ | * //reverse_copy//: zakres źródłowy i docelowy nie zachodzą na siebie | ||
+ | |||
+ | ===== Złożoność ===== | ||
+ | **reverse**: liniowa, N/2 zamian\\ | ||
+ | **reverse_copy**: liniowa, N przypisań | ||
+ | |||
+ | ===== Przykłady użycia ===== | ||
+ | == stworzenie kolekcji == | ||
+ | <code cpp> | ||
+ | using namespace std; | ||
+ | ... | ||
+ | vector<string> quote_vector; | ||
+ | vector<int> num_vector; | ||
+ | list<string> quote_list; | ||
+ | |||
+ | const int nums[] = { 1, 2, 3, 4, 5 }; | ||
+ | |||
+ | quote_vector.push_back("przyklad"); | ||
+ | quote_vector.push_back("reverse"); | ||
+ | quote_vector.push_back("i"); | ||
+ | quote_vector.push_back("reverse_copy"); | ||
+ | |||
+ | quote_list.push_back("kolejny"); | ||
+ | quote_list.push_back("przyklad"); | ||
+ | quote_list.push_back("dla"); | ||
+ | quote_list.push_back("listy"); | ||
+ | </code> | ||
+ | == reverse == | ||
+ | <code cpp> | ||
+ | /* odwrócenie wybranego zakresu elementów */ | ||
+ | reverse(quote_vector.begin() + 1, quote_vector.end()); | ||
+ | |||
+ | /* użycie optymalnej wersji algorytmu dla listy */ | ||
+ | quote_list.reverse(); | ||
+ | </code> | ||
+ | |||
+ | == reverse_copy == | ||
+ | <code cpp> | ||
+ | /* odwrócona kopia wybranego zakresu elementów, | ||
+ | z wykorzystaniem iteratora, wstawiającego elementy | ||
+ | na koniec kolejki */ | ||
+ | reverse_copy(quote_vector.begin(), quote_vector.end() - 1, | ||
+ | back_inserter(quote_list)); | ||
+ | |||
+ | /* użycie algorytmu bez iteratorów wstawiających | ||
+ | - kontener docelowy musi zapewnić odpowiednią ilość | ||
+ | miejsca */ | ||
+ | num_vector.reserve(5); | ||
+ | reverse_copy(nums, nums + 5, num_vector.begin()); | ||
+ | </code> |