大きいSTLアルゴリズムチュートリアル:ソート操作

この次の部分でthe big STL algorithm tutorial , 我々は並べ替え操作をカバーします-異なるシリーズでカバーされる範囲を除いて.

sort

stable_sort

partial_sort

partial_sort_copy

is_sorted

is_sorted_until

nth_element

sortそんなことを言っても過言ではないかstd::sort は、上記のソートアルゴリズムの旗艦アルゴリズムですか?少なくとも、このアルゴリズムの基礎を議論するなら、少なくとも、すべての詳細を議論する必要はありません.
デフォルトではstd::sort つのパラメータ、2つの反復子を使用して、ユーザーがソートしたい範囲を定義します.
定義する3番目のオプションパラメータがあります.いつものように、それはラムダ、関数ポインタまたは関数オブジェクト(ファンクション)でありえます.これはバイナリ関数で、2つの要素を受け取り、boolを返します.この関数は、非常に合理的に見えるコンポーネントを変更してはいけません.この関数はtrue 最初のパラメータがソートされた範囲の2番目の前にある場合.std::sort はvoidアルゴリズムで、何も返しません.コンパレータの有無による例を見ましょう.

#include <iostream>
#include <algorithm>
#include <vector>

enum class Transmission {Automatic, Manual};

struct Car {
  int horsePower;
  Transmission transmission;
};

int main() {
  std::vector<int> numbers {1,9,7,4,5,6,3,8,2};
  std::sort(numbers.begin(), numbers.end());
  std::for_each(numbers.begin(), numbers.end(), [](auto num){ std::cout << num << " ";});    
  std::cout << '\n';

  std::vector cars {
    Car{100, Transmission::Automatic},
    Car{80, Transmission::Manual},
    Car{250, Transmission::Manual},
    Car{100, Transmission::Manual},
    Car{120, Transmission::Automatic},
  };

  std::sort(cars.begin(), cars.end(), [](const Car& lhs, const Car& rhs){return lhs.horsePower < rhs.horsePower;});
  std::for_each(cars.begin(), cars.end(), [](auto car){ std::cout << "Car.hp " << car.horsePower << " " << ((car.transmission == Transmission::Manual) ? "manual" : "automatic") << '\n';});    
}

上の例は非常に簡単ですが、どのように注意する価値があるコンパレータはどのように書かれている.より小さいパフォーマンス・カーがより強いものの前に来るようにtrue 最初に渡される車が第2より弱いならば.それは私たちが昇天したコンテナを構築した方法です.
stable_sort違いは何ですかstable_sort and sort ?stable_sort 適用後、等価要素の順序が保存されることを保証します.sort そんな約束はしない.
言い換えれば、車の例に固執して、入力容器に手動のギアボックス車が自動的なものに先行して、彼らが両方とも同じパフォーマンスを持つならば、それは呼び出しの後でさえそれの前に来るでしょうstable_sort を参照してください.

#include <iostream>
#include <algorithm>
#include <vector>

enum class Transmission {Automatic, Manual};

struct Car {
  int horsePower;
  Transmission transmission;
};

int main() {
  std::vector cars {
    Car{100, Transmission::Automatic},
    Car{80, Transmission::Manual},
    Car{250, Transmission::Manual},
    Car{100, Transmission::Manual},
    Car{120, Transmission::Automatic},
  };

  std::stable_sort(cars.begin(), cars.end(), [](const Car& lhs, const Car& rhs){return lhs.horsePower < rhs.horsePower;});
  std::for_each(cars.begin(), cars.end(), [](auto car){ std::cout << "Car.hp " << car.horsePower << " " << ((car.transmission == Transmission::Manual) ? "manual" : "automatic") << '\n';});    
}

partial_sort名前が示すように、このアルゴリズムはコンテナ全体をソートすることはありません.しかし、それは正確に何をソートしますか?
それは入力として3つのイテレータをプラスして、我々がすでに見た比較器と異なっていないオプションのコンパレータを加えます.つの反復子に集中しましょう.
最初の1つは入力範囲の始まりを表し、3番目は1番目です.
あなたが範囲をソートするまで、中間のものはポイントを与えます.このイテレータは、最後のソートされた値ではなく、範囲をソートするまでの位置を示します.
簡単な例を見てみましょう.

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector numbers {6, 8, 1, 5, 9, 4, 7, 2, 3};

  std::partial_sort(numbers.begin(), numbers.begin()+4, numbers.end());
  std::for_each(numbers.begin(), numbers.end(), [](auto number){ std::cout << number << ' ';});    
}
/*
1 2 3 4 9 8 7 6 5 
*/

この例では、ランダム順序で1から9までの数のベクトルがあります.( C + 20を使用して、型を省略することができます.コールpartial_sort 中の要素がある容器全体にnumbers.begin()+4 .numbers.begin()+4 位置のポイント9 最初のベクトルでは、5番目の数字(0から始まる位置4)です.だから我々の呼び出しpartial_sort 番目の要素(除外)まで要素をソートしたいので、最初の4つの要素を指定します.
その結果1 2 3 4 9 8 7 6 5 それを正確に示す.最初の4つの場所では、我々は、要素をソートしていない後.彼らは逆のソートに従っているようですが、だまされないでください、それはちょうど偶然の一致です.位置の後の要素middle 特定の順序に従ってはいけません.
partial_sort_copy partial_sort_copy とはpartial_sort それから、多くは予想します.私たちが今までにこのシリーズで見たことに基づいて、あなたはおそらくそれが出力範囲の始めを意味している余分のパラメタから離れて同じサインを持っていると思います.
しかし、それはそうではありません.
つの入力イテレータの代わりに、それは2を取るだけです.最初は1つ、範囲の終わりは部分的にソートしたい.それから、2つの出力イテレータを始めと1つに取ります.
そしてもちろん、通常のオプションのコンパレータがあります.
この出力範囲の長さは、どのように多くの要素をソートするかを定義します.例を見てみましょう.

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector numbers {6, 8, 1, 5, 9, 4, 7, 2, 3};
  std::vector<int> output(4);

  std::partial_sort_copy(numbers.begin(), numbers.end(), output.begin(), output.end());
  std::for_each(output.begin(), output.end(), [](auto number){ std::cout << number << ' ';});    
}
/*
1 2 3 4 
*/

注意すべきことがいくつかあります.

ソートされた要素だけがコピーされます.

std::partial_sort_copy 出力範囲の大きさをチェックします.言い換えると、デフォルトではベクトルを初期化し、その後容量を予約すると、出力ベクトルのサイズがまだ0であるため、何もコピーされません.

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector numbers {6, 8, 1, 5, 9, 4, 7, 2, 3};
  std::vector<int> output;
  output.reserve(4);

  std::partial_sort_copy(numbers.begin(), numbers.end(), output.begin(), output.end());
  std::cout << std::boolalpha << "is the output empty? " << output.empty() << '\n';
}
/*
is the output empty? true
*/

個人的に、私はこのアルゴリズムのサインがそれほど大きくないとわかります.それは我々が使用した慣習に従っていない<algorithms> ヘッダ.出力範囲を定義するのは非実用的だと思います.呼び出し側がすべての挿入された要素を収容するのに十分大きいことを確認しなければならない最初だけを求めるより安全です.しかし、この解決策では、特定のサイズにベクトルを初期化しなければならず、初期化時に同じ要素をn回、n要素の既定の初期化をコピーすることを意味します.安いかもしれませんが、場合によっては高価かもしれません.というのは、単にあなたがstd::back_inserter 出力として、それは問題ではない.
is_sorted is_sorted 超簡単です.これは、範囲の開始と終了をオプションの比較器を使用して、範囲をソートするかどうかをbool

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector sortedNumbers {1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::vector unsortedNumbers {6, 8, 1, 5, 9, 4, 7, 2, 3};
  std::vector descendingNumbers {9, 8, 7, 6, 5, 4, 3, 2, 1};
  std::cout << std::boolalpha << "is the sortedNumbers sorted? " << std::is_sorted(sortedNumbers.begin(), sortedNumbers.end()) << '\n';
  std::cout << std::boolalpha << "is the unsortedNumbers sorted? " << std::is_sorted(unsortedNumbers.begin(), unsortedNumbers.end()) << '\n';
  std::cout << std::boolalpha << "is the descendingNumbers sorted? " << std::is_sorted(descendingNumbers.begin(), descendingNumbers.end()) << '\n';
  std::cout << std::boolalpha << "is the descendingNumbers sorted? " << std::is_sorted(descendingNumbers.begin(), descendingNumbers.end(), [](auto lfs, auto rhs){ return lfs > rhs; }) << '\n';
  std::cout << std::boolalpha << "is the descendingNumbers sorted? " << std::is_sorted(descendingNumbers.begin(), descendingNumbers.end(), std::greater<>{}) << '\n';
}
/* 
is the sortedNumbers sorted? true
is the unsortedNumbers sorted? false
is the descendingNumbers sorted? false
is the descendingNumbers sorted? true
is the descendingNumbers sorted? true
*/

ソートされていることを自分自身を思い出させる価値があるoperator< . あなたがそれを考えてもdescendingNumbers きれいにソートされます.std::is_sorted デフォルトでそう思わない.別の比較器に基づいて比較する場合は、あなたが最後の2行で見ることができるように、それを渡す必要があります.
is_sorted_until is_sorted_until その開始と終了とオプションの比較器で定義される範囲をとります.最初の項目を開始する最後のソート要素を指すイテレータを返します.
あなたが呼ぶならばis_sorted の範囲を返します.is_sorted_until , 返すtrue . 一方、返り値+ 1でコールすると、結果はfalse .

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector numbers {1, 2, 3, 4, 9, 5, 6, 7, 8, 9};
  auto lastSortedNumber = std::is_sorted_until(numbers.begin(), numbers.end());
  std::cout << "Last sorted number in numbers: " << *lastSortedNumber << '\n';
  std::cout << std::boolalpha;
  std::cout << "std::is_sorted(numbers.begin(), lastSortedNumber): " << std::is_sorted(numbers.begin(), lastSortedNumber) << '\n';
  std::cout << "std::is_sorted(numbers.begin(), lastSortedNumber+1): " << std::is_sorted(numbers.begin(), lastSortedNumber+1) << '\n';
}
/*
Last sorted number in numbers: 5
std::is_sorted(numbers.begin(), lastSortedNumber): true
std::is_sorted(numbers.begin(), lastSortedNumber+1): false
*/

nth_element nth_element 私がそれを見たとき、その名前で私に何も言わなかった機能です.あなたは、それのようにそれを得ますか?
よろしい.しばらくの間無視しましょう.nth_element コンテナがソートされた場合、そこにある要素を見つけるために、n番目の位置にコンテナを配置します.
何か特定の順序とより大きなものに続いていないより小さいか等しい要素がある前に.
パラメータはpartial_sort . 最初のパラメータは先頭、3番目は終わり、中央にはn番目の要素があります.いつものように、カスタムコンパレータで渡すことができます.
例を見てみましょう.

#include <iostream>
#include <algorithm>
#include <vector>


int main() {
  std::vector numbers {6, 8, 1, 4, 9, 5, 7, 2, 3};
  std::nth_element(numbers.begin(), numbers.begin()+4, numbers.end());
  std::for_each(numbers.begin(), numbers.end(), [](auto number){ std::cout << number << ' ';});
  std::cout << '\n';
  std::cout << "The fifth largest element is: " << numbers[4] << '\n';
}

/*
3 2 1 4 5 6 7 8 9 
The fifth largest element is: 5

*/

上の例では、numbers.begin()+4 中間パラメータとして、我々は2009年に5番目の最大の要素は何かを決めたnumbers .

結論
今日、ソートアルゴリズムについて学びました.いくつかはかなり簡単ですsort , partial_sort or is_sorted ), 中nth_element 少なくとも私-考えてくださいpartial_sort_copy 私たちにいくつかの驚きと矛盾を与えた.私は、あなたが今日の発見を楽しんだことを望みます.

接続深い
あなたがこの記事をおもしろく見つけたならばsubscribe to my personal blog そして、接続しましょう!