Hello from lk's World

18 May 2014 » Algorithms 之 heap 系列

heap 是非常基础的数据结构，姥姥书中也有很详尽的介绍。STL 中，我们可以在一段 RandomAccessIterator 上 make_heap，然后进行 pop_heap 或者 push_heap 来加入元素或者删除元素。默认的 heap 操作都是用 operator less 定义的，形成的是最大堆。

首先先来热身，看看 is_heap 以及 is_heap_until。既然 heap 的算法已经非常熟悉了，那么就先来 yy 一下怎么实现的吧。heap 可以看做数组中的二叉树，只要保证 parent 比两个 child 都大就可以了，也就是 comp(parent, child) || comp(parent, child + 1) 为 false。parent 从开头到 range / 2 就可以了，不过要注意 child + 1 这个在边界是否存在。

    _Distance
    __is_heap_until(_RandomAccessIterator __first, _Distance __n,
                    _Compare __comp)
    {
      _Distance __parent = 0;
      for (_Distance __child = 1; __child < __n; ++__child)
        {
          if (__comp(__first + __parent, __first + __child))
            return __child;
          if ((__child & 1) == 0)
            ++__parent;
        }
      return __n;
    }

16 May 2014 » Algorithms 之 sort & stable_sort

sort 应该是 <algorithm> 里面灰常喜闻乐见的东东了。 Sorting operations 除了 sort 和 stable_sort 这些之外，还有一些其他辅助设施。（以后 concept check 一律略）

先来热身的。is_sorted 和 is_sorted_until，后者是前者的一般化。

  template<typename _ForwardIterator, typename _Compare>
    _ForwardIterator
    __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
                      _Compare __comp)
    {
      if (__first == __last)
        return __last;
      _ForwardIterator __next = __first;
      for (++__next; __next != __last; __first = __next, ++__next)
        if (__comp(__next, __first))
          return __next;
      return __next;
    }

14 May 2014 » Algorithms 之 Non-modifying sequence operations

似乎有趣的东西并不多了，今天开始刷 algorithms 。先从最简单的开始，Non-modifying sequence operations，基本上都是在两个 iterator 之间做一些查找工作。

都是满满的编程练习题啊。

先看三个简单的，all_of，any_of，none_of。

  template<typename _InputIterator, typename _Predicate>
    inline bool
    all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
    { return __last == std::find_if_not(__first, __last, __pred); }

  template<typename _InputIterator, typename _Predicate>
    inline bool
    none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
    { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }

  template<typename _InputIterator, typename _Predicate>
    inline bool
    any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
    { return !std::none_of(__first, __last, __pred); }

13 May 2014 » 从 duration 看 user defined literal

C++11 引入了 user defined literal，干嘛用的呢？继续抄例子：

#include <iostream>
 
// used as conversion
constexpr long double operator"" _deg ( long double deg )
{
    return deg*3.141592/180;
}
 
// used with custom type
struct mytype
{
    mytype ( unsigned long long m):m(m){}
    unsigned long long m;
};
mytype operator"" _mytype ( unsigned long long n )
{
    return mytype(n);
}
 
int main(){
    double x = 90.0_deg;
    std::cout << std::fixed << x << '\n';
    mytype y = 123_mytype;
    std::cout << y.m << '\n';
}

12 May 2014 » 很村上喔

断断续续看完了《1Q84》，《挪威的森林》，《国境以南，太阳以西》。这是第一次看村上（我读书少。。），但是已经完完全全被吸引进去了。平淡，清新，孤独，还有天马行空的想象力。

可惜，等到回过头来想记录下来，已经有些晚了。也就是刚刚看过的《国境》记的多一些。

那是个彤云密布、天色黯淡的冬日午后，太阳光仿佛在勉强传过沉沉低垂的云层是被削成了粉末。目力所及，一切都那么呆板迟钝，没有生机。薄暮时分，房间里已经如暗黑一般。记得没有开灯。惟有取暖炉的火苗红晕晕地照出墙壁。

至今我还仍清晰记得她那伴着表情变化而细微地改变形状的薄唇，记得那眸子深处一闪一灭的隐约光亮。那光亮令我想起在细细长长的房间尽头摇曳不定的小小烛光。