std::stable_sort

`std::stable_sort` 是 C++ 标准库 `<algorithm>` 模块中的一个函数模板，用于对容器中的元素进行稳定排序。所谓稳定排序，就是对于相等的元素，其原有的相对顺序在排序后保持不变。这意味着如果有两个元素 a 和 b，a 在 b 前面并且它们都等于某个中间值，那么在排序后，a 仍然会出现在 b 的前面。

`std::stable_sort` 接受两个参数：一个是需要排序的范围，另一个是可以选择性的提供一个比较函数（如果默认比较不是所需的排序方式）。它的基本语法如下：

template <typename RandomIt>
void stable_sort(RandomIt first, RandomIt last);

其中 `RandomIt` 是随机访问迭代器，`first` 表示开始位置，`last` 表示结束但不包括的位置。

例如，对一个 `std::vector<int>` 进行稳定排序：

std::vector<int> vec = {4, 2, 4, 1, 3};
std::stable_sort(vec.begin(), vec.end());

相关问题

std::stable_sort 与sort 区别

std::stable_sort和std::sort是C++标准库中的两个排序算法，它们在排序元素时有一些区别。

1. std::sort是一种不稳定的排序算法，而std::stable_sort是一种稳定的排序算法。稳定排序算法意味着如果两个元素的值相等，它们在排序后的结果中的相对顺序将保持不变。而不稳定排序算法则没有这个保证。

2. std::sort的平均时间复杂度为O(nlogn)，std::stable_sort的平均时间复杂度为O(nlog^2n)。这是因为std::stable_sort需要保持相等元素的相对顺序，所以在排序过程中需要更多的操作。

3. std::sort使用的是快速排序算法或者堆排序算法，而std::stable_sort使用的是归并排序算法。快速排序和堆排序是原地排序算法，它们不需要额外的内存空间。而归并排序需要额外的内存空间来存储临时结果。

下面是一个使用std::sort和std::stable_sort的示例：

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

int main() {
    std::vector<int> nums = {5, 2, 8, 3, 1, 4};

    // 使用std::sort进行排序
    std::sort(nums.begin(), nums.end());
    std::cout << "使用std::sort排序后的结果：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用std::stable_sort进行排序
    std::stable_sort(nums.begin(), nums.end());
    std::cout << "使用std::stable_sort排序后的结果：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：
使用std::sort排序后的结果：1 2 3 4 5 8
使用std::stable_sort排序后的结果：1 2 3 4 5 8

在vs2015 c++ .h中加入这段代码会报重定义 namespace cv_dnn { namespace { template <typename T> static inline bool SortScorePairDescend(const std::pair<float, T>& pair1, const std::pair<float, T>& pair2) { return pair1.first > pair2.first; } } // namespace inline void GetMaxScoreIndex(const std::vector<float>& scores, const float threshold, const int top_k, std::vector<std::pair<float, int> >& score_index_vec) { for (size_t i = 0; i < scores.size(); ++i) { if (scores[i] > threshold) { score_index_vec.push_back(std::make_pair(scores[i], i)); } } std::stable_sort(score_index_vec.begin(), score_index_vec.end(), SortScorePairDescend<int>); if (top_k > 0 && top_k < (int)score_index_vec.size()) { score_index_vec.resize(top_k); } } template <typename BoxType> inline void NMSFast_(const std::vector<BoxType>& bboxes, const std::vector<float>& scores, const float score_threshold, const float nms_threshold, const float eta, const int top_k, std::vector<int>& indices, float(*computeOverlap)(const BoxType&, const BoxType&)) { CV_Assert(bboxes.size() == scores.size()); std::vector<std::pair<float, int> > score_index_vec; GetMaxScoreIndex(scores, score_threshold, top_k, score_index_vec); // Do nms. float adaptive_threshold = nms_threshold; indices.clear(); for (size_t i = 0; i < score_index_vec.size(); ++i) { const int idx = score_index_vec[i].second; bool keep = true; for (int k = 0; k < (int)indices.size() && keep; ++k) { const int kept_idx = indices[k]; float overlap = computeOverlap(bboxes[idx], bboxes[kept_idx]); keep = overlap <= adaptive_threshold; } if (keep) indices.push_back(idx); if (keep && eta < 1 && adaptive_threshold > 0.5) { adaptive_threshold *= eta; } } } // copied from opencv 3.4, not exist in 3.0 template<typename Tp> static inline double jaccardDistance_(const Rect_<Tp>& a, const Rect<_Tp>& b) { Tp Aa = a.area(); Tp Ab = b.area(); if ((Aa + Ab) <= std::numeric_limits<Tp>::epsilon()) { // jaccard_index = 1 -> distance = 0 return 0.0; } double Aab = (a & b).area(); // distance = 1 - jaccard_index return 1.0 - Aab / (Aa + Ab - Aab); } template <typename T> static inline float rectOverlap(const T& a, const T& b) { return 1.f - static_cast<float>(jaccardDistance(a, b)); } void NMSBoxes(const std::vector<Rect>& bboxes, const std::vector<float>& scores, const float score_threshold, const float nms_threshold, std::vector<int>& indices, const float eta = 1, const int top_k = 0) { NMSFast(bboxes, scores, score_threshold, nms_threshold, eta, top_k, indices, rectOverlap); } }

在加入这段代码时，如果在同一个命名空间内有相同的函数或变量，则会报重定义的错误。如果你确定已经检查过代码，在其他地方没有定义相同的函数或变量，可以尝试将代码放在一个新的命名空间中。例如：

namespace my_cv_dnn {
    // 这里放你的代码
}

然后在使用时使用新的命名空间即可。