Article

目录

C++ 的Lambda表达式

C++ 11 标准发布，各大编译器都开始支持里面的各种新特性，其中一项比较有意思的就是lambda表达式。

语法规则

C++ 11 Lambda表达式的四种声明方式

  1. \[ capture \]( params ) mutable(optional) exception attribute -> ret { body }
  2. \[ capture \]( params ) -> ret { body }
  3. \[ capture \]( params ) { body }
  4. \[ capture \]{ body }
  • capture是外部引用的参数
  • params是函数参数
  • 后面可以跟一些函数修饰符
  • ret是返回值类型，如果不指定，会推断一个类型
  • body部分是函数内容 具体用法可以参照C++文档，这里就不复述了

这四个声明式都会返回一个匿名的仿函数实例）。 这里有一个比较重要的一点，就是他是一个仿函数实例，而不是直接一个函数。

Article

今年准备安安心心写一个协程库。一方面是觉得协程挺有意思，另一方面也是因为C/C++在这方面没有一个非常权威的解决方案。 按照我自己风格还是喜欢C++，所以协程库定名为 libcopp 。 源码托管在 github: https://github.com/owent/libcopp 镜像托管 http://git.oschina.net/owent/distinctionpp

首先介绍: 什么是协程

协程(coroutine)，是一种用户态模拟线程的组件。（具体说明参见：http://zh.wikipedia.org/wiki/%E5%8D%8F%E7%A8%8B）

Article

C++11标准里有动态模板参数已经是众所周知的事儿了。但是当时还有个主流编译器还不支持。 但是现在，主要的编译器。VC(Windows),GCC(Windows,Linux),Clang(Mac,IOS)都已经支持了。所以就可以准备用于生产环境了。 type_traits没啥好说的。主要是一些静态检测。主要还是要看动态模板参数和他们两的结合使用上。 动态模版参数标准文档见: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2242.pdf 和 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2555.pdf 虽然贴出来了。估计是没人看得。所以就直接说重点。

Article

用过std和boost的function对象和bind函数的童鞋们都知道这玩意用起来腰不酸了，腿不疼了，心情也舒畅了。先上一个简单得示例：

std::string str;
std::function<bool()> func = std::bind(&std::string::at, &str);
bool is_empty = func();

但是这是怎么做到的呢？看完源码以后，你会发现这里面有着一些很巧妙的设计。

Article

/**
 * 二维ACM计算几何模板
 * 注意变量类型更改和EPS
 * #include <cmath>
 * #include <cstdio>
 * By OWenT
 */

const double eps = 1e-8;
const double pi = std::acos(-1.0);
//点
class point
{
public:
    double x, y;
    point(){};
    point(double x, double y):x(x),y(y){};

    static int xmult(const point &ps, const point &pe, const point &po)
    {
        return (ps.x - po.x) * (pe.y - po.y) - (pe.x - po.x) * (ps.y - po.y);
    }

    //相对原点的差乘结果…
Article

/**
 * 简易四则运算（栈实现）
 * #include <stack>
 * #include <cstring>
 */
std::stack<char> opr;
std::stack<double> num;
char oprPRI[256];
//初始化调用
void initCalc()
{
    //优先级设置
    char oprMap[7][2] = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}, {'(', 100}, {')', 0} };
    for(int i = 0; i < 7; i ++)
        oprPRI[oprMap[i][0]] = oprMap[i][1];
}
bool checkNum(char c)…
Article

基础函数:

// 最大公约数,欧几里得定理
int gcd(int a, int b)
{
    return b?gcd(b, a % b): a;
}
// 拓展欧几里得定理
// 求解ax + by = gcd(a,b)
int ext_gcd(int a, int b, int &x, int &y)
{
    int tmp, ret;
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    ret = ext_gcd(b, a % b, x, y);
    tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return ret;
}
//交换数值
void swap(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

/**
 * a的b次方Mod c…
Article

树状数组模块

ACM个人模板

POJ 2155 题目测试通过

/**
 * 树状数组模块
 * 下标从0开始
 */
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran…
Article

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))…
Article

/**
 * Hash模板
 * Based: 0
 * template<unsigned long _SZ,class _T, unsigned long *pFun(_T _Off)>
 * class _My_Hash_ToInt
 * 传入数据大小_SZ,传入类型_T,Hash函数
 * 传入类型_T必须重载 = 和 == 符号
 * 收录了ELFHash函数
 * 主要是为了判重的简化些的模板
 * Hash算法性能比较见 http://www.cnblogs.com/lonelycatcher/archive/2011/08/23/2150587.html
 */

const long hashsize = 51071; //Hash表大小(注意修改)
// 各种Hash算法
unsigned int SDBMHash(char *str)
{
    unsigned int hash = hashsize;

    while (*str)
    {
        //…
Article

//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
    return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
    long length = 1,lth;
    LISTYPE lR[LISMAXN];
    lR[0] = list[0];

    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int…
Article

//Prime连通路模块
#define N 1000         //最大数据规模
#define MAXNUM 3000000   //最大路径长度
typedef double PrimeType;//路径类型

PrimeType PrimeRecord[N];
PrimeType dis[N][N];
int isLined[N] = {1,0};

PrimeType GetPrimeLength(const long n)
{
    PrimeType tmpLen = MAXNUM;
    long tmpPos = 0,left = n - 1;
    PrimeType sumLen = 0;

    for(long i = 1 ; i < n ; i ++)
        PrimeRecord[i] = dis[0][i];
    while(left --)
    {
        tmpLen = MAXNUM;…
Article

//MULDATATYPE为矩阵元素类型,MAXMAT为最大矩阵大小

typedef long MULDATATYPE;
#define MAXMAT 100
#define inf 1000000000

#define fabs(x) ((x)>0?(x):-(x))
#define zero(x) (fabs(x)<1e-10)

struct mat
{
    long n,m;
    MULDATATYPE data[MAXMAT][MAXMAT];
    void operator =(const mat& a);
    mat operator +(const mat& a);
    mat operator -(const mat& a);
    //0-1邻接矩阵
    mat operator &(const mat& a);
    mat operator |(const mat& a);
};…
Article

点到直线距离

// (x0,y0)到(x1,y1)和(x2,y2)确定的直线的距离

double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2)
{
    //化为ax+by+c=0的形式
    double a = y1-y2;
    double b = x2-x1;
    double c = x1*y2-x2*y1;
    double d = (a*x0+b*y0+c)/sqrt(a*a+b*b);
    /*
    如果是线段判断垂足

    double xp = (b*b*x0-a*b*y0-a*c)/(a*a+b*b);
    double yp = (-a*b*x0+a*a*y0-b*c)/(a*a+b*b);
    double xb = (x1>x2)?x1:x2;…
Article

//n每个用例的点个数
//MAXN为最大点个数
//PTYPE为坐标值类型
#include<iostream>
#include<cmath>
using namespace std;

#define MAXN 1005
#define EPS 1e-10
typedef double PTYPE;

struct point
{
    PTYPE x,y;
};
struct node
{
    PTYPE k;
};
int cmp(const void * a, const void * b)
{
    return((*(PTYPE*)a-*(PTYPE*)b>0)?1:-1);
}
node numK[MAXN * MAXN / 2];
point pt[MAXN];
int main()
{

    int n , maxNum = 1 , tmpNum = 0;…
Article

//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
    for(int i = 0 ; i <= n ; i ++)
        DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
    DSet[id] = findP(DSet[id]);
    return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
    a = findP(a);
    b = findP(b);
    if(a > b)
        a ^= b ^= a ^= b;
    DSet[b] = a;
    return a;
}
Article

/**
 * KMP模式匹配
 * 算法复杂度O(m+n)
 * ACM 模板 
 *
 * @Author OWenT
 * @link http://www.owent.net
 */

// 最大字符串长度
const int maxLen = 10000;
// 前一个匹配位置,多次匹配注意要重新初始化
// 注：preMatch[i]表示0~preMatch[i-1]能和?~i匹配
int preMatch[maxLen]={0};

/**
 * kmp匹配算法
 * @param char[] source 查找源
 * @param char[] checked 查找目标
 * @return int 根据以下两个分支返回值分别表示不同的含义
 */
int kmp_match(char source[],char checked[]) {
    int i = 0, j = 0;
    memset(preMatch, 0, sizeof(preMatch));…