Як я відкрив бібліотеку алгоритмів C ++ і навчився не винаходити колесо

Днями з цікавості я заглянув до бібліотеки алгоритмів C ++. І виявив досить велику кількість цікавих функцій!

Це буквально вразило мене.

Чому? Я маю на увазі, що в основному я писав C ++ протягом усього університетського життя. І це було особливо через мої стосунки любові і ненависті з конкурентним програмуванням.

І на жаль, я ніколи не користувався цією дивовижною бібліотекою, яку нам пропонує С ++.

Боже, я почувався таким наївним!

Тож я вирішив, що настав час перестати бути наївними та пізнати корисність алгоритмів С ++ - принаймні на вищому рівні. І як колись сказав старий, ділитися знаннями - це сила -  от і я тут.

Застереження : я широко використовував функції від C ++ 11 і пізніше. Якщо ви не зовсім знайомі з новішими виданнями мови, фрагменти коду, які я надав тут, можуть здатися дещо незграбними. З іншого боку, бібліотека, яку ми тут обговорюємо, є набагато самодостатнішою та елегантнішою за все, що я писав нижче. Не соромтеся знаходити помилки та вказувати на них. А також, я не міг насправді розглянути багато доповнень до C ++ 17 у цій публікації, оскільки більшість його функцій ще не втілені в життя в GCC.

Тож без зайвих сумнівів, почнемо!

  1. all_of any_of none_of

Ці функції просто шукають all,anyабо noneелементів контейнера відповідає певній визначеній вами властивості. Перевірте приклад нижче:

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

Зверніть увагу, як у прикладі конкретна властивість передається як лямбда-функція.

Тож all_of, any_of, none_ofшукайте якусь конкретну властивість у вашому collection. Ці функції майже повністю пояснюють, що вони повинні робити. Поряд із введенням лямбда в C ++ 11, вони дуже зручні у використанні.

2. for_each

Я завжди був настільки звик використовувати вікову forпетлю, що ця мила штука ніколи не переходила мені в очі. В основному, for_eachзастосовує функцію до діапазону контейнера.

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

Якщо ви розробник JavaScript, наведений вище код повинен дзвонити.

3. count count_if

Приблизно як функції, описані на початку, countі count_ifобидва шукають конкретні властивості у вашій колекції даних.

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

І в результаті ви отримуєте рахунок, який відповідає вашому заданому значенню або має дане властивість, яке ви надаєте у формі лямбда-функції.

4. find_if

Скажімо, ви хочете знайти перший елемент у вашій колекції, який задовольняє певній властивості. Можна використовувати 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 });

Пам'ятайте, як показано у наведеному вище прикладі, ви отримаєте ітератор до першого елемента, який відповідає заданій властивості. То що, якщо ви хочете знайти всі елементи, що відповідають властивості, використовуючи find_if?

5. generate

Ця функція по суті змінює значення вашої колекції або її діапазону на основі генератора, який ви надаєте. Генератор є функцією форми

T f();де Tсумісний тип з нашою колекцією.

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}

У наведеному вище прикладі зауважте, що ми фактично змінюємо колекцію на місці . І генератор тут - це лямбда-функція, яку ми надали.

6. shuffle

Зі стандарту C ++ 17, random_shuffleбуло видалено. Тепер ми віддаємо перевагу, shuffleщо є більш ефективним, враховуючи те, що воно використовує перевагу заголовка 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);

Зверніть увагу, що ми використовуємо Mersenne Twister, генератор псевдовипадкових чисел, представлений в C ++ 11.

Генератори випадкових чисел стали набагато зрілішими в C ++ із введенням randomбібліотека та включення кращих методів.

7. nth_element

Ця функція досить корисна, враховуючи те, що вона має цікаву складність.

Скажімо, ви хочете знати n-й елемент вашої колекції, якщо він був відсортований, але ви не хочете сортувати колекцію, щоб зробити O (n журнал (n))операції.

Що б ти зробив?

Тоді nth_elementваш друг. Він знаходить потрібний елемент в 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

Цікаво, що nth_elementваша колекція може бути відсортованою чи ні. Він просто зробить будь-який порядок, який потрібен, щоб знайти n-й елемент. Ось цікава дискусія щодо StackOverflow.

А також, ви завжди можете додати власну функцію порівняння (як ми додавали лямбди в попередніх прикладах), щоб зробити її більш ефективною.

8. equal_range

Отже, припустимо, у вас є відсортована колекція цілих чисел. Ви хочете знайти діапазон, у якому всі елементи мають певне значення. Наприклад:

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

У цьому коді ми шукаємо діапазон в vectorякий тримає все 5. Відповідь така (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!