【c++编程基础】std::unique的理解

前言

项目中想要实现一个功能，对于一个自定义类，包含坐标和类别等属性，按照到某个中心点的角度从小到大排序，如果角度相同，只保留距离中心点更近的元素，过程中用到了0-360的角度计算，自定义函数排序，以及删除重复元素等内容，故记录之。

具体内容

1. 计算到中心点的角度；

// 计算点到中心点的角度（0-360度）
float calculateAngle(const cv::Point& center, const cv::Point& point) {
    cv::Point vec = point - center;
    float angle = atan2f(vec.y, vec.x) * 180.0f / CV_PI; // 将弧度转换为角度
    if (angle < 0) {
        angle += 360.0f; // 确保角度在0-360度范围内
    }
    return angle;
}

2. 比较函数，角度从小到大排序，如果角度相同，保留距离近的，舍弃距离远的；

bool compareByAngle(const Fish2IpmPot& p1, const Fish2IpmPot& p2, const cv::Point& center) {
    float angle1 = calculateAngle(center, p1.coord);
    float angle2 = calculateAngle(center, p2.coord);
    // if(std::abs(angle1-angle2) < ANGLE_TOLERANCE){
    if(angle1 == angle2){
        float dist1 = cv::norm(p1.coord - center);
        float dist2 = cv::norm(p2.coord - center);
        return dist1 < dist2;
    }
    return angle1 < angle2;
}

3. 对above区域的fs进行排序；

void sortAbove(std::vector<Fish2IpmPot>& pts){
    // 180-360, 与x轴的夹角，顺时针
    std::sort(pts.begin(), pts.end(), [](const Fish2IpmPot& p1, const Fish2IpmPot& p2){
        return compareByAngle(p1, p2, a_center);
    });    
    // 去重：舍弃角度相同但距离较远的点
    auto last = std::unique(pts.begin(), pts.end(), [a_center](const Fish2IpmPot& p1, const Fish2IpmPot& p2) {
        float angle1 = calculateAngle(a_center, p1.coord);
        float angle2 = calculateAngle(a_center, p2.coord);
        return angle1 == angle2; // 如果角度相同，认为是重复点
    });
    // 删除重复点
    pts.erase(last, pts.end());
}

4. 对std::unique的理解；

1) std::unique函数，用于去除容器中相邻重复元素，连续重复的元素只保留最前面的元素；

特别需要强调和注意的是，

a)只有当遇到连续重复的元素，才会起到去重作用，如果容器中存在非相邻的重复元素，则无法去除。比如{1,2,1}，则unique不能对其进行去重；

b) unique操作不会改变容器的大小，它只是将保留下来的元素从头一一覆盖到容器中去，多出来的部分依旧是可以访问的，这部分元素需要自行删除；

2)unique是稳定的，去重后，剩余元素的顺序是不变的；

3) 原型定义在algorithm头文件；

4) unique有两个方法，一个是使用默认的方式来定义重复元素，另一种是以自定义方式来判断是否是重复元素；

[first, last)表示容器中需要去重的范围，返回值是一个前向指针，指向去重后的最后一个有效元素的下一个位置iter，可以通过删除[iter, end)，保留[first,iter)达到去重效果；

a) 默认方式

默认方式: 如果有连续的元素都满足彼此相等或者指向的对象相等，则为重复元素；
template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

b) 自定义方式

自定义方式：如果有连续的元素都满足彼此相等，或者指向的对象在自定义的二元谓词的作用下依旧为true即binary_pred(*i, *(i-1))==true，则为重复元素；
template <class ForwardIterator， class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);

5) 由于unique只能对相邻的连续的重复元素去重，一般需要先进行排序，采用sort和unique的方式进行去重，同时使用erase删除迭代器之后的无效元素；

6) unique的时间复杂度O(N)，空间复杂度是O(1)；sort的时间复杂度平均是O(NlogN)，最坏是O(N*N)，空间复杂度O(logN)；

7) 简单示例

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

int main() {
    std::vector<int> vec = {1, 1, 2, 3, 3, 4, 5, 5, 6};
    auto new_end = std::unique(vec.begin(), vec.end());
    std::cout << "Vector after unique: " << vec.size() << std::endl;
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl << "Vector from begin to new_end: " << vec.size() << std::endl;;
    for (auto it = vec.begin(); it != new_end; ++it) {
        std::cout << *it << " ";
    }
    vec.erase(new_end, vec.end());
    std::cout << std::endl << "Vector after erase: " << vec.size() << std::endl;
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }    
    return 0;
}

后记

今天是2024年的最后一天，明天元旦。

祝自己，平安喜乐、万事顺遂、外儒内法、拓展认知边界、提升职场能力、永葆赤子之心！

参考

1. unique()函数_unique() 函数-CSDN博客；

2. STL 官网学习笔记—— unique_std::unique会改变元素顺序吗-CSDN博客；

完