c++ STL中的vector与list为什么没有提供find操作?


map里有,set里也有,vector,list没有,太不公平了吧。

其实应该考虑为什么map,set里有find操作。

include<algorithm>里有通用的find操作,通用的find内部是从begin到end进行一次遍历,复杂度是O(n)。

通过iterator从begin到end遍历map与set时,得到的结果是按key排序的结果,而不是插入时的顺序(所以这两个容器没有push_back操作),

其实,insert到map与set中的元素会被组织到一颗红黑树上,红黑树是一颗平衡二叉树,平衡二叉树是一颗二叉排序树,对一颗二叉排序树的查找有点像二分查找,复杂度是O(log(n))。

由于map与set的数据结构能有更快的查找方法,所以在容器内提供了find方法。

原文地址:https://www.cnblogs.com/panyihua/p/3928082.html