Zilele trecute, din curiozitate, m-am uitat în biblioteca algoritmului C ++. Și am aflat un număr destul de bun de caracteristici interesante!

Acest lucru m-a uimit literalmente.

De ce? Adică am scris în cea mai mare parte C ++ de-a lungul vieții mele universitare. Și a fost în special datorită relației mele de iubire-ură cu programare competitivă.

Și, din păcate, nu am profitat cu adevărat de această uimitoare bibliotecă pe care ne-a oferit-o C ++.

Doamne, m-am simțit atât de naiv!

Așa că am decis că este timpul să nu mai fiu naiv și să cunosc utilitatea algoritmilor C ++ – cel puțin la un nivel superior. Și cum a spus odată un bătrân, împărtășirea cunoștințelor este putere – aici sunt.

Declinarea responsabilității: Am folosit foarte mult caracteristici de la C ++ 11 și nu numai. Dacă nu sunteți familiarizați cu edițiile mai noi ale limbajului, fragmentele de cod pe care le-am furnizat aici ar putea părea puțin stângace. Pe de altă parte, biblioteca pe care o discutăm aici este mult mai autonomă și mai elegantă decât orice am scris mai jos. Simțiți-vă liber să găsiți greșeli și să le indicați. Și, de asemenea, nu aș putea lua în considerare multe dintre adăugirile C ++ 17 din această postare, deoarece majoritatea caracteristicilor sale nu au fost încă aduse în viață în GCC.

Așadar, fără alte întrebări, să începem!

  1. all_of any_of none_of

Aceste funcții caută pur și simplu dacă all, any sau none dintre elementele unui container urmează unele proprietăți specifice definite de dvs. Verificați exemplul de mai jos:

std::vector<int> collection = {3, 6, 12, 6, 9, 12};

// Are all numbers divisible by 3?
bool divby3 = std::all_of(begin(collection), end(collection), [](int x) {
    return x % 3 == 0;
});
// divby3 equals true, because all numbers are divisible by 3

// Is any number divisible by 2?
bool divby2 = std::any_of(begin(collection), end(collection), [](int x) {
    return x % 2 == 0;
});
// divby2 equals true because 6, 12 divisible by 2

// Is no number divisible by 6?
bool divby6 = std::none_of(begin(collection), end(collection), [](int x) {
    return x % 6 == 0;
});
// divby6 equals false because 6, 12 divisible by 6

Observați cum, în exemplu, proprietate specificăeste transmis ca o funcție lambda.

Asa de all_of, any_of, none_of căutați anumite proprietăți specifice în collection. Aceste funcții se explică de la sine despre ceea ce ar trebui să facă. Odată cu introducerea lambdas în C ++ 11, sunt destul de la îndemână.

2. for_each

Am fost întotdeauna atât de obișnuit să folosesc vechi for buclă că acest lucru drăguț nu mi-a trecut niciodată prin vedere. Pe scurt, for_each aplică o funcție unei game de containere.

std::vector<int> collection = {2,4,4,1,1,3,9};

// notice that we pass x as reference!
std::for_each(begin(collection), end(collection), [] (int &x) {
    x += 26;
});

Dacă sunteți dezvoltator JavaScript, codul de mai sus ar trebui să sune.

3. count count_if

La fel ca funcțiile descrise la început, count și count_if ambele caută proprietăți specifice în colecția dvs. dată de date.

std::vector<int> collection={1, 9, 9, 4, 2, 6};

// How many 9s are there in collection?
int nines = std::count(begin(collection), end(collection), 9);
// How many elements of the collection are even?
int evens = std::count_if(begin(collection), end(collection), [](int x) {
    return x % 2 == 0;
});
// nines equals 2, evens equals 3

Și, ca rezultat, primiți numara care se potrivește cu valoarea dată sau are proprietatea dată pe care o furnizați sub forma unei funcții lambda.

4. find_if

Spuneți că doriți să găsiți primul element din colecția dvs. care să satisfacă o anumită proprietate. Poți să folosești find_if.

std::vector<int> collection = {1, 2, 0, 5, 0, 3, 4};

// itr contains the iterator to the first element following the specific property
auto itr = std::find_if(begin(collection), end(collection), [](int x) {
    return x % 2==0; // the property
});

Amintiți-vă, așa cum se arată în exemplul de mai sus, veți obține iterator la primul element care se potrivește proprietății date. Ce se întâmplă dacă doriți să găsiți toate elementele care se potrivesc proprietății folosind find_if?

Cum am descoperit biblioteca de algoritmi C si am
O artă abstractă la care să te uiți dacă te plictisești. (Steve Johnson pe Unsplash)

5. generate

Această funcție modifică în esență valorile colecției dvs. sau o gamă a acesteia, pe baza fișierului generator tu furnizezi. Generatorul este o funcție a formei
T f(); Unde T este un tip compatibil cu colecția noastră.

std::vector<int> collection={1, 2, 0, 5, 0, 3, 4};

int counter=0;

// notice that we are capturing counter by reference
std::generate(begin(collection), end(collection), [&]() {
    return counter++;
});

// collection gets replaced by values starting from 0
// modified collection = {0,1,2,3,4,5,6}

În exemplul de mai sus, observați că ne schimbăm de fapt colecția la loc . Și generatorul de aici este funcția lambda pe care am furnizat-o.

6. shuffle

Din standardul C ++ 17, random_shuffle a fost indepartat. Acum preferăm shuffle care este mai eficient, având în vedere că profită de antet random.

std::vector<int> collection = {1, 2, 13, 5, 12, 3, 4};

std::random_device rd;
std::mt19937 rand_gen(rd());
std::shuffle(begin(collection), end(collection), rand_gen);

Rețineți că folosim Mersenne Twister, un generator de numere pseudo-aleatorii introdus în C ++ 11.

Generatorii de numere aleatorii au devenit mult mai maturi în C ++ odată cu introducerea random bibliotecă și includerea unor metode mai bune.

7. nth_element

Această funcție este destul de utilă, având în vedere că are o complexitate interesantă.

Spuneți că doriți să știți n-a element al colecției dvs. dacă a fost sortată, dar nu doriți să sortați colecția pentru a crea un O (n jurnal (n)) Operațiune.

Ce ai face?

Atunci nth_element este prietenul tau. Găsește elementul dorit în Pe).

std::vector<int> collection = {1, 2, 13, 5, 12, 3, 4};

auto median_pos = collection.begin() + collection.size() / 2;
std::nth_element(begin(collection), median_pos, end(collection));

// note that the original vector will be changed due to the operations
// done by nth_element

Interesant este că nth_element poate face sau nu sortarea colecției dvs. Va face doar orice ordine este necesară pentru a găsi al n-lea element. Iată o discuție interesantă despre StackOverflow.

Și, de asemenea, puteți adăuga oricând propria funcție de comparație (cum am adăugat lambdas în exemplele anterioare) pentru ao face mai eficientă.

8. equal_range

Deci, să presupunem că aveți o colecție sortată de numere întregi. Doriți să găsiți intervalul în care toate elementele au o valoare specifică. De exemplu:

// sorted collection
std::vector<int> collection={1, 2, 5, 5, 5, 6, 9, 12};

// we are looking for a range where all elements equal to 5
auto range = std::equal_range(begin(collection), end(collection), 5);

// the required range is printed like this
std::cout << (range.first - begin(collection)) << " " <<
  			 (range.second - begin(collection)) << std::endl;

În acest cod, căutăm un gamă în vector care ține totul 5. Raspunsul este (2~4).

Desigur, putem folosi această funcție pentru propria noastră proprietate personalizată. Trebuie să vă asigurați că proprietatea pe care o aveți se aliniază la ordinea datelor. Vedea acest articol pentru referință.

In cele din urma, lower_bound și upper_bound ambele vă pot ajuta să realizați același lucru pe care l-ați realizat folosind equal_range.

9. merge inplace_merge

Imaginați-vă că aveți două colecții sortate (ce lucru distractiv să vă imaginați, nu-i așa?), Doriți să le îmbinați și doriți, de asemenea, ca colecția combinată să rămână sortată. Cum ai face asta?

Puteți doar să adăugați a doua colecție la prima și să sortați din nou rezultatul, care adaugă un plus O (jurnal (n)) factor. În loc de asta, putem folosi doar merge.

std::vector<int> c1 = {1, 2, 5, 5, 5, 6, 9, 12};
std::vector<int> c2 = {2, 4, 4, 5, 7, 15};

std::vector<int> result; // contains merged elements
std::merge(begin(c1), end(c1), begin(c2), end(c2), std::back_inserter(result));

// result = {1, 2, 2, 4, 4, 5, 5, 5, 5, 6, 7, 9, 12, 15}

Pe de altă parte, îți amintești când implementezi fuzionează sortarea, trebuie să fuzionăm două părți ale matricei noastre? inplace_merge poate fi utilizat în mod convenabil pentru asta.

Uită-te la acest mic fuzionează sort pe baza exemplului dat în cppreference:

void merge_sort(auto l, auto r)
{
    if(r - l > 1)
    {
        auto mid = l+(r-l)/2;
        merge_sort(l, mid);
        merge_sort(mid, r);
        std::inplace_merge(l, mid, r);
    }
}

std::vector<int> collection = {2, 4, 4, 1, 1, 3, 9};
merge_sort(begin(collection), end(collection));

Cat de tare e asta!

1611582369 989 Cum am descoperit biblioteca de algoritmi C si am
Apropo de cool, iată un tip cool. ? (Dawid Zawiła pe Unsplash)

10. minmax minmax_element

minmax returnează minimul și maximul celor două valori date, sau lista dată. Returnează o pereche și poate oferi, de asemenea, funcționalitatea propriei metode de comparație. minmax_element face același lucru și pentru containerul dvs.

int a = 9, b = 12;

// out.first contains the minimum element, out.second is the maximum one
auto out = std::minmax(a, b);

std::vector<int> collection = {6, 5, 3, 2, 1, 4, 6, 7};
auto result = std::minmax_element(begin(collection), end(collection));

// you can also add compare function as the third argument
// (result.first - collection.begin()) is the index of the minimum element
// (result.second - collection.begin()) is the index of the maximum element

11. accumulate partial_sum

accumulate face ce spune, o face se acumuleazăvalorile colecției dvs. în intervalul dat, utilizând valoarea inițială și o funcție de operație binară. Convinge-te singur:

std::vector<int> collection = {6, 5, 3, 2, 1, 4, 6, 7};

// Note that we are providing 0 as the initial value, as it should be.
// std::plus<int>() tells that the function should do sums
int sum = std::accumulate(begin(collection), end(collection), 0, std::plus<int>());

// What would happen if initial value was 0 instead of 1 in this call?
int prod = std::accumulate(begin(collection), end(collection), 1, std::multiplies<int>());

// You can also use your custom binary operation.
int custom = std::accumulate(begin(collection), end(collection), 0, [](int x, int y) {
    return x+y;
});

Deci, cum este valoarea custom calculat?

La început, cumulul ia valoarea inițială (0) la argument x, prima valoare din colecția (6) la argument y, face operațiunea, apoi o atribuie valorii acumulate. În al doilea apel, transmite valoarea acumulată către x și următorul element din colecție la y, și astfel continuă.

partial_sum se acumulează lucruri de genul, dar păstrează și rezultatul primului n termeni într-un container de destinație.

std::vector<int> collection = {6, 5, 3, 2, 1, 4, 6, 7};
std::vector<int> sums, mults;

// contains the partial sum of collection in result
std::partial_sum(begin(collection), end(collection), std::back_inserter(sums));

// contains the partial product
std::partial_sum(begin(collection), end(collection), std::back_inserter(mults), std::multiplies<int>());

Și, bineînțeles, așa cum vă așteptați, puteți utiliza propria operațiune personalizată.

12. adjacent_difference

Doriți să găsiți diferențele adiacente în valorile dvs., puteți utiliza pur și simplu această funcție.

std::vector<int> collection = {6, 5, 3, 2, 1, 4, 6, 7};
std::vector<int> diffs;
std::adjacent_difference(begin(collection), end(collection), std::back_inserter(diffs));
// The first element of diffs will be same as the first element of collection

Destul de simplu, nu?

Dar poate face mult mai mult. Uita-te la asta:

std::vector<int> fibs(10, 1);
std::adjacent_difference(begin(fibs), end(fibs) - 1, begin(fibs) + 1, std::plus<>{});

Ce fac aceste două linii? Ei găsesc primele 10 numere Fibonacci! Vezi cum? ?


Deci asta a fost pentru astăzi. Mulțumesc pentru lectură! Sper că ai învățat ceva nou.

Aș dori cu siguranță să aduc câteva lucruri noi pentru tine în viitorul apropiat.

Noroc!