Wie ich die C ++ - Algorithmusbibliothek entdeckte und lernte, das Rad nicht neu zu erfinden

Neulich habe ich aus Neugier in die C ++ - Algorithmusbibliothek geschaut. Und fand eine ganze Reihe cooler Funktionen heraus!

Das hat mich buchstäblich erstaunt.

Warum? Ich meine, ich habe während meines gesamten Universitätslebens hauptsächlich C ++ geschrieben. Und es war besonders wegen meiner Hassliebe zu wettbewerbsfähiger Programmierung.

Und leider hatte ich diese erstaunliche Bibliothek, die C ++ uns angeboten hat, nie wirklich ausgenutzt.

Meine Güte, ich fühlte mich so naiv!

Also entschied ich, dass es Zeit war, nicht mehr naiv zu sein und die Nützlichkeit von C ++ - Algorithmen kennenzulernen - zumindest auf einer höheren Ebene. Und wie ein alter Mann einmal sagte, Wissen zu teilen ist Macht -  also bin ich hier.

Haftungsausschluss : Ich habe stark Funktionen aus C ++ 11 und höher verwendet. Wenn Sie mit neueren Editionen der Sprache nicht ganz vertraut sind, wirken die hier bereitgestellten Codefragmente möglicherweise etwas ungeschickt. Andererseits ist die Bibliothek, die wir hier diskutieren, weitaus autarker und eleganter als alles, was ich unten geschrieben habe. Fühlen Sie sich frei, Fehler zu finden und darauf hinzuweisen. Außerdem konnte ich viele der C ++ 17-Ergänzungen in diesem Beitrag nicht wirklich berücksichtigen, da die meisten Funktionen in GCC noch nicht zum Leben erweckt wurden.

Also, ohne weiteres, fangen wir an!

  1. all_of any_of none_of

Diese Funktionen suchen einfach, ob all,anyoder noneder Elemente eines Containers folgt einer bestimmten von Ihnen definierten Eigenschaft. Überprüfen Sie das folgende Beispiel:

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

Beachten Sie, wie im Beispiel die bestimmte Eigenschaft als Lambda-Funktion übergeben wird.

Suchen Sie also all_of, any_of, none_ofnach einer bestimmten Immobilie in Ihrem collection. Diese Funktionen sind ziemlich selbsterklärend für das, was sie tun sollen. Zusammen mit der Einführung von Lambdas in C ++ 11 sind sie sehr praktisch zu verwenden.

2. for_each

Ich war schon immer so daran gewöhnt, eine uralte forSchleife zu verwenden, dass mir dieses süße Ding nie in den Sinn kam. Wendet grundsätzlich for_eacheine Funktion auf einen Bereich eines Containers an.

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

Wenn Sie ein JavaScript-Entwickler sind, sollte der obige Code eine Glocke läuten.

3. count count_if

Ähnlich wie die eingangs beschriebenen Funktionen, countund count_ifbeide suchen nach bestimmten Eigenschaften in Ihrer gegebenen Datensammlung.

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

Als Ergebnis erhalten Sie die Anzahl , die Ihrem angegebenen Wert entspricht, oder haben die angegebene Eigenschaft, die Sie in Form einer Lambda-Funktion angeben.

4. find_if

Angenommen, Sie möchten das erste Element in Ihrer Sammlung finden, das eine bestimmte Eigenschaft erfüllt. Sie können verwenden 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 });

Denken Sie daran, wie im obigen Beispiel gezeigt, dass Sie den Iterator zum ersten Element bringen , das Ihrer angegebenen Eigenschaft entspricht. Was ist, wenn Sie alle Elemente finden möchten, die mit der Eigenschaft übereinstimmen find_if?

5. generate

Diese Funktion ändert im Wesentlichen die Werte Ihrer Sammlung oder einen Bereich davon, basierend auf dem von Ihnen bereitgestellten Generator . Der Generator ist eine Funktion der Form

T f();Wo Tist ein kompatibler Typ mit unserer Sammlung.

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}

In dem obigen Beispiel, dass Ankündigung ändern wir tatsächlich unsere Sammlung an Ort und Stelle . Und der Generator hier ist die Lambda-Funktion, die wir bereitgestellt haben.

6. shuffle

Aus dem Standard von C ++ 17, random_shufflewurde entfernt. Jetzt bevorzugen wir, shufflewas effektiver ist, da es den Header nutzt 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);

Beachten Sie, dass wir Mersenne Twister verwenden, einen in C ++ 11 eingeführten Pseudozufallszahlengenerator.

Zufallszahlengeneratoren sind in C ++ mit der Einführung von weitaus ausgereifter geworden randomBibliothek und Einbeziehung besserer Methoden.

7. nth_element

Diese Funktion ist sehr nützlich, da sie eine interessante Komplexität aufweist.

Angenommen, Sie möchten das n-te Element Ihrer Sammlung kennen, wenn es sortiert wurde, aber Sie möchten die Sammlung nicht sortieren, um ein O (n log (n)) zu erstellen.Operation.

Was würden Sie tun?

Dann nth_elementist dein Freund. Es findet das gewünschte Element in 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

Interessanterweise nth_elementkann Ihre Sammlung sortiert werden oder nicht. Es wird einfach jede Reihenfolge ausführen, die erforderlich ist, um das n-te Element zu finden. Hier ist eine interessante Diskussion über StackOverflow.

Außerdem können Sie jederzeit Ihre eigene Vergleichsfunktion hinzufügen (wie wir in den vorherigen Beispielen Lambdas hinzugefügt haben), um sie effektiver zu gestalten.

8. equal_range

Angenommen, Sie haben eine sortierte Sammlung von Ganzzahlen. Sie möchten den Bereich ermitteln, in dem alle Elemente einen bestimmten Wert haben. Zum Beispiel:

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

In diesem Code suchen wir für einen Bereich in der vectordie mit allen hält 5. Die Antwort lautet (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.

I would definitely like to bring some new stuff for ya’ll again in near future.

Cheers!