模板实例化对成员函数的要求

问题的背景

假如想写一个类模板C,能够实例化此模板的类型必须具有一个名为Clone()const成员函数,此函数不带参数,返回值为指针,指向同类型的对象。
就像这样:

template<typename T>
class C
{
    // ...
};

思考的过程

我们可以在模板C中写一段代码,让它去调用函数Clone(),那么如果实例化的类型T没有这个函数的话,就不能通过编译。可是在模板类中只有被使用到的函数才会被实例化,所以我们只能去考虑一定会被实例化的函数。

  • 构造函数
  • 析构函数

我们首先就会考虑到这两个函数,然后再考虑一下,一个类可能有很多个构造函数,但是一定只会有一个析构函数,所以写在析构函数里会更划算一些。

首先就会写出这样的代码来:

template<typename T>
class C
{
pulibc:
    ~C()
    {
        // ...
        T t;
        t.Clone();
        // ...
    }
};

但是这样的实现会造成一定程度的浪费,因为不但构造了一个T的实体,还要调用T的默认构造函数,最后还要析构一次。
经过仔细的思考之后我们发现,其实我们并不需要真的去调用这个函数,只要对这样的函数提出一个要求就可以了。就会发现了下面这段更好的代码。

template<typename T>
class C
{
pulibc:
    ~C()
    {
        // ...

        T* (T::*test) () const = &T::Clone;
        test;

        // ...
    }
};

在这里只是对这样的一个函数提出的一个需求的要求,并没有实例化这个类型。

这样做的好处同时还有,会有一个漂亮很多的很明显的报错。

2015多校Contest 5. 1003. Hotaru's problem

题目大意

一个N-sequence由三个部分组成,并符合:

  1. 第一部分和第三部分相同。
  2. 第一部分和第二部分回文。

求最长的N-sequence的长度。

分析

N-sequence的特征是第一部分和第三部分相同,并且第一部分和第二部分回文。那么条件可以转化成:第一部分第二部分 回文,并且第二部分第三部分 回文。那么问题就转化成了:两个回文串的重合问题。

先用manacher求出任意一个位置作中心的最长回文串的长度。因为第一部分和第二部分组成的回文串s1一定是一个偶数长度的串,所以一定是我们添加的#位置。每个中间位置i可以覆盖左边的i-rad[i]到右边的i+rad[i]的范围。我们存下来能覆盖的最大右侧,这样我们在枚举每一个第二个端点的时候,去找到第一个端点。

在枚举到每个端点2的时候,我们可以算出来最大合法的端点1的位置,就是:i-rad[i]。那么我们就要找一个在合法范围内的最小的做端点。显然可以存下来当前所有右侧合法的端点,然后二分查找。然后就结束了。

代码

比赛的时候蠢在了好几个不一样的地方。真是…

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int maxn = 200100;
vector<int> a;
int rad[maxn];
vector<int> del[maxn];
set<int> fuck;

void manacher() {
    memset(rad, 0, sizeof(rad));
    int n = a.size();
    int i,j,k;
    i=0;
    j=1;
    while(i<n)
    {
        while(i-j>=0 && i+j<n && a[i-j]==a[i+j])
            j++;
        rad[i]=j-1;
        k=1;
        while(k<=rad[i] && rad[i]-k!=rad[i-k])
        {
            rad[i+k]=min(rad[i-k],rad[i]-k);
            k++;
        }
        i += k;
        j = max(j-k,0);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n;
        scanf("%d", &n);
        a.clear();

        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            a.push_back(-1);
            a.push_back(x);
        }
        a.push_back(-1);

        manacher();
    //    for (int i = 0; i < a.size(); i++) {
    //        printf("%2d ", i);
    //    }puts("");
    //    for (int i = 0; i < a.size(); i++) {
    //        printf("%2d ", a[i]);
    //    }puts("");
    //    for (int i = 0; i < a.size(); i++) {
    //        printf("%2d ", rad[i]);
    //    }puts("");
        int len = a.size();

        for (int i = 0; i < len; i++) {
            del[i].clear();
        }

        for (int i = 0; i < len; i++) {
            if (a[i] == -1) {
                if (i+rad[i] < len) {
                    del[i+rad[i]].push_back(i);
    //                printf("del %d at %d\n", i, i+rad[i]);
                }
            }
        }

        int ans = 0;
        fuck.clear();
        for (int i = 0; i < len; i++) {
            if (a[i] != -1) continue;

            set<int>::iterator iter = fuck.lower_bound(i-rad[i]);
            if (iter != fuck.end()) {
    //            printf("find %d at %d\n", *iter, i);
                ans = max(ans, (i-*iter) / 2);
            }

            fuck.insert(i);
            for (int j = 0; j < (int) del[i].size(); j++) {
                fuck.erase(del[i][j]);
            }
        }
        printf("Case #%d: %d\n", cas, ans * 3);
    }
    return 0;
}

/*
idx:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
raw: -1  2 -1  3 -1  4 -1  4 -1  3 -1  2 -1  2 -1  3 -1  4 -1  4 -1
rad:  0  1  0  1  0  1  6  1  0  1  0  1  8  1  0  1  0  1  2  1  0
*/

Operator new 的重载

new作为关键字是不能被重载的。当new作为关键字的时候的行为是:

  1. 调用operator new分配内存。
  2. 调用构造函数生成对象。
  3. 返回相应的指针。

new的行为是不能被改变的,但是这里的operator new的行为是可以改变的。也就是对operator new的重载。

new 运算符表达式的重载

operator new操作符可以被每个类作为成员函数重载,也可以作为全局函数重载。这里应该是推荐作为成员函数重载的。

void* operator new(size_t size) throw(std::bad_alloc);

参数是一个size_t类型,指明了要分配的内存的大小。

void* operator new(std::size_t) throw(std::bad_alloc);
void* operator delete(std::size_t) throw();

如果在构造函数执行的时候发生异常,在栈展开的过程中,要回收在第一步中operator new分配的内存的时候,会调用想对应的operator delete函数。

void* operator new[](size_t size) throw(std::bad_alloc);

用于分配数组对象内存的new操作符。如果数组的基类型没有这个成员函数的话,会调用全局的版本分配内存。

void * operator new[] (std::size_t) throw(std::bad_alloc);
void operator delete[](void*) throw();
void* operator new(size_t,void*)

带位置的new操作符(placement new)重载版本。C++标准库中已经提供了这个版本的简单实现,只是简单的返回参数指定的地址。

// Default placement versions of operator new.
inline void* operator new(std::size_t, void* __p) throw() { return __p; }
inline void* operator new[](std::size_t, void* __p) throw() { return __p; }

// Default placement versions of operator delete.
inline void  operator delete  (void*, void*) throw() { }
inline void  operator delete[](void*, void*) throw() { }
自行定制参数的operator new函数
operator new(size_,Type1, Type2, ... );

这时候就可以自定义参数以及其行为。

struct point {
    int x, y;
    point() = default;
    point(int x, int y) : x(x), y(y) {}
    void* operator new(size_t, int&cur);
} _pool[maxn];
int cur;

void* point::operator new(size_t sz, int &cur) {
    return _pool+(cur++);
}

reference:

  1. https://zh.wikipedia.org/zh/New_(C%2B%2B)

主席树

主席树我的理解是可持久化线段树的一种应用吧。本质上就是可持久化线段树,不过我们在查询的时候用到了他们之间可以相减的性质。

首先介绍一下可持久化线段树。

可持久化线段树

可持久化线段树是可持久化数据结构中的一种,主席树的实现就是利用了可持久化线段树的。

可持久化数据结构

所谓的可持久化数据结构,就是保存这个数据结构的历史版本,同时应该公用他们的公有部分来减少内存上的消耗。

可持久化线段树

在每次更新的时候,我们保存下来每次更新的历史版本,以便我们之后查阅。在主席树中我们用到的线段树是保存当前范围内位置有多少个数的。以下都用这个当例子。

下面图中点的表示:

建树

建立一颗空树,这里只要递归的建立就可以了。和普通的线段树是一样的。build(1, 5)

更新

我们这里的更新操作是不改变原有的点,对于所有的修改我们都会建立新的点出来。
insert(root, 1, 5, 3):在3位置插入了一个值。

insert(root, 1, 5, 4):在4位置插入了一个值。

我们可以看到,在修改线段树上维护的数据的时候我们都没有改变原本的点,只是建立了一个新点出来。这样我们可以放心的复用以前的点(因为他们根本就没有变过),这样来达到节省空间的目的。

查询

查询的方法和普通的线段树一样,还是根据所查信息来决定是走左孩子还有右孩子就可以了。

主席树

主席树中我们处理任意区间第K大的方法,有点像在处理任意区间和的时候我们用的求好前缀和再相减的过程。这里我们在查询的时候就是把两个线段树相减。
如果查询区间(s, t)的第K大,我们首先可以找到他们两个所对应的数字插入的时候的线段树,(我们把数组里的元素按顺序插入,并且把插入后的根保存起来。因为这些根一定都是不同的,假定我们保存在了数组T中。即当前的查询可以表示为:query(s, t, ln, rn, k)
那么如果\(T[t].left.data - T[s-1].left.data <= k\),就证明了这个第K小的数应该在左边。我们递归的处理 query(s.left, t.left, ln, mid, k),否则第K小的数就应该在右边,我们递归处理query(s.right, t.right, mid+1, rn, k-(t.left.data-s.left.data))(注意更新右侧不是第K小,应该减去左侧数字的个数。)

代码实现和例题

例题poj2104 代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;  
const int maxn = 1000100;

struct node {  
    node *ls, *rs;
    int data;
} _pool[maxn * 20], *current;


void init() {  
    current = _pool;
}

node* allocNode() {  
    return current++;
}

node* build(int ln, int rn) {  
    node* now = allocNode();
    now->data = 0;
    now->ls = NULL;
    now->rs = NULL;
    if (ln < rn) {
        int mid = (ln + rn) / 2;
        now->ls = build(ln, mid);
        now->rs = build(mid + 1, rn);
    }
    return now;
}

node* insert(node* root, int ln, int rn, int val) {  
    node* now = allocNode();
    *now = *root;
    now->data++;
    if (ln != rn) {
        int mid = (ln + rn) / 2;
        if (val <= mid) {
            now->ls= insert(now->ls, ln, mid, val);
        }
        else {
            now->rs= insert(now->rs, mid+1, rn, val);
        }
    }
    return now;
}

int query(node* s, node* t, int ln, int rn, int k) {  
    //printf(">>> [%d, %d], (%d, %d), %d\n", s-_pool, t-_pool, ln, rn, k);
    //printf("--- <%d, %d>, <%d, %d>\n", s->ls-_pool, s->rs-_pool, t->ls-_pool, t->rs-_pool);
    if (ln == rn) return ln;
    int delta = t->ls->data - s->ls->data;
    int mid = (ln + rn) / 2;
    if (delta >= k) {
        return query(s->ls, t->ls, ln, mid, k);
    }
    else {
        return query(s->rs, t->rs, mid+1, rn, k - delta);
    }
}

void treeShow(node* root) {  
    if (root != NULL) {
        printf("%d: <(%d, %d), %d>\n", root-_pool, root->ls-_pool, root->rs-_pool, root->data);
        treeShow(root->ls);
        treeShow(root->rs);
    }
}

node* T[maxn];  
int ori[maxn];  
int dis[maxn];  
int main() {  
    int n, q;
    while (scanf("%d%d", &n, &q) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &ori[i]);
            dis[i] = ori[i];
        }
        sort(dis + 1, dis + n + 1);
        int m = unique(dis + 1, dis + 1 + n) - dis - 1;
        T[0] = build(1, m);

        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(dis + 1, dis + m + 1, ori[i]) - dis;
            T[i] = insert(T[i-1], 1, m, pos);
        }
        //treeShow(T[2]);

        for (int i = 0; i < q; i++) {
            int s, t, k;
            scanf("%d%d%d", &s, &t, &k);
            printf("%d\n", dis[query(T[s-1], T[t], 1, m, k)]);
        }
    }
    return 0;
}
				<div style="clear:both;">
				</div>

UVALive 5848. Soju

题目大意

给定两个平面上的点集,求两个点集中距离最近的两个点的距离。(这里的距离说的是曼哈顿距离。)题目中保证了左边点集的点都一定在右侧的点集的左侧。也就是任意一个在左侧集合的点的横坐标都小于任意一个在右侧集合的点。

分析

题目中反复的提示了左侧的点一定在左侧。那么来分析曼哈顿距离的式子: [|x_1-x_2|+|y_1-x_2|] 其中令(x_1, y_1)是处于左侧的点的话,其中的第一项一定是小于0的,可以去掉绝对值符号。那么我们如果令我们枚举的右侧点在左侧点的下面的话,右侧的绝对值就也可以去掉了。那么式子就可以变成如下的形式: [(y_1-x_1)-(y_2-x_2)]那么这个时候只要维护后一项的值最大就好了。对于右侧点再上方的情况,类似处理。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
const int inf = INT_MAX;

struct point {
    int x, y;
    point() {}
    point(int x, int y) : x(x), y(y) {}
    void input() {
        scanf("%d%d", &x, &y);
    }
} a[maxn], b[maxn];

bool operator < (const point& a, const point& b) {
    return a.y < b.y;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            a[i].input();
        }
        int m;
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            b[i].input();
        }
        sort(a, a+n);
        sort(b, b+m);

        int ans = inf;

        for (int i = 0, j = 0, tmp = -inf; i < n; i++) {
            for (; j < m; j++) {
                if (a[i].y < b[j].y) {
                    break;
                }
                tmp = max(tmp, b[j].y - b[j].x);
            }
            ans = min(ans, a[i].y - a[i].x - tmp);
        }

        reverse(a, a+n);
        reverse(b, b+m);

        for (int i = 0, j = 0, tmp = inf; i < n; i++) {
            for (; j < m; j++) {
                if (a[i].y > b[j].y) {
                    break;
                }
                tmp = min(tmp, b[j].y + b[j].x);
            }
            ans = min(ans, tmp - a[i].x - a[i].y);
        }

        printf("%d\n", ans);
    }
    return 0;
}

Python 装饰器

给函数添加一个包装层以添加额外的处理部分,我们就可以使用装饰器这种方法。

定义一个装饰器:
import time

def timethis(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(func.__name__, end - start)
        return result
    return wrapper
使用这个装饰器
@timethis
def countdown(n):
    while n > 0:
        n -= 1

当如此编写代码的时候和单独这么写的效果是一样的:

def countdown(n):
    while n > 0:
        n -= 1
countdown = timethis(countdown)
保存函数签名等信息

但是我们像上面那么做的时候,其实是丢失了函数签名,doc等信息的,这时候可以通过对装饰器的装饰来解决这个问题。改动一下上面的代码:

import time
from functools import wraps

def timethis(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(func.__name__, end - start)
        return result
    return wrapper
对装饰器进行解包装

可以通过访问__wrapped__属性来实现对原始函数的访问。

一个可以接受参数的装饰器

其实是很简单的,在外层的函数部分接受定义装饰器时的参数就可以了。

from functools import wraps, partial
import logging

def logged(level, name=None, message=None):
    def decorator(func):
        logname = name if name else func.__module__
        log = logging.getLogger(logname)
        logmsg = message if message else func.__name__

        @wraps(func)
        def wrapper(*args, **kwargs):
            log.log(level, logmsg)
            return func(*args, **kwargs)

        return wrapper

    return decorator


@logged(logging.DEBUG)
def add(x, y):
    return x + y

logging.basicConfig(level=logging.DEBUG)
print(add(2, 3))
装饰器参数需要可以修改

还是刚才的那段代码,这次用到了另一个装饰器并且使用了nonlocal关键字来声明装饰器内部的属性。

from functools import wraps, partial
import logging

def attach_wrapper(obj, func=None):
    if func is None:
        return partial(attach_wrapper, obj)
    setattr(obj, func.__name__, func)
    return func

def logged(level, name=None, message=None):
    def decorator(func):
        logname = name if name else func.__module__
        log = logging.getLogger(logname)
        logmsg = message if message else func.__name__

        @wraps(func)
        def wrapper(*args, **kwargs):
            log.log(level, logmsg)
            return func(*args, **kwargs)

        @attach_wrapper(wrapper)
        def set_level(newlevel):
            nonlocal level
            level = newlevel

        @attach_wrapper(wrapper)
        def set_message(newmsg):
            nonlocal logmsg
            logmsg = newmsg

        return wrapper

    return decorator


@logged(logging.DEBUG)
def add(x, y):
    return x + y

logging.basicConfig(level=logging.DEBUG)
print(add(2, 3))
可选参数的装饰器

还是上面的那段代码,如果level属性也是可选的,像上面那么写我们就必须用这样的方式去使用它:

@logged()
def fuck():
    pass

但是显然这不是我所希望的,因为我们总会忘记那个空的括号。所以我们就可以改动一下:

def logged(func=None, *, level=logging.DEBUG, name=None, message=None):
    if func is None:
        return partial(logged, level=level, name=name, message=message)
    logname = name if name else func.__module__
    log = logging.getLogger(logname)
    logmsg = message if message else func.__name__

    @wraps(func)
    def wrapper(*args, **kwargs):
        log.log(level, logmsg)
        return func(*args, **kwargs)
    return wrapper

副作用是*之后的参数必须显式的给出形参的名字。

用类来实现装饰器

前面给出的都是用函数闭包来实现装饰器的例子,当然我们也可以用一个类来实现装饰器。

from functools import wraps

class A:
    def decorator1(self, func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            print("Decorate 1")
            return func(*args, **kwargs)
        return wrapper

    @classmethod
    def decorator2(cls, func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            print ('Decorator 2')
            return func(*args, **kwargs)
        return wrapper
把装饰器定义成类

这个时候要实现类的__call____get__方法。

class Profield:
    def __init__(self, func):
        wraps(func)(self)
        self.ncalls = 0

    def __call__(self, *args, **kwargs):
        self.ncalls += 1
        return self.__wrapped__(*args, **kwargs)

    def __get__(self, instance, cls):
        if instance is None:
            return self
        else:
            return types.MethodType(self, instance)

这里的__get__方法的实现一定不能忽略。


相关资料:

利用装饰器给被包装的函数添加参数
import inspect

def optional_debug(func):
    if 'debug' in inspect.getargspec(func).args:
        raise TypeError('debug argument already defined.')
    @wraps(func)
    def wrapper(*args, debug=False, **kwargs):
        if debug:
            print("fuck debug", func.__name__)
        return func(*args, **kwargs)
    return wrapper

这里的实现还检查了被包装的函数是不是已经有要包装进去的参数了来保证不会有参数名字冲突的问题。 但是这种实现不能解决函数签名的问题,在函数签名中是没有我们加入的debug这个参数的。所以我们再次修改我们的实现。

def optional_debug(func):
    if 'debug' in inspect.getargspec(func).args:
        raise TypeError('debug argument already defined.')
    @wraps(func)
    def wrapper(*args, debug=False, **kwargs):
        if debug:
            print("fuck debug", func.__name__)
        return func(*args, **kwargs)

    sig = inspect.signature(func)
    parms = list(sig, parameters.values())
    parms.append(inspect.Parameter('debug', inspect.Parameter.KEYWORD_ONLY, default=False))
    wrapper.__signature__ = sig.replace(parameters=parms)

    return wrapper
利用装饰器改变类方法的行为
def log_getattribute(cls):
    orig_getattribute = cls.__getattribute__

    def new_attribute(self, name):
        print('getting:', name)
        return orig_getattribute(self, name)

    cls.__getattribute__ = new_attribute

@log_getattribute
class A:
    def __init__(self, x):
        self.x = x
    def spam(self):
        pass
				<div style="clear:both;">
				</div>