std::stable_sort
时间: 2024-07-31 21:01:00 浏览: 91
`std::stable_sort` 是 C++ 标准库 `<algorithm>` 模块中的一个函数模板,用于对容器中的元素进行稳定排序。所谓稳定排序,就是对于相等的元素,其原有的相对顺序在排序后保持不变。这意味着如果有两个元素 a 和 b,a 在 b 前面并且它们都等于某个中间值,那么在排序后,a 仍然会出现在 b 的前面。
`std::stable_sort` 接受两个参数:一个是需要排序的范围,另一个是可以选择性的提供一个比较函数(如果默认比较不是所需的排序方式)。它的基本语法如下:
```cpp
template <typename RandomIt>
void stable_sort(RandomIt first, RandomIt last);
```
其中 `RandomIt` 是随机访问迭代器,`first` 表示开始位置,`last` 表示结束但不包括的位置。
例如,对一个 `std::vector<int>` 进行稳定排序:
```cpp
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的示例:
```cpp
#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); } }
在加入这段代码时,如果在同一个命名空间内有相同的函数或变量,则会报重定义的错误。如果你确定已经检查过代码,在其他地方没有定义相同的函数或变量,可以尝试将代码放在一个新的命名空间中。例如:
```cpp
namespace my_cv_dnn {
// 这里放你的代码
}
```
然后在使用时使用新的命名空间即可。
阅读全文