Question

c++ stl set 中find方法是如何实现的

find方法是如何实现的？
其复杂度是多少？
然后还有一个问题。一组只有少量数据 低于10个，但是要对其进行多次查找大概100W次
使用vector 和 set 哪个比较快？
还有一个问题，使用set比较的时候会先声明一个iterator 然后 find 返回 一个iterator并将其付给 前面声明的iterator 再来判断是否等于end 。
用vector 可以用【1】 这样像数组一样操作， 这样和使用iterator 效率上是否一样？

Answer 1

是用在平衡二叉树上查找的算法实现的，复杂度是O(log n)。
STLport里面的实现代码如下：

_Base_ptr _M_find(const _KT& __k) const {
_Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k.
_Base_ptr __x = _M_root(); // Current node.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
if (__y != &this->_M_header._M_data) {
if (_M_key_compare(__k, _S_key(__y))) {
__y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
}
}
return __y;
}

第二个问题，单独使用的话，set应该比较快些（vector 的话，要先来个排序然后再二分，估计速度也差不多），不过如果你用的编译器新的话，能支持C++11的话，建议你用unordered_set应该可以更快些。 要想速度更更快些的话，就不要用stl了，自己小心点实现个哈希算法应该可以办到。

追问

哈希算法，怎样利用它查找呢？

追答

这个...估计你不懂哈希吧！
你找本数据结构或者算法的书学学，你就知道了，我在这里几句话说不明白的。

追问

哈希我是知道的，但是对于我面临的问题， 少量数据 大量查询，用哈希就代表着大量散列过程。这个过程比比较过程快吗？

追答

你自己实现，针对你的key的类型来设计哈希函数，设计得好的话，查找的平均时间复杂度是O(1)！
如果你的key是字符串的话，你可以考虑改用字典树，就可以同样很快的！

追问

然后这个hash我稍微试了下 对于大量数据搜索是很快的 但是少量数据多次查询，其本身散列计算远比比较耗时间

Answer 2

set就是个红黑树，find的时间复杂度O(log2(N))，其实现大约就是二叉排序树查找，只不过红黑树的统计学特性更好；至于好在哪儿，我没研究过，感兴趣可以自己看算法导论；
vector 和set的问题，用hash表也不一定就最快，比如string，hash运算也消耗资源；
如果10个int的话，我觉得vector可能比set更好，你自己写个程序试试，time计算下时间；
如果查找元素的次序有规律的话，可以利用一下啊提高效率，将出现频率更高的元素放在前面；

Answer 3

我觉得第二个问题是vector快一些吧，就是要先用sort排序，然后用已序区间上的算法来查找。set和已序查找的渐近时间是一样的，但是我觉得vector直接支持随机访问，应该会比基于二叉树实现的set来得快把，毕竟会少掉很多的辅助结构。
我也不是非常明白底层实现，以上是个人推断仅供参考。