Überprüfung auf Existenz in std :: map - count vs find

So scheint es zwei allgemein akzeptablen Methoden der Bestimmung, ob ein Schlüssel vorhanden ist in einer std::map:

map.find(key) != map.end()
map.count(key) > 0

Ist eine effizienter als die andere? Insbesondere das Konzept der count() könnte dahingehend interpretiert, dass die Methode iteriert über alle Schlüssel, die Auszählung insgesamt Anzahl (und aufgrund der definition von std::map, dass total count immer 0 oder 1). Ist count () - garantiert auf "stop", nachdem eine übereinstimmung, die auf der gleichen Komplexität wie ein find()?

InformationsquelleAutor der Frage dolphy | 2014-08-25

  1. 38

    Da eine Karte nur maximal einen Schlüssel count im wesentlichen zu stoppen, nachdem ein element gefunden wurde. Jedoch, im Hinblick auf die Allgemeinen Behälter, wie multimaps und multimengen, find ist strikt besser, wenn Sie nur die Sorge, ob einige element mit diesem Schlüssel existiert, da kann es wirklich beenden, sobald das erste passende element gefunden wurde.

    Im Allgemeinen, sowohl count und find verwenden der container-spezifischen lookup-Methoden (tree traversal) oder hash-Tabelle-lookup), die sind immer ziemlich effizient. Es ist nur so, dass count weiter Durchlaufen, bis das Ende des equal-range, in der Erwägung, dass find nicht. Außerdem sollte Ihr code Dokuments, so dass, wenn Sie etwas finden wollen, verwenden Sie find.

    InformationsquelleAutor der Antwort Kerrek SB

  2. 9

    Entsprechend den source-code, schlage ich find. Finden Sie die Quelle code.

    In GCC, die code ist folgender (stl_map.h):

        const_iterator
    find(const key_type& __x) const
    { return _M_t.find(__x); }

    size_type                                                                              
    count(const key_type& __x) const                                                       
    { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }

    In Visual Studio auf der windows-Plattform, die code sind folgende (xtree):

        const_iterator find(const key_type& _Keyval) const
    {   //find an element in nonmutable sequence that matches _Keyval
        const_iterator _Where = lower_bound(_Keyval);
        return (_Where == end()
            || _DEBUG_LT_PRED(this->_Getcomp(),
                _Keyval, this->_Key(_Where._Mynode()))
                    ? end() : _Where);
    }

    //....

    const_iterator lower_bound(const key_type& _Keyval) const
    {   //find leftmost node not less than _Keyval in nonmutable tree
        return (const_iterator(_Lbound(_Keyval), this));
    }

    //....

    _Nodeptr _Lbound(const key_type& _Keyval) const
    {   //find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Wherenode = this->_Myhead;    //end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  //descend right subtree
            else
                {   //_Pnode not less than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode = this->_Left(_Pnode);   //descend left subtree
                }

        return (_Wherenode);    //return best remembered candidate
    }

    //..........................................
    //..........................................

    size_type count(const key_type& _Keyval) const
    {   //count all elements that match _Keyval
        _Paircc _Ans = equal_range(_Keyval);
        size_type _Num = 0;
        _Distance(_Ans.first, _Ans.second, _Num);
        return (_Num);
    }

    //....

    _Pairii equal_range(const key_type& _Keyval) const
    {   //find range equivalent to _Keyval in nonmutable tree
        return (_Eqrange(_Keyval));
    }

    //....

    _Paircc _Eqrange(const key_type& _Keyval) const
    {   //find leftmost node not less than _Keyval
        _Nodeptr _Pnode = _Root();
        _Nodeptr _Lonode = this->_Myhead;   //end() if search fails
        _Nodeptr _Hinode = this->_Myhead;   //end() if search fails

        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
                _Pnode = this->_Right(_Pnode);  //descend right subtree
            else
                {   //_Pnode not less than _Keyval, remember it
                if (this->_Isnil(_Hinode)
                        && _DEBUG_LT_PRED(this->_Getcomp(), _Keyval,
                        this->_Key(_Pnode)))
                    _Hinode = _Pnode;   //_Pnode greater, remember it
                _Lonode = _Pnode;
                _Pnode = this->_Left(_Pnode);   //descend left subtree
                }

        _Pnode = this->_Isnil(_Hinode) ? _Root()
            : this->_Left(_Hinode); //continue scan for upper bound
        while (!this->_Isnil(_Pnode))
            if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode)))
                {   //_Pnode greater than _Keyval, remember it
                _Hinode = _Pnode;
                _Pnode = this->_Left(_Pnode);   //descend left subtree
                }
            else
                _Pnode = this->_Right(_Pnode);  //descend right subtree

        const_iterator _First = const_iterator(_Lonode, this);
        const_iterator _Last = const_iterator(_Hinode, this);
        return (_Paircc(_First, _Last));
    }

    InformationsquelleAutor der Antwort Bright Chen

  3. 3

    Wenn Sie nur wollen, um herauszufinden, ob der Schlüssel vorhanden ist oder nicht, und kümmern sich nicht um den Wert, es ist besser, verwenden Sie map::count da gibt es nur eine ganze Zahl. map::find gibt einen iterator, so indem count speichern Sie den Bau von einem iterator.

    InformationsquelleAutor der Antwort Sagar Jha

Schreibe einen Kommentar