Hvordan jeg opdagede C ++ - algoritmebiblioteket og lærte ikke at genopfinde hjulet

Den anden dag af nysgerrighed kiggede jeg ind i C ++ - algoritmebiblioteket. Og fandt ud af et stort antal seje funktioner!

Dette overraskede mig bogstaveligt talt.

Hvorfor? Jeg mener, at jeg for det meste har skrevet C ++ gennem hele mit universitetsliv. Og det var især på grund af mit kærlighedshat-forhold til konkurrencedygtig programmering.

Og desværre havde jeg aldrig rigtig draget fordel af dette fantastiske bibliotek, som C ++ har tilbudt os.

Gosh jeg følte mig så naiv!

Så jeg besluttede, at det var på tide at stoppe med at være naiv og kende nytten af ​​C ++ - algoritmer - i det mindste på et højere niveau. Og som en gammel mand engang sagde, at dele viden er magt -  så her er jeg.

Ansvarsfraskrivelse : Jeg har meget anvendte funktioner fra C ++ 11 og derover. Hvis du ikke er fortrolig med nyere udgaver af sproget, kan de kodestykker, jeg har angivet her, virke lidt klodset. På den anden side er biblioteket, vi diskuterer her, langt mere selvforsynende og elegant end noget, jeg har skrevet nedenfor. Du er velkommen til at finde fejl og påpege dem. Og også, jeg kunne ikke rigtig overveje mange af C ++ 17 tilføjelser i dette indlæg, da de fleste af dets funktioner endnu ikke skal bringes til live i GCC.

Så uden videre, lad os begynde!

  1. all_of any_of none_of

Disse funktioner blot kigge efter, om all,anyeller noneaf elementerne i en container følger nogle specifikke egenskaber, der er defineret af dig. Se eksemplet nedenfor:

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

Læg mærke til, hvordan den specifikke egenskab i eksemplet videregives som en lambda-funktion.

all_of, any_of, none_ofkig efter en bestemt ejendom i din collection. Disse funktioner er stort set selvforklarende for, hvad de skal gøre. Sammen med introduktionen af lambdas i C ++ 11 er de ret praktiske at bruge.

2. for_each

Jeg har altid været så vant til at bruge ældgamle forsløjfer, at denne søde ting aldrig passerede mit syn. Grundlæggende for_eachanvender en funktion til en række af en container.

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; });

Hvis du er JavaScript-udvikler, skal ovenstående kode ringe.

3. count count_if

Næsten ligesom de funktioner, der blev beskrevet i begyndelsen, countog count_ifbegge ser efter specifikke egenskaber i din givne dataindsamling.

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

Og et resultat, du modtager antallet, der matcher din givne værdi, eller har den givne egenskab, som du giver i form af en lambda-funktion.

4. find_if

Sig, at du vil finde det første element i din samling, der tilfredsstiller en bestemt ejendom. Du kan bruge 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 });

Husk, som vist i ovenstående eksempel, får du iteratoren til det første element, der matcher din givne ejendom. Så hvad hvis du vil finde alle de elementer, der matcher ejendommen ved hjælp af find_if?

5. generate

Denne funktion ændrer i det væsentlige værdierne i din samling eller en række af den baseret på den generator, du giver. Generatoren er en funktion af formularen

T f();hvor Ter en kompatibel type med vores samling.

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}

Bemærk i ovenstående eksempel, at vi faktisk ændrer vores samling på stedet . Og generatoren her er den lambda-funktion, vi leverede.

6. shuffle

Fra standarden på C ++ 17, random_shuffleer blevet fjernet. Nu foretrækker vi, shufflehvilket er mere effektivt, da det udnytter headeren 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);

Bemærk, at vi bruger Mersenne Twister, en pseudo-tilfældig talgenerator introduceret i C ++ 11.

Tilfældige talgeneratorer er blevet langt mere modne i C ++ med introduktionen af randombibliotek og inkludering af bedre metoder.

7. nth_element

Denne funktion er ret nyttig, da den har en interessant kompleksitet.

Sig, at du vil vide det n- element i din samling, hvis den blev sorteret, men du ikke ønsker at sortere samlingen for at oprette en O (n-log (n))operation.

Hvad ville du gøre?

nth_elementer din ven. Den finder det ønskede element i 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

Interessant nth_elementnok kan din samling muligvis blive sorteret eller ikke. Det gør bare den rækkefølge, det tager at finde det n-th element. Her er en interessant diskussion om StackOverflow.

Og også kan du altid tilføje din egen sammenligningsfunktion (som vi tilføjede lambdas i tidligere eksempler) for at gøre den mere effektiv.

8. equal_range

Så lad os sige, at du har en sorteret samling af heltal. Du vil finde det område, hvor alle elementerne har en bestemt værdi. For eksempel:

// 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;

I denne kode leder vi efter et interval i det, vectorder holder alt 5. Svaret er (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.

Jeg vil bestemt gerne medbringe nogle nye ting til dig igen i nær fremtid.

Skål!