C++博客-首页原创精华区

实现C++远程调用类的操作。

陈梓瀚(vczh) — Sat, 04 Jul 2009 02:07:00 GMT

摘要: 这次展示如何将一个服务器端的C++类让客户端调用。使用早上刚刚开发完的工具，用户可以不用处理任何传输过程中的连接和编码解码等操作。这次实现一个四则运算的语法分析器，客户端发送表达式，服务器端传回语法树（继承树那个模型），客户端将语法树传回去，服务器端传回运算结果。阅读全文

陈梓瀚(vczh) 2009-07-04 10:07 发表评论

mktags0.3版本发布--支持指定某个目录的搜索深度

那谁 — Thu, 02 Jul 2009 11:51:00 GMT

摘要: 阅读全文

那谁 2009-07-02 19:51 发表评论

基类角色之对象管理器

李现民 — Thu, 02 Jul 2009 04:49:00 GMT

基类角色之对象管理器

版本：0.1

最后修改：2009-07-02

撰写：李现民

问题描述

C++程序设计中，保存一个生命周期不是由类对象自己维护的其它对象的指针通常是个坏主意，因为程序逻辑很难判断在使用该指针的时刻其所指对象是否已经被销毁。这种应用需求很常见，例如在网游设计中，由于华丽的装备加载需要进行大量硬盘I/O，因此加载过程通常由一个独立的加载线程执行，由于在装备加载完成的时刻该玩家很可能已经下线，因此加载线程就需要能够去判断此时玩家对象是否仍然有效。

为了解决该问题，通常会设计一个PlayerManager类用于跟踪管理当前所有的玩家对象，而加载线程通过提供玩家id以确认该玩家对象仍然存在。此种设计方案需要一个独立的PlayerManager类，并提供一个全局的PlayerManager类对象以跟踪当前的所有玩家对象。

出于代码复用的目的，我希望实现一个通用基类解决此类问题。该基类需要为子类对象至少提供以下几方面的能力：

为所有的对象分配一个全局唯一的index，通过该index能够（尽可能快的）获取到拥有该index的类对象（或NULL）；
自动跟踪类对象的生成与销毁，不需要手工编写额外代码；
实现迭代器，提供遍历当前所有有效对象的能力；
提供“移除”接口，使得对象可以主动要求放弃被对象管理器跟踪；
各子类实现拥有完全独立的管理器逻辑；

解决方案

将实现代码保存为objectman.hpp，内容如下：

/********************************************************************
created:    2009-06-29
author:    lixianmin

purpose:    base class for object manager
Copyright (C) 2009 - All Rights Reserved
*********************************************************************/
#ifndef _LIB_OBJECT_MAN_HPP_INCLUDED_
#define _LIB_OBJECT_MAN_HPP_INCLUDED_
#include <cassert>
#include <map>

namespace lib
{
    template<typename T>
    class objectman
    {
    public:
        typedef int index_t;                                // 索引类型
        typedef std::map<index_t, T*>   object_map;         // 容器类型

        enum { INVAID_INDEX= 0};                          // 无效索引

    public:
        // 迭代器
        class iterator
        {
        public:
            iterator(void): _iter(_mObjects.begin()){}                // 构造函数
            bool has_next(void) const { return (_mObjects.end()!= _iter); }     // 测试是否还有下一个对象
            T* next(void) { return has_next()? (_iter++->second): NULL;    }    // 获取下一个对象指针

        private:
            typename object_map::iterator _iter;
        };

    public:
        // 构造函数
        objectman(void)
        {
            enable_index();
        }

        // copy 构造函数
        objectman(const objectman& rhs)
        {
            enable_index();
        }

        // 析构函数
        virtual ~objectman(void)
        {
            disable_index();
        }

        // 赋值操作符
        objectman& operator= (const objectman& rhs)
        {

        }

        // 通过索引获取对象
        static T* get_by_index(index_t index)
        {
            object_map::iterator iter= _mObjects.find(index);
            if (_mObjects.end()!= iter)
            {
                T* pObject= iter->second;
                assert(NULL!= pObject);
                return pObject;
            }

            return NULL;
        }

        // 获取对象索引
        index_t get_index(void) const { return _idxObject; }

        // 生成索引（使能被对象管理器遍历到）
        void enable_index(void)
        {
            _idxObject= ++_idxGenderator;
            assert(get_index()!= INVAID_INDEX);
            assert(_mObjects.find(get_index())== _mObjects.end());
            _mObjects.insert(std::make_pair(get_index(), static_cast<T*>(this)));
        }

        // 移除索引（使不能被对象管理器遍历到）
        void disable_index(void)
        {
            if (get_index()!= INVAID_INDEX)
            {
                assert(_mObjects.find(get_index())!= _mObjects.end());
                _mObjects.erase(get_index());

                _idxObject= INVAID_INDEX;
            }
        }

    private:
        friend class iterator;
        static object_map    _mObjects;                        // 对象容器
        static index_t        _idxGenderator;                    // 索引发生器

        index_t                _idxObject;               // 对象索引
    };

    template<typename T>
    typename objectman<T>::object_map objectman<T>::_mObjects;

    template<typename T>
    typename objectman<T>::index_t objectman<T>::_idxGenderator= 0;
}

#endif

测试代码

测试代码如下：

#include <cassert>
#include "objectman.hpp"
// 声明一个类
class Player:public lib::objectman<Player>
{

};

int main(int argc, char* argv[])
{
    const int idxDisabled= 5;
    // 生成对象
    for (int i= 0; i< 10; ++i)
    {
        Player* pPlayer= new Player;
        if (idxDisabled== pPlayer->get_index())
        {
            // 从对象管理器中移除该对象
            pPlayer->disable_index();
        }
    }

    //使用迭代器遍历类对象
    Player::iterator iter;
    while(iter.has_next())
    {
        Player* pPlayer= iter.next();
        const int idxPlayer= pPlayer->get_index();
        // 断言之：遍历不到已经移除的对象
        assert(idxPlayer!= idxDisabled);
        // 断言之：可以通过idxPerson取得对象指针
        assert(pPlayer== Player::get_by_index(idxPlayer));

        // 回收对象
        delete pPlayer;
        pPlayer= NULL;
    }

    // 断言之：所有对象均已被删除
    Player::iterator iter2;
    assert(!iter2.has_next());

    system("pause");
    return 0;
}

vs2008下所有断言均动作通过。

已知问题

在大量生成对象的情况下，index索引空间（代码定义为int的范围）有可能使用殆尽，甚至产生重复，这会导致两个对象拥有相同index的严重错误；
std::map的查找速度不是特别另人满意；

李现民 2009-07-02 12:49 发表评论

关于ECLIPSE中j2me程序运行时报ALERT: java/lang/ClassFormatError: Bad version information.错误

kaisne — Thu, 02 Jul 2009 03:13:00 GMT

今天在ECLIPSE中写的j2me程序运行时候，报ALERT: java/lang/ClassFormatError: Bad version information.一个错误。开始一直以为是自己的程序问题。后来查了一下才知道，原来是Eclipse中设置版本的编译级别的问题。
解决方法：
选择eclipse中的"window"->preferences->设置jdk complier compliance leve为1.3或1.4,因为j2me不支持jdk5,6.设置好后就OK了.

kaisne 2009-07-02 11:13 发表评论

C代码中符合标准的方式输出中文

Corner Zhang — Wed, 01 Jul 2009 09:58:00 GMT

wchat_t str[40] = { L"我的英文名为Corner Zhang!\n" };
setlocale(LC_ALL, "chs');
wprintf(L"%s", str);

Corner Zhang 2009-07-01 17:58 发表评论

编程时经常使用到的标点符号列表!

Corner Zhang — Wed, 01 Jul 2009 09:44:00 GMT

Punctuation type:
~ -- waveline 波浪线
! -- bang 叹号
@ -- at ???
# -- pond 井号
$ -- dollar 美元符
%-- percent 百分号
^ -- accent 幂
& -- and 和
* -- star 星号
( -- open round 左括号
）-- close round 右括号
+ -- plus 加
- -- sub 减
= -- equal 等于
_ -- underline 下划线
\ -- backslash 反斜线
| -- vertical 竖线
{ -- open brace 左花括号
} -- close brace 右花括号
[ -- open quad 左方括号
] -- close quad 左方括号
: -- colon 冒号
; -- semicolon 分号
" -- quote 引号
' -- single quote 单引号
? -- question 问号
/ -- slash 斜线
< -- open angle 左尖括号
> -- close angle 右尖括号
, -- comma 逗号
. -- dot 点号

还有空白符:
' ' -- space 空格
'\n' -- newline 换行
'\t' -- table 制表符
\r' -- return ？？？

Corner Zhang 2009-07-01 17:44 发表评论

NO.7 信令系统基本功能结构

Khan's Notebook — Wed, 01 Jul 2009 08:16:00 GMT

摘要: No.7 SS7 阅读全文

Khan's Notebook 2009-07-01 16:16 发表评论

关于boost库中shared_ptr执行速度的简单测试

HIT@ME — Tue, 30 Jun 2009 13:09:00 GMT

记得以前在一本书上看过boost::shared_ptr的回带来一定的效率损失,但是并不大.今天闲来无事,编译了一个BOOST并简单测试了一下,看看到底有多少性能损失.测试代码和结果如下:

比较函数
template
class compareP
{
public:
        bool operator() (const T lh,const T rh) const
        {
                return *lh<*rh;
        }

};

boost:
int _tmain(int argc, _TCHAR* argv[])
{
        DWORD oldtime = GetTickCount();
        typedef map,size_t,compareP > > container_type;
        typedef container_type::iterator iterator;
        container_type container;
        for (size_t i(0) ; i<500000 ; ++i)
        {
                boost::shared_ptr pstr(new string);
                char buffer[32];
                *pstr = itoa(i,buffer,10);
                container[pstr]=0;
        }
        cout<return EXIT_SUCCESS;
}

boost结果:
2000
2015
2015
2016
2017

指针:
int _tmain(int argc, _TCHAR* argv[])
{
        DWORD oldtime = GetTickCount();
        typedef map > container_type;
        typedef container_type::iterator iterator;
        container_type container;
        for (size_t i(0) ; i<500000 ; ++i)
        {
                string *pstr = new string;
                char buffer[32];
                *pstr = itoa(i,buffer,10);
                container[pstr]=0;
        }
        cout<return EXIT_SUCCESS;
}

指针结果:
937
938
954
953
953

执行速度已经相差一倍了.自动内存管理的代价啊!~~~~
环境:Q8200 2.33GHZ 4G内存

以上只是简单的测试,仅拱参考

补充说明：

很多朋友流言说在MAP中存放string*没有意义。可是我上一个项目就需要这么做。

试想我现在有10篇文档，现在需要统计每篇文档当中每个字出现的次数，还需要统计全部文章中全部字出现的次数。为了保证效率，应当保证每个字在内存当中只留一份拷贝（因为以后有可能统计每个词，甚至每句话出现的次数）。要实现这个功能，是否还有更好的算法？

还有朋友流言说指针版没有销毁string指针。可是在这个程序中执行cout<

luck朋友的方法最为有效，把比较函数变成：

bool operator() (const T &lh,const T &rh) const

{

return *lh<*rh;

}

下面是shared_ptr执行5次的时间：

968

969

985

969

下面是string*执行5次的时间：

859

875

860

859

860

看来即使是小对象也不能放松！当很多小对象发生构造和析构时所耗费的时间还是不容小视的！~

HIT@ME 2009-06-30 21:09 发表评论

用gdb跟踪函数栈桢的变化情况

那谁 — Tue, 30 Jun 2009 12:43:00 GMT

摘要: 阅读全文

那谁 2009-06-30 20:43 发表评论

USACO 3.1 Stamps

YZY — Tue, 30 Jun 2009 12:37:00 GMT

摘要: 动态规划题阅读全文

YZY 2009-06-30 20:37 发表评论

之前做的LOD动态地形

陈昱(CY) — Tue, 30 Jun 2009 04:53:00 GMT

摘要: 看了何咏的文章（http://www.graphixer.com.cn/ShowWorks.asp?Type=1&ID=28）后，再找到了最原始的那篇论文，也实现了一个，仅仅实现了动态地形优化部分，纹理等其它无关算法的内容没有加上去。使用OpenGL渲染，即以前做毕业设计时的框架，顺便也可以改进一下以前的游戏框架~这里就不说算法了，读者可以找找何咏说到的那篇论文，个人觉得主要难点是理解消除... 阅读全文

陈昱(CY) 2009-06-30 12:53 发表评论

C++基于类似反射机制的函数调用完成

陈梓瀚(vczh) — Tue, 30 Jun 2009 04:47:00 GMT

摘要: 现在不仅可以阅读类的成员，也可以用函数名的字符串去调用函数并取得结果了。代码与这篇文章的实例类似，因此只贴出更改的部分以及程序截图。阅读全文

陈梓瀚(vczh) 2009-06-30 12:47 发表评论

USACO 3.1 Humble Numbers

YZY — Mon, 29 Jun 2009 16:05:00 GMT

摘要: 二分法阅读全文

YZY 2009-06-30 00:05 发表评论

USACO 3.1 Score Inflation

YZY — Mon, 29 Jun 2009 14:21:00 GMT

摘要: 背包问题阅读全文

YZY 2009-06-29 22:21 发表评论

USACO 3.1 Agri-Net

YZY — Mon, 29 Jun 2009 13:48:00 GMT

摘要: 最小生成树问题
阅读全文

YZY 2009-06-29 21:48 发表评论

残废版HTTP Server之小试牛刀

陈梓瀚(vczh) — Mon, 29 Jun 2009 13:19:00 GMT

摘要: 为了给C++的反射做Demo，不得不研究一下HTTP的协议。后来发现Windows自带了API可以用，于是就写了个小东西。程序打开之后，如果检测到【http://localhost:8080/vczh/FILENAME】这样子的请求，就将一个目录下面的东西读出来，然后返回。于是就可以用IE来运行某个地方的网页了。代码如下：阅读全文

陈梓瀚(vczh) 2009-06-29 21:19 发表评论

这是我向往的生活

Condor — Mon, 29 Jun 2009 06:34:00 GMT

　　我不向往苏轼那种“大江东去，浪淘尽，千古风流人物”的豪迈气概，也不向往易安那种“才下眉头，却上心头”的婉约凄凉，更不具有杜甫“大庇天下寒士俱欢颜”的伟大胸怀，因为现实不是这样的时代。我所向往的生活，就是快乐幸福、安定和谐。
　　“燕草如碧丝，秦桑低绿枝。”在风和日丽的春天，伴着清脆的鸟鸣，携着飘香的鲜花，和一群知心的朋友在和煦的阳光下，嬉戏、玩耍。让碧丝般的小草，轻抚我们疲倦的身体；让轻柔的春风，抹去我们心中的烦恼；让悦耳的鸟鸣，唤醒我们青春的活力。这是我神往的生活。
　　“接天莲叶无穷碧，映日荷花别样红。”在烈日炎炎的夏天，最快不过于伙伴们像鱼儿一般在水中自由自在地穿梭，你追我，我赶你，时儿水花四溅，时儿欢声笑语。让清凉的溪水冲刷快要蒸发的身体，使我们依旧像新生的嫩叶一般鲜亮；让水花和笑声一起飞溅，使我们仍然充满生机地迎接下一步的挑战。这是我追求的生活。
　　“人道天凉好个秋。”秋高气爽的天气里，拿本书，音乐在耳中穿梭，迎着习习的凉风，坐在窗台边享受闲适的午后，忘了生活的烦恼，忘了学习的压力，忘了时间的流逝，就这样安静的看着书，听着音乐，好好体验一番“少年不识愁滋味”。这是多么惬意的生活啊，我向往！
　　“梅须逊雪三分白，雪却输梅一段香。”我没有雪一般的洁白，也不会有梅的百里飘香。在这个老鼠都不愿意出来偷吃的季节，我没有梅与雪的情操，我所向往的只是能像冬眠的动物一般，蜷缩在自己那个温暖而又温馨的空间里，做上一个甜甜的美梦，隐约听到妈妈不停的叫唤时，睁开朦胧的双眼，迎着厨房里飘出的阵阵清香舒展。“睡觉睡到自然醒”一定是人生一件快事。在寒假里让我睡个饱觉吧，这是我渴望的生活！！
　　让和煦的阳光抚慰我疲倦的心灵吧；让清凉的溪水冲刷去一身的烦恼吧；让恬静的秋意抚平我内心的躁动吧，让充足的睡眠为我的生活加煤加炭吧！我向往这样的生活！
　　听竹声瑟瑟，看世事萧萧。

Condor 2009-06-29 14:34 发表评论

mktags0.2版本发布

那谁 — Mon, 29 Jun 2009 04:38:00 GMT

摘要: 阅读全文

那谁 2009-06-29 12:38 发表评论

C++基于类似反射机制的XML序列化和反序列化完成

陈梓瀚(vczh) — Mon, 29 Jun 2009 04:12:00 GMT

摘要: 跟上一篇文章一样，一样的数据结构，但是添加了对数组、列表和映射的更多的支持。首先是代码，然后是序列化后的XML文件。阅读全文

陈梓瀚(vczh) 2009-06-29 12:12 发表评论

以前写的一个N连看

陈昱(CY) — Sun, 28 Jun 2009 11:50:00 GMT

摘要: 这一周，我写好了一个连连看，在设计连连看的算法的过程中，我设计了一个可以控制连数的连连看算法，并把连连看改成了“n连看”，然后经过算法优化，使我的连连看算法在20连、无解、矩阵是13*11、最坏情况（一个周围空旷，一个被包围）下，运算速度仅2秒左右。而经过优化之前，到了6连的最坏情况下就已经慢得无法接受了。基本的算法是这样的：先写一个函数f1，判断点1和点2能否经过某个方向... 阅读全文

陈昱(CY) 2009-06-28 19:50 发表评论

USACO 2.4 Fractions to Decimals

YZY — Sun, 28 Jun 2009 10:49:00 GMT

摘要: 模拟题，将分数转换成带循环节小数形式。阅读全文

YZY 2009-06-28 18:49 发表评论

USACO 2.4 Bessie Come Home

YZY — Sun, 28 Jun 2009 09:25:00 GMT

摘要: 最短路径问题阅读全文

YZY 2009-06-28 17:25 发表评论

USACO 2.4 Cow Tours

YZY — Sat, 27 Jun 2009 14:10:00 GMT

这题综合了dfs,floyd算法。

首先用 floyd计算出两两之间的最短路径。然后用dfs将图着色。对每两两不同颜色的结点，我们把它们相连，然后看产生的图的直径的大小。
直径的大小只可能仍为原两连通图直径之一，或者是包括新添加的路径所产生的最长路径，取这三者中的最大值。新路径产生的最长路径只可能是两点的距离加上两点到其他点的最长距离。最开始的时候只考虑了新添加的路径，没考虑原直径会比新路径大的情况，wa了n次。。

#include <iostream>
#include <fstream>

#include <cfloat>
#include <cmath>

using namespace std;

ifstream fin("cowtour.in");
ofstream fout("cowtour.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

double path[150][150];

char graph[150][150];

int x[150];
int y[150];

int n;

int color[150];

double diameter[150];
double maxPath[150];

void floyd()
{
    for(int k=0;k<n;++k)
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j){
                if(i!=j){
                    path[i][j]=min(path[i][j],path[i][k]+path[k][j]);
                }
            }
}

void make_color(int i,int c)
{
    if( color[i]!=0 )
        return;

    color[i] = c;

    for(int j=0;j<n;++j){
        if(color[j]==0&&graph[i][j])
            make_color(j,c);
    }
}

void solve()
{
    in>>n;

    for(int i=0;i<n;++i){
        in>>x[i]>>y[i];
    }

    for(int i=0;i<n;++i){
        string s;
        in>>s;
        for(int j=0;j<n;++j){
            graph[i][j]=s[j]-'0';
            if(graph[i][j]){
                path[i][j] = sqrt( (x[i]-x[j])*(x[i]-x[j])
                    +(y[i]-y[j])*(y[i]-y[j]) );
            }else{
                path[i][j] = DBL_MAX/4;
            }
        }
    }

    floyd();

    int c = 0;
    for(int i=0;i<n;++i)
        if(color[i]==0)
            make_color(i,++c);

    for(int i=0;i<n;++i){
        maxPath[i] = 0;
        for(int j=0;j<n;++j){
            if(i!=j&&color[i]==color[j]){
                maxPath[i] = max(maxPath[i],path[i][j]);
            }
        }

        diameter[color[i]] = max(diameter[color[i]],maxPath[i]);
    }

    double dia = DBL_MAX;

    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j){

            if(color[i]==color[j]) continue;

            double d1 = 0;
            for(int p=0;p<n;++p){
                if(i!=p&&color[i]==color[p])
                    d1 = max(d1,path[i][p]);
            }

            double d2 = 0;
            for(int p=0;p<n;++p){
                if(j!=p&&color[j]==color[p])
                    d2 = max(d2,path[j][p]);
            }

            double dist = sqrt( (x[i]-x[j])*(x[i]-x[j])+
                    (y[i]-y[j])*(y[i]-y[j]) );

            dia = min(dia,max(d1+d2+dist,max(diameter[color[i]],diameter[color[j]])) );
        }

    out.setf(ios::fixed,ios::floatfield);
    out.precision(6);
    out<<dia<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-06-27 22:10 发表评论

mktags--根据指定的文件路径以及文件类型生成ctags以及cscope索引文件的工具

那谁 — Sat, 27 Jun 2009 13:38:00 GMT

摘要: 阅读全文

那谁 2009-06-27 21:38 发表评论

一种字符串转化为16进制显示的算法

爱红尘 — Sat, 27 Jun 2009 05:08:00 GMT

摘要: 一种字符串转化为16进制显示的算法阅读全文

爱红尘 2009-06-27 13:08 发表评论

USACO 2.4 Overfencing

YZY — Fri, 26 Jun 2009 14:25:00 GMT

找出两个迷宫的出口，然后分别进行dfs，求出到每一个点的最短距离。
然后对每一个点，求到最短的那个出口的距离，然后再求这个值的最大值即可。
找出口写得比较繁琐。

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("maze1.in");
ofstream fout("maze1.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

char maze[2*100+1][2*38+1];

bool visited[100][38];

int shortest1[100][38];
int shortest2[100][38];

bool get_first;
int exit1r,exit1c;
int exit2r,exit2c;
int w,h;

struct queue_node{
    int i,j,depth;
    queue_node(int i,int j,int depth){
        this->i = i;
        this->j = j;
        this->depth = depth;
    }
};

void bfs(int i,int j,int shortest[100][38])
{
    queue<queue_node>q;

    q.push(queue_node(i,j,1));

    while(!q.empty()){

        queue_node node = q.front();
        q.pop();

        if(visited[node.i][node.j])
            continue;

        visited[node.i][node.j] = true;

        shortest[node.i][node.j] = node.depth;

        if(node.i!=0&&maze[2*node.i][2*node.j+1]==' '){
            q.push(queue_node(node.i-1,node.j,node.depth+1));
        }
        if(node.i!=h-1&&maze[2*node.i+2][2*node.j+1]==' '){
            q.push(queue_node(node.i+1,node.j,node.depth+1));
        }
        if(node.j!=0&&maze[2*node.i+1][2*node.j]==' '){
            q.push(queue_node(node.i,node.j-1,node.depth+1));
        }
        if(node.j!=w-1&&maze[2*node.i+1][2*node.j+2]==' '){
            q.push(queue_node(node.i,node.j+1,node.depth+1));
        }
    }
}

void solve()
{
    in>>w>>h;

    for(int i=0;i<2*h+1;++i)
        for(int j=0;j<2*w+1;++j){

            do{
            in.get(maze[i][j]);
            }while(maze[i][j]=='\n');

            if((i==0||i==2*h||j==0||j==2*w)&&maze[i][j]==' '){
                if(!get_first){
                    if(i==2*h)
                        exit1r = h-1;
                    else
                        exit1r = i/2;
                    if(j==2*w)
                        exit1c = w-1;
                    else
                        exit1c = j/2;
                    get_first = true;
                }else{
                    if(i==2*h)
                        exit2r = h-1;
                    else
                        exit2r = i/2;
                    if(j==2*w)
                        exit2c = w-1;
                    else
                        exit2c = j/2;
                }
            }
        }

    memset(visited,0,sizeof(visited));
    bfs(exit1r,exit1c,shortest1);
    memset(visited,0,sizeof(visited));
    bfs(exit2r,exit2c,shortest2);

    int res = INT_MIN;

    for(int i=0;i<h;++i)
     for(int j=0;j<w;++j){
         res = max(res, min(shortest1[i][j],shortest2[i][j]) );
     }

    out<<res<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-06-26 22:25 发表评论

ASIO攻破！！！

Fri, 26 Jun 2009 14:14:00 GMT

花了足足3天时间，外加1天心情休整，终于在第5天编写出了一个能运行的基于asio和thread_group的框架，差点没气晕过去，把源码都看懂了才感觉会用了。
测试了一下，debug下一万次回应耗时800+毫秒，release下是200+毫秒，机器配置双核2.5G英特尔，4个线程并行工作，无错的感觉真好，再也不用担心iocp出一些奇怪的问题啦，因为是巨人们写的实现，呵呵。

进入正题，简要说一下asio的实现原理吧。在win32平台上，asio是基于IOCP技术实现的，我以前也用过IOCP，却没想到居然能扩展成这样，真是神奇！在其他平台下还会有别的方法去实现，具体见io_service类下面这部分的源码：

  // The type of the platform-specific implementation.
#if defined(BOOST_ASIO_HAS_IOCP)
  typedef detail::win_iocp_io_service impl_type;
  friend class detail::win_iocp_overlapped_ptr;
#elif defined(BOOST_ASIO_HAS_EPOLL)
  typedef detail::task_io_service<detail::epoll_reactor<false> > impl_type;
#elif defined(BOOST_ASIO_HAS_KQUEUE)
  typedef detail::task_io_service<detail::kqueue_reactor<false> > impl_type;
#elif defined(BOOST_ASIO_HAS_DEV_POLL)
  typedef detail::task_io_service<detail::dev_poll_reactor<false> > impl_type;
#else
  typedef detail::task_io_service<detail::select_reactor<false> > impl_type;
#endif

这部分代码其实就在boost::asio::io_service类声明中的最前面几行，可以看见在不同平台下，io_service类的实现将会不同。很显然，windows平台下当然是win_iocp_io_service类为实现了（不过我一开始还以为win_iocp_io_service是直接拿出来用的呢，还在疑惑这样怎么有移植性呢？官方文档也对该类只字不提，其实我卡壳就是卡在这里了，差点就直接用这个类了^_^!）。

那么就分析一下win_iocp_io_service的代码吧，这里完全是用IOCP来路由各种任务，大家使用post来委托任务，内部调用的其实是IOCP的PostQueuedCompletionStatus函数，然后线程们用run来接受任务，内部其实是阻塞在IOCP的GetQueuedCompletionStatus函数上，一旦有了任务就立即返回，执行完后再一个循环，继续阻塞在这里等待下一个任务的到来，这种设计思想堪称神奇，对线程、服务以及任务完全解耦，灵活度达到了如此高度，不愧为boost库的东西！我只能有拜的份了...

说一下总体的设计思想，其实io_service就像是劳工中介所，而一个线程就是一个劳工，而调用post的模块相当于富人们，他们去中介所委托任务，而劳工们就听候中介所的调遣去执行这些任务，任务的内容就写在富人们给你的handler上，也就是函数指针，指针指向具体实现就是任务的实质内容。其实在整个过程中，富人们都不知道是哪个老公帮他们做的工作，只知道是中介所负责完成这些就可以了。这使得逻辑上的耦合降到了最低。不过这样的比喻也有个不恰当的地方，如果硬要这样比喻的话，我只能说：其实劳工里面也有很多富人的^o^! 。很多劳工在完成任务的过程中自己也托给中介所一些任务，然后这些任务很可能还是自己去完成。这也难怪，运行代码的总是这些线程，那么调用post的肯定也会有这些线程了，不过不管怎么说，如此循环往复可以解决问题就行，比喻不见得就得恰当，任何事物之间都不可能完全相同，只要能阐述思想就行。

最后还要说明的一点就是：委托的任务其实可以设定执行的时间的，很不错的设定，内部实现则是通过定时器原理，GetQueuedCompletionStatus有一个等待时间的参数似乎被用在这方面，还有源码中的定时器线程我并没有过多的去理解，总之大体原理已基本掌握，剩下的就是使劲的用它了！！！

但愿这篇随笔也能对正在研究asio的朋友们有所帮助吧。

酿 2009-06-26 22:14 发表评论

USACO 2.4 The Tamworth Two

YZY — Fri, 26 Jun 2009 12:48:00 GMT

模拟题。按题目要求编码即可，每过一分钟，更新一下农夫和奶牛的状态。如果该状态以前出现过，说明有循环，不可能到达，输出0.

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("ttwo.in");
ofstream fout("ttwo.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

char grid[10][10];

bool visited[10][10][4][10][10][4];

int north = 0;
int east = 1;
int south = 2;
int west = 3;

//方向为0,1,2,3时向前走一步row和column的增加值
int delr[4] = {
    -1,0,1,0
};
int delc[4] = {
    0,1,0,-1
};

// farmer的当前row,column,direction.
int fc,fr,fd;
int cc,cr,cd;

bool available(int i,int j)
{
    if(i>=0&&i<=9&&j>=0&&j<=9&&grid[i][j]!='*')
        return true;
    else
        return false;
}

void one_step()
{
    if( available( fr+delr[fd],fc+delc[fd] ) ){
        fr += delr[fd];
        fc += delc[fd];
    }else{
        fd+=1;
        fd%=4;
    }

    if( available( cr+delr[cd],cc+delc[cd] ) ){
        cr += delr[cd];
        cc += delc[cd];
    }else{
        cd+=1;
        cd%=4;
    }
}

void solve()
{
    for(int i=0;i<10;++i)
        for(int j=0;j<10;++j){
            in>>grid[i][j];
            if(grid[i][j]=='F')
                fr=i,fc=j,fd=0;
            if(grid[i][j]=='C')
                cr=i,cc=j,cd=0;
        }

    memset(visited,0,sizeof(visited));

    visited[fc][fr][fd][cc][cr][cd] = true;

    int res = 0;

    while(true){

        one_step();
        res++;

        if( fc==cc&&fr==cr ){
            out<<res<<endl;
            exit(0);
        }

        if(visited[fc][fr][fd][cc][cr][cd]){
            out<<0<<endl;
            exit(0);
        }

        visited[fc][fr][fd][cc][cr][cd]=true;
    }
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-06-26 20:48 发表评论

USACO 2.3 Controlling Companies

YZY — Fri, 26 Jun 2009 12:01:00 GMT

每加一个新结点，更新一下对各公司控制值,递归地加入新控制的结点即可。用一个布尔向量记录一下已经控制的公司，以免无穷递归。

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("concom.in");
ofstream fout("concom.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int stock[101][101];
int n;
bool control[101];

void add_control(int cr,int ce)
{
    if(control[ce]) return;

    control[ce] = true;
    for(int i = 1; i<=100; ++i){
        if(i!=cr&&!control[i]){
            stock[cr][i]+=stock[ce][i];

            if(stock[cr][i]>50)
                add_control(cr,i);
        }
    }
}

void solve()
{
    memset(stock,0,sizeof(stock));

    in>>n;

    int i,j,p;

    while(n--){
        in>>i>>j>>p;
        stock[i][j] = p;
    }


   for(int i=1;i<=100;++i){

       memset(control,0,sizeof(control));

       for(int j=1;j<=100;++j){

           if(i==j) continue;

           if( stock[i][j]>50){
               add_control(i,j);
           }
       }

       for(int j=1;j<=100;++j){
           if(control[j]){
               out<<i<<' '<<j<<endl;
           }
       }
   }
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-06-26 20:01 发表评论

初探C++ Builder 2009的UnicodeString

土仔 — Thu, 25 Jun 2009 16:41:00 GMT

摘要: 摘要: Tags：C++ Builder 2009 UnicodeString Big5 GB
利用C++ Builder 2009实现一个在简体XP中可显示繁体TXT内容的记事本，并对C++ Builder 2009的UnicodeString进行源码跟踪。
阅读全文

土仔 2009-06-26 00:41 发表评论