STL庫中find函數(shù)

jtll521 2011-12-21

展開全文

接觸STL不多，但每當寫程序的時候,，會先想到用它,，還算個好習慣吧，畢竟自己寫的鏈表之類的沒那么好,。

如何使用STL進行查找,？通用算法find()和find_if()可以做這些。就象for_each(), count(), count_if() 一樣,，這些算法也使用iterator范圍,，這個范圍指出一個list或任意其他容器中的一部分來處理。通常首iterator指著開始的位置,，次iterator指著停止處理的地方,。由次iterator指出的元素不被處理。
這是find()如何工作：

/*
|| How to find things in an STL list
*/
#include <string>
#include <list>
#include <algorithm>

int main (void) {
    list<string> Fruit;
    list<string>::iterator FruitIterator;

    Fruit.push_back("Apple");
    Fruit.push_back("Pineapple");
    Fruit.push_back("Star Apple");

    FruitIterator = find (Fruit.begin(), Fruit.end(), "Pineapple");

    if (FruitIterator == Fruit.end()) {
        cout << "Fruit not found in list" << endl;
    }
    else {
        cout << *FruitIterator << endl;
    }
}

輸出是：

Pineapple

如果沒有找到指出的對象,，就會返回Fruit.end()的值,，要是找到了就返回一個指著找到的對象的iterator。

/* 值得注意的是,，這里find函數(shù)的最后一個參數(shù),，我認為需要是簡單簡單類型的內(nèi)容，或者是缺醒類型，如string, int, char, double, float等,，如果你想用一個自定義類型的數(shù)據(jù)作為查找依據(jù)則會出錯,。

如，有這樣的數(shù)據(jù)結(jié)構(gòu)：

struct MyType

{

int a,b;

}

MyType* mt;

mt = new MyType;

mt->a = 1;

mt->b = 2;

list<MyType> mList;

find(mList.begin(), mList.end(), *mt);

這里find函數(shù)是不能完成查詢的,，最簡單的原因就是它無法知道通過對比MyType的哪項完成查詢,。

所以，在這樣的情況下有兩種選擇,，一種是寫一個查找條件函數(shù),，利用find_if()，另一種就是自己寫查詢函數(shù),。當然推薦第一種,。*/

--------------------------------------------------------------------------------

使用STL通用算法find_if()在list中搜索對象

這是find()的一個更強大的版本。這個例子演示了find_if(),，它接收一個函數(shù)對象的參數(shù)作為參數(shù),，并使用它來做更復雜的評價對象是否和給出的查找條件相付。
假設我們的list中有一些按年代排列的包含了事件和日期的記錄,。我們希望找出發(fā)生在1997年的事件。

/*
|| How to find things in an STL list MkII
*/
#include <string>
#include <list>
#include <algorithm>

class EventIsIn1997 {
public:
    bool operator () (string& EventRecord) {
        // year field is at position 12 for 4 characters in EventRecord
        return EventRecord.substr(12,4)=="1997";
    }
};

int main (void) {
    list<string> Events;

    // string positions 0123456789012345678901234567890123456789012345
    Events.push_back("07 January 1995 Draft plan of house prepared");
    Events.push_back("07 February 1996 Detailed plan of house prepared");
    Events.push_back("10 January 1997 Client agrees to job");
    Events.push_back("15 January 1997 Builder starts work on bedroom");
    Events.push_back("30 April 1997 Builder finishes work");

    list<string>::iterator EventIterator = find_if (Events.begin(), Events.end(), EventIsIn1997());

    // find_if completes the first time EventIsIn1997()() returns true
    // for any object. It returns an iterator to that object which we
    // can dereference to get the object, or if EventIsIn1997()() never
    // returned true, find_if returns end()
    if (EventIterator==Events.end()) {
        cout << "Event not found in list" << endl;
    }
    else {
        cout << *EventIterator << endl;
    }
}

這是程序的輸出：

10 January 1997 Client agrees to job

--------------------------------------------------------------------------------

使用STL通用算法search在list中找一個序列
一些字符在STL容器中很好處理,，讓我們看一看一個難處理的字符序列,。我們將定義一個list來放字符。
list<char> Characters;

現(xiàn)在我們有了一個字符序列,，它不用任何幫助就知道然后管理內(nèi)存,。它知道它是從哪里開始、到哪里結(jié)束,。它非常有用,。我不知道我是否說過以null結(jié)尾的字符數(shù)組。

讓我們加入一些我們喜歡的字符到這個list中：

Characters.push_back('\0');
Characters.push_back('\0');
Characters.push_back('1');
Characters.push_back('2');

我們將得到多少個空字符呢,？

int NumberOfNullCharacters(0);
count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters);
cout << "We have " << NumberOfNullCharacters << endl;
讓我們找字符'1'

list<char>::iterator Iter;
Iter = find(Characters.begin(), Characters.end(), '1');
cout << "We found " << *Iter << endl;
這個例子演示了STL容器允許你以更標準的方法來處理空字符?，F(xiàn)在讓我們用STL的search算法來搜索容器中的兩個null。
就象你猜的一樣,，STL通用算法search()用來搜索一個容器,，但是是搜索一個元素串，不象find()和find_if() 只搜索單個的元素,。

/*
|| How to use the search algorithm in an STL list
*/
#include <string>
#include <list>
#include <algorithm>

int main ( void){

    list<char> TargetCharacters;
    list<char> ListOfCharacters;

    TargetCharacters.push_back('\0');
    TargetCharacters.push_back('\0');

    ListOfCharacters.push_back('1');
    ListOfCharacters.push_back('2');
    ListOfCharacters.push_back('\0');
    ListOfCharacters.push_back('\0');

    list<char>::iterator PositionOfNulls = search(ListOfCharacters.begin(), ListOfCharacters.end(), TargetCharacters.begin(), TargetCharacters.end());

    if (PositionOfNulls!=ListOfCharacters.end())
        cout << "We found the nulls" << endl;
}

The output of the program will be 這是程序的輸出：

We found the nulls

search算法在一個序列中找另一個序列的第一次出現(xiàn)的位置,。在這個例子里我們在ListOfCharacters中找TargetCharacters這個序列的第一次出現(xiàn)，TargetCharacters是包含兩個null字符的序列,。
search的參數(shù)是兩個指著查找目標的iterator和兩個指著搜索范圍的iterators,。因此我們我們在整個的ListOfCharacters的范圍內(nèi)查找TargetCharacters這個list的整個序列。

如果TargetCharacters被發(fā)現(xiàn),，search就會返回一個指著ListOfCharacters中序列匹配的第一個字符的iterator,。如果沒有找到匹配項,，search返回ListOfCharacters.end()的值。

用C++的stl庫,，相信大家都有用vector的經(jīng)歷,，畢竟vector支持直接下標方式取數(shù)據(jù)的確方便很多。

但是vector默認是不提供find方法的,，所以我們在查找的時候,，通常這樣寫代碼：

vector<int> vec;
for(unsigned int i = 0;i<vec.size();++i)
{
    if(vec[i]==xxx)
    {
        break;
    }
}

并不是說提供不了，而是stl庫中實際上已經(jīng)有通用的find函數(shù)（不止find……）

可以看一下下面的代碼：

int main(int argc,char* argv[])
{
    vector<int> vec;
    vec.push_back(123);
    vec.push_back(456);
    vector<int>::iterator findit = find(vec.begin(),vec.end(),123);
    //vector<int>::iterator findit = find(vec.begin(),vec.end(),111);
    if(findit==vec.end())
    {
        printf("no find\n");
    }
    else
    {
        printf("find[%d]\n",*findit);
    }
    return 0;
}

這樣的寫法會不會簡單很多呢,？
需要說明的是,，雖然這個通用的find方法也是可以用在map，set等上面的,，但是效率會比容器內(nèi)部的find方法慢很多,，所以，除非容器實在是沒有提供find方法,，否則還是建議不要用公共的這一種,。

另外，作為題外話,，我們需要注意一下vector的刪除(erase)操作,。由于vector需要能以下標方式取數(shù)據(jù)，所以必須時刻保證連續(xù)的存儲空間,，對應于實現(xiàn)上,，即，當刪除vector中間的一個成員時,，這個成員后面的所有成員,，會以原順序向前全部拷貝過來。有興趣的朋友,，可以用這個例子測試一下,。
這里起碼告訴了我們兩件事：

1.vector中一個成員被刪除，會導致后面的成員進行copy和析構(gòu)操作,。
2.vector不適合做有大量插入刪除操作的容器,，因為拷貝內(nèi)存本身浪費很大

OK，到此為止啦~