Narzędzia użytkownika

Narzędzia witryny


adjacent_difference

Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

adjacent_difference [2009/05/19 09:54] (aktualna)
rnowak2 utworzono
Linia 1: Linia 1:
 +====== Algorytm adjacent_difference() ======
 +
 +adjacent_difference jest nazwą przeciążonej funkcji występującej w dwóch postaciach :
 +
 +<code cpp>
 +template <class InputIterator,​ class OutputIterator>​
 +OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
 +                                   ​OutputIterator result);
 +
 +template <class InputIterator,​ class OutputIterator,​ class BinaryFunction>​
 +OutputIterator adjacent_difference(InputIterator first, InputIterator last,
 +                                   ​OutputIterator result,
 +                                   ​BinaryFunction binary_op);
 +</​code>​
 +
 +===== Opis =====
 +
 +Algorytm zawarty w Standard Template Library. Funkcja adjacent_difference() w zakresie określonym przez iteratory //first//, //last// dokonuje odejmowania kolejnych przylegających do siebie elementów. Element *first przypisywany jest do elementu *result będącym iteratorem na koelkcje wynikową. Dla każdego elementu iteratora i w zakresie [first + 1, last), różnica *i oraz *(i - 1) przypisywana jest do *(result + (i - first)).
 +Dzięki temu, iż oprócz składowania różnic w kolekcji wynikowej na pierwszej pozycji przechowujemy pierwszy element możemy odtworzyć kolekcję wejściową na podstawie, której powstał wynik. Operacją odwrotną do adjacent_difference,​ którą można użyć do tego celu jest jest partial_sum.
 +Nie ma przeciwwskazań aby iterator wynikowy był tożsamy z wejściowym umożliwiając obliczanie różnic na kolekcji 'w miejscu'​.
 +
 +===== Nagłówek =====
 +<code cpp>#​include<​numeric></​code>​
 +
 +===== Parametry ===== 
 +
 +Wymagania dla obu wersji:
 +    first  - iterator wskazujący początek zakresu wejściowego
 +    last   - iterator wskazujący koniec zakresu wejściowego
 + result - iterator wskazujący początek kolekcji wyjściowej
 + Wartości dla typu InputIterator dają się konwertować do wartości dla typu OutputIterator
 + [first, last) jest poprawnym zakresem ​
 + [result, result + (last - first)) jest poprawnym zakresem ​
 +
 +Dodatkowe wymagania dla pierwszej wersji:
 + Wartość zwracana x - y jest zdefiniowana i daje się konwertować do wartości OutputIterator. ​
 +
 +Dodatkowe wymagania dla drugiej wersji:
 + BinaryFunction jest funkcją binarną.
 + Wartości dla typu InputIterator dają się konwertować odpowiednio do wartości pierwszego i drugiego argumentu funkcji binarnej. ​
 + Wynik funkcji binarnej dają się konwertować do wartości dla typu OutputIterator. ​
 +
 +===== Złożoność =====
 +
 + Liniowa. brak operacji jeśli [first, last) jest przedziałem pustym, w przeciwnym przypadku dokładnie (last - first) - 1 opearcji. ​
 +
 +===== Przyklady =====
 +
 +<code cpp>
 +#include "​stdafx.h"​
 +#include <​vector>​
 +#include <​list>​
 +#include <​numeric>​
 +#include <​functional>​
 +#include <​iostream>​
 +
 +using namespace std;
 +
 +int _tmain(int argc, _TCHAR* argv[])
 +{
 +   list <int> L1;
 +   list <​int>::​iterator LIter1, LIterend, LIterend2;
 +
 +   ​vector<​int>​ V1( 10 ), V2( 10 );
 +   ​vector<​int>::​iterator VIter1, VIter2, VIterend, VIterend2;
 +
 +   int t; // Generacja {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
 +   for ( t = 1 ; t <= 10 ; t++ )
 +      L1.push_back( t * t );
 +
 +   cout << "​Kolekcja wejsciowa L1 :\n ( " ;
 +   for ( LIter1 = L1.begin( ) ; LIter1 != L1.end( ) ; ++LIter1 )
 +      cout << *LIter1 << " ";
 +   cout << "​)."​ << endl;
 +</​code> ​
 +
 +  * Zastosowanie pierwszej wersji algorytmu
 +
 +<code cpp>
 +   // ​ Standardowa użycie adjacent_difference na liście, wynik zwracany przypisany do wektora
 +   ​VIterend = adjacent_difference ( L1.begin ( ) , L1.end ( ) , V1.begin ( ) );
 +   
 +   cout << "​Kolekcja wyjsciowa, standardowe adjacent_differences:​\n ( " ;
 +   for ( VIter1 = V1.begin( ) ; VIter1 != VIterend ; ++VIter1 )
 +      cout << *VIter1 << " ";
 +   cout << "​)."​ << endl;
 +</​code> ​
 +
 +  * Zastosowanie drugiej wersji algorytmu (mnożenie)
 +
 +<code cpp>
 +   
 +   // ​ Użycie adjacent_difference z funkcją bianrną - mnożenie - na liście, wynik zwracany przypisany do wektora
 +   ​VIterend2 = adjacent_difference ( L1.begin ( ) , L1.end ( ) , V2.begin ( ) , 
 +      multiplies<​int>​( ) );
 +   
 +   cout << "​Kolekcja wyjsciowa, adjacent_differences dla funcji binarnej - mnozenia:\n ( " ;
 +   for ( VIter2 = V2.begin( ) ; VIter2 != VIterend2 ; ++VIter2 )
 +      cout << *VIter2 << " ";
 +   cout << "​)."​ << endl;
 +</​code>​
 +
 +  * Zastosowanie algorytmu 'w miejscu'​
 +
 +<code cpp>
 +   // Użycie adjacent_difference 'w miejscu'​
 +   ​LIterend2 = adjacent_difference ( L1.begin ( ) , L1.end ( ) , L1.begin ( ) );
 +   cout << "​Kolekcja wyjsciowa i wejsciowa tozsame, adjacent_differences w miesjcu na L1:\n ( " ;
 +   for ( LIter1 = L1.begin( ) ; LIter1 != LIterend2 ; ++LIter1 )
 +      cout << *LIter1 << " ";
 +   cout << "​)."​ << endl;
 +
 +}
 +</​code>​
 +
 +
 +===== adjacent_difference.cpp ​ =====
 +{{:​stl_algorytmy:​stl_algorytmy:​adjacent_difference.cpp|}}
 +
 +
 +
 +
  
adjacent_difference.txt · ostatnio zmienione: 2009/05/19 09:54 przez rnowak2