C++中set的插入和查找 与二分查找对比 效率如何
我是分别用 st.inset插入25w个整数，然后再用st.count与x匹配 x是我输入的值
另外是把25w个数据复制到数组f[] 然后用二分查找匹配。。。。两种算法提交后 前者共耗时2600ms 空间9000kb 后者 耗时600ms 内存2000kb。。。。想问问具体为什么 据说set的查找也是二分。。lgn复杂度
如果已知数据有序，那么顺序表的二分查找当然最快。但是顺序表的插入性能极差，比如我要在头部插入一个数据，则要吧所有的数据后移一格，开销极大。红黑树则平衡了插入性能和查找性能。所以就有你看到的数据了，set的时间空间性能都比较差。
顺序复制数组，不涉及到插入，所以数组很快。但是插入，删除的话，红黑树需要一些时间来调整结构，所以有时间和空间的开销。
如果你有这样的一批数据，数量比较大，假设25w左右，他们需要频繁的发生插入，删除，以及查找工作，那么数组就无法处理了，红黑树则是更好的选择。
你可以研究一下红黑树的性质，就很容易理解了。
如果有不清楚的地方请追问。追问
好吧谢谢您。。我忘了 提到 set里面是每次插入都有自动排序。。。而我在数组方面是先全部赋值完成再用sort排序。
那么我那样使用set和二分查找造成的时间和空间的差别 是 因为 处理输入数据时，红黑树的插入过程每次都排序吗
空间差别：红黑树是树，不仅仅需要存储你给的值，还要存储树所需的其他信息，比如子节点，父节点的地址，节点颜色。
时间差别：红黑树并不是每次都需要排序，但是会在有些情况下对树进行调整，红黑树的插入策略还是有点小复杂的，你需要专门的研究。
顺序表并不适合不断的插入。理由如下：即使你一直保证顺序表有序，那么当你使用二分查找找到需要插入的点的时候，进行数据插入，插入时候你不得不对后面所有的数据往后移动一格。当数据很大，移动大量的内存开销很大的。所以不适合插入。此外，当对数据进行删除，又要对大量内存向前移动一格。相比之下，红黑树的插入，删除性能就好很多。
复杂度的确都是logN（排序其实是平均logN，最坏情况下是logN^2），有一个小问题是二分查找是绝对的2的对数次循环，红黑树并不是绝对平衡的平均下来会比2的对数次循环多。不过这个只是小问题。另外一个小问题是红黑树的每次循环的代价要比排序大，排序只是一个比较和一个可能的交换，红黑树是一个申请内存，初始化结构加一个可能的涉及三个节点的旋转。
然后真正影响速度的大问题是内存局域性（memory locality），内存局域性差就不能有效利用CPU的高速缓存。
排序方法你写入的时候不读取数据，排序的时候用的快速排序算法某种意义上也是一个牺牲绝对复杂度（最坏的情况下是logN^2）从而提高内存局域性的算法。二分查找是一个内存局域性差的操作，但是你只执行了一次。
而set每次插入都是内存局域性几乎等于没有的操作，而且set本身的数据量又大很多，所以自然就慢了。
set更适合需要不断插入，并且随时要在里面查找的情况（这种情况一般叫在线排序online sorting）。set插入的复杂度是logN，而排序的方法插入的复杂度是N。所以只要N足够大，就能抵消内存局域性的代价。但是你的情况显然不符合。追问
谢谢。最后一段，set更适合不断地插入，然后随时查找。。。
比较起 每次往数组赋值一个数，然后sort排序。。然后二分查找。。这两种效率应该一样吧。
而我的 问题中 出现时间空间有差别应该是因为 前者是每次插入都排序。而后者只全部输入完成之后一次排序。吧
向数组插入的复杂度是N（先用二分查找确定插入位置，然后把内容向后挪）。你说的加进去再排序的复杂度是N*logN，也就是排序的复杂度。向set插入的复杂度是logN。显然前者比后者慢太多了。即便向set插入一次循环的时间是排序一次循环的100倍。元素超过100个的时候排序就比set慢了。我那个方法元素超过1000个也开始比set慢了。（而且注意，其实set插入也没慢到100倍上）
复杂度差一级是很可怕的，你的情况之所以它们两个的单次循环性能会影响结果，因为时间复杂度是一样的。
另外更正我上面一个很脑残的笔误，排序最坏情况下是N^2不是什么logN^2。
