Kā es atklāju C ++ algoritmu bibliotēku un iemācījos neizgudrot riteni no jauna

Kādu dienu ziņkārības dēļ es ieskatījos C ++ algoritmu bibliotēkā. Un uzzinājāt diezgan labu skaitu atdzist funkciju!

Tas mani burtiski pārsteidza.

Kāpēc? Es domāju, ka es savas universitātes dzīves laikā galvenokārt esmu rakstījis C ++. Un tas bija īpaši saistīts ar manām mīlestības un naida attiecībām ar konkurētspējīgu programmēšanu.

Un ļoti diemžēl es nekad nebiju īsti izmantojis šīs apbrīnojamās bibliotēkas priekšrocības, ko C ++ mums ir piedāvājis.

Dievs, es jutos tik naiva!

Tāpēc es nolēmu, ka ir pienācis laiks pārtraukt būt naivam un iepazīt C ++ algoritmu lietderību - vismaz augstākā līmenī. Un, kā kādreiz teica vecs vīrietis, dalīšanās ar zināšanām ir spēks -  tāpēc šeit es esmu.

Atruna : man ir ļoti izmantotas funkcijas no C ++ 11 un tālāk. Ja jums nav diezgan pazīstami jaunāki valodas izdevumi, šeit sniegtie kodu fragmenti var šķist mazliet neveikli. No otras puses, bibliotēka, kuru mēs šeit apspriežam, ir daudz pašpietiekama un eleganta nekā viss, ko esmu rakstījis zemāk. Jūtieties brīvi atrast kļūdas un norādīt uz tām. Turklāt es īsti nevarēju apsvērt daudzus C ++ 17 papildinājumus šajā ierakstā, jo lielākā daļa tā funkciju vēl ir jāievieš GCC dzīvē.

Tātad, bez liekas pārdomām, sāksim!

  1. all_of any_of none_of

Šīs funkcijas vienkārši meklēt, vai all,anyvai nonekonteinera elementi atbilst kādam konkrētam rekvizītam, kuru esat definējis. Pārbaudiet šo piemēru:

std::vector 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

Ievērojiet, kā piemērā īpašais īpašums tiek nodots kā lambda funkcija.

Tāpēc all_of, any_of, none_ofmeklējiet kādu īpašu īpašumu savā īpašumā collection. Šīs funkcijas diezgan lielā mērā izskaidro to, kas tām jādara. Līdz ar lambdas ieviešanu C ++ 11, tās ir diezgan ērti lietot.

2. for_each

Es vienmēr esmu bijis tik pieradis izmantot mūžseno forcilpu, ka šī jaukā lieta man nekad nav šķērsojusi redzi. Būtībā for_eachfunkcija tiek piemērota konteinera diapazonam.

std::vector 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; });

Ja esat JavaScript izstrādātājs, iepriekš norādītajam kodam vajadzētu piezvanīt.

3. count count_if

Diezgan līdzīgas sākumā aprakstītajām funkcijām, countun count_ifabas jūsu konkrētajā datu kolekcijā meklē īpašas īpašības.

std::vector 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

Rezultātā jūs saņemat skaitīšanu, kas atbilst jūsu dotajai vērtībai vai kam ir dotais rekvizīts, kuru jūs sniedzat lambda funkcijas veidā.

4. find_if

Pieņemsim, ka vēlaties atrast savu kolekcijas pirmo elementu, kas atbilst noteiktam īpašumam. Jūs varat izmantot find_if.

std::vector 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 });

Atcerieties, kā parādīts iepriekš, piemēram, jūs saņemsiet iterator uz pirmo elementu , kas atbilst jūsu doto īpašumu. Tātad, ja jūs vēlaties atrast visus elementus, kas atbilst īpašumam, izmantojot find_if?

5. generate

Šī funkcija, pamatojoties uz jūsu piedāvāto ģeneratoru, būtībā maina jūsu kolekcijas vai tās diapazona vērtības . Ģenerators ir formas funkcija

T f();kur Tir savietojams veids ar mūsu kolekciju.

std::vector 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}

Iepriekš minētajā piemērā ievērojiet, ka mēs faktiski mainām savu kolekciju uz vietas . Un ģenerators šeit ir lambda funkcija, kuru mēs nodrošinājām.

6. shuffle

No C ++ 17 standarta random_shuffleir noņemts. Tagad mēs dodam priekšroku tam, shufflekas ir efektīvāks, ņemot vērā to, ka tas izmanto galvenes priekšrocības random.

std::vector 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);

Ņemiet vērā, ka mēs izmantojam Mersenne Twister, pseido-nejaušu skaitļu ģeneratoru, kas ieviests C ++ 11.

Nejaušo skaitļu ģeneratori ir kļuvuši daudz nobriedušāki C ++, ieviešot randombibliotēka un labāku metožu iekļaušana.

7. nth_element

Šī funkcija ir diezgan noderīga, ņemot vērā, ka tai ir interesanta sarežģītība.

Pieņemsim, ka vēlaties uzzināt n-to kolekcijas elementu, ja tas ir sakārtots, bet nevēlaties kārtot kolekciju, lai izveidotu O (n žurnāls (n))darbība.

Ko tu darītu?

Tad nth_elementir tavs draugs. Tas atrod vajadzīgo elementu O (n) .

std::vector 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

Interesanti, nth_elementvai tas var padarīt jūsu kolekciju šķirotu. Tas vienkārši veiks visu nepieciešamo secību, lai atrastu n-to elementu. Šeit ir interesanta diskusija par StackOverflow.

Turklāt jūs vienmēr varat pievienot savu salīdzināšanas funkciju (tāpat kā iepriekšējos piemēros mēs pievienojām lambdas), lai tā būtu efektīvāka.

8. equal_range

Pieņemsim, ka jums ir sakārtota veselu skaitļu kolekcija. Jūs vēlaties atrast diapazonu, kurā visiem elementiem ir noteikta vērtība. Piemēram:

// sorted collection std::vector 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;

Šajā kodā mēs meklējam diapazonu , vectorkas satur visu 5. Atbilde ir (2~4).

Of course we can use this function for our own custom property. You need to ensure that the property you have aligns with the order of the data. See this article for reference.

Finally, lower_bound and upper_bound both can help you to achieve the same that you achieved using equal_range.

9. merge inplace_merge

Imagine you have two sorted collections (what a fun thing to imagine, right?), you want to merge them, and you also want the merged collection to remain sorted. How would you do that?

You can just add the second collection to the first one and sort the result again which adds an extra O(log(n))factor. Instead of that, we can just use merge.

std::vector c1 = {1, 2, 5, 5, 5, 6, 9, 12}; std::vector c2 = {2, 4, 4, 5, 7, 15}; std::vector 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}

On the other hand, do you remember when implementing merge sort, we need to merge two sides of our array? inplace_merge can be conveniently used for that.

Look at this tiny merge sort based on the example given in 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 collection = {2, 4, 4, 1, 1, 3, 9}; merge_sort(begin(collection), end(collection));

How cool is that!

10. minmax minmax_element

minmax returns the minimum and maximum of the given two values, or the given list. It returns a pair and it can also provide the functionality of your own comparison method. minmax_element does the same for your container.

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 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 does what it says, it accumulates values of your collection in the given range, using the initial value and a binary operation function. See for yourself:

std::vector 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() tells that the function should do sums int sum = std::accumulate(begin(collection), end(collection), 0, std::plus()); // 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()); // You can also use your custom binary operation. int custom = std::accumulate(begin(collection), end(collection), 0, [](int x, int y) { return x+y; });

So how is the value of custom calculated?

At the beginning, accumulate takes the initial value (0) to the argument x, the first value in the collection (6) to argument y, does the operation, then assigns it to the accumulated value. In the second call, it passes the accumulated value to x and the next element in the collection to y, and thus proceeds.

partial_sum does things much like accumulate, but it also keeps the result of first nterms in a destination container.

std::vector collection = {6, 5, 3, 2, 1, 4, 6, 7}; std::vector 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());

And of course as you expected, you can use your own custom operation.

12. adjacent_difference

You want to find the adjacent differences in your values, you can simply use this function.

std::vector collection = {6, 5, 3, 2, 1, 4, 6, 7}; std::vector 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

Pretty simple, right?

But it can do much more. Look at this:

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

What do these two lines do? They find the first 10 Fibonacci numbers! Do you see how? ?

So that was it for today. Thanks for reading! I hope you learned something new.

Es noteikti vēlētos tuvākajā laikā atkal paņemt līdzi jaunas lietas.

Priekā!