katukutu's blog

STL set vs map time complexity
By katukutu, history, 9 years ago, In English

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 :)

Tags stl
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I haven't had this experience. I have seen cases where multiset<something> times out while map<something,int> doesn't, but there the reason was that the coders used multiset::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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 into M[x]. That made him confident that std::set is a slow stuff and it is a bad idea to use it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      isn't lower_bound in set O(logN) ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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) -> .

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

TLE code

set<int>Set;
set<int>::iterator it;
int a[100005];
for(now=0,i=1; i<=N; i++)
{
     it=upper_bound(Set.begin(),Set.end(),a[i]);

     if(it==Set.end()){
         Set.erase(Set.begin());
     }
     else{
         Set.erase(it);
         now++;
     }
}

AC code

map<int,bool>Map;
map<int,bool>::iterator it;
int a[100005];
for(now=0,i=1; i<=N; i++)
{
      it=Map.upper_bound(a[i]);

      if(it==Map.end()){
           Map.erase(Map.begin());
      }
      else{
           Map.erase(it);
           now++;
      }
 }

I have no idea how this happened, since both are supposed to have same complexity, O(NlogN), here N<=10^5.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    :) 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 use Set.lower_bound(x)/Set.upper_bound(x) that perform a search over a binary search tree, that works obviously in .

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot! I had a wrong idea that it was O(logN).

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This fact cost me 5 TLE in the last contest. Btw Thank you for the info it is clear now.

      → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Internally map, multimap, set, and multiset 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.

→ Reply