C ++アルゴリズムライブラリを発見し、車輪の再発明をしないことを学んだ方法

先日、好奇心から、C ++アルゴリズムライブラリを調べました。そして、かなりの数のクールな機能を見つけました!

これは文字通り私を驚かせました。

どうして?つまり、私は大学生活を通してほとんどC ++を書いてきました。そして、それは特に競技プログラミングとの私の愛憎関係のためでした。

そして非常に残念なことに、C ++が提供してくれたこの素晴らしいライブラリを実際に利用したことはありませんでした。

おやおや、私はとてもナイーブに感じました!

それで、私は、ナイーブになるのをやめて、少なくともより高いレベルで、C ++アルゴリズムの有用性を知る時が来たと判断しました。そして、老人がかつて言ったように、知識を共有することは力です— それで私はここにいます。

免責事項:C ++ 11以降の機能を頻繁に使用しています。この言語の新しいエディションに精通していない場合は、ここで提供したコードスニペットが少し不器用に見えるかもしれません。一方、ここで説明するライブラリは、私が以下に書いたものよりもはるかに自給自足でエレガントです。間違いを見つけて指摘してください。また、その機能のほとんどがGCCでまだ実現されていないため、この投稿でC ++ 17の追加の多くを実際に検討することはできませんでした。

それで、それ以上の苦労なしに、始めましょう!

  1. all_of any_of none_of

これらの機能は、単にかどうかを探しallanyまたは 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.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.3。 count count_if

最初に説明した関数とほとんど同じでcountcount_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.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.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.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);

C ++ 11で導入された疑似乱数ジェネレーターであるMersenneTwisterを使用していることに注意してください。

乱数ジェネレーターは、C ++の導入により、はるかに成熟しました。 randomライブラリとより良いメソッドの包含。

7。 nth_element

この関数は、興味深い複雑さがあるため、非常に便利です。

コレクションが並べ替えられた場合、コレクションのn番目の要素を知りたいが、コレクションを並べ替えてO(n log(n))を作成したくないとします。操作。

あなたならどうしますか?

Then nth_element is your friend. It finds the desired 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

Interestingly, nth_element may or may not make your collection sorted. It will just do whatever order it takes to find the n-th element. Here is an interesting discussion on StackOverflow.

And also, you can always add your own comparison function (like we added lambdas in previous examples) to make it more effective.

8. equal_range

So let’s say you have a sorted collection of integers. You want to find the range in which all the elements have a specific value. For example:

// 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 this code, we are looking for a range in the vector that holds all 5. The answer is (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!