概述

在編碼中經(jīng)常會(huì)遇到一種場(chǎng)景，就是要在數(shù)組或列表中查找某個(gè)元素是否存在，其實(shí)對(duì)于這種線(xiàn)性操作，自己實(shí)現(xiàn)一個(gè)循環(huán)來(lái)檢查是非常簡(jiǎn)單的事情，那既然這樣，為啥還要專(zhuān)門(mén)寫(xiě)篇博客來(lái)分享呢？
一個(gè)最重要的原因就是我們?cè)揪涂梢杂酶?jiǎn)潔直觀高效的方式去替代手寫(xiě)for循環(huán)，這個(gè)方式就是使用C++標(biāo)準(zhǔn)庫(kù)函數(shù)。

再啰嗦幾句。
通常在面試的時(shí)候，為了考察面試者的編碼功底，會(huì)讓其從頭實(shí)現(xiàn)某些基礎(chǔ)的算法，但是在實(shí)際開(kāi)發(fā)中，很多東西都有現(xiàn)成的封裝。只有把語(yǔ)言、標(biāo)準(zhǔn)庫(kù)“雙劍合璧”才能算是真正的C++。而且據(jù)C++標(biāo)準(zhǔn)委員會(huì)的安排，今后C++也會(huì)更側(cè)重于擴(kuò)充庫(kù)而不是擴(kuò)充語(yǔ)言，可見(jiàn)其分量的輕重了。

總之，C++標(biāo)準(zhǔn)庫(kù)是一個(gè)非常強(qiáng)大的東東，并且實(shí)現(xiàn)這些標(biāo)準(zhǔn)庫(kù)的人都是些非常牛逼的頂級(jí)程序員，性能都是最優(yōu)的。所以不要總想著所有事情都親力親為的去寫(xiě)一遍，既浪費(fèi)時(shí)間，寫(xiě)出來(lái)的東西可能還很菜。那么，這里就通過(guò)一些簡(jiǎn)單的示例來(lái)演示如何通過(guò)標(biāo)準(zhǔn)庫(kù)函數(shù)來(lái)實(shí)現(xiàn)。

正文

如何檢查vector中是否包含給定元素。

std::count

最簡(jiǎn)單的方式是對(duì)vector中的指定元素進(jìn)行計(jì)數(shù)，如果count不為零，表示該元素存在，那么std::count可以很容易實(shí)現(xiàn)。

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

int main()
{
	std::vector<int> v = { 1, 20, 2, 6, 3, 7 };
	int key = 6;

	if (std::count(v.begin(), v.end(), key))
		std::cout << "Element found";
	else
		std::cout << "Element not found";

	return 0;
}

std::find

相比第一種方式，std::find()算法能夠更快速的查找給定范圍內(nèi)的值，因?yàn)閟td::count()會(huì)變量整個(gè)容器以獲得元素計(jì)數(shù)，而find()在找到匹配元素后就立即停止搜索。

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

int main()
{
	std::vector<int> v = { 1, 20, 2, 6, 3, 7 };
	int key = 6;

	if (std::find(v.begin(), v.end(), key) != v.end())
		std::cout << "Element found";
	else
		std::cout << "Element not found";

	return 0;
}

std::find_if

和find相似的還有一個(gè)叫 std::find_if()算法，如果查找需要滿(mǎn)足某些條件，那么推薦使用該方法。這里我們可以結(jié)合lambda來(lái)使用，非常簡(jiǎn)潔。

比如，要查找列表中是否有元素能被5整除

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

int main()
{
  auto lst = {1,4,9,5,11};
  if(std::find_if(lst.begin(),lst.end(),[](auto v){
    if(v%5 ==0)
      return true;
    else
      return false;
  }) != lst.end()){
    std::cout << "Element found";
  }
  else{
    std::cout << "Element not found";
  }
  return 0;
}

C++ 11 - std::any_of

該算法與std::find_if相似，但不是返回滿(mǎn)足條件的的序列中第一個(gè)元素的迭代器，而是如果任何元素滿(mǎn)足條件后返回true，否則返回false。

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

struct compare
{
	int key;
	compare(int const &i): key(i) { }

	bool operator()(int const &i)
	{
		return (i == key);
	}
};

int main()
{
	std::vector<int> v = { 4, 7, 5, 2, 6, 9 };
	int key = 6;

	if (std::any_of(v.begin(), v.end(), compare(key)))
		std::cout << "Element found";
	else
		std::cout << "Element not found";

	return 0;
}

或者直接修改find_of的案例：

int main()
{
  auto lst = {1,4,9,5,11};
  if(std::any_of(lst.begin(),lst.end(),[](int v){
    if(v%5 ==0)
      return true;
    else
      return false;
  })){
    std::cout << "Element found";
  }
  else{
    std::cout << "Element not found";
  }
  return 0;
}

C++ 11 - std::none_of

該算法剛好和any_of相反，如果給定的條件在范圍內(nèi)所有元素都返回false，則返回true，如果至少一個(gè)元素返回true，則返回false。

直接修改上述示例，將if條件改成“非”就可以了，不再贅述。

std::binary_search

最后一種方法，如果vector是有序的，那么可以考慮使用這種算法，如果在給定范圍內(nèi)找到元素，則返回true，否則返回false。該方式是采用二分法查找，時(shí)間復(fù)雜度為O(log(n))，速度比較快。

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

int main()
{
	std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7 };
	int key = 4;

	if (std::binary_search(v.begin(), v.end(), key))
		std::cout << "Element found";
	else
		std::cout << "Element not found";

	return 0;
}

OK，以上所有方法都可以實(shí)現(xiàn)我們想要的結(jié)果，只是在不同情況下選擇一種自己喜歡的方式即可。

附：
C++接口文檔：https://en.cppreference.com/w/
C++算法庫(kù)介紹：https://en.cppreference.com/w/cpp/algorithm

到此這篇關(guān)于C++中檢查vector是否包含給定元素的幾種方式的文章就介紹到這了,更多相關(guān)C++檢查vector是否包含給定元素內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論