C++ 检查 std::map 中是否存在 - 计数与查找

Checking for existence in std::map - count vs find

提问by dolphy

So there seem to be two generally acceptable methods of determining whether or not a key exists in a std::map:

因此，似乎有两种普遍可接受的方法来确定 std::map 中是否存在键：

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

Is one more efficient than the other? Specifically, the concept of count() could be interpreted to mean that the method will iterate over every key, tallying a total count (and because of the definition of std::map, that total count will always be 0 or 1). Is count() guaranteed to "stop" after a match, operating at the same complexity as a find()?

一种比另一种更有效吗？具体来说，count() 的概念可以解释为意味着该方法将迭代每个键，计算总计数（并且由于 std::map 的定义，总计数将始终为 0 或 1）。count() 是否保证在匹配后“停止”，以与 find() 相同的复杂性运行？

采纳答案by Kerrek SB

Since a map can only have at most one key, countwill essentially stop after one element has been found. However, in view of more general containers such as multimaps and multisets, findis strictly better if you only care whether someelement with this key exists, since it can really stop once the first matching element has been found.

由于地图最多只能有一个键，count因此在找到一个元素后基本上会停止。但是，考虑到更通用的容器，例如 multimaps 和 multisets，find如果您只关心是否存在具有此键的某个元素，则绝对更好，因为一旦找到第一个匹配元素，它就可以真正停止。

In general, both countand findwill use the container-specific lookup methods (tree traversal or hash table lookup), which are always fairly efficient. It's just that counthas to continue iterating until the end of the equal-range, whereas finddoes not. Moreover, your code should document intent, so if you want to find something, use find.

一般来说，无论count和find作者会使用特定容器的查找方法（树遍历或哈希表查找），它总是相当有效。只是count必须继续迭代直到等距结束，而find不会。此外，您的代码应该记录意图，因此如果您想查找某些内容，请使用find.

回答by Bright Chen

According to the source code, I suggest to use find. See the source code.

根据源代码，我建议使用find. 查看源代码。

In GCC, the code is following (stl_map.h):

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

In Visual Studio on the windows platform, the code are following (xtree):

在windows平台的Visual Studio中，代码如下（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));
    }

回答by Sagar Jha

If you just want to find whether the key exists or not, and don't care about the value, it is better to use map::countas it returns only an integer. map::findreturns an iterator, thus by using count, you will save the construction of an iterator.

如果您只想查找键是否存在，而不关心值，最好使用map::count它，因为它只返回一个整数。map::find返回一个迭代器，因此通过使用count，您将节省迭代器的构造。