[smart pointer] [reference counter] 智能指標 引用計數

鑒於有些題目需要記憶體的限制，因此必須要考慮到記憶體的管理。
而智能指標可以幫助我們解決這個問題

在C++11，STL已經有內件shared_ptr，但是速度很慢，而大部分在比賽時會用到的只有引用計數的概念(可以參考Brain大神的blog)，因此我將引用計數(參考自 C++ Template 侯捷譯)部分特別獨立出來，做了一份模板

以下為模板:

	#ifndef REFERENCE_POINTER
	#define REFERENCE_POINTER
	template<typename T>
	struct _RefCounter{
	T data;
	int ref;
	_RefCounter(const T&d=0):data(d),ref(0){}
	};
	template<typename T>
	struct reference_pointer{
	_RefCounter<T> *p;
	T *operator->(){return &p->data;}
	T &operator*(){return p->data;}
	operator _RefCounter<T>*(){return p;}
	reference_pointer &operator=(const reference_pointer &t){
	if(p&&!--p->ref)delete p;
	p=t.p;
	p&&++p->ref;
	return *this;
	}
	reference_pointer(_RefCounter<T> *t=0):p(t){
	p&&++p->ref;
	}
	reference_pointer(const reference_pointer &t):p(t.p){
	p&&++p->ref;
	}
	~reference_pointer(){
	if(p&&!--p->ref)delete p;
	}
	};
	template<typename T>
	inline reference_pointer<T> new_reference(const T&nd){
	return reference_pointer<T>(new _RefCounter<T>(nd));
	}
	#endif

view raw reference_counting.cpp hosted with ❤ by GitHub

用法:

reference_pointer<int> a;//建立一個int的引用指標a
a = new_reference(5);//a指向新增int動態變數，其值為5
a = new_reference<int>(5);//同上，只是定義較為嚴謹
a = new_reference((int)5);//同上，只是定義較為嚴謹
reference_pointer<int> b = a;//將b指向a所指向之物

struct P{
     int a,b;
     P(int _a,int _b):a(_a),b(_b){}
}p(2,3);
reference_pointer<P> a;//建立一個P的引用指標a
c = new_reference(P(1,2));//指向新增P動態變數，其值為1,2
c = new_reference<P>(P(1,2));//同上，只是定義較為嚴謹
c = new_reference(p);//指向新增P動態變數，其值為p

其他的用法可以由下面的代碼看出來(HOJ Problem : 226 - K. CP AC代碼):

	#include<bits/stdc++.h>
	using namespace std;
	#ifndef REFERENCE_POINTER
	#define REFERENCE_POINTER
	template<typename T>
	struct _RefCounter{
	T data;
	int ref;
	_RefCounter(const T&d=0):data(d),ref(0){}
	};
	template<typename T>
	struct reference_pointer{
	_RefCounter<T> *p;
	T *operator->(){return &p->data;}
	T &operator*(){return p->data;}
	operator _RefCounter<T>*(){return p;}
	reference_pointer &operator=(const reference_pointer &t){
	if(p&&!--p->ref)delete p;
	p=t.p;
	p&&++p->ref;
	return *this;
	}
	reference_pointer(_RefCounter<T> *t=0):p(t){
	p&&++p->ref;
	}
	reference_pointer(const reference_pointer &t):p(t.p){
	p&&++p->ref;
	}
	~reference_pointer(){
	if(p&&!--p->ref)delete p;
	}
	};
	template<typename T>
	inline reference_pointer<T> new_reference(const T&nd){
	return reference_pointer<T>(new _RefCounter<T>(nd));
	}
	#endif
	struct node;
	typedef reference_pointer<node> pt;
	struct node{
	char data;
	int size;
	pt l,r;
	node(const node&t):data(t.data),size(t.size),l(t.l),r(t.r){}
	node(const char &d):data(d),size(1){}
	inline void up(){
	size=1;
	if(l)size+=l->size;
	if(r)size+=r->size;
	}
	};
	inline int size(pt &o){return o?o->size:0;}
	void split(pt o,pt &a,pt &b,int k){
	if(!o)a=b=0;
	else{
	o=new_reference(*o);
	if(k<=size(o->l)){
	b=o;
	split(o->l,a,b->l,k);
	}else{
	a=o;
	split(o->r,a->r,b,k-size(o->l)-1);
	}
	o->up();
	}
	}
	pt merge(pt a,pt b){
	if(!a||!b)return a?a:b;
	static int x;
	if(x++%(a->size+b->size)<a->size){
	a->r=merge(a->r,b);
	a->up();
	return a;
	}else{
	b->l=merge(a,b->l);
	b->up();
	return b;
	}
	}
	pt build(char *s,int l,int r){
	int mid=(l+r)>>1;
	pt k=new_reference(node(s[mid]));
	if(l<=mid-1)k->l=build(s,l,mid-1);
	if(mid+1<=r)k->r=build(s,mid+1,r);
	k->up();
	return k;
	}
	void dfs(pt&t){
	if(!t)return;
	dfs(t->l);
	putchar(t->data);
	dfs(t->r);
	}
	char s[1000005];
	pt root;
	pt a,b,c,d,e,f;
	int n,m;
	int main(){
	scanf("%d%s%d",&m,s,&n);
	root=build(s,0,strlen(s)-1);
	while(n--){
	int l,r,x;
	scanf("%d%d%d",&l,&r,&x);
	split(root,b,c,++r);
	split(b,a,b,l);
	split(root,d,e,x);
	root=merge(merge(d,b),e);
	split(root,root,f,m);
	}
	dfs(root);puts("");
	return 0;
	}

view raw reference_counting_example.cpp hosted with ❤ by GitHub

其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹