C++ set容器如何保证唯一性 红黑树实现与自定义排序

<p>std::set保证元素唯一性的核心机制在于其底层使用红黑树结构并结合排序规则。红黑树在插入时通过比较操作决定节点位置，若等于当前节点则不插入，从而避免重复；此外，红黑树的自平衡特性使操作复杂度稳定在o(log n)。自定义排序可通过提供比较函数改变排序逻辑，但必须满足严格弱序以确保正确判断唯一性。常见误区是若需存储重复值应使用std::multiset。实际应用中，存储自定义类型时需确保比较函数覆盖所有影响唯一性的字段。</p> <p><img src=”https://img.php.cn/upload/article/000/969/633/175488330395455.png” alt=”C++ set容器如何保证唯一性 红黑树实现与自定义排序”></p> <p>C++ 中的 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>std::set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 容器之所以能保证元素唯一性，核心机制在于其内部基于<strong>红黑树（Red-Black Tree）</strong>实现，并结合了排序规则。下面我们从底层结构和自定义排序两个角度来详细说明。</p> <img src=”https://img.php.cn/upload/article/000/969/633/175488330375022.png” alt=”C++ set容器如何保证唯一性 红黑树实现与自定义排序”><hr> <h3>红黑树如何支持唯一性</h3> <p><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>std::set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 底层使用的是红黑树这种自平衡二叉搜索树。红黑树在插入新节点时会根据比较结果决定插入位置，而这个比较过程直接决定了是否允许重复值存在。</p> <ul><li>插入新元素时，会与当前节点进行比较：<ul> <li>如果小于当前节点，则进入左子树；</li> <li>如果大于当前节点，则进入右子树；</li> <li>如果等于当前节点，就不再插入。</li> </ul> </li></ul> <p>换句话说，红黑树的查找逻辑天然地避免了重复值的插入，这就实现了 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 的唯一性。</p> <p><span>立即学习</span>“<a href=”https://pan.quark.cn/s/6e7abc4abb9f” style=”text-decoration: underline !important; color: blue; font-weight: bolder;” rel=”nofollow” target=”_blank”>C++免费学习笔记（深入）</a>”；</p> <img src=”https://img.php.cn/upload/article/000/969/633/175488330382008.png” alt=”C++ set容器如何保证唯一性 红黑树实现与自定义排序”><p>此外，红黑树还保持了树的平衡性，使得插入、删除、查找的时间复杂度稳定在 O(log n)，这为 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 提供了高效的性能保障。</p> <hr> <h3>自定义排序影响唯一性的判断方式</h3> <p>默认情况下，<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>std::set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 使用 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>operator<</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 来比较元素大小。但如果你希望按照自己的规则排序，可以提供一个自定义的比较函数或仿函数。</p> <img src=”https://img.php.cn/upload/article/000/969/633/175488330462291.png” alt=”C++ set容器如何保证唯一性 红黑树实现与自定义排序”><p>例如：</p><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=’brush:cpp;toolbar:false;’>struct MyCompare { bool operator()(const int& a, const int& b) const { return a > b; // 降序排列 } }; std::set<int, MyCompare> mySet;</pre><div class=”contentsignin”></div></div><p>在这个例子中，虽然排序顺序变了，但唯一性的判断仍然是通过比较函数来完成的。只要你的比较函数满足严格弱序（strict weak ordering），<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 就能正常工作。</p> <blockquote>⚠️ 注意：如果你的比较函数没有正确处理相等关系，可能会导致 set 行为异常，比如误判重复或者漏判重复。</blockquote> <p>所以，自定义排序的关键点是：</p> <ul> <li>保持比较逻辑的正确性；</li> <li>不要遗漏对“等于”情况的处理（虽然不需要显式写等于，但要确保比较函数隐含这一逻辑）；</li> <li>避免使用 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>operator==</pre><div class=”contentsignin”></div></div>，因为 set 内部只用到了 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”><</pre><div class=”contentsignin”></div></div> 或你提供的比较方式。</li> </ul> <hr> <h3>常见误区：<a >为什么</a>不能有重复值？</h3> <p>有些初学者可能会疑惑：“如果我想存多个相同值怎么办？”这时候应该考虑使用 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>std::multiset</pre><div class=”contentsignin”></div></div>，它允许重复元素，同时仍然基于红黑树实现。</p> <p><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 和 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>multiset</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 的<a >区别</a>就在于：</p> <ul> <li><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 在插入前检查是否存在相等的元素；</li> <li><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>multiset</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 直接插入，不管有没有相同的。</li> </ul> <p>因此，如果你确实需要存储重复项，请选择 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>multiset</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>。</p> <hr> <h3>实际应用中的小技巧</h3> <p>有时候我们想存储自定义类型对象到 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>，这时候除了提供比较函数外，还需要注意几点：</p> <ul> <li>类型必须可复制或可移动；</li> <li>比较函数应覆盖所有可能影响唯一性的字段；</li> <li>如果字段较多，建议重载 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>operator<</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 或使用 lambda（C++14+ 支持）；</li> </ul> <p>举个例子：</p><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=’brush:cpp;toolbar:false;’>struct Person { std::string name; int age; }; struct ComparePerson { bool operator()(const Person& a, const Person& b) const { if (a.name != b.name) return a.name < b.name; return a.age < b.age; } }; std::set<Person, ComparePerson> people;</pre><div class=”contentsignin”></div></div><p>这样设置后，只有当两个人的姓名和年龄都完全相同时，才会被视为重复，不会被插入。</p> <hr> <p>基本上就这些。理解 <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>set</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div> 的唯一性机制，关键在于搞清楚红黑树的插入逻辑和比较函数的作用方式。掌握了这两点，就能灵活运用并避免常见问题。</p>