C++如何使用STL算法实现数据去重

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort and std::unique
#include <set>       // For std::set approach
#include <unordered_set> // For std::unordered_set approach

void printVector(const std::vector<int>& vec, const std::string& msg) {
    std::cout << msg;
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data = {1, 3, 2, 4, 3, 1, 5, 2, 6, 4};
    printVector(data, "原始数据: ");

    // 方法一：使用 std::sort + std::unique
    // 这种方法会改变原始顺序，但效率高
    std::vector<int> data_sorted_unique = data; // 复制一份，不影响原始data
    std::sort(data_sorted_unique.begin(), data_sorted_unique.end());
    // std::unique 将重复元素移动到末尾，并返回新逻辑末尾的迭代器
    auto last = std::unique(data_sorted_unique.begin(), data_sorted_unique.end());
    // 真正删除重复元素
    data_sorted_unique.erase(last, data_sorted_unique.end());
    printVector(data_sorted_unique, "std::sort + std::unique 去重后: ");

    // 方法二：使用 std::set (保持排序且去重)
    // 这种方法会创建新的排序好的去重集合
    std::set<int> unique_set(data.begin(), data.end());
    std::vector<int> data_from_set(unique_set.begin(), unique_set.end());
    printVector(data_from_set, "std::set 去重后: ");

    // 方法三：使用 std::unordered_set (不保持排序，但去重，通常最快)
    // 这种方法会创建新的不保证顺序的去重集合
    std::unordered_set<int> unique_unordered_set(data.begin(), data.end());
    std::vector<int> data_from_unordered_set(unique_unordered_set.begin(), unique_unordered_set.end());
    printVector(data_from_unordered_set, "std::unordered_set 去重后: ");

    return 0;
}

struct Person {
    std::string name;
    int age;

    // 为 std::sort, std::unique, std::set 提供小于运算符
    // 假设我们认为名字和年龄都相同的人是同一个
    bool operator<(const Person& other) const {
        if (name != other.name) {
            return name < other.name;
        }
        return age < other.age;
    }

    // 为 std::unique 提供相等运算符（虽然 std::unique 默认用 operator==，
    // 但如果想自定义相等逻辑，可以传入自定义比较器）
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 示例：使用自定义比较器去重
struct PersonAgeComparator {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age; // 仅按年龄排序
    }
};

// 假设我们认为名字相同的人就是同一个，年龄不重要
struct PersonNameEquality {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name;
    }
};

// 续上 Person struct 定义

// 为 std::unordered_set 特化 std::hash
namespace std {
    template <>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // 组合多个成员的哈希值，避免简单叠加可能导致的冲突
            // 这是一个常见的哈希组合技巧，例如boost::hash_combine
            size_t h1 = std::hash<std::string>{}(p.name);
            size_t h2 = std::hash<int>{}(p.age);
            return h1 ^ (h2 << 1); // 简单的组合方式
        }
    };
}

int main_custom_types() {
    std::vector<Person> people = {
        {"Alice", 30}, {"Bob", 25}, {"Alice", 30}, {"Charlie", 35}, {"Bob", 25}
    };

    // 使用 std::set 去重
    std::set<Person> unique_people_set(people.begin(), people.end());
    std::cout << "Set去重后:" << std::endl;
    for (const auto& p : unique_people_set) {
        std::cout << p.name << " " << p.age << std::endl;
    }

    // 使用 std::unordered_set 去重
    std::unordered_set<Person> unique_people_unordered_set(people.begin(), people.end());
    std::cout << "Unordered_set去重后:" << std::endl;
    for (const auto& p : unique_people_unordered_set) {
        std::cout << p.name << " " << p.age << std::endl;
    }

    return 0;
}