Tech Off Post

Single Post Permalink

View Thread: std::set: count(v) vs. find(v) != end()
  • User profile image
    tobiasloew

    Hi,

    I just came across std::set's count method and was wondering, why there is no std::set-specific optimization of count (e.g. by just returning find(arg)!=end()).

    The reason for my question is that the following code:

    #include <SDKDDKVer.h>
    
    #include <stdio.h>
    #include <tchar.h>
    #include <iostream>
    #include <set>
    
    #define USE_BUILTIN_COUNT
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        int n;
        std::cin >> n;
    
        std::set<int> s;
        s.insert(n);
    #ifdef USE_BUILTIN_COUNT
        size_t cnt = s.count(4);
    #else
        size_t cnt = size_t(s.find(4) != s.end());
    #endif
        std::cout << cnt << std::endl;
        return 0;
    }
    

    generates when build with VS 2015 Update 2 x64/release/O2 

    with USE_BUILTIN_COUNT defined: 64 lines of assembly for the "count"

    without USE_BUILTIN_COUNT defined: 21 lines of assembly for the "find != end"

    In x86-builds (release, O2) it get's even worse: with USE_BUILTIN_COUNT defined, the internal std::set calls to _Eqrange and _Distance2 won't get inlined!

    Please check, if it's possible to tweek std::set's count method.

    regards

    Tobias

    PS: I haven't looked up the standard, to check if this optimization is prohibited in some way.