在 C++ 中對一對向量進行排序
Jinku Hu
2023年10月12日
-
使用
std::sort演算法按 C++ 中的第一個元素值對向量進行排序 -
使用帶有 Lambda 表示式的
std::sort演算法按 C++ 中的第二個元素值對對向量進行排序 -
使用帶有自定義函式的
std::sort演算法在 C++ 中對向量進行排序
本文將解釋如何在 C++ 中對成對的向量進行排序。
使用 std::sort 演算法按 C++ 中的第一個元素值對向量進行排序
Pairs 在 C++ 標準模板庫中作為一個單獨的類提供。它實現了一種將兩個異構物件儲存為一個單元的型別。std::pair 演算法本質上是一個類似元組的資料結構，只有兩個元素。
使用兩個模板引數宣告一個 pair 物件，這些引數指定每個元素的型別。我們可以通過將 pair 宣告作為向量模板引數來宣告 pair 物件的向量。可以使用初始化列表通過用單獨的大括號傳遞每一對來初始化成對向量，如下面的程式碼片段所示。
我們可以使用 STL 提供的通用排序演算法對成對的向量進行排序。std::sort 函式採用要排序的範圍的兩個迭代器，預設情況下它以非降序重新排列元素。在成對的情況下，向量按每對的第一個元素排序。
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end());
cout << "vec1: ";
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {6,six}; {12,eleven}; {32,thirty-two}; {43,forty-three};
使用帶有 Lambda 表示式的 std::sort 演算法按 C++ 中的第二個元素值對對向量進行排序
或者，如果我們將可選的比較函式物件傳遞給 std::sort 演算法，我們可以通過第二個元素值對給定的對向量進行排序。在這種情況下，我們使用 lambda 表示式來形成一個函式物件，並將其作為 sort 函式呼叫的第三個引數傳遞。請注意，這本質上是為該對的元素定義任何自定義比較例程的方法。
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end(),
[](const auto &x, const auto &y) { return x.second < y.second; });
cout << "vec1: ";
printVector(vec1);
cout << endl;
return EXIT_SUCCESS;
}
輸出：
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {12,eleven}; {43,forty-three}; {6,six}; {32,thirty-two};
使用帶有自定義函式的 std::sort 演算法在 C++ 中對向量進行排序
另一種將比較函式傳遞給 std::sort 演算法的方法是以 bool cmp(const Type1 &a, const Type2 &b) 的形式定義一個單獨的函式。通常，std::sort 的執行時間複雜度為 O(nlogn)。
以下示例定義了一個 sortPairs 函式，用於比較每對中的第一個元素。但是，你可以為儲存自定義類物件的對或必須評估多個資料成員的對定義更復雜的比較函式。
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
bool sortPairs(const pair<int, string> &x, const pair<int, string> &y) {
return x.first > y.first;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end(), sortPairs);
cout << "vec1: ";
printVector(vec1);
cout << endl;
return EXIT_SUCCESS;
}
輸出：
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {43,forty-three}; {32,thirty-two}; {12,eleven}; {6,six};
作者： Jinku Hu
