In general, both STL set and map has O(log(N)) complexity for insert, delete, search etc operations. But in some problems, where N<=10^5, O(NlogN) algorithms using set gives TLE, while map gets AC. Can someone please explain how map gives a better runtime than set? Thanks in advance :)
I haven't had this experience. I have seen cases where
multiset<something>
times out whilemap<something,int>
doesn't, but there the reason was that the coders usedmultiset::count
which is linear in the answer it returns.It would certainly be helpful if you could share examples of what you are talking about.
I've met a person that claimed the same thing as a topicstarter, his problem was that in some problem he used
lower_bound(S.begin(), S.end(), x)
when using std::set (that works obviously in linear time), and then he rewritten it onto std::map and changed lower-bound line intoM[x]
. That made him confident thatstd::set
is a slow stuff and it is a bad idea to use it.isn't lower_bound in set O(logN) ?
Read my comment below.
Bad guy
lower_bound(S.begin(), S.end(), x)
-> O(n) or (not sure exactly, that depends on implementation) because std::set iterators are not random-access.Good guy
S.lower_bound(x)
-> .TLE code
AC code
I have no idea how this happened, since both are supposed to have same complexity, O(NlogN), here N<=10^5.
:) That's completely the same with what I described in my comment above.
upper_bound(Set.begin(), Set.end(), x)
is a function that doesn't know anything about std::set internal structure. Set iterators are not random-access meaning that upper_bound has to perform O(n) iterator movements in order to access any position in the container. That's why you should never use lower_bound/upper_bound with std::set, but you can useSet.lower_bound(x)
/Set.upper_bound(x)
that perform a search over a binary search tree, that works obviously in .Thanks a lot! I had a wrong idea that it was O(logN).
This fact cost me 5 TLE in the last contest. Btw Thank you for the info it is clear now.
Internally
map
,multimap
,set
, andmultiset
all use the same implementation (which is a red-black tree for the STL library shipped with GNU C++). As misof suggests, most likely you're seeing a difference because you're comparing apples with oranges, i.e., map and set being used differently.