面试题：C++ sort对复杂模板类型的适配及性能优化

Question

假设有一个模板类模板如下：template<typename T, typename U> class ComplexType { public: T data1; U data2; // 构造函数及其他成员略 }; 现在有一个std::vector<ComplexType<int, double>>类型的容器，需要使用sort算法对其进行排序，排序规则是先按data1的降序排列，如果data1相同则按data2的升序排列。请写出完整的实现代码，并考虑如何进行性能优化（例如减少不必要的拷贝等）。

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T, typename U>
class ComplexType {
public:
    T data1;
    U data2;
    // 构造函数及其他成员略
    ComplexType(T d1, U d2) : data1(d1), data2(d2) {}
};

// 比较函数
bool compare(const ComplexType<int, double>& a, const ComplexType<int, double>& b) {
    if (a.data1 != b.data1) {
        return a.data1 > b.data1;
    } else {
        return a.data2 < b.data2;
    }
}

int main() {
    std::vector<ComplexType<int, double>> vec;
    vec.emplace_back(3, 5.5);
    vec.emplace_back(1, 4.2);
    vec.emplace_back(3, 2.1);
    vec.emplace_back(2, 3.7);

    // 使用自定义比较函数进行排序
    std::sort(vec.begin(), vec.end(), compare);

    // 输出排序后的结果
    for (const auto& item : vec) {
        std::cout << "data1: " << item.data1 << ", data2: " << item.data2 << std::endl;
    }

    return 0;
}

性能优化

1. 减少拷贝：在现代C++ 中，std::sort 通常会使用std::move 而不是拷贝来进行元素的交换，尤其是在std::vector 中，因为std::vector 的元素存储在连续的内存中。此外，在emplace_back 时直接在容器内构造对象，避免了额外的拷贝或移动操作。
2. 使用并行排序：对于较大规模的数据，可以考虑使用并行排序算法，如std::execution::par 策略的std::sort，例如std::sort(std::execution::par, vec.begin(), vec.end(), compare);。但这需要根据具体的应用场景和硬件环境来评估是否合适，因为并行化可能带来线程调度等额外开销。