====== Algorytm find_end ======
template
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate comp);
Właściwie lepszą nazwą dla algorytmu find_end byłaby search_end, ponieważ działanie algorytmu search oraz find_end jest dosyć podobne.
Oba poszukują dopasowania sekwencji [first2, last2) w sekwencji [first1, last1). Różnica polega na tym, że search zwraca iterator wskazujący
na pierwszy obiekt w pierwszym dopasowaniu, a find_end na pierwszy w ostatnim dopasowaniu.
W przypadku braku dopasowania find_end zwraca last1
Różnica pomiędzy dwiema wersjami algorytmu find_end polega na sposobie w jaki algorytm uznaje dwa elementy za równe. Pierwsza wersja wykorzystuje
operator==, natomiast druga BinaryPredicat.
===== Nagłówki =====
find_end jest zdefiniowany w nagłówku w STL oraz poza standardem, w nagłówku algo.h
===== Wymagania na typy =====
==== Dla wersji pierwszej ====
* ForwardIterator1 typu Forward Iterator.
* ForwardIterator2 typu Forward Iterator.
* wartość ForwardIterator1-a jest typu EqualityComparable.
* wartość ForwardIterator2-a jest typu EqualityComparable.
* Obiekty będące wartościami ForwardIterator1-a muszą być porównywane z obiektami będącymi wartościami ForwardIterator2-a.
==== Dla wersji drugiej ====
* ForwardIterator1 typu Forward Iterator.
* ForwardIterator2 typu Forward Iterator.
* BinaryPredicate typu Binary Predicate.
* wartość ForwardIterator1-a musi być konwertowana na typ pierwszego argumentu dla BinaryPredicate.
* wartość ForwardIterator2-a musi być konwertowana na typ drugiego argumentu dla BinaryPredicate.
===== Złożoność =====
Liczba porównań jest proporcjonalna do (last1 - first1) * (last2 - first2).
===== Przykłady użycia =====
===== Pierwsza wersja algorytmu =====
void find_end_type1(){
//utworzenie napisu oraz suffixu
char* s = "executable.exe";
char* suffix = "exe";
const int N = strlen(s);
const int N_suf = strlen(suffix);
char* location = find_end(s, s + N,
suffix, suffix + N_suf);
if (location != s + N) {
cout << "Znaleziono dopasowanie dla " << suffix << " w " << s << endl;
cout << s << endl;
int i;
for (i = 0; i < (location - s); ++i)
cout << ' ';
for (i = 0; i < N_suf; ++i)
cout << '^';
cout << endl;
}
else
cout << "Nie znaleziono dopasowania dla " << suffix << " w " << s << endl;
}
==== Druga wersja algorytmu ====
void find_end_type2(){
//utworzenie wektora skladajacego sie z 3 takich samych ciagow liczb
vector wektor;
for (int i=0; i<3; ++i){
for (int j=0; j<10; ++j){
wektor.push_back(j);
}
}
//utworzenie krotkiego sufixu, ktory bedzie poszukiwany we wczesniej utworzonym wektorze
vector suffix;
suffix.push_back(5);
suffix.push_back(6);
//wypisanie wstepnego komentarza:
cout << "Szukanie dopasowania dla ";
for(vector::iterator i = suffix.begin(); i!=suffix.end(); ++i){
cout << *i;
}
cout << " w ";
for(vector::iterator i = wektor.begin(); i!=wektor.end(); ++i){
cout << *i;
}
cout << endl;
//wyszykanie dopasowania
vector::iterator iter = find_end(wektor.begin(), wektor.end(), suffix.begin(), suffix.end(), equal_to());
//jesli funkcja find_end zwrocila element nie bedacy last1 to wypisywany jest komentarz o znalezieniu
//wraz z ilustracja znalezionego sufiksu w wektorze
if(iter != wektor.end()){
cout << "Znaleziono:\n";
for(vector::iterator i = wektor.begin(); i!=wektor.end(); ++i){
cout << *i;
}
cout << endl;
for(int i=0; i