vector去重排序

Vector是C++标准库中的动态数组容器，它允许你在运行时添加、删除元素。如果你想要从一个vector中去除重复项并保持顺序，可以先创建一个新的vector，然后遍历原来的vector，只将未出现在新vector中的元素添加进去。这通常通过迭代器和条件判断来实现。 以下是一个简单的示例： ```cpp #include <iostream> #include <vector> #include <algorithm> // 包含sort函数 std::vector<int> remove_duplicates_and_sort(const std::vector<int>& vec) { std::vector<int> new_vec; for (const auto& elem : vec) { if (new_vec.end() == std::find(new_vec.begin(), new_vec.end(), elem)) { new_vec.push_back(elem); } } // 使用stl sort对新vector进行升序排序 std::sort(new_vec.begin(), new_vec.end()); return new_vec; } int main() { std::vector<int> vec = {5, 3, 2, 5, 4, 2, 1}; std::vector<int> unique_sorted_vec = remove_duplicates_and_sort(vec); for (const auto& num : unique_sorted_vec) { std::cout << num << " "; }

<think>好的，我现在需要回答用户关于C++ vector去重方法及代码示例的问题。用户提到了参考引用中的内容，我需要结合这些信息来整理出有效的去重方法。 首先，用户提供的引用[1]提到了使用排序和unique算法的方法，这是STL中常用的去重方式。引用[2]则介绍了使用std::set和std::unordered_set的方法。这些方法各有优缺点，需要逐一分析。 第一种方法：排序后使用unique和erase。步骤是先对vector排序，这样相同的元素会相邻，然后用unique将重复元素移到末尾，最后用erase删除这些元素。这种方法的时间复杂度主要是排序的O(n log n)，适用于需要保留顺序且允许修改原顺序的情况。 第二种方法：使用std::set。将vector元素插入set中，由于set自动去重，再将set元素复制回vector。这种方法同样需要O(n log n)的时间，因为set插入是log n的，但会额外使用O(n)空间。好处是不改变原vector元素的顺序，但结果会被排序。 第三种方法：使用std::unordered_set。与set类似，但unordered_set不排序，插入时间是O(1)平均情况。但同样需要额外空间，并且结果的顺序可能被打乱，取决于哈希函数和实现。 接下来需要比较这些方法的适用场景。如果用户希望保持原有顺序，可能需要更复杂的方法，比如遍历并记录首次出现的元素。但常见的方法是先排序再用unique，或者用unordered_set但牺牲顺序。 现在需要编写代码示例。对于第一种方法，代码应包括sort、unique、erase的调用。第二种方法则需要创建set，用assign或循环插入。第三种则是用unordered_set，注意结果顺序可能不同。 还需要注意，unique函数需要配合排序使用，否则只能去除连续的重复元素。例如，未排序的vector直接用unique是无法完全去重的。 用户可能关心效率和空间的问题，比如对于大数据集，哪种方法更高效。排序+unique的方法在时间复杂度上是O(n log n)，而set和unordered_set的方法时间复杂度类似，但可能有不同的常数因子。例如，unordered_set的插入更快，但遍历时可能不如连续内存访问高效。 最后，需要总结这些方法的优缺点，帮助用户根据具体情况选择合适的方法。</think>### C++ vector去重方法及代码示例 在C++中，对`vector`去重可以通过多种方法实现，具体选择取决于是否需要保留元素顺序或对性能的要求。以下是三种常见方法及其代码示例： --- #### **方法1：排序后使用`unique`和`erase`（推荐高效方法）** **步骤**： 1. 使用`std::sort`排序，使重复元素相邻。 2. 使用`std::unique`将重复元素移至容器末尾。 3. 使用`erase`删除末尾的重复元素。 **代码示例**： ```cpp #include <vector> #include <algorithm> int main() { std::vector<int> vec = {3, 1, 2, 2, 3, 4, 4, 5}; // 1. 排序 std::sort(vec.begin(), vec.end()); // 2. 去重 auto last = std::unique(vec.begin(), vec.end()); // 3. 删除重复元素 vec.erase(last, vec.end()); return 0; } ``` **特点**： - 时间复杂度：$O(n \log n)$（主要来自排序）。 - 会改变元素顺序，但效率高，适用于无需保留原顺序的场景[^1]。 --- #### **方法2：使用`std::set`（自动去重）** **步骤**： 1. 将`vector`元素插入`std::set`中（自动去重）。 2. 将`set`内容复制回`vector`。 **代码示例**： ```cpp #include <vector> #include <set> int main() { std::vector<int> vec = {3, 1, 2, 2, 3, 4, 4, 5}; // 1. 插入到set去重 std::set<int> s(vec.begin(), vec.end()); // 2. 复制回vector（结果会被排序） vec.assign(s.begin(), s.end()); return 0; } ``` **特点**： - 时间复杂度：$O(n \log n)$（插入`set`的开销）。 - 结果会被排序，且需要额外空间存储`set`[^2]。 --- #### **方法3：使用`std::unordered_set`（不排序去重）** **步骤**： 1. 将`vector`元素插入`std::unordered_set`（去重但不排序）。 2. 将`unordered_set`内容复制回`vector`。 **代码示例**： ```cpp #include <vector> #include <unordered_set> int main() { std::vector<int> vec = {3, 1, 2, 2, 3, 4, 4, 5}; // 1. 插入到unordered_set去重 std::unordered_set<int> us(vec.begin(), vec.end()); // 2. 复制回vector（顺序可能打乱） vec.assign(us.begin(), us.end()); return 0; } ``` **特点**： - 时间复杂度：$O(n)$（平均情况，哈希表插入效率）。 - 元素顺序不可控，但速度快于`std::set`。 --- ### **方法对比** | 方法 | 时间复杂度 | 空间复杂度 | 保留原顺序 | 结果是否排序 | |------------|------------------|------------|------------|--------------| | 排序+`unique` | $O(n \log n)$ | $O(1)$ | ❌ | ✔️ | | `std::set` | $O(n \log n)$ | $O(n)$ | ❌ | ✔️ | | `unordered_set` | $O(n)$ | $O(n)$ | ❌ | ❌ | --- ### **选择建议** - 若需**高效去重且不关心顺序**，优先选择**排序+`unique`**。 - 若需**保留插入顺序**，需手动遍历去重（时间复杂度$O(n^2)$）。 - 若需**快速去重且接受无序结果**，使用`unordered_set`。