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

bool operator()(int a,int b)const{
    if(x[p[a]]^x[p[b]])return x[p[a]]<x[p[b]];
    return a<b;
}

Then, it passed the test.

Thanks ConstructorU, you taught me a great lesson.