溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
STL主要包含容器，迭代器，算法三塊內容，用戶可以對容器進行一系列的操作，比如遍歷和計算，而STL提供的迭代器和容器完美地提供了這樣的接口。其中std::vector是最常用的容器之一，vector是一個模板類，定義在命名空間namespace下，使用vector需要在包含相關頭文件。今天主要講解對vector的排序的使用。
sort類函數：
| 函數名 | 功能描述 |
|---|---|
| sort | 對給定區間所有元素進行排序 |
| stable_sort | 對給定區間所有元素進行穩定排序 |
| partial_sort | 對給定區間所有元素部分排序 |
| partial_sort_copy | 對給定區間復制并排序 |
| nth_element | 找出給定區間的某個位置對應的元素 |
| is_sorted | 判斷一個區間是否已經排好序 |
| partition | 使得符合某個條件的元素放在前面 |
| stable_partition | 相對穩定的使得符合某個條件的元素放在前面 |
需要頭文件<algorithm>
語法描述：sort（begin，end，cmp），cmp參數可以沒有，如果沒有默認非降序排序。
常見的排序算法有快速排序、冒泡排序、歸并排序等。STL中sort函數的實現跟STL的版本有關，而往往sort函數是由多種排序算法混合而成的。
1. vector元素為內置數據類型
STL中sort函數的使用方法如下，默認對容器進行從小到大的排序。
#include <vector> // std::vector
#include <algorithm> // std::sort
int main(){
std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
std::sort(vi.begin(), vi.end()); // 相當于 std::sort(vi.begin(), vi.end(), std::less<int>());
for (int i = 0; i < vi.size(); ++i) {
printf("%d ", vi[i]);
}
printf("\n");
// output: 0 1 1 1 2 2 5 8
當然也可以指定對容器進行從大到小的排序：
#include <vector> // std::vector
#include <algorithm> // std::sort
int main(){
std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
std::sort(vi.begin(), vi.end(), std::greater<int>());
for (int i = 0; i < vi.size(); ++i) {
printf("%d ", vi[i]);
}
printf("\n");
// output: 8 5 2 2 1 1 1 0
2. vector元素為用戶自定義數據類型
如果vector內的元素為用戶自定義類型，并且用戶想要按照自定義類型的某些組合特性進行排序。先來看看sort函數的定義：
template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
其中前兩個參數為迭代器類型，第三個參數為比較函數。下面的例子中，類Character擁有兩個屬性，age_ 和 name_，這里為了簡單起見，變量均為public。現在需要對一個元素類型為Character的vector進行按照Character的 age_ 從小打到進行排序。
class Character {
public:
Character(int n, string s) : age_(n), name_(s) {}
int age_;
string name_;
};
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
return ca->age_ < cb->age_;
}
};
int main(){
vector<Character*> vc{new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian")};
sort(vc.begin(), vc.end(), Compare());
for (int i = 0; i < vc.size(); ++i) {
printf("%s ", vc[i]->name_.c_str());
}
return 0;
}// output: sasaki satchel nozomi qingtian
對于sort的第三個函數，用戶可以自己定義任何類型的比較方式，但是需要滿足 strict weak ordering 的條件：
X a; X b; Condition: Test Result a is equivalent to b: Compare(a, b) false Compare(b, a) false a is less than b Compare(a, b) true Compare(b, a) false b is less than a Compare(a, b) false Compare(b, a) true
上述例子中的 Compare 函數基于 Character 對象的 age_ 變量值進行比較。根據 strict weak ordering 的條件，對 vector 按照某種條件進行排序就比較好理解了。
對于 vector 的兩個元素 a, b，如果 a 必須排在 b 前面，需要滿足下面的條件：Compare(a, b) = true, Compare(b, a) = false; 如果滿足 Compare(a, b) = false & Compare(b, a) = false，則說明兩個元素是相等的；
拓展：對 vector 中的元素進行排序，使得 age_ 為 1 的元素排在前面，age_ != 1的元素排在后面；
分析：這種情況下 Character 被分為兩類，age_ ==1 和 age_ != 1；對于任意兩個 Character 對象 a, b：
1. 相等（a == b）：a->age_ == 1 && b->age_ ==1，或者 a->age_ != 1 && b->age_ != 1；
2. 小于（a < b）：a->age_ == 1 && b->age_ != 1；
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
if (ca->age_ == 1 && cb->age_ == 1 ||
ca->age_ != 1 && cb->age_ != 1) return false;
return ca->age_ == 1;
}
};
完整的測試代碼：
class Character {
public:
Character(int n, string s) : age_(n), name_(s) {}
int age_;
string name_;
};
class Compare {
public:
bool operator() (Character* ca, Character* cb) {
if (ca->age_ == 1 && cb->age_ == 1 ||
ca->age_ != 1 && cb->age_ != 1) return false;
return ca->age_ == 1;
}
};
int main() {
vector<Character*> vc{ new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian") };
sort(vc.begin(), vc.end(), Compare());
for (int i = 0; i < vc.size(); ++i) {
printf("%s ", vc[i]->name_.c_str());
}
return 0;
}// output: sasaki satchel nozomi qingtian
Reference:
1. std::sort
2. comparator
3. strict weak order
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
