Narzędzia użytkownika

Narzędzia witryny


find_end

Algorytm find_end

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 
find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
         ForwardIterator2 first2, ForwardIterator2 last2);
 
template <class ForwardIterator1, class ForwardIterator2, 
          class BinaryPredicate>
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 <algorithm> 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<int> 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<int> suffix;
	suffix.push_back(5);
	suffix.push_back(6);
 
	//wypisanie wstepnego komentarza:
	cout << "Szukanie dopasowania dla ";
	for(vector<int>::iterator i = suffix.begin(); i!=suffix.end(); ++i){
		cout << *i;
	}
	cout << " w ";
	for(vector<int>::iterator i = wektor.begin(); i!=wektor.end(); ++i){
		cout << *i;
	}
 
	cout << endl;
 
	//wyszykanie dopasowania
	vector<int>::iterator iter = find_end(wektor.begin(), wektor.end(), suffix.begin(), suffix.end(), equal_to<int>());
 
	//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<int>::iterator i = wektor.begin(); i!=wektor.end(); ++i){
			cout << *i;
		}
		cout << endl;
		for(int i=0; i<iter-wektor.begin(); ++i){
			cout << ' ';
		}
		for(int i=0; i<suffix.size(); ++i){
			cout << '^';
		}
		cout << endl;
	}else{
		cout << "Nie znaleziono.\n";
	}
}
find_end.txt · ostatnio zmienione: 2008/12/11 23:16 przez rdziedzi