开发者

How to search for an element in an stl list?

Is there a find() function for l开发者_StackOverflowist as there was in vector?

Is there a way to do that in list?


You use std::find from <algorithm>, which works equally well for std::list and std::vector. std::vector does not have its own search/find function.

#include <list>
#include <algorithm>

int main()
{
    std::list<int> ilist;
    ilist.push_back(1);
    ilist.push_back(2);
    ilist.push_back(3);

    std::list<int>::iterator findIter = std::find(ilist.begin(), ilist.end(), 1);
}

Note that this works for built-in types like int as well as standard library types like std::string by default because they have operator== provided for them. If you are using using std::find on a container of a user-defined type, you should overload operator== to allow std::find to work properly - see EqualityComparable concept.


No, not directly in the std::list template itself. You can however use std::find algorithm like that:

std::list<int> my_list;
//...
int some_value = 12;
std::list<int>::iterator iter = std::find (my_list.begin(), my_list.end(), some_value);
// now variable iter either represents valid iterator pointing to the found element,
// or it will be equal to my_list.end()


Besides using std::find (from algorithm), you can also use std::find_if (which is, IMO, better than std::find), or other find algorithm from this list


#include <list>
#include <algorithm>
#include <iostream>

int main()
{
    std::list<int> myList{ 5, 19, 34, 3, 33 };
    

    auto it = std::find_if( std::begin( myList ),
                            std::end( myList ),
                            [&]( const int v ){ return 0 == ( v % 17 ); } );
        
    if ( myList.end() == it )
    {
        std::cout << "item not found" << std::endl;
    }
    else
    {
        const int pos = std::distance( myList.begin(), it ) + 1;
        std::cout << "item divisible by 17 found at position " << pos << std::endl;
    }
}


What you can do and what you should do are different matters.

If the list is very short, or you are only ever going to call find once then use the linear approach above.

However linear-search is one of the biggest evils I find in slow code, and consider using an ordered collection (set or multiset if you allow duplicates). If you need to keep a list for other reasons eg using an LRU technique or you need to maintain the insertion order or some other order, create an index for it. You can actually do that using a std::set of the list iterators (or multiset) although you need to maintain this any time your list is modified.


No, find() method is not a member of std::list. Instead, use std::find from <algorithm>

    std :: list < int > l;
    std :: list < int > :: iterator pos;

    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
    l.push_back(5);
    l.push_back(6);

    int elem = 3;   
    pos = find(l.begin() , l.end() , elem);
    if(pos != l.end() )
        std :: cout << "Element is present. "<<std :: endl;
    else
        std :: cout << "Element is not present. "<<std :: endl;
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜