Wie kann man nach einem Element in einer stl-Liste suchen?

Question

Gibt es eine find() Funktion für Listen wie bei Vektoren?

Gibt es eine Möglichkeit, dies in der Liste zu tun?

Answer 1

Sie verwenden std::find de <algorithm> , die ebenso gut funktioniert für std::list y std::vector . std::vector hat keine eigene Such-/Findfunktion.

#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);
}

Beachten Sie, dass dies auch für eingebaute Typen wie int sowie Standardbibliothekstypen wie std::string standardmäßig, denn sie haben operator== für sie vorgesehen. Wenn Sie Folgendes verwenden std::find auf einen Container eines benutzerdefinierten Typs, sollten Sie die operator== zu ermöglichen std::find richtig zu funktionieren: EqualityComparable Konzept

Answer 2

Nein, nicht direkt in der std::list Vorlage selbst. Sie können jedoch std::find einen solchen Algorithmus:

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()

Answer 3

Neben der Verwendung von std::find (aus dem Algorithmus), können Sie auch std::find_if (das IMO besser ist als std::find) oder einen anderen Suchalgorithmus aus diese Liste

---

#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;
    }
}

Answer 4

Was Sie tun können und was Sie tun sollten, sind unterschiedliche Dinge.

Wenn die Liste sehr kurz ist oder Sie die Suche nur einmal aufrufen, verwenden Sie den oben beschriebenen linearen Ansatz.

Allerdings ist die lineare Suche eines der größten Übel, die ich in langsamem Code finde, und erwägen Sie die Verwendung einer geordneten Sammlung (Set oder Multiset, wenn Sie Duplikate zulassen). Wenn Sie eine Liste aus anderen Gründen aufbewahren müssen, z. B. mit einer LRU-Technik, oder Sie müssen die Einfügereihenfolge oder eine andere Reihenfolge beibehalten, erstellen Sie einen Index dafür. Sie können dazu ein std::set der Listen-Iteratoren (oder ein multiset) verwenden, obwohl Sie dieses jedes Mal pflegen müssen, wenn Ihre Liste geändert wird.

Answer 5

Nein, die find()-Methode ist kein Mitglied von std::list . Verwenden Sie stattdessen std::find de <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;