C++ vector容器 find erase的使用操作:查找並刪除指定元素

Posted on by

概念：容器、迭代器、算法

STL包括容器、迭代器和算法：

容器

用於管理一些相關的數據類型。每種容器都有它的優缺點，不同的容器反映出程序設計的不同需求。容器自身可能由數組或鏈表實現，或者容器中的每個元素都有特殊的關鍵值。

迭代器

用於遍歷一個數據集中的每個元素。這些數據集可能是容器或者容器的子集。迭代器的主要優點是它們為任意類型的容器提供一個小巧並且通用(註意通用很重要)的接口。例如，迭代器接口的一個操作是讓它依次遍歷數據集的每個元素。這個操作是依賴容器的內總部結構獨立完成的。迭代器之所以有效是因為容器類提供它自己的迭代器類型來做“正確的事”，容本身的迭代器瞭解容器的內部結構。

迭代器的接口幾乎相當於普通的指針。讓一個迭代器遞增隻需調用++操作符。使用*操作符可以得到迭代器引用的數據值。因而迭代器可以被任為是一種智能指針。

算法

被用於處理數據集中的元素。例如它們可以搜索、排序、修改數據或者其他目的。算法使用迭代器，因此，一個算法隻需被編寫一次就可以用於任意的容器，因為迭代器的接口對所有類型的容器是通用的。這就是find()的位置

為瞭給算法更多的擴展性，需要提供一些被算法調用的附屬函數。可以使用通用算法去適應非常特別和復雜的需求。你可以提供自己的搜索標準或者特殊的操作去綁定元素。

STL的概念是將數據和操作獨立開來。數據由容器類管理，而操作是由可配置的算法定義。迭代器則是這兩個元素之間的線索。它允許任何算法和容器的交互。

在某種意義上，STL的概念有勃於面向對象編程的初衷：STL將數據和算法分離而非綁定它們。然而，這樣做的理由非常重要：原則上，你可以將任何容器同任何算法綁定，得到的結果是STL是非常可擴展的。

STL的一個標準是它支持任意數據類型。“標準模板庫”意味著，所有部分是適應任意類型的模板。STL是通用編程的例子。容器和算法對任意類型和類都是通用的。

STL甚至提供更多的通用組件。使用 適配器 和函數體，你可以為特定需要補充、限制和配置算法和接口。

註意find不屬於vector的成員，而存在於算法中，應加上頭文件#include <algorithm>

C++ vector 刪除符合條件的元素

包含頭文件：

#include <iostream>
#include <vector>
#include <algorithm>//註意要包含該頭文件

C++ vector中實際刪除元素使用的是容器vector中std::vector::erase()方法。

C++ 中std::remove()並不刪除元素，因為容器的size()沒有變化，隻是元素的替換。

1.erase( ) 刪除元素

函數原型：

iterator erase (iterator position);//刪除指定元素
iterator erase (iterator first, iterator last);//刪除指定范圍內的元素

返回值：指向刪除元素(或范圍)的下一個元素。

（An iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.）

對於c++裡面的容器, 我們可以使用iterator進行方便的遍歷. 但是當我們通過iterator對vector/map等進行修改時, 我們就要小心瞭。

cplusplus的reference裡對 std::vector::erase 的描述是:

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

由上可知，原有iter指針在刪除元素後會失效，之後的行為都變得不可預知.。

對於vector, erase會返回下一個iterator, 因此我們可以使用如下的方法:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
 vector<int> a = { 12, 23, 34, 45, 56, 67, 78, 89 };
 auto iter = a.begin();
 while (iter != a.end()) 
 {
  if (*iter > 30) 
  {
   iter = a.erase(iter);//用iter接收返回值
  }
  else //不要忘記這一段
  {
   ++iter;
  }
 }
 for (const auto &element : a) {
  cout << element << endl;
 }
 return 0;
}

實現代碼

例1. 用while循環查找並刪除一個元素

#include <vector>
using namespace std;
void main(void)
{
 vector<int> array;
 array.push_back(1);
 array.push_back(2);
 array.push_back(3);
 array.push_back(4);
 array.push_back(5);
 vector<int>::iterator itr = array.begin();
 while (itr != array.end())
 {
  if (*itr == 3)
  {
   itr = array.erase(itr);//刪除元素，返回值指向已刪除元素的下一個位置
  }
  else
  {
   ++itr;
  }
 }
}

例2. 用for循環遍歷刪除所有元素

#include <vector>
#include <iostream>
using namespace std;
int main()
{
        vector<int> test_vec;
        for (int i = 0; i<100;i++)
        {
                test_vec.push_back(i);
        }
        for(vector<int>::iterator it  = test_vec.begin(); it != test_vec.end(); )
         {
                 cout<<*(it)<<endl;
                 it = test_vec.erase(it);
        }
         return 0;
 }

例3. 刪除重復元素

若要求按照數據原來的順序，參照本文最後的代碼

若不要求按照數據原來的順序，可用：

sort(v.begin(),v.end());                           //unique隻能比較相鄰元素是否重復
v.erase(unique(v.begin(), v.end()), v.end());      //unique將重復的元素移到末尾，返回末尾中第一個重復值的地址

2.find( ) 查找元素

官方文檔給出的定義：

find (STL)

在范圍中找到具有指定值的元素的第一個匹配項位置。

用於確定要在范圍中搜索的指定值第一次出現的位置的輸入迭代器。 如果找不到具有等效值的元素，則返回 last。

template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last,        const T& val);

first

用於確定要在范圍中搜索其指定值的第一個元素的位置的輸入迭代器。

last

用於確定要在范圍中搜索其指定值的最後一個元素之後下一個元素的位置的輸入迭代器。

val

要搜索的值。

find() 函數：在容器內查找指定的元素，這個元素必須是基本數據類型的。

語法：find(arr.begin(), arr.end(), 50);第一個參數是array的起始地址，第二個參數是array的結束地址，第三個參數是需要查找的值。

如果想從指定位置開始查找，可以這樣寫：find(c.begin()+i+1, c.end(), c[i]);

其中i為自定義的位移量，結合for循環可以實現從當前位置開始查找

查找成功：返回一個指向指定元素的迭代器

查找失敗：返回end迭代器

STL庫中，find( )源碼如下：

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
 while (first != last && *first != value)
 {
  ++first;
 }
 ++first;
 return first;
}

用find查找並刪除一個元素

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> arr(100);//整型的array數組
int main()
{
 arr[20] = 50;//其餘都是默認值0
 vector<int>::iterator s = find(arr.begin(), arr.end(), 50);//第一個參數是array的起始地址，第二個參數是array的結束地址，第三個參數是需要查找的值
 if (s != arr.end())//如果找到，就輸出這個元素
 {
  cout << *s << endl;
 } 
 else//如果沒找到
 {
  cout << "not find!" << endl;
 }
 system("pause");
 return 0;
}

另外還有一個函數: find_if函數

find_if函數，帶條件的查找元素。

容器元素類型是類的時候，不能使用find函數，隻能通過find_if函數來實現。

find_if函數依次的遍歷容器的元素，返回第一個使函數為true的元素的迭代器；如果查找失敗則返回end迭代器。

3.remove()

std::vector沒有直接刪除特定值元素的成員方法。所以必須使用remove算法：

std::vector <Elem> coll;
//remove all elements with value val
coll.erase(remove(coll.begin(), coll.end(), val), coll.end());

remove()返回的是刪除後的尾部迭代器，必須調用erase()顯式地刪除其後的元素。

如果僅刪除第一個特定值元素：

std::vector <Elem> coll;
//remove first element with value val
std::vector<Elem>::iterator pos;
pos = find(coll.begin(), coll.end(), val);
if (pos != coll.end())
{
 coll.erase(pos);
}

4.代碼實例（一道牛客網練習題）

內容：

輸入兩行字符c[ ], b[ ];

該程序把c[ ]中與b[ ]重復的元素全部刪除

並且把c[ ]本身內部重復的元素也刪除（大小寫被一律轉化為大寫）

最後輸出剩餘的不重復的元素

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	vector <char> c;
	vector <char> d;
	char keyBoard;
	//輸入c數組，用回車結束
	while (keyBoard = getchar())
	{
		if (keyBoard == '\n')break;
		c.push_back(keyBoard);
	}
	//輸入d數組，用回車結束
	while (keyBoard = getchar())
	{
		if (keyBoard == '\n')break;
		d.push_back(keyBoard);
	}
	//c-d：c,d數組對比，刪除c數組中與d數組相同的元素
	vector<char>::iterator iter = c.begin();
	int i;
	for (i = 0; i < d.size(); i++)
	{
		iter = find(c.begin(), c.end(), d[i]);
		if (iter != c.end())
		{
			c.erase(iter);
		}
	}
	//把c數組中剩餘的小寫字母轉換為大寫，其餘字符不變
	for (i = 0; i < c.size(); i++)
	{
		if (c[i] >= 'a'&&c[i] <= 'z')
		{
			c[i] -= 32;
		}
	}
	//刪除c數組中的重復元素
	for (i = 0; i < c.size(); i++)
	{
		iter = find(++(find(c.begin(), c.end(), c[i])), c.end(), c[i]);//巧妙用++，從第一個想要查找的元素開始查找，刪除後面的，保留第一個
		if (iter != c.end())
		{
			c.erase(iter);
			i--;
		}
	}
	//輸出c數組中的所有元素
	for (i = 0; i < c.size(); i++)
	{
		cout << c[i];
	}
	return 0;
}

補充：C++ STL vector容器元素的查找和搜索 find() find_if()函數的使用

看代碼吧~

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std; 
void print(const int& temp){
    cout<<temp<<endl;
}
 
int main()
{
    const int ARRAY_SIZE=8;
    int IntArray[ARRAY_SIZE]={1,2,3,4,5,6,7};
    vector<int> myvt;
    vector<int>::iterator location_index;
    for(int i=0;i<8;++i){
        myvt.push_back(IntArray[i]);
    }
    for_each(myvt.begin(),myvt.end(),print);
    location_index=find(myvt.begin(),myvt.end(),2);  //find函數
    cout<<"數字2的下標是："<<(location_index-myvt.begin())<<endl;
    location_index=find_if(myvt.begin(),myvt.end(),bind2nd(greater<int>(),5));
    cout<<"第一個大於5的數字的下標是："<<(location_index-myvt.begin())<<endl;
    return 0;
}

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方，望不吝賜教。

推薦閱讀：