Comment j'ai découvert la bibliothèque d'algorithmes C ++ et appris à ne pas réinventer la roue

L'autre jour, par curiosité, j'ai regardé dans la bibliothèque d'algorithmes C ++. Et découvrez un bon nombre de fonctionnalités intéressantes!

Cela m'a littéralement étonné.

Pourquoi? Je veux dire que j'ai surtout écrit du C ++ tout au long de ma vie universitaire. Et c'était surtout à cause de ma relation amour-haine avec la programmation compétitive.

Et très malheureusement, je n'avais jamais vraiment profité de cette étonnante bibliothèque que C ++ nous a offerte.

Gosh je me sentais si naïf!

J'ai donc décidé qu'il était temps d'arrêter d'être naïf et de connaître l'utilité des algorithmes C ++ - au moins à un niveau supérieur. Et comme un vieil homme l'a dit un jour, partager la connaissance est un pouvoir -  alors me voici.

Avertissement : J'ai beaucoup utilisé des fonctionnalités de C ++ 11 et au-delà. Si vous n'êtes pas tout à fait familier avec les nouvelles éditions du langage, les extraits de code que j'ai fournis ici peuvent sembler un peu maladroits. D'un autre côté, la bibliothèque dont nous parlons ici est beaucoup plus autonome et élégante que tout ce que j'ai écrit ci-dessous. N'hésitez pas à trouver des erreurs et à les signaler. Et aussi, je ne pourrais pas vraiment considérer beaucoup d'ajouts de C ++ 17 dans cet article, car la plupart de ses fonctionnalités n'ont pas encore pris vie dans GCC.

Alors sans plus tarder, commençons!

  1. all_of any_of none_of

Ces fonctions recherchent simplement si all,anyou nonedes éléments d'un conteneur suit une propriété spécifique définie par vous. Consultez l'exemple ci-dessous:

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

Notez comment, dans l'exemple, la propriété spécifique est transmise en tant que fonction lambda.

Alors all_of, any_of, none_ofrecherchez une propriété spécifique dans votre collection. Ces fonctions sont assez explicites sur ce qu'elles sont censées faire. Parallèlement à l'introduction des lambdas en C ++ 11, ils sont assez pratiques à utiliser.

2. for_each

J'ai toujours été tellement habitué à utiliser une forboucle séculaire que cette chose mignonne ne m'a jamais traversé la vue. Fondamentalement, for_eachapplique une fonction à une plage d'un conteneur.

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

Si vous êtes un développeur JavaScript, le code ci-dessus devrait sonner une cloche.

3. count count_if

Un peu comme les fonctions décrites au début, countet les count_ifdeux recherchent des propriétés spécifiques dans votre collection de données donnée.

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

Et un résultat, vous recevez le nombre qui correspond à votre valeur donnée, ou a la propriété donnée que vous fournissez sous la forme d'une fonction lambda.

4. find_if

Supposons que vous souhaitiez trouver le premier élément de votre collection satisfaisant une propriété particulière. Vous pouvez utiliser 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 });

N'oubliez pas, comme indiqué dans l'exemple ci-dessus, vous obtiendrez l' itérateur du premier élément qui correspond à votre propriété donnée. Alors que faire si vous voulez trouver tous les éléments qui correspondent à la propriété en utilisant find_if?

5. generate

Cette fonction modifie essentiellement les valeurs de votre collection, ou une plage de celle-ci, en fonction du générateur que vous fournissez. Le générateur est fonction de la forme

T f();Test un type compatible avec notre collection.

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}

Dans l'exemple ci-dessus, notez que nous modifions en fait notre collection sur place . Et le générateur ici est la fonction lambda que nous avons fournie.

6. shuffle

À partir de la norme C ++ 17, random_shufflea été retiré. Maintenant, nous préférons shufflece qui est le plus efficace, étant donné qu'il tire parti de l'en-tête 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);

Notez que nous utilisons Mersenne Twister, un générateur de nombres pseudo-aléatoires introduit dans C ++ 11.

Les générateurs de nombres aléatoires sont devenus beaucoup plus matures en C ++ avec l'introduction de randombibliothèque et inclusion de meilleures méthodes.

sept. nth_element

Cette fonction est assez utile, étant donné qu'elle a une complexité intéressante.

Supposons que vous souhaitiez connaître le n-ième élément de votre collection s'il a été trié, mais que vous ne voulez pas trier la collection pour créer un O (n log (n))opération.

Qu'est-ce que tu ferais?

Alors nth_elementest votre ami. Il trouve l'élément souhaité dans 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

Fait intéressant, nth_elementpeut ou peut ne pas faire votre collection triée. Il fera juste l'ordre qu'il faut pour trouver le n-ième élément. Voici une discussion intéressante sur StackOverflow.

Et aussi, vous pouvez toujours ajouter votre propre fonction de comparaison (comme nous avons ajouté des lambdas dans les exemples précédents) pour la rendre plus efficace.

8. equal_range

Alors disons que vous avez une collection triée d'entiers. Vous voulez trouver la plage dans laquelle tous les éléments ont une valeur spécifique. Par exemple:

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

Dans ce code, nous recherchons une plage dans le vectorqui contient tout 5. La réponse est (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!