迹忆客 专注技术分享

本文将解释如何在 C++ 中对成对的向量进行排序。

使用 std::sort 算法按 C++ 中的第一个元素值对向量进行排序

Pairs 在 C++ 标准模板库中作为一个单独的类提供。它实现了一种将两个异构对象存储为一个单元的类型。std::pair 算法本质上是一个类似元组的数据结构，只有两个元素。

使用两个模板参数声明一个 pair 对象，这些参数指定每个元素的类型。我们可以通过将 pair 声明作为向量模板参数来声明 pair 对象的向量。可以使用初始化列表通过用单独的大括号传递每一对来初始化成对向量，如下面的代码片段所示。

我们可以使用 STL 提供的通用排序算法对成对的向量进行排序。std::sort 函数采用要排序的范围的两个迭代器，默认情况下它以非降序重新排列元素。在成对的情况下，向量按每对的第一个元素排序。

#include <iostream>
#include <vector>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector; using std::pair;

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::cout; using std::cin;
using std::endl; using std::string;
using std::vector; using std::pair;

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::cout; using std::cin;
using std::endl; using std::string;
using std::vector; using std::pair;

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