Comprobación de la existencia en std:: map-count vs find
Así que parece que hay dos métodos generalmente aceptables para determinar si existe o no 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 como que el método iterará sobre cada clave, contando un conteo total (y debido a la definición de std::map, ese conteo total siempre será 0 o 1). ¿Se garantiza que count () se" detenga " después de una coincidencia, operando con la misma complejidad que find ()?
3 answers
Dado que un mapa solo puede tener como máximo una clave, count esencialmente se detendrá 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 le importa si existe algún elemento con esta clave, 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 (tree traversal o hash table lookup), que son siempre bastante eficiente. Es solo que count tiene que continuar iterando hasta el final del rango igual, mientras que find no lo hace. Además, su código debe documentar la intención, por lo que si desea encontrar algo, use find.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-25 16:33:21
De acuerdo con el código fuente, sugiero usar find. Consulte 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 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));
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-09-15 03:06:39
Si solo desea encontrar si la clave existe o no, y no le importa el valor, es mejor usar map::count ya que devuelve solo un entero. map::find devuelve un iterador, por lo que al usar count, guardará la construcción de un iterador.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-07-12 14:24:47