ConstructorU taught me a lesson
Difference between en4 and en5, changed 0 character(s)
Abstract↵
------------------↵

1. Never apply a binary search on `std::list`.↵
2. If you want to make a custom `_Comp` function for `std::set` , write down as many instructions to distinguish elements in the set as possible.↵

[cut] I think it's important.↵

Detail↵
------------------↵

When I was solving one of the problems in the ConstructorU's Open Cup's Practice Round, I wrote this ↵

~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
    return x[p[a]]<x[p[b]];↵
}),idx);↵
~~~~~↵

when `lst` is a `std::list` . I will insert a permutation with a size about $2\times 10^5$ in it.↵

But after I waited for a half minute, I killed the process.↵

So I took a look in the file `stl_algobase.h` , then deep in the file `stl_iterator_base_funcs.h` , I found the function `__advance` which drives `lower_bound` and other binary-search functions designed for containers with bidirectional iterators:↵

~~~~~↵
template<typename _BidirectionalIterator, typename _Distance>↵
    inline _GLIBCXX14_CONSTEXPR void↵
    __advance(_BidirectionalIterator& __i, _Distance __n,↵
      bidirectional_iterator_tag)↵
    {↵
      // concept requirements↵
      __glibcxx_function_requires(_BidirectionalIteratorConcept<↵
  _BidirectionalIterator>)↵
      if (__n > 0)↵
        while (__n--)↵
  ++__i;↵
      else↵
        while (__n++)↵
  --__i;↵
    }↵
~~~~~↵

I was shocked because its time complexity is $O(n)$ .↵

Considered that `vector` may solve this problem but have a higher time complexity when massively insert elements in the front of it, I used `set` instead, and modified the lambda function I wrote above to the `_Comp` function of it.↵

It passed the sample, but it got a Wrong verdict.↵

When I tried to debug, I was confused when I saw that the `set` said $4=5$ . Then, I found that $x[p[4]]=x[p[5]]$ in my input.↵

So I modified the function `_Comp` a bit to this:↵

~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
    if(x[p[a]]^x[p[b]])return x[p[a]]<x[p[b]];↵
    return a<b;↵
}),idx);↵
~~~~~↵

Then, it passed the test.↵

Thanks [user:ConstructorU,2024-02-03], you taught me a great lesson.↵







History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English shiny_shine 2024-02-03 12:31:11 63
en5 English shiny_shine 2024-02-03 12:17:06 0 (published)
en4 English shiny_shine 2024-02-03 12:16:38 24 Tiny change: '.\n\n[cut]\n\nDetail' -> '.\n\n[cut] I think it's important.\n\nDetail'
en3 English shiny_shine 2024-02-03 12:16:05 50
en2 English shiny_shine 2024-02-03 12:15:28 24 Tiny change: '.\n\n[cut]\n\nWhen I' -> '.\n\n[cut] I think it's important.\n\nWhen I'
en1 English shiny_shine 2024-02-03 12:14:21 2168 Initial revision (saved to drafts)