Varianty sekvenčního algoritmu “find”
C++ 11

image_printTisk

Tento článek pojednává o sekvenčních vyhledávacích algoritmech knihovny STL. Ukážeme si algoritmus pro hledání na základě hodnoty nebo za pomocí predikátu. Další možností je také hledání nějaké podposloupnosti hodnot dané rozsahem definovaným za pomocí iterátorů. Návratovou hodnotou je iterátor odkazující na nalezenou hodnotu, pokud však hledání není úspěšné, je vrácena hodnota iterátoru end().

Algoritmus find

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> data = {
    "Aleš", "Klára", "Dušan", "Dominik", "Honza"
};

void printIndex(vector<string>::iterator& it) {
    if(it != data.end())
        cout << "Index ve vektoru je " << distance(data.begin(), it) << endl;
    else
        cout << "Záznam nenalezen." << endl;
}

int main() {
    auto it = find(data.begin(), data.end(), "Dominik");
    printIndex(it);
    it = find(data.begin(), data.end(), "Václav");
    printIndex(it);
    it = find(data.begin(), data.end(), "Aleš");
    printIndex(it);
    
    return 0;
}
Unable to connect to the JDoodle service.

Algoritmy find_if find_if_not

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct Employee {
    string name;
    int wage;
};

vector<Employee> data = {
    { "Honza", 20000 },
    { "Alice", 35000 },
    { "Roman", 10000 },
    { "Klára", 40000 },
    { "Aleš", 15000 }
};

using EmpIterator = typename vector<Employee>::iterator;

template<typename C> 
void find_all(C& container, function<typename C::iterator(typename C::iterator)> Op) {
    auto it = container.begin();
    while(it != container.end()) {
        it = Op(it);
    }
}

template<typename Iterator>
void safe_increment(Iterator& it, Iterator end) {
    if(it != end) {
        it++;
    }
}

void printEmployee(EmpIterator it) {
    if(it != data.end()) {
        cout << it->name << " má plat " << it->wage << endl;
    }
}

int main() {
    // Najdi všechny zaměstnance s platem > 25000
    find_all(data, [](EmpIterator it) {
        it = find_if(it, data.end(), [](const Employee& e) { 
            return e.wage > 25000; });
        printEmployee(it);
        safe_increment(it, data.end());
        return it;
    });
    
    cout << endl;
    
    // Vyřaď zaměstnance s platem 15000 - 25000
    find_all(data, [](EmpIterator it) {
        it = find_if_not(it, data.end(), [](const Employee& e) { 
            return e.wage >= 15000 && e.wage <= 25000; });
        printEmployee(it);
        safe_increment(it, data.end());
        return it;
    });
    
    return 0;
}
Unable to connect to the JDoodle service.

Algoritmy find_first_of a find_end

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string::difference_type charIndex(string& s, string::iterator& it) {
    return distance(s.begin(), it);
}

int main() {
    // Indexy:  01234567890123456789
    string s = "xxxFOO_BARabcd_FOOdd";
    string foo = "FOO";
    string bar = "BAR";
    
    auto it = find_first_of(s.begin(), s.end(), bar.begin(), bar.end());
    cout << "Index pro BAR je " << charIndex(s, it) << endl;
    
    it = find_end(s.begin(), s.end(), foo.begin(), foo.end());
    cout << "Index pro posledního FOO je " << charIndex(s, it) << endl;
    
    return 0;
}
Unable to connect to the JDoodle service.

Algoritmus adjacent_find

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sequence = {
  1, 2, 3, 3, 3, 2, 4, 5, 6, 6, 6, 6, 6, 5, 4, 3, 2, 1, 1, 2 ,3
};

template<typename Iterator>
Iterator printConstantRegion(Iterator it, Iterator end) {
    typename Iterator::value_type value = *it;
    while(it != end) {
        if(*it != value)
            break;
        cout << *it << ";";
        it++;
    }
    cout << endl;
    return it;
}

int main() {
    auto it = sequence.begin();
    while(it != sequence.end()) {
        it = adjacent_find(it, sequence.end());
        if(it != sequence.end())
            it = printConstantRegion(it, sequence.end());
    }
}
Unable to connect to the JDoodle service.

Shrnutí

 

image_printTisk
Varianty sekvenčního algoritmu “find”
C++ 11
Ohodnoťte tento článek

Související články

  • Sekvenční algoritmy “all_of”, “any_of” a “none_of” V tomto článku si popíšeme sekvenční algoritmy all_of, any_of a none_of. Jejich princip spočívá v tom, že se jim v argumentu předá testovací operace, reprezentovaná nejčastěji lambda […]
  • Úvod do algoritmů STL Úvod Co jsou algoritmy STL - operace nad datovými strukturami STL Jak fungují? Vazba přes iterátory Není přímý přístup do datové struktury kvůli abstrakci od její […]
  • Datová struktura “queue” Fronta funguje na principu zvaném FIFO (First-In First-Out). To znamená, že prvek, který byl do fronty vložen dříve, bude také dříve zpracováván. V podstatě můžeme říci, že prvky vyjímáme […]
  • Datový typ “string” V tomto článku si představíme skupinu datových typů knihovny STL pro práci s texty. Seznámíme se s jejich inicializací, stejně tak si popíšeme další základní metody pro práci s touto […]
  • Šablony funkcí II V tomto článku dokončíme výklad o šablonách funkcí. Zmíníme se o tom, že šablony mohou obsahovat kromě parametrů reprezentujících datové typy také celočíselné hodnoty a dále si představíme […]
  • Úvod do iterátorů Dva hlavní pilíře STL knihovny jsou její datové struktury a obecné algoritmy pro práci s nimi. Vzhledem k různosti datových struktur a obecnosti algoritmů potřebujeme nějaký spojovací […]