被封装强迫症克小记

发表于 | 更新于

这篇的所有内容纯属一个超级蒟蒻的自言自语。 今天做一道树剖题，看完题目之后想到了一种很诡的做法：

在每条链上挂一个Treap，里面装这个链上含有的线段树的根节点。

（你笑笑说直接全局建线段树就行了，不需要每个点建一个，但我太蒟蒻，怎么研究过那种写法） 于是就很愉快地开始写 数据结构这样存储 

1
2
struct TreapNode;
struct SegNode;

然后发现，这样做，每次进行操作要传递很多可以不传递的变量，比如 

1
SegTree.Access(root,1,PathSize,Rank(pos),PathSize);

前三个都是与此次操作无关的。 写完A掉之后，感觉不爽。 于是重新设计重写。 

1
2
3
4
5
6
7
8
struct Treap;
{
	struct TreapNode;
};
struct Seg;
{
	struct SegNode;
};

发现这样做比原来的写法在实现数据结构上麻烦了不少，就比如需要四种null，重名了，只好改成nullSeg什么的。而且struct套struct写起来各种坑。 A掉之后，感觉不爽。 于是开始研究stl的写法。。发现stl_tree.h中定义的_Rb_tree是这样的 

1
2
3
4
5
struct _Rb_tree_node;
class _Rb_tree
{
    _Rb_tree_node ...;
};

感觉不错。于是写写写，写完之后，感觉好些了。 然后看到Sengxian大神的代码，发现好多namespace啊 试了试，发现namespace确实好，用着很舒服。。其中一个好就是null不会重复了。。 于是 我的数据结构 就变成了这样 

1
2
3
4
5
6
7
8
namespace Treap
{
    struct Node;
    struct Treap
    {
        Node ...;
    };
}

以后就这么写了。。。 这两天状态很差，明天一定要加油了。