template<typename _RandomAccessIterator, typename _Compare>
    inline void
    nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
        _RandomAccessIterator __last, _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                  _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
        typename iterator_traits<_RandomAccessIterator>::value_type,
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __nth);
      __glibcxx_requires_valid_range(__nth, __last);

      if (__first == __last || __nth == __last)
    return;

      std::__introselect(__first, __nth, __last,
             std::__lg(__last - __first) * 2,
             __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    void
    __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
          _RandomAccessIterator __last, _Size __depth_limit,
          _Compare __comp)
    {
      while (__last - __first > 3)
    {
      if (__depth_limit == 0)
        {
          std::__heap_select(__first, __nth + 1, __last, __comp);
          // Place the nth largest element in its final position.
          std::iter_swap(__first, __nth);
          return;
        }
      --__depth_limit;                                               
      _RandomAccessIterator __cut =      
        std::__unguarded_partition_pivot(__first, __last, __comp); //这里函数返回的是分割后右段的第一个元素。后面会详细讲解一下这个的功能
      if (__cut <= __nth)  //如果右段起点小于等于nth 
        __first = __cut;   //进入右段，对右段进行下次的分割
      else
        __last = __cut;
    }
      std::__insertion_sort(__first, __last, __comp);
    }

 template<typename _RandomAccessIterator, typename _Compare>
    inline _RandomAccessIterator
    __unguarded_partition_pivot(_RandomAccessIterator __first,
                _RandomAccessIterator __last, _Compare __comp)
    {
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;  
      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,    //对first last mid排序找到中位值
                  __comp);                                                    //这里的中位值即下面的pivot点
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);  //这里即实现了对于类似快排若左边大于pivot则与右边小于pivot的交换
    }                                                                           //并返回的是右端第一个