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
std::set::countis logarithmic in size,std::findon vector is linear in size.https://cplusplus.com/reference/set/set/count/
https://cplusplus.com/reference/algorithm/find/
Also, while
std::set::countis logarithmic in size, this is not true forstd::multiset::count, which is logarithmic in size and linear in number of matches.https://cplusplus.com/reference/set/multiset/count/
Oh thats cool thanks, tho do u know why its logarithmic in size? It seems pretty counter intuitive to me.
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)
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.
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