21xrx.com
2024-11-22 03:36:10 Friday
登录
文章检索 我的文章 写文章
C++ Set的顺序问题
2023-07-02 20:21:09 深夜i     --     --
C++ Set 顺序问题

C++中的Set是一种常见的容器类型,它可以存储一组元素,保证元素唯一且有序,底层实现常采用红黑树等数据结构。将元素插入Set中,Set会自动按照一定的规则将元素排列起来。

然而,有时候会出现Set的顺序并不是我们想要的情况。比如,我们希望Set按照插入的顺序排列,而实际上Set却按照元素大小排列。这时我们需要了解Set底层的实现方式。

Set的底层使用红黑树实现,红黑树是一种自平衡二叉搜索树,通过对树的平衡调整,保证树的高度最小,查找、插入、删除等操作的时间复杂度都是O(log n)。节点在红黑树中的位置是由节点的权值大小决定的,也就是说Set中元素的顺序是由权值大小决定的。

如果我们希望Set按照插入顺序排列,则可以使用另一种容器类型——unordered_set。unordered_set底层使用哈希表实现,哈希表的查找、插入、删除等操作时间复杂度都是O(1),而且元素的排列顺序是无序的。

综上所述,当我们使用Set存储数据时,需要根据实际需求来选择不同的容器类型。如果我们需要排序且不关心插入顺序,则可以使用Set。如果我们需要保持插入顺序,则可以使用vector或list;如果我们不关心顺序,则可以使用unordered_set。

在使用Set时,我们也可以通过重载比较运算符来改变元素的排序方式。但是需要注意的是,如果我们改变了排序方式,则必须保证新的排序方式满足严格弱序关系,否则可能会导致Set失去唯一性或无法进行正常的查找、插入、删除等操作。

总之,Set是一种非常实用的容器类型,在进行数据存储和查找时发挥着巨大的作用。通过了解其底层实现和使用场景,能够更好地使用Set,提高代码效率和准确性。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复