c++ - from - Comprobando la existencia en std:: map-count vs. find

std:: map cplusplus

Question

Entonces parece que hay dos métodos generalmente aceptables para determinar si existe una clave en un std :: map:

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

¿Es uno más eficiente que el otro? Específicamente, el concepto de count () podría interpretarse en el sentido de que el método iterará sobre cada tecla, contabilizando un recuento total (y debido a la definición de std :: map, esa cuenta total siempre será 0 o 1). ¿Count () garantiza "detenerse" después de una coincidencia, operando con la misma complejidad que find ()?

Answer 1

Como un mapa solo puede tener como máximo una clave, el count se detendrá esencialmente después de que se haya encontrado un elemento. Sin embargo, en vista de contenedores más generales como multimaps y multisets, find es estrictamente mejor si solo te importa si algún elemento con esta clave existe, ya que realmente puede detenerse una vez que se ha encontrado el primer elemento coincidente.

En general, tanto count como find utilizarán los métodos de búsqueda específicos del contenedor (búsqueda en árbol o búsqueda en la tabla hash), que siempre son bastante eficientes. Es solo que el count tiene que continuar iterando hasta el final del rango igual, mientras que el find no lo hace. Además, su código debe documentar la intención, por lo que si desea buscar algo, use find .

Answer 2

De acuerdo con el código fuente, sugiero usar find . Ver el código fuente

En GCC, el código está siguiendo ( 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; }  

En Visual Studio en la plataforma de Windows, el código está siguiendo ( 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));
    }

Answer 3

Si solo quiere saber si la clave existe o no, y no le importa el valor, es mejor usar map::count ya que solo devuelve un número entero. map::find devuelve un iterador, por lo tanto, al usar count , guardará la construcción de un iterador.