Cómo descubrí la biblioteca de algoritmos C ++ y aprendí a no reinventar la rueda

El otro día, por curiosidad, busqué en la biblioteca de algoritmos C ++. ¡Y descubrí un buen número de funciones interesantes!

Esto literalmente me asombró.

¿Por qué? Quiero decir, he escrito principalmente C ++ a lo largo de mi vida universitaria. Y fue particularmente por mi relación de amor-odio con la programación competitiva.

Y muy desafortunadamente, nunca había aprovechado realmente esta increíble biblioteca que C ++ nos ha ofrecido.

¡Dios, me sentí tan ingenuo!

Así que decidí que era hora de dejar de ser ingenuo y conocer la utilidad de los algoritmos C ++, al menos en un nivel superior. Y como dijo una vez un anciano, compartir conocimientos es poder,  así que aquí estoy.

Descargo de responsabilidad : He utilizado mucho funciones de C ++ 11 y posteriores. Si no está muy familiarizado con las ediciones más recientes del lenguaje, los fragmentos de código que he proporcionado aquí pueden parecer un poco torpes. Por otro lado, la biblioteca que discutimos aquí es mucho más autosuficiente y elegante que cualquier cosa que haya escrito a continuación. Siéntase libre de encontrar errores y señalarlos. Y también, realmente no podría considerar muchas de las adiciones de C ++ 17 en esta publicación, ya que la mayoría de sus características aún no han cobrado vida en GCC.

Así que sin más preámbulos, ¡comencemos!

  1. all_of any_of none_of

Estas funciones simplemente buscan si all,anyo nonede los elementos de un contenedor sigue alguna propiedad específica definida por usted. Mira el ejemplo a continuación:

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

Observe cómo en el ejemplo, la propiedad específica se pasa como una función lambda.

Así que all_of, any_of, none_ofbusque alguna propiedad específica en su collection. Estas funciones se explican por sí mismas sobre lo que se supone que deben hacer. Junto con la introducción de lambdas en C ++ 11, son bastante útiles de usar.

2. for_each

Siempre he estado tan acostumbrado a usar un forlazo antiguo que esta linda cosa nunca cruzó mi vista. Básicamente, for_eachaplica una función a un rango de un contenedor.

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 es un desarrollador de JavaScript, el código anterior debería sonarle.

3. count count_if

Muy parecido a las funciones descritas al principio, county count_ifambas buscan propiedades específicas en su colección de datos dada.

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

Y como resultado, recibe el recuento que coincide con su valor dado, o tiene la propiedad dada que proporciona en forma de función lambda.

4. find_if

Supongamos que desea encontrar el primer elemento de su colección que satisfaga una propiedad en particular. Puede utilizar 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 });

Recuerde, como se muestra en el ejemplo anterior, obtendrá el iterador para el primer elemento que coincida con su propiedad dada. Entonces, ¿qué pasa si desea encontrar todos los elementos que coinciden con la propiedad que utiliza find_if?

5. generate

Esta función esencialmente cambia los valores de su colección, o un rango de ella, en función del generador que proporcione. El generador es una función de la forma

T f();donde Tes un tipo compatible con nuestra colección.

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}

En el ejemplo anterior, observe que en realidad estamos cambiando nuestra colección en el lugar . Y el generador aquí es la función lambda que proporcionamos.

6. shuffle

Desde el estándar de C ++ 17, random_shuffleha sido removido. Ahora preferimos shufflecuál es más efectivo, dado que aprovecha el encabezado 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);

Tenga en cuenta que estamos usando Mersenne Twister, un generador de números pseudoaleatorios introducido en C ++ 11.

Los generadores de números aleatorios se han vuelto mucho más maduros en C ++ con la introducción de randombiblioteca e inclusión de mejores métodos.

7. nth_element

Esta función es bastante útil, dado que tiene una complejidad interesante.

Digamos que quiere saber el n-ésimo elemento de su colección si fue ordenado, pero no quiere ordenar la colección para hacer un O (n log (n))operación.

¿Qué harías?

Entonces nth_elementes tu amigo. Encuentra el elemento deseado en 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

Curiosamente, nth_elementpuede que su colección esté ordenada o no. Simplemente hará el orden que sea necesario para encontrar el n-ésimo elemento. Aquí hay una discusión interesante sobre StackOverflow.

Y también, siempre puede agregar su propia función de comparación (como agregamos lambdas en ejemplos anteriores) para que sea más efectiva.

8. equal_range

Digamos que tiene una colección ordenada de números enteros. Desea encontrar el rango en el que todos los elementos tienen un valor específico. Por ejemplo:

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

En este código, buscamos un rango en el vectorque contenga todo 5. La respuesta es (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!