C++
並べ替え

備考

指定された順序でシーケンスコンテナをソートする

コンテナ内の値にすでにオーバーロードされている演算子がある場合、 std::sortを特殊なファンクタとともに使用して、昇順または降順のいずれかでstd::sortことができます。

#include <vector>
#include <algorithm>
#include <functional>

std::vector<int> v = {5,1,2,4,3};

//sort in ascending order (1,2,3,4,5)
std::sort(v.begin(), v.end(), std::less<int>());

// Or just:
std::sort(v.begin(), v.end());

//sort in descending order (5,4,3,2,1)
std::sort(v.begin(), v.end(), std::greater<int>());

//Or just:
std::sort(v.rbegin(), v.rend());

std::sort(v.begin(), v.end(), std::less<>());     // ascending order
std::sort(v.begin(), v.end(), std::greater<>());  // descending order

オーバーロードされた少ない演算子によるシーケンスコンテナのソート

順序付け関数が渡されない場合、 std::sortは、要素のペアに対してoperator<を呼び出すことによって要素を順序付けします。これは、文脈上bool変換可能な型（またはbool ）を返す必要があります。基本型（整数、浮動小数点数、ポインタなど）は既に比較演算子で構築されています。

この演算子をオーバーロードして、デフォルトのsort呼び出しをユーザー定義型で動作させることができます。

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>    

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    // Use variable to provide total order operator less
    //`this` always represents the left-hand side of the compare.
    bool operator<(const Base &b) const { 
        return this->variable < b.variable;
    }
    
    int variable;
};

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using operator<(const Base &b) function
    std::sort(vector.begin(), vector.end());
    std::sort(deque.begin(), deque.end());
    // List must be sorted differently due to its design
    list.sort();

    return 0;
}

compare関数を使用してシーケンスコンテナをソートする

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
       
    int variable;
};

bool compare(const Base &a, const Base &b) {
    return a.variable < b.variable;
}

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using comparing function
    std::sort(vector.begin(), vector.end(), compare);
    std::sort(deque.begin(), deque.end(), compare);
    list.sort(compare);

    return 0;
}

ラムダ式を使用したシーケンスコンテナのソート（C ++ 11）

// Include sequence containers
#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>

// Include sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    int variable;
};


int main() {
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // We're using C++11, so let's use initializer lists to insert items.
    std::vector <Base> vector = {a, b};
    std::deque <Base> deque = {a, b};
    std::list <Base> list = {a, b};
    std::array <Base, 2> array = {a, b};
    std::forward_list<Base> flist = {a, b};
    
    // We can sort data using an inline lambda expression
    std::sort(std::begin(vector), std::end(vector),
      [](const Base &a, const Base &b) { return a.variable < b.variable;});

    // We can also pass a lambda object as the comparator
    // and reuse the lambda multiple times
    auto compare = [](const Base &a, const Base &b) {
                     return a.variable < b.variable;};
    std::sort(std::begin(deque), std::end(deque), compare);
    std::sort(std::begin(array), std::end(array), compare);
    list.sort(compare);
    flist.sort(compare);

    return 0;
}

コンテナの並べ替えと順序付け

std::sortは標準ライブラリヘッダーalgorithmにあり、一連のイテレータで定義された一連の値をソートするための標準ライブラリアルゴリズムです。 std::sortは、2つの値を比較するために使用されたファンクタの最後のパラメータをとります。これは順序を決定する方法です。 std::sortは安定していないことに注意してください。

比較関数は 、要素にStrict、Weak Orderingを課す必要があります。シンプルな小（または小）の比較で十分です。

ランダムアクセスイテレータを持つコンテナは、 std::sortアルゴリズムを使用してソートすることができます。

#include <vector>
#include <algorithm>

std::vector<int> MyVector = {3, 1, 2}

//Default comparison of <
std::sort(MyVector.begin(), MyVector.end());

std::sortでは、イテレータがランダムアクセスイテレータである必要があります。シーケンスコンテナstd::listとstd::forward_list （C ++ 11が必要）はランダムアクセスイテレータを提供しないので、 std::sort使用できません。しかし、独自のイテレータ型で動作するソートアルゴリズムを実装するsortメンバ関数を持っています。

#include <list>
#include <algorithm>

std::list<int> MyList = {3, 1, 2}

//Default comparison of <
//Whole list only.
MyList.sort();

メンバーのsort関数は常にリスト全体をソートするので、要素のサブレンジをソートすることはできません。しかし、 listとforward_listは高速なスプライス操作があるので、ソートする要素をリストから抽出し、ソートしてから、かなり効率的な場所に戻しておくことができます：

void sort_sublist(std::list<int>& mylist, std::list<int>::const_iterator start, std::list<int>::const_iterator end) {
    //extract and sort half-open sub range denoted by start and end iterator 
    std::list<int> tmp;
    tmp.splice(tmp.begin(), list, start, end);
    tmp.sort();
    //re-insert range at the point we extracted it from
    list.splice(end, tmp);
}

std :: map（昇順および降順）でソート

この例では、マップを使用してキーの 昇順に要素をソートします。下の例では、 std::string代わりに、classを含む任意の型を使用できます。

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::map<double, std::string> sorted_map;
    // Sort the names of the planets according to their size
    sorted_map.insert(std::make_pair(0.3829, "Mercury"));
    sorted_map.insert(std::make_pair(0.9499, "Venus"));
    sorted_map.insert(std::make_pair(1,      "Earth"));
    sorted_map.insert(std::make_pair(0.532,  "Mars"));
    sorted_map.insert(std::make_pair(10.97,  "Jupiter"));
    sorted_map.insert(std::make_pair(9.14,   "Saturn"));
    sorted_map.insert(std::make_pair(3.981,  "Uranus"));
    sorted_map.insert(std::make_pair(3.865,  "Neptune"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (" << entry.first << " of Earth's radius)" << '\n';
    }
}

出力：

Mercury (0.3829 of Earth's radius)
Mars (0.532 of Earth's radius)
Venus (0.9499 of Earth's radius)
Earth (1 of Earth's radius)
Neptune (3.865 of Earth's radius)
Uranus (3.981 of Earth's radius)
Saturn (9.14 of Earth's radius)
Jupiter (10.97 of Earth's radius)

等しいキーを持つエントリが可能な場合は、 multimap代わりにmultimapを使用しmap （次の例のように）。

降順で要素をソートするには、適切な比較ファンクタ（ std::greater<> ）を使用してマップを宣言します。

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::multimap<int, std::string, std::greater<int>> sorted_map;
    // Sort the names of animals in descending order of the number of legs
    sorted_map.insert(std::make_pair(6,   "bug"));
    sorted_map.insert(std::make_pair(4,   "cat"));
    sorted_map.insert(std::make_pair(100, "centipede"));
    sorted_map.insert(std::make_pair(2,   "chicken"));
    sorted_map.insert(std::make_pair(0,   "fish"));
    sorted_map.insert(std::make_pair(4,   "horse"));
    sorted_map.insert(std::make_pair(8,   "spider"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (has " << entry.first << " legs)" << '\n';
    }
}

出力

centipede (has 100 legs)
spider (has 8 legs)
bug (has 6 legs)
cat (has 4 legs)
horse (has 4 legs)
chicken (has 2 legs)
fish (has 0 legs)

組み込み配列の並べ替え

sortアルゴリズムは、2つのイテレータで定義されたシーケンスをソートします。これはビルトイン（Cスタイルとも呼ばれます）配列をソートするのに十分です。

int arr1[] = {36, 24, 42, 60, 59};

// sort numbers in ascending order
sort(std::begin(arr1), std::end(arr1));

// sort numbers in descending order
sort(std::begin(arr1), std::end(arr1), std::greater<int>());

C ++ 11より前では、配列の終わりを配列のサイズを使って「計算する」必要がありました。

// Use a hard-coded number for array size
sort(arr1, arr1 + 5);

// Alternatively, use an expression
const size_t arr1_size = sizeof(arr1) / sizeof(*arr1);
sort(arr1, arr1 + arr1_size);