PhewPhewPhew's blog

Which is faster Map or Set, Count or Find?
By PhewPhewPhew, history, 17 months ago, In English

In the recent Div4 contest problem F: My submission1 using map + .find fails on TC 25 (TLE). My submission2 using set + .find fails on TC 33 (TLE). But when I used .count with set it barely passes in C++20 (submission) but gave TLE in C++17 as well as C++23. Why is it so?

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
17 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

set is faster than map because in the implementation of these data structure in Red-black Tree, set uses only key whereas map uses both key and value pair. Both count and find has same time complexity but when used with set or map, count is faster as it directly returns true or false as only one key is present, but if used with multiset count may be slower than find if count of that particular element is high.

Edit: And abt this problem, time complexity also differs by number of time .end() iterator is called when using find and comparing it with another iterator whereas when using count, .end() iterator is not required and compared just as boolean value.

→ Reply
  • »
    »
    17 months ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    Tell me more about what you think the count() function does and how it is so much faster than find() (hint: the implementation of count is literally return find(v) == end() ? 0 : 1)

    → Reply
    • »
      »
      »
      17 months ago, hide # ^ |
       
      Vote: I like it +7 Vote: I do not like it

      GOING DEEPER

      find() is just implimentation of lower_bound

      → Reply
    • »
      »
      »
      17 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      That's what my doubt is, it makes sense that find would be better in case of multisets or vector

      → Reply
    • »
      »
      »
      17 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      As count() is implemented using find() internally, compiler optimizations make count() faster in practice. count() avoids iterator handling and simplifies the check to a boolean result, allowing compilers to optimize it more aggressively.

      → Reply
»
17 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Seems to be a matter of whether you use int or long long as well. As $$$x$$$ isn't that large, using int is enough to pass on C++17 (though still taking a whopping 3.6s). Ever since that Div1+2 problem A incident I've been pretty mindful to these type optimizations

→ Reply
»
17 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

In F .. my map solution was giving TLE , but unordered map passed with around 700ms .. (rare to see unordered_map solutions passing)

→ Reply