Блог пользователя katukutu

STL set vs map time complexity
Автор katukutu, история, 9 лет назад, По-английски

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

Теги stl
  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      isn't lower_bound in set O(logN) ?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

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

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить