//---------------------------15/03/31----------------------------

    //lower_bound(要求有序)

    template<class ForwardIterator, class T>

    inline ForwardIterator lower_bound(ForwardIterator first,

                                       ForwardIterator last,

                                       const T& value)

    {

        return __lower_bound(first, last, value, distance_type(first),

                             iterator_category(first));

    }

    //采用二分法来寻找第一个允许插入的位置

    template<class ForwardIterator, class T, class Distance>

    ForwardIterator __lower_bound(ForwardIterator first,

                                  ForwardIterator last,

                                  const T& value, Distance*

                                  forward_iterator_tag)

    {

        Distance len = 0;

        //取到数组大小len

        distance(first, last, len);

        Distance half;

        ForwardIterator middle;

        while (len > 0)

        {

            //找到中间的位置，取”下界“，然而其实是取half＋1，因为这里是first+half

            //虽然取的是下界 比如len=3 取到half＝1， first+1 就是第2个

            half = len >> 1;

            middle = first;

            advance(middle, half);

            if(*middle < value)

            {

                first = middle;

                ++first;

                //first一开始指向 half＋1的元素，所以右边剩下的是 len－half－1

                len = len - half - 1;

            }

            else

                len = half;

        }

        return first;

    }

    //其实感觉没有必要使用两个版本，distance函数和advance函数底层就已经对迭代器进行分类运算了

    //效率上应该不会差的。

    template<class RandomAccessIterator, class T, class Distance>

    RandomAccessIterator __lower_bound(RandomAccessIterator first,

                                       RandomAccessIterator last,

                                       const T& value, Distance*,

                                       random_access_iterator_tag)

    {

        Distance len = last - first;

        Distance half;

        RandomAccessIterator middle;

        while (len > 0)

        {

            half = len >> 1;

            middle = first + half;

            if(*middle < value)

            {

                first = middle + 1;

                len = len - half - 1;

            }

            else

                len = half;

        }

        return first;

    }

    //upper_bound(要求有序)

    template<class ForwardIterator, class T>

    inline ForwardIterator upper_bound(ForwardIterator first,

                                       ForwardIterator last,

                                       const T& value)

    {

        return __upper_bound(first, last, value, distance_type(first),

                             iterator_category(first));

    }

    template<class ForwardIterator, class T, class Distance>

    ForwardIterator __upper_bound(ForwardIterator first,

                                  ForwardIterator last,

                                  const T& value, Distance*

                                  forward_iterator_tag)

    {

        Distance len = 0;

        //取到数组大小len

        distance(first, last, len);

        Distance half;

        ForwardIterator middle;

        while (len > 0)

        {

            //和lower_bound不一样，当 value 等于 middle 时是向右走的。所以指向

            //的位置的值不是value，而是第一个大于value的值

            half = len >> 1;

            middle = first;

            advance(middle, half);

            if(value < *middle)

                len = half;

            else

            {

                first = middle;

                ++first;

                len = len - half - 1;

            }

        }

        return first;

    }

    template<class RandomAccessIterator, class T, class Distance>

    RandomAccessIterator __upper_bound(RandomAccessIterator first,

                                       RandomAccessIterator last,

                                       const T& value, Distance*,

                                       random_access_iterator_tag)

    {

        Distance len = last - first;

        Distance half;

        RandomAccessIterator middle;

        while (len > 0)

        {

            half = len >> 1;

            middle = first + half;

            if(value < *middle)

                len = half;

            else

            {

                first = middle+1;

                len = len -half -1;

            }

        }

        return first;

    }

    //binary_search(要求有序)

    template<class ForwardIterator, class T>

    bool binary_search(ForwardIterator first, ForwardIterator last,

                       const T& value)

    {

        ForwardIterator i =lower_bound(first, last, value);

        return i != last && !(value < *i);

        //如果不存在，使用lower_bound获得的*i > value;所以如果value < *i说明没找到

    }

    template<class ForwardIterator, class T, class Compare>

    bool binary_search(ForwardIterator first, ForwardIterator last,

                       const T& value, Compare comp)

    {

        ForwardIterator i = lower_bound(first, last, value, comp);

        return i != last && !comp(value, *i);

    }

    //next_permutation

    /*

下一个排列组合：

abc，acb，bac，bca，cab，cba。依次排序，前面的元素最迟改变，

        把后面的都排序一遍，当前面的元素改变时，最后的元素要依次排序

acbd的 b<d，所以固定前面元素，得到acdb，再下一个 d>b c < d所以可以让c 变成d 得到adbc

*/

    template<class BidirectionalIterator>

    bool next_permutation(BidirectionalIterator first,

                          BidirectionalIterator last)

    {

        if(first == last)

            return false;

        BidirectionalIterator i = first;

        ++i;

        if(i == last)

            return false;

        //区间没有元素和只有一个元素都返回false；

        i = last;

        -- i;

        //i＝最后一个元素

        for(;;)

        {

            //ii成了最后一个元素

            BidirectionalIterator ii = i;

            //i成了最后一个元素的前驱

            --i;

            //只要不是成倒序的就可以找到 *i < *ii，如果是倒序的说明没有下一个排列组合了

            if(*i < *ii)

            {

                /* 

现在情况是 i d c... j 首先 d > c >... > j

                    i < d 。因为后面都是倒序的，我们要找到一个比i大一阶的数填到i的位置。

所以while(!(*i < *--j)只要j小于等于i就左走，找到一个大于i的就可以把

                    这个数放入i的位置，把i放入j的位置。i放到j的位置。d开始到末尾的序列还是倒序的

所以要reverse( d c ... last)d就是ii在的位置

*/

                BidirectionalIterator j =last;

                while(!(*i < *--j));

                iter_swap(i, j);

                reverse(ii, last);

                return true;

            }

            if(i == first)

            {

                //整个序列时倒序的，直接把它变成正序就好了。并要返回false

                reverse(first, last);

                return false;

            }

        }

    }

    //prev_permutation

    template<class BidirectionalIterator>

    bool prev_permutation(BidirectionalIterator first,

                          BidirectionalIterator last)

    {

        if(first == last)

            return false;

        BidirectionalIterator i = first;

        ++i;

        if(i == last)

            return false;

        i = last;

        --i;

        //和next操作刚好相反，先找到一个数比他后驱大，再找到比他小一阶的数交换，之后反转

        for(;;)

        {

            BidirectionalIterator ii = i;

            --i;

            if(*ii < *i)

            {

                BidirectionalIterator j =last;

                while(!(*--j < *i));

                iter_swap(i, j);

                reverse(ii, last);

                return true;

            }

            if(i == first)

            {

                reverse(first, last);

                return false;

            }

        }

    }

    //random_shuffle

    //对区间[first,last)随机产生一个排列

    template<class RandomAccessIterator>

    inline void random_shuffle(RandomAccessIterator first,

                               RandomAccessIterator last)

    {

        __random_shuffle(first, last, distance_type(first));

    }

    template<class RandomAccessIterator, class Distance>

    void __random_shuffle(RandomAccessIterator first,

                          RandomAccessIterator last,

                          Distance*)

    {

        if(first == last)

            return;

        for(RandomAccessIterator i =first + 1; i != last; ++i)

#ifdef __STL_NO_DRAND48

            iter_swap(i, first + Distance(rand()%((i - first) + 1)));

#else

        iter_swap(i, first + Distance(lrand48() % ((i - first) + 1)));

#endif

    }

    template<class RandomAccessIterator, class RandomNumberGenerator>

    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,

                        RandomNumberGenerator& rand)

    {

        if(first == last)

            return;

        for(RandomAccessIterator i = first + 1; i != last; ++i)

            iter_swap(i, first + rand((i - first) + 1));

    }

    //partial_sort

    //基于堆来对前面部分数据进行排序

    template<class RandomAccessIterator>

    inline void partial_sort(RandomAccessIterator first,

                             RandomAccessIterator middle,

                             RandomAccessIterator last)

    {

        __partial_sort(first, middle, last, value_type(first));

    }

    template<class RandomAccessIterator, class T>

    void __partial_sort(RandomAccessIterator first,

                        RandomAccessIterator middle,

                        RandomAccessIterator last,T*)

    {

        make_heap(first, middle);

        for(RandomAccessIterator i = middle; i < last; ++i)

        {

            if(*i < *first)

                __pop_heap(first, middle, i, T(*i), distance_type(first));

            sort_heap(first, middle);

        }

    }

    //sort

    //Insetion Sort

    template<class RandomAccessIterator>

    void __insertion_sort(RandomAccessIterator first,

                          RandomAccessIterator last)

    {

        if(first == last)

            return ;

        for(RandomAccessIterator i =first + 1; i != last; ++i)

            __linear_insert(first, i,value_type(first));

    }

    template<class RandomAccessIterator, class T>

    inline void __linear_insert(RandomAccessIterator first,

                                RandomAccessIterator last, T*)

    {

        T value = *last;

        //确保第一个元素是最小的

        if(value < *first)

        {

            copy_backward(first, last, last + 1);

            *first = value;

        }

        else

            __unguarded_linear_insert(last, value);

    }

    template<class RandomAccessIterator, class T>

    void __unguarded_linear_insert(RandomAccessIterator last, T value)

    {

        //插入排序，从尾部开始比较，原因是这样正好可以边比较边把元素后移，

        //不需要找到位置然后都后移一次。

        RandomAccessIterator next = last;

        --next;

        //不用判断越界，前面已经保证头部是最小的了

        while (value < *next)

        {

            *last = *next;

            last = next;

            --next;

        }

        *last = value;

    }

    //取中间值

    template<class T>

    inline const T& __median(const T& a, const T& b, const T& c)

    {

        if(a < b)

            if(b < c)

                return b;   //a < b < c

            else if(a < c)

                return c;   //a < b, b >= c, a<c

            else

                return a;

        else if(a < c)      //c > a >=b

            return a;

        else if(b < c)      // a >=b, a <= c, b < c

            return c;

        else

            return b;

    }

    //很正常的快排划分步骤最后得到的结果是 first后面包括first的值是大于等于pivot值的

    //first前面的值是小于pivot值的

    template<class RandomAccessIterator, class T>

    RandomAccessIterator __unguarded_partition(RandomAccessIterator first,

                                               RandomAccessIterator last,

                                               T pivot)

    {

        while (true)

        {

            while (*first < pivot)

                ++first;

            --last;

            while(pivot < *last)

                --last;

            if(!(first < last))

                return first;

            iter_swap(first, last);

            ++first;

        }

    }

    //真正的sort

    template<class RandomAccessIterator>

    inline void sort(RandomAccessIterator first,

                     RandomAccessIterator last)

    {

        if(first != last)

        {

            __introsort_loop(first, last, value_type(first), __lg(last - first)*2);

            __final_insertion_sort(first, last);

        }

    }

    template<class Size>

    inline Size __lg(Size n)

    {

        Size k;

        for(k = 0; n > 1; n >>= 1)

            ++k;

        return k;

    }

    template<class RandomAccessIterator, class T, class Size>

    void __introsort_loop(RandomAccessIterator first,

                          RandomAccessIterator last, T*,

                          Size depth_limit)

    {

        //__stl_treshold 是全局常数 为const int 16

        while (last - first > __stl_threshold)

        {

            if (depth_limit == 0)

            {

                //如果调用深度到达限制就改调用堆排序

                partial_sort(first, last, last);

                return;

            }

            //深度减一

            --depth_limit;

            //调用一次划分返回 关键元素的迭代器

            RandomAccessIterator cur = __unguarded_partition(

                first, last, T(__median(*first,

                                        *(first + (last - first) / 2),

                                        *(last - 1))));

            //对右边进行迭代

            __introsort_loop(cur, last, value_type(first), depth_limit);

            last = cur;

        }

    }

    template<class RandomAccessIterator>

    void __final_insertion_sort(RandomAccessIterator first,

                                RandomAccessIterator last)

    {

        if (last - first > __stl_threshold)

        {

            __insertion_sort(first, first + __stl_threshold);

            __unguarded_insertion_sort(first + __stl_threshold, last);

        }

        else

            __insertion_sort(first, last);

    }

    template<class RandomAccessIterator>

    inline void  __unguarded_insertion_sort(RandomAccessIterator first,

                                             RandomAccessIterator last)

    {

        __unguarded_insertion_sort_aux(first, last, value_type(first));

    }

    template<class RandomAccessIterator, class T>

    void __unguarded_insertion_sort_aux(RandomAccessIterator first,

                                        RandomAccessIterator last,

                                        T*)

    {

        for(RandomAccessIterator i = first; i != last; ++i)

            __unguarded_linear_insert(i, T(*i));

    }

    /*

        sort总结：先采用快排，有两种情况产生：

        1>深度没有超出极限，会诞生一个个区间，每个区间大小 小于等于__stl_threshold(默认为16)，

        然后对前16个采用插入排序，需要判断尾元素是否小于first元素。这次调用完就确保first是最小的

然后再调用__unguarded_linear_sort就可以少一个判断，也就可以从first + __stl_threshold

的地方进行开始调用__unguared_linear_sort，插入位置会一直往左，有可能会越过first + __stl_threshold

的位置。

(ps:一开始我想不明白的一点是，如果先对前16个元素调用一次__unguarded_linear_insert，那如果当初划分时

        前面13个(只要小于16就行)是一个区间，那不是会把后面的3个元素牵扯进来，如果后面的3个元素不是最小的三个

那排序不就失败了，我当时想的是final sort那调用__unguarded_linear_insert(first +__stl_threshold, last)

会以first +__stl_threshold为first区间，对之后的所有元素进行排序，会造成一个问题，前16个中有比后面

        大的元素。后来才发现sgi的奇妙设计，那个while (value < *next),并没有越界判断，所以会一直往左搜索。)

        2>迭代深度超出限制，会对之后迭代的区间进行堆排序，这时剩下的区间就是不确定的，有已经排序好的(深度超出限制)，

        也有没排序的(快排迭代达到16个元素的)，再次调用插入排序，对所有区间整理一遍。

*/

    //equal_range(要求有序)

    //返回由 等于传入值 的元素 组成的区间

    template<class ForwardIterator, class T>

    inline pair<ForwardIterator, ForwardIterator>

    equal_range(ForwardIterator first, ForwardIterator last,

                const T& value)

    {

        return __equal_range(first, last, value, distance_type(first),

                             iterator_category(first));

    }

    template<class RandomAccessIterator, class T, class Distance>

    pair<RandomAccessIterator, RandomAccessIterator>

    __equal_range(RandomAccessIterator first, RandomAccessIterator last,

                  const T& value, Distance*, random_access_iterator_tag)

    {

        Distance len = last - first;

        Distance half;

        RandomAccessIterator middle, left, right;

        while (len > 0)

        {

            half = len >> 1;

            middle = first + half;

            if(*middle < value)

            {

                first = middle + 1;

                len = len - half -1;

            }

            else if(value < *middle)

                len = half;

            else

            {

                left = lower_bound(first, middle, value);

                right = upper_bound(++middle, first + len, value);

                return pair<RandomAccessIterator, RandomAccessIterator>(left, right);

            }

            //因为lower_bound和upper_bound都会调用同样的步骤直到相等。

        }

        return pair<RandomAccessIterator, RandomAccessIterator>(first, first);

        //在没有value值的情况下，返回一个区间[first,first)也就是first＝last的情况，这样可以表示

        //没有相应元素。

    }

    template<class ForwardIterator, class T, class Distance>

    pair<ForwardIterator, ForwardIterator>

    __equal_range(ForwardIterator first, ForwardIterator last,

                  const T& value, Distance*, forward_iterator_tag)

    {

        Distance len = last - first;

        Distance half;

        ForwardIterator middle, left, right;

        while (len > 0)

        {

            half = len >> 1;

            middle = first;

            advance(middle, half);

            if(*middle < value)

            {

                first = middle;

                ++first;

                len = len - half -1;

            }

            else if(value < *middle)

                len = half;

            else

            {

                left = lower_bound(first, middle, value);

                advance(first, len);

                right = upper_bound(++middle, first, value);

                return pair<ForwardIterator, ForwardIterator>(left, right);

            }

        }

        return pair<ForwardIterator, ForwardIterator>(first, first);

    }