随笔-103  评论-224  文章-30  trackbacks-0
 
   在开发HTTP相关程序时,经常会碰到从网络链接URL中提取协议名、服务器、路径等目标对象,如果使用C/C++字符串操作函数,那么则显得有点麻烦且代码不易维护,其实关于文本内容的解析工作,都可优先考虑使用正则表达式库来解决处理,C++方面的正则库也有很多种,如atl、pcre、boost。下面就使用boost中的regex来解析URL提取协议名、服务器、路径为目标说明其用法。

协议名
   可有可无,如果有时则后面必跟着://,如果没有,则默认为使用http协议。通常还有其它的协议如https、ssl、ftp、mailto等。因此匹配协议名的正则表达式应该是(?:(mailto|ssh|ftp|https?)://)?,注意这个表达式本身捕获了协议名,但不包括://。
   
服务器
   或是域名,如www.csdn.net;或是IP地址,如192.168.1.1,可带端口号,如192.168.1.1:8080。匹配域名的正则表达式为(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z])),表达式"(?:com|net|edu|biz|gov|org|in(?:t|fo)"匹配了com、net、edu、biz、gov、org、int、info等常见的域名,而(?-i:[a-z][a-z])匹配了国家代码,而且只允许小写为合法的,如www.richcomm.com.cn。匹配IP要尽量精确,考虑到IP每部分应为数字且范围在0-255之间,因此表达式应为(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])。注意以上域名或IP的正则式本身不捕获它们,这是为了留在后面作为整体捕获。
   端口号的正则表达式为(?::(\d{1,5}))?,这里限制了端口号为1至5位的数字,更精确的匹配如要求在某范围如[1024,65535]间则可参考以上IP正则模式。综上所得,匹配服务器的正则表达式为((?:(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))|(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])))(?::(\d{1,5}))?,这个正则式作为整体捕获了域名或IP,及端口号(若有),如www.csdn.net,则得到www.csdn.net和空(没有端口,http默认为80,https默认为443)子串;192.168.1.1:8080则得到192.168.1.1和8080子串。
   
路径
   最简单的形式为(/.*)?,更精确的形式为/[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]*(?:[.!,?]+[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]+)*。
   
   以上所有正则表达式均为ascii字符集,对于unicode字符集则在其前加L即可。
   
   为方便使用,封装成了两个自由模板函数,如下所示
 1template<typename charT>
 2inline bool boost_match(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
 3{
 4    boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags); 
 5    if(NULL==result)
 6        return boost::regex_match(text,expression);
 7    return boost::regex_match(text,*result,expression);
 8}

 9
10template<typename charT>
11inline bool boost_search(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
12{
13    boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags); 
14    if(NULL==result)
15        return boost::regex_search(text,expression);
16    return boost::regex_search(text,*result,expression);
17}
   
   测试示例如下      
 1static const string protocol = "(?:(mailto|ssh|ftp|https?)://)?";
 2static const string hostname = "(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))";
 3static const string ip = "(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])";
 4static const string port = "(?::(\\d{1,5}))?";
 5static const string path = "(/.*)?";
 6static const string pattern = protocol + "((?:" + hostname + "|" + ip + "))" + port + path;
 7
 8int _tmain(int argc, _TCHAR* argv[])
 9{
10    using namespace boost;
11
12    //形式1: 带协议名,服务器为名称,不带端口号
13    bool ret;
14    string text = "http://www.cppblog.com/qinqing1984";
15    boost::cmatch what;
16    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
17    assert(ret);
18    assert(what[1].str()=="http");
19    assert(what[2].str()=="www.cppblog.com");
20    assert(what[3].str()=="");
21    assert(what[4].str()=="/qinqing1984");
22
23    //形式2: 不带协议名,服务器为名称,带端口号
24    text = "www.cppblog.com:80/qinqing1984";
25    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
26    assert(ret);
27    assert(what[1].str()=="");
28    assert(what[2].str()=="www.cppblog.com");
29    assert(what[3].str()=="80");
30    assert(what[4].str()=="/qinqing1984");
31
32    //形式3: 不带协议名,服务器为名称,不带路径
33    text = "www.cppblog.com:80";
34    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
35    assert(ret);
36    assert(what[1].str()=="");
37    assert(what[2].str()=="www.cppblog.com");
38    assert(what[3].str()=="80");
39    assert(what[4].str()=="");
40
41    //形式4: 协议为https,服务器为IP,带端口号
42    text = "https://192.168.1.1:443/index.html";
43    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
44    assert(ret);
45    assert(what[1].str()=="https");
46    assert(what[2].str()=="192.168.1.1");
47    assert(what[3].str()=="443");
48    assert(what[4].str()=="/index.html");
49
50    //形式5: 端口超过5位数
51    text = "ftp://192.168.1.1:888888";
52    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
53    assert(!ret);
54
55    //形式6: 没有协议名
56    text = "//192.168.1.1/index.html";
57    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
58    assert(!ret);
59
60    //形式7: 没有服务器
61    text = "http:///index.html";
62    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
63    assert(!ret);
64
65    //形式8: 不合法的服务器
66    text = "cppblog/index.html";
67    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
68    assert(!ret);
69
70    return 0;
71}
   对URL的解析,因时间有限,本文所述不尽详细,只是略作分析,以点带面,更多的精确匹配则依赖于实际的应用需求。
posted @ 2011-11-27 17:22 春秋十二月 阅读(7438) | 评论 (5)编辑 收藏
     摘要:    在《基于stl序列容器实现的通用集合类》一文中,已经讲到了具体实现,近来因再次用到它又改进完善了,主要体现在以下几点:1)增加了查找操作方法,支持按值类型和谓词条件两种方式。2)增加重载了按值类型和谓词条件2种方式删除元素的方法。3)增加了2个模板参数以支持线程安全,一个是线程模型模板类,一个是互斥锁类,使用loki库来实现,因此所有方法现在都是线程安全的,当需...  阅读全文
posted @ 2011-10-21 18:43 春秋十二月 阅读(3003) | 评论 (1)编辑 收藏
     摘要:    本文讲述双端堆的5个公开泛型操作算法:make_dheap(原位构造双端堆)、push_dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证),每个算法都提供<小于运算符和仿函数比较2个版本,要注意的是比较必须是严格弱序的,即对于<版本存在a<b为真且b<...  阅读全文
posted @ 2011-10-05 13:24 春秋十二月 阅读(2519) | 评论 (1)编辑 收藏
     摘要:    在《基于双端堆实现的优先级队列(1):原理》一文中讲述了双端堆的相关原理,本文则详细讲述具体的内部实现,便于区分,内部函数名称都以双下划线作为前缀,在这里,有几个关键问题需要说明    1)怎么求一个结点的对称结点:如果完全二叉树根结点从索引1开始但不存储元素,那么最小堆根结点则在索引2,最大堆根结点则在索引3,4和5为2的左右孩...  阅读全文
posted @ 2011-10-03 17:54 春秋十二月 阅读(2053) | 评论 (1)编辑 收藏
前言
   众所周知,stl中的优先级队列是基于最大堆实现的,能够在对数时间内插入元素和获取优先级最高的元素,但如果要求在对数时间内还能获取优先级最低的元素,而不只是获取优先级最高的元素,该怎么实现呢?可以用最大堆-最小堆或双端堆数据结构来实现,最大堆-最小堆和双端堆都是支持双端优先队列的插入、删除最小元素和最大元素等操作的堆,在这些操作上,时间复杂度都是对数时间,但是双端堆的操作比最大堆-最小堆的相应操作还要快一个常数因子,而且算法更加简单,因此本文讲述选择使用双端堆实现优先级队列的原理。

定义与性质
   双端堆是一颗完全二叉树,该完全二叉树要么为空,要么满足以下性质:
 (1)根结点不包含元素
 (2)左子树是一个最小堆
 (3)右子树是一个最大堆
 (4)如果右子树不为空,则令i是其中任一结点,j是i在右子树中的对应结点,如果i在右子树中的对应结点不存在,则j为i的父结点在右子树中的对应结点,  对于结点i和j,i的关键字值小于等于j的关键字值。
   从以上性质可以推出:对于左子结中的任一结点i,设j为i的对称结点,则由最小元素到i,i到j,j到最大元素的路径上元素是非递减有序的。在双端堆上的操作算法核心就是为了保证这样的单向路径上元素必须是非递减有序的。
   例如下图所示,就是一个双端堆
操作算法
 (1)插入元素:设所插结点为i,其对称结点为j,要分2种情况 a)当i处于最小堆时,则j处于最大堆中,如果KeyValue(i)>KeyValue(j),则设置value= KeyValue(i),KeyValue(i)=KeyValue(j),并执行在最大堆中位置j处插入值value的操作;否则执行在最小堆中位置i处插入值KeyValue(i)的操作。b)当i处于最大堆时,则j处于最小堆中,如果KeyValue(i)<KeyValue(j),则设置value=KeyValue(i),KeyValue(i)=KeyVaue(j),并执行在最小堆中位置i处插入值value的操作;否则执行在最大堆中位置j处插入值KeyValue(i)的操作。

 (2)删除最小元素:首先在最小堆中执行一个向下回溯过程,这个过程执行的堆大小要比原来的堆小1,从最小元素结点开始,每次选取关键字值较小的孩子结点,并用其值更新父结点值,直到底部没有孩子结点,执行的结果是在底部某叶子结点i处形成一个空洞(形象说法,这个空洞需要后续操作来调整填补,下同),i的对称结点j在最大堆中,设最末元素结点为e,如果KeyValue(e)>KeyValue(j),则设置KeyValue(i)=KeyValue(j),并执行在最大堆中位置j处插入值KeyValue(e)的操作;否则执行在最小堆中位置i处插入值KeyValue(e)的操作。

 (3)删除最大元素:这个操作比删除最小元素要麻烦一点,和删除最小元素类似,先执行一个向下回溯过程得到空洞结点i,其对称结点为j,为了保证能满足双端堆的性质,需要考虑以下几种情况:a)j只存在一个孩子,如下图第1个所示。 b)j存在两个孩子,如下图第2个所示。 c)j不存在孩子,但存在左兄弟(可能存在孩子),如下图第3个所示。 d)j不存在孩子,但存在右兄弟,如下图最后一个所示。
令min为具有较小值的结点,max为具有较大值的结点,最末元素结点为e,value=KeyValue(e),如果j存在孩子结点,则 min为孩子中关键字值较小的结点,max为关键字值较大的结点;否则min为j和其兄弟结点中关键字值较小的结点,max为关键字值较大的结点。如果KeyValue(min)<value而且value<KeyValue(max),在这种情况下,只需调整i或其父结点、max的值即可,操作如下:如果KeyValue(i)<KeyValue(max),则设置KeyValue(parent(i))=KeyValue(max),否则设置KeyValue(i)=KeyValue(max),最后设置KeyValue(max)=value;如果KeyValue(max)<=value,在这种情况下,则执行在最大堆中位置i处插入值value的操作;如果value<=KeyVlaue(min),在这种情况下,先调整i或其父结点、max的值(见上),再执行在最小堆中位置min处插入值value的操作。

 (4)构造堆:给定一个元素大小为N的序列S,在这个序列空间上构造堆,一般有两种实现方法,一是循环N-1次,每次插入元素S[i],也就是自顶向下构建堆,时间复杂度为O(NlgN)。另一种是从最后一个内部结点N/2左右开始,执行调整堆操作,直到第一个元素,也就是自底向上构建堆,时间复杂度为O(N)。

 (5)最大堆(最小堆)插入:这是一个向上回溯过程,和单个最大堆(最小堆)操作是一样的,从底部某处开始,比较待插元素和结点关键字值大小,直到前者不大于(不小于)后者时或碰到最大堆(最小堆)顶部为止,这时就找到了插入位置,将待插元素放到这个位置即可。

   设双端堆元素个数为N,由于完全二叉树高度为O(lgN),则插入元素操作时间复杂度为O(lgN),删除最小元素和最大元素为不超过2O(lgN),实现这些操作最重要的一点就是要保证性质4,只有当性质4满足时,双端堆才有意义,才能保证获取最大元素和最小元素操作的对数时间,具体的实现详见下文。
posted @ 2011-10-03 17:53 春秋十二月 阅读(3154) | 评论 (3)编辑 收藏
     摘要: 类型定义     在多叉树中,深度遍历迭代器有只读、读写、只读反转、读写反转4种,在mtree容器中的定义如下: Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ -->1&n...  阅读全文
posted @ 2011-10-03 17:52 春秋十二月 阅读(3041) | 评论 (0)编辑 收藏
   一、default constructor---默认构造函数,亦即无参构造函数。从对象构造语义上讲,可分为以下2种:1)trivial 平凡的,可以理解为浅构造  2)notrivial 非平凡的,可以理解为深构造。当一个class没有显式地(explicitly)声明或定义任何constructor的时候,一个default constructor就会被编译器隐式地(implicitly)声明或定义出来。那么这个implicitly default constructor到底是trivial还是notrivial的呢?对于一个class,当存在以下4种情况时,其implicitly default constructor就是notrivial的。
   (1)class内含一个或多个成员对象(member object),且这些member object中至少一个存在default constructor(无论是显式的default constructor还是隐式的notrival default constructor)
   (2)class派生自一个继承串链,其中至少有一个base class存在default constructor(再次强调,无论是显式的default constructor还是隐式的notrival default constructor)
   (3)class声明一个或多个虚函数(virtual function)
   (4)class派生自一个继承串链,其中至少有一个虚基类(virtual base class),而不管这些virtual base class是否存在default constructor
   显而易见,这4种情况是正交的,当不存在以上4种情况时,其implicitly default constructor就是trivial的。只有notrivial的default constructor才会被编译器真正生成,而trivial的不会生成。

   二、copy constructor---拷贝构造函数,亦即带有当且仅有一个参数,类型为同类对象的构造函数。从对象拷贝语义上讲,可分为以下2种:1)bitwise copy 位拷贝,可以理解为浅拷贝  2)no bitwise copy 非位拷凡,可以理解为深拷贝。当一个class没有显式地声明或定义copy constructor时,一个copy constructor就会被编译器隐式地声明或定义出来。那么这个implicitly copy constructor到底是bitwise copy还是no bitwise copy的呢?对于一个class,当存在以下4种情况时,其implicitly copy constructor就是no bitwise copy的。
   (1)class内含一个或多个成员对象,且这些member object中至少一个存在copy constructor(无论是显式的copy constructor还是隐式的no bitwise copy constructor)
   (2)class派生自一个继承串链,其中至少有一个base class存在copy constructor(再次强调,无论是显式的copy constructor还是隐式的no bitwise copy constructor)
   (3)class声明一个或多个虚函数
   (4)class派生自一个继承串链,其中至少有一个虚基类,而不管这些virtual base class是否存在copy constructor
   显而易见,这4种情况是正交的,当不存在以上4种情况时,其implicitly copy constructor就是bitwise copy的。只有no bitwise copy的copy constructor才会被编译器真正生成,而bitwise copy的不会生成。

   三、对于defualt constructor,当一个class内显式地存在constructor(包括default constructor)时,编译器不会再生成它,但如果这个class满足以上4种情况至少一种时,编译器就需要负责执行相关的初始化:对于(1)要调用成员对象的default constructor;对于(2)要调用基类的default constructor;对于(3)要设定虚函数表的指针;对于(4)要设定虚基类的指针和偏移量。而这些初始化在用户代码执行前。
        
   四、对于copy constructor,当一个class内显式地存在copy constructor时,编译器不会再生成它,但如果这个class满足以上情况(3)或(和)(4)时,编译器就需要负责执行相关的拷贝:对于(3)要决定怎么设定虚函数表指针。对于(4)要决定怎么设定虚基类的指针和偏移量。同理类推,如果这个class满足情况(1)或(和)(2),而且其成员对象或基类子对象又满足情况(3)或(和)(4)时,编译器也需要负责执行相关的拷贝了。而这些拷贝在用户代码执行前。
posted @ 2011-08-31 11:40 春秋十二月 阅读(4763) | 评论 (0)编辑 收藏
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1/***************************************************************************************&...  阅读全文
posted @ 2011-08-27 15:12 春秋十二月 阅读(2529) | 评论 (0)编辑 收藏
     摘要: 类型定义    在多叉树中,叶子遍历迭代器有只读、读写、只读反转、读写反转4种,在mtree容器中的定义如下: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1  &nb...  阅读全文
posted @ 2011-08-25 10:35 春秋十二月 阅读(2057) | 评论 (0)编辑 收藏
     摘要: 类型定义    在多叉树中,兄弟遍历迭代器有只读、读写、只读反转、读写反转4种,在mtree容器中的定义如下: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->1   ...  阅读全文
posted @ 2011-08-20 21:06 春秋十二月 阅读(1650) | 评论 (0)编辑 收藏
仅列出标题
共11页: First 3 4 5 6 7 8 9 10 11