>>> 背景

今天在學一些C++ STL容器，看到sort函數允許自定義排序規則，小小地實操了一下。

>>> 內容

vector

在正式開始使用sort之前，我們先鋪墊一些關于vector容器的內容，以及自定義標準輸出流，為我們后面的探索鋪墊一下。

vector容器是一種動長的模板容器，需要 # include 。定義一個vector對象需要指定元素類型，這個類型可以是基礎類型，結構體，自定義類型和vector類型自身（達到嵌套多維vector的目的）。

如下面代碼所示，創建了一個元素類型為 int 的vector對象，并使用列表進行初始化。除此之外，還可以使用assign方法進行快速初始化。

// 元素為 1,2,3,4,5
vector< int > vec(5) = {1, 2, 3, 4, 5}; 
// 元素為 1,1,1,1,1
vector< int > vec(5);
vec.assign(1, 5)

還可以創建二維容器，如下所示。注意到此時的模板元素類型參數變成了 vector< int >。

vector< vector< int >> vec2 = {vec, vec, vec, vec, vec};

為了能夠方便地打印出vector對象的元素，需要自定義一些輸出函數。這里分別對一維和二維的vector容器定義了打印函數（模板）。

template < typename T >
void print1vec(const vector< T >& v) {
    auto iter = v.begin();
    while (iter != v.end()) {
        cout < < *iter < < " ";
        iter++;
    }
    cout < < endl;
}


template < typename T >
void print2vec(const vector< vector< T >>& v) {
    auto iter = v.begin();
    while (iter != v.end()) {
        print1vec(*iter);
        iter++;
    }
    cout < < endl;
}

為了讓輸出更加優雅和方便，可以重載<<運算符，如下所示。

template < typename T >
ostream& operator< const vector< T >& v) {
    auto iter = v.begin();
    while (iter != v.end()) {
        os < < *iter < < " ";
        iter++;
    }
    os < < endl;
    return os;
};


template < typename T >
ostream& operator< const vector< vector< T >>& v) {
    auto iter = v.begin();
    while (iter != v.end()) {
        os < < *iter;
        iter++;
    }
    os < < endl;
    return os;
};

sort

使用sort需要 #include 。sort函數最簡單的用法如下。第一個參數傳入容器的頭地址（或指向頭元素的迭代器），第二個參數傳入容器的尾地址（或指向尾元素的迭代器）的下一個位置（前閉后開的區間）。

int arr[5] = {1, 3, 5, 2, 4};
    sort(arr, arr + 5);
    for (int i = 0; i < 5; ++i)
        cout < < arr[i] < < " ";

>> 1 2 3 4 5

還可以傳入第3個參數，即排序判據。該判據由一個函數對象來實現，有兩個參數，返回bool值。sort在排序時，會依次把兩個元素傳入給該函數對象進行判斷，如果返回值為true，那么就會把第一個參數代表的元素放到隊列中靠前的位置。

因此，可以傳入判據函數來快速實現降序排序（這里使用了lambda表達式）。如下所示。

int arr[5] = {1, 3, 5, 2, 4};
sort(arr, arr + 5,
        [](int a, int b) {
            return a > b;
        });
    for (int i = 0; i < 5; ++i)
        cout < < arr[i] < < " ";

5 4 3 2 1

判據函數給了用戶自己決定元素比較關系的途徑，尤其是對一些非基礎類型的數據（如結構、類）可以方便地進行排序。

下面就創建了一個結構體 ，并規定如果該結構體的兩個成員的平方和越小，排序越靠前。

struct Point {
    int x; 
    int y;
};


ostream& operator< const Point& p) {
    os < < "(" < < p.x < < ", " < < p.y < < ")";
    return os;
};

vector< Point > vec3;
Point p1 = {1, 1};
Point p2 = {-3, -3};
Point p3 = {2, 2};
vec3.push_back(p1);
vec3.push_back(p2);
vec3.push_back(p3);
cout < < "vec3: " < < endl;
cout < < vec3;
sort(vec3.begin(), vec3.end(),
    [](Point a, Point b){
        return a.x * a.x +  a.y * a.y < b.x * b.x +  b.y * b.y;
    });
cout < < vec3;

> > vec3:
(1, 1) (-3, -3) (2, 2)
(1, 1) (2, 2) (-3, -3)