Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Jbi's blog

Time difference between count and find
By Jbi, history, 5 months ago, In English

Hey cf ppl,

I was just wondering why set.count() works a lot faster than using vector.find(), from personal coding experience

This question seems to have already been answered on stack overflow, but it gave a what I thought as an incorrect answer, telling me that vector.find() would run faster than set.count() because it breaks as soon as it reaches the first occurence while set.count() would continually iterate through the whole array.

Thanks

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

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

std::set::count is logarithmic in size, std::find on vector is linear in size.

https://cplusplus.com/reference/set/set/count/

https://cplusplus.com/reference/algorithm/find/

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

    Also, while std::set::count is logarithmic in size, this is not true for std::multiset::count, which is logarithmic in size and linear in number of matches.

    https://cplusplus.com/reference/set/multiset/count/

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

      Oh thats cool thanks, tho do u know why its logarithmic in size? It seems pretty counter intuitive to me.

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

        Basically, because it is written via different structure that is able to efficiently tell you whether some value is present in a set or not. (if i am not mistaken,either self balancing binary tree, heap, or black&red binary tree is used for std::set)

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

        Similar idea to why binary search is logarithmic. std::set is implemented with some sort of binary tree (usually red-black tree) that allows for logarithmic searches.

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

Because set is sorted so presence of any element (element can only occur once in a set so finding count is equivalent to finding presence of element) can be found in log(n) time

→ Reply