STL 中 set 的实现原理

1. set 的 底层数据结构是 红黑树,一种高效的平衡检索二叉树

2. set 容器中 每一个元素就是二叉树的每一个节点,对于set容器的插入删除操作,效率都比较高,原因是因为二叉树的删除插入元素并不需要进行内

存拷贝和内存移动,只是改变了指针的指向

3. 对 set 进行插入删除操作 都不会引起iterator的失效,因为迭代器相当于一个指针指向每一个二叉树的节点,对set的插入删除并不会改变原有内存

中节点的改变, 但是vector的插入删除操作一般会发生内存移动和内存拷贝,所以会发生迭代器的失效

4. set容器的检索速度很快,因为采用二分查找的方法




原文地址:https://www.cnblogs.com/ZhangJinkun/p/4534212.html