使用C++ sort函數(shù)對vector進(jìn)行自定義排序

>>> 背景

今天在學(xué)一些C++ STL容器，看到sort函數(shù)允許自定義排序規(guī)則，小小地實(shí)操了一下。

>>> 內(nèi)容

vector

在正式開始使用sort之前，我們先鋪墊一些關(guān)于vector容器的內(nèi)容，以及自定義標(biāo)準(zhǔn)輸出流，為我們后面的探索鋪墊一下。

vector容器是一種動(dòng)長的模板容器，需要 # include 。定義一個(gè)vector對象需要指定元素類型，這個(gè)類型可以是基礎(chǔ)類型，結(jié)構(gòu)體，自定義類型和vector類型自身（達(dá)到嵌套多維vector的目的）。

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

// 元素為 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)

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

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

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

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

為了讓輸出更加優(yōu)雅和方便，可以重載<<運(yùn)算符，如下所示。

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函數(shù)最簡單的用法如下。第一個(gè)參數(shù)傳入容器的頭地址（或指向頭元素的迭代器），第二個(gè)參數(shù)傳入容器的尾地址（或指向尾元素的迭代器）的下一個(gè)位置（前閉后開的區(qū)間）。

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個(gè)參數(shù)，即排序判據(jù)。該判據(jù)由一個(gè)函數(shù)對象來實(shí)現(xiàn)，有兩個(gè)參數(shù)，返回bool值。sort在排序時(shí)，會(huì)依次把兩個(gè)元素傳入給該函數(shù)對象進(jìn)行判斷，如果返回值為true，那么就會(huì)把第一個(gè)參數(shù)代表的元素放到隊(duì)列中靠前的位置。

因此，可以傳入判據(jù)函數(shù)來快速實(shí)現(xiàn)降序排序（這里使用了lambda表達(dá)式）。如下所示。

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

判據(jù)函數(shù)給了用戶自己決定元素比較關(guān)系的途徑，尤其是對一些非基礎(chǔ)類型的數(shù)據(jù)（如結(jié)構(gòu)、類）可以方便地進(jìn)行排序。

下面就創(chuàng)建了一個(gè)結(jié)構(gòu)體 ，并規(guī)定如果該結(jié)構(gòu)體的兩個(gè)成員的平方和越小，排序越靠前。

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)