c++判断vector中是否存在特定元素的方法

简介

常常需要在vector中查找元素是否存在,或者确定元素的个数。但vector未提供相关的成员函数。

这里不讨论手写for遍历的方法。无论从工作量还是效率方面,都应该优先选用STL算法。

注意:对于任意的vector,查找某个元素需要耗费线性时间。除非该vector是有序的。

算法模块提供了查找的多种方式。

以下代码需要包含该头文件。以在vector中查找元素为例。

方法与示例

1. std::count

对于只需要知道包含特定元素的数量的应用来说,这是最简单的方式。如果count返回0,则表示不存在该元素。

示例:

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;
using std::count;
using std::cout;
using std::endl;

int main()
{ 
		vector<int> v{  4, 7, 9, 1, 2, 5 };
		int key = 2;
		
		if (count(v.begin(), v.end(), key))
		{ 
				cout << "Element found" << endl;
		}
		else
		{ 
				cout << "Element NOT found" << endl;
		}
		
		return 0;
}
2. std::find

find会在查找到指定值后立即返回,所以它一般比count更快(因为count总是要遍历整个容器)。

上述代码只需要更改条件判断语句:

if (std::find(v.begin(), v.end(), key) != v.end())

3. std::find_if

它也能完成任务,但有点大材小用了。

find_if需要一个判别式。如果查找的值需要满足特定的条件时,比如查找小于3且大于1的值时,适合该方式。

如果有多个值符合条件,则返回查找到符合条件的第一个值的迭代器。

条件判断语句:

if (std::find_if(v.begin(), v.end(), [] (int i) { return i < 3 && i > 1 } ) != v.end())

4. std::any_of(C++11)

与find_if类似,但它返回bool值。

如果判断式返回true,则它也返回true。否则返回false。

条件判断语句:

if (std::any_of(v.begin(), v.end(), [] (int i) { return i < 3 && i > 1 } ))

扩展:std::none_of,是any_of的反面。也就是,当判断式是false时它返回true,否则返回flase。

5. std::binary_search

作为磨刀不误砍柴工的一种方式,可以对vector先排序,再查找,就可以使用二分查找了。

二分查找的时间效率为O(logn)。

代码片断:

sort(v.begin(), v.end());
if (std::binary_search(v.begin(), v.end(), key))

小结

方法虽多,侧重各不相同。选择适合的算法有助于提高代码可读性和执行效率,简单总结如下:

  • 对于已经排序的vector,使用binary_search
  • 仅判断是否存在某元素,使用find
  • 需要某元素总个数时,使用count
  • 支持复杂条件的查找时,使用any_of(仅知道是否存在)/find_if(返回了第一个元素的迭代器)
    原文作者:guotianqing
    原文地址: https://blog.csdn.net/guotianqing/article/details/105832070
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞