C++ STL容器去重主要有两种方法：一是结合std::sort与std::unique，适用于vector等支持随机访问的容器，先排序使重复元素相邻，再用std::unique将重复元素移至末尾并配合erase删除；二是利用std::set或std::unordered_set的唯一性插入特性实现去重。前者原地操作、内存开销小，时间复杂度O(N log N)；后者需额外O(N)空间，但代码简洁，其中unordered_set平均时间复杂度为O(N)。std::unique不直接改变容器大小，仅返回新逻辑末尾迭代器，需调用erase完成实际删除，体现STL算法与容器分离的设计思想。不同容器策略不同：vector/deque推荐sort+unique；list应使用其成员函数sort()和unique()；set/map类容器键天然唯一，无需额外去重。选择方法时需权衡时间与空间复杂度、元素类型约束、是否保持顺序及原地修改需求，根据具体场景灵活选用。
在C++的STL中，实现容器的去重操作，主要有两大类方法：一种是利用
std::sort配合
std::unique算法，通过排序将重复元素聚集，然后移除；另一种则是借助
std::set或
std::unordered_set等本身就具有唯一性特性的容器来完成。这两种方法各有其适用场景和性能考量，我个人在实际开发中会根据具体需求灵活选择。
解决方案
要实现C++ STL容器的去重，最常用且高效的方案，尤其对于
std::vector或
std::deque这类支持随机访问迭代器的容器，是结合
std::sort和
std::unique。这个组合利用了
std::sort将所有相同元素排在一起的特性，然后
std::unique就能非常高效地找到并“标记”出重复项。
具体步骤是这样的：
-
排序：首先，对容器进行排序。
std::sort(vec.begin(), vec.end());
这一步是关键，它确保了所有值相同的元素都会相邻。 -
标记并移动：然后，调用
std::unique
。std::unique
本身并不会改变容器的大小，它做的是将唯一的元素移到范围的前面，并返回一个指向“新”逻辑末尾的迭代器。所有重复的元素会被移到这个逻辑末尾之后。 -
实际移除：最后，使用容器的
erase
方法，从std::unique
返回的迭代器位置开始，删除到容器的物理末尾。这样，容器的实际大小就被调整了。例如：vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
#include#include #include // for std::sort and std::unique #include // for std::set based de-duplication #include // for std::unordered_set based de-duplication // 示例1: 使用 std::sort + std::unique 去重 std::vector void deduplicate_vector_sort_unique(std::vector & vec) { std::cout << "Original vector (sort+unique): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; std::sort(vec.begin(), vec.end()); // std::unique 返回一个迭代器，指向新的逻辑末尾 // 实际的删除操作需要结合 erase vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); std::cout << "Deduplicated vector (sort+unique): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; } // 示例2: 使用 std::set 去重 std::vector void deduplicate_vector_set(std::vector & vec) { std::cout << "Original vector (set): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; // 将vector元素插入到set中，set会自动处理唯一性 std::set unique_elements(vec.begin(), vec.end()); // 清空原vector，再将set中的元素复制回来 vec.assign(unique_elements.begin(), unique_elements.end()); std::cout << "Deduplicated vector (set): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; } // 示例3: 使用 std::unordered_set 去重 std::vector void deduplicate_vector_unordered_set(std::vector & vec) { std::cout << "Original vector (unordered_set): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; // 将vector元素插入到unordered_set中 std::unordered_set unique_elements(vec.begin(), vec.end()); // 清空原vector，再将unordered_set中的元素复制回来 vec.assign(unique_elements.begin(), unique_elements.end()); std::cout << "Deduplicated vector (unordered_set): "; for (int x : vec) std::cout << x << " "; std::cout << std::endl; } int main() { std::vector data1 = {1, 3, 2, 4, 3, 1, 5, 2, 6, 4}; deduplicate_vector_sort_unique(data1); std::cout << "--------------------" << std::endl; std::vector data2 = {10, 30, 20, 40, 30, 10, 50, 20, 60, 40}; deduplicate_vector_set(data2); std::cout << "--------------------" << std::endl; std::vector data3 = {100, 300, 200, 400, 300, 100, 500, 200, 600, 400}; deduplicate_vector_unordered_set(data3); std::cout << "--------------------" << std::endl; return 0; }
可以看到，
std::sort+
std::unique的方式是原地修改，不需要额外的存储空间（除了排序算法可能需要的少量辅助空间）。而基于
std::set或
std::unordered_set的方法，则需要一个临时的集合来存储唯一元素，这会带来额外的内存开销，但代码逻辑上可能更直观一些，特别是当你不需要关心元素的原始顺序时。
立即学习“C++免费学习笔记（深入）”；
为什么std::unique
不能直接完成去重？
这确实是一个初学者常常会感到困惑的地方，我当初学习的时候也曾掉入这个“坑”。很多人会误以为
std::unique一调用，容器就自动变小了，但事实并非如此。
std::unique这个算法，它本质上是一个“搬运工”，而不是一个“删除工”。
它的设计哲学，我认为体现了STL中算法与容器分离的原则。
std::unique的任务是重新排列元素，将连续的重复元素中的第一个保留下来，而将其他的重复元素移动到序列的末尾。它返回的迭代器，指向的是这个“新”的、由唯一元素组成的序列的逻辑末尾。至于物理上的删除和容器大小的调整，那得由容器自己来完成，因为只有容器才知道如何高效地增删元素和管理内存。
举个例子，如果你的
vector是
{1, 2, 2, 3, 3, 3, 4}，调用std::unique后，它可能会变成
{1, 2, 3, 4, 3, 3, 4}（具体末尾的元素是什么，标准没有严格规定，但它们肯定不再是“有效”的唯一元素），然后std::unique会返回一个指向
4后面的迭代器。此时，容器的大小依然是7。只有当你接着调用
vec.erase(unique_it, vec.end())，容器才会真正地收缩到大小4。
这种设计的好处在于，
std::unique可以作用于任何支持前向迭代器的序列，而不仅仅是
vector。如果它自己去改变容器大小，那它的通用性就会大打折扣，因为它需要了解容器的内部实现细节。所以，它的职责很明确：找出并标记重复，而非实际删除。
面对不同STL容器，去重策略有何差异？
去重策略的选择，很大程度上取决于你正在使用的具体STL容器类型，因为不同容器的底层实现和迭代器特性差异巨大。
-
std::vector
和std::deque
：-
首选
std::sort
+std::unique
+erase
：这是最经典、通常也是效率最高的方案，尤其对于大型数据集。它们支持随机访问迭代器，std::sort
能发挥最大效率。而且，这是原地操作，没有额外的内存开销。 -
备选
std::set
/std::unordered_set
：如果你不关心元素的原始顺序，或者希望得到一个天然有序（std::set
）或无序但快速查找（std::unordered_set
）的唯一元素集合，那么可以先将容器元素全部插入到对应的集合中，然后再将集合中的元素赋值回原容器（如果需要）。这种方式代码简洁，但有额外的内存和复制开销。
-
首选
-
std::list
：std::list
是一个双向链表，不支持随机访问迭代器，这意味着你不能直接使用std::sort
（因为std::sort
需要随机访问）。-
链表特有方法：
std::list
有它自己的成员函数sort()
和unique()
。list::sort()
是链表特有的排序算法，效率很高；list::unique()
则会移除所有连续的重复元素。所以，对于std::list
，最推荐的做法是：myList.sort(); myList.unique();
-
借助其他容器：如果链表非常大，或者你出于某种原因不想原地修改，也可以将其元素复制到一个
std::vector
中，对vector
进行去重，然后再将结果复制回std::list
。但这通常会带来较大的性能损失。 -
std::set
/std::unordered_set
：同样，也可以将list
的元素插入到std::set
或std::unordered_set
中，再复制回来。这在逻辑上很清晰，但同样有额外的内存和复制成本。
-
std::set
、std::multiset
、std::map
、std::multimap
、std::unordered_set
、std::unordered_map
：-
无需去重（对于键）：
std::set
和std::unordered_set
本身就只存储唯一的键，所以它们本身就已经是去重过的了。你不需要对它们进行额外的去重操作。std::map
和std::unordered_map
也只存储唯一的键值对，如果你指的是对键去重，那它们也已经做到了。 -
对值去重（对于
map
类）：如果你想对std::map
或std::multimap
的值进行去重，那情况就不同了。你需要遍历容器，提取出所有的值到一个std::vector
或std::list
中，然后对这个新的容器进行上述的去重操作。这其实是将问题转化为了对其他容器的去重。
-
无需去重（对于键）：
总的来说，理解容器的底层特性是选择去重策略的关键。对于顺序容器（
vector,
deque），
sort+
unique是黄金搭档；对于
list，利用其成员函数是最佳实践；而关联容器和无序关联容器，在键的层面，它们天生就是去重过的。
选择哪种去重方法时，需要考虑哪些性能与设计权衡？
在实际项目中，选择去重方法并非一刀切，它涉及多方面的权衡考量，这往往也是体现一个开发者经验和对C++理解深度的点。
-
时间复杂度：
-
std::sort
+std::unique
：主要由排序决定，通常是 O(N log N)。std::unique
本身是 O(N)。这是比较高效的方案。 -
std::set
：将N个元素插入std::set
的平均时间复杂度是 O(N log N)，因为每次插入都是 O(log N)。 -
std::unordered_set
：将N个元素插入std::unordered_set
的平均时间复杂度是 O(N)，因为每次插入平均是 O(1)。但在最坏情况下（哈希冲突严重），可能退化到 O(N^2)。 -
std::list::sort()
+std::list::unique()
：list::sort()
通常是 O(N log N)，list::unique()
是 O(N)。
-
-
空间复杂度：
-
std::sort
+std::unique
：对于std::vector
和std::deque
，通常是 O(1) 的额外空间（原地修改），除非std::sort
内部使用了非原地排序算法，但通常现代STL实现都会尽量原地。这是其一大优势。 -
std::set
/std::unordered_set
：需要 O(N) 的额外空间来存储临时的集合，因为你要把所有元素复制进去。对于内存敏感的应用，这可能是一个问题。
-
-
元素类型要求：
-
std::sort
：要求元素类型支持operator<
（或提供自定义比较器）。 -
std::unique
：要求元素类型支持operator==
（或提供自定义谓词）。 -
std::set
：要求元素类型支持operator<
（或提供自定义比较器）。 -
std::unordered_set
：要求元素类型支持operator==
和std::hash
特化（或提供自定义哈希函数和相等谓词）。如果自定义类型没有提供这些，那么就不能使用unordered_set
。
-
-
是否需要保持原始顺序？
-
std::sort
+std::unique
：会彻底打乱原始顺序。 -
std::set
：会按照其内部的排序规则（通常是升序）重新排列元素。 -
std::unordered_set
：不会保持任何特定顺序，元素的最终顺序是不确定的。 - 如果原始相对顺序对你很重要，那么这些方法都不能直接满足需求。你可能需要更复杂的策略，比如使用一个辅助的
std::unordered_set
来检查唯一性，同时遍历原始容器，将唯一的元素复制到一个新的容器中。
-
-
原地修改 vs. 创建新容器：
-
std::sort
+std::unique
：是原地修改，直接操作原容器。 -
std::set
/std::unordered_set
：通常意味着创建一个新的集合，然后将结果复制回原容器（如果需要）。这涉及到额外的构造、析构和复制成本。
-
我的个人看法和经验是：
-
对于
std::vector
和std::deque
，如果对元素的顺序没有严格要求，或者排序后的顺序也可以接受，那么std::sort
+std::unique
几乎总是我的首选。 它效率高，内存占用小，是C++处理这类问题的经典范式。 -
如果数据量非常大，且对性能要求极致，并且元素类型支持高效哈希，
std::unordered_set
通常能提供最快的平均去重速度。 但要警惕最坏情况和哈希冲突带来的性能问题。 -
如果需要去重后的元素保持有序，或者需要利用集合的查找特性，
std::set
是很好的选择。 它提供有序性，但插入和查找的对数时间复杂度意味着它可能比unordered_set
慢，比sort
+unique
在某些情况下也慢。 - 在某些场景下，如果你的元素类型很复杂，或者你需要根据非常规的规则判断“相等”，那么自定义的哈希函数或比较器就变得至关重要。 这时候，选择哪种容器和算法，就不仅仅是性能问题，更是实现复杂逻辑的便利性问题。
最终的选择，是性能、内存、代码可读性、以及对原始数据顺序要求的综合平衡。没有绝对“最好”的方法，只有最适合你当前需求的方法。
