-M1's blog

Which is faster Map or Set, Count or Find?
By -M1, history, 7 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I find this phenomenon intriguing as well. My solution 296722764 passed, even though it doesn't seem significantly different from the TLE-ed ones. Btw, I used contains instead of count or find.

→ Reply
»
7 days ago, # |
← 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
  • »
    »
    7 days ago, # ^ |
      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
    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      GOING DEEPER

      find() is just implimentation of lower_bound

      → Reply
    • »
      »
      »
      7 days ago, # ^ |
        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
    • »
      »
      »
      7 days ago, # ^ |
        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
»
6 days ago, # |
← 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
  • »
    »
    6 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Maybe that's the issue, will keep this in mind in future contests. Thnx :)

    → Reply
»
6 days ago, # |
  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