Проверка наличия в std:: map - count vs find
Таким образом, существует, по-видимому, два общеприемлемых метода определения того, существует или нет ключ в std:: map:
map.find(key) != map.end()
map.count(key) > 0
Является ли более эффективным, чем другой? В частности, понятие count() может быть истолковано как означающее, что метод будет перебирать по каждому ключу, подсчитывая общее количество (и из-за определения std:: map, что общий счет всегда будет 0 или 1). Считается ли count() "останавливаться" после матча, работая с той же сложностью, что и find()?
Ответы
Ответ 1
Так как карта может содержать не более одного ключа, count будет по существу останавливаться после того, как будет найден один элемент. Однако, с учетом более общих контейнеров, таких как мультиплексоры и мультимножества, find строго лучше, если вы заботитесь только о том, существует ли какой-либо элемент с этим ключом, поскольку он действительно может остановиться после обнаружения первого совпадающего элемента.
В общем, как count, так и find будут использовать методы поиска по конкретным контейнерам (обход дерева или поиск таблицы хэшей), которые всегда достаточно эффективны. Просто, чтобы count продолжал итерацию до конца равного диапазона, а find - нет. Кроме того, ваш код должен документировать намерение, поэтому, если вы хотите что-то найти, используйте find.
Ответ 2
В соответствии с исходным кодом я предлагаю использовать find. См. Исходный код.
В GCC код следующий (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; }
В Visual Studio на платформе Windows следующий код (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));
}
Ответ 3
Если вы просто хотите узнать, существует ли ключ или нет, и не заботятся о значении, лучше использовать map::count, поскольку он возвращает только целое число. map::find возвращает итератор, таким образом, используя count, вы сохраните конструкцию итератора.
