C_and_CPP 版 (精华区)

发信人: seaboy (浪小), 信区: C_and_CPP
标  题: Al-Go-Rithms 
发信站: 哈工大紫丁香 (2003年06月20日09:40:44 星期五), 站内信件

Al-Go-Rithms 

徐波 翻译

-------------------------------------------------------------------------------
-

各类报道纷至沓来。地表附近及邻近空间正发生什么事，我根本摸不着头脑。从各种迹象
看，亚洲人似乎已经占领了这个地方，但到目前为止，我还没有看到他们。 

我和珍妮正与世隔绝般地在地下古城工作。这是一个奇妙的，既黑又冷的，深埋冰底的生
态建筑。庞大的建筑里到处都是寂静的走廊和房间，有些房间的用途一望便知（如奇形怪
状的厕所设施），有些就颇显神秘（有一个巨大的房间，里面是空的，但却有三个直径十
英尺的金属球不知用什么方法悬于半空）。这三个金属球似乎在提示某个地方有些能源可
能处于激活状态，但除此之外实在看不出它们还有什么作用，而且我们研究的这些史前文
物几乎看不出有生命的痕迹。 

在这片古老而又黑暗的静谥王国里，我们小心翼翼地移动着，几乎总是挤在白色灯光的周
围和工作区附近。虽然并不要求保持肃静，但我们发现自己总是压低着噪子说话，除了表
示虔诚之外，并没有明显的理由要这么做，也许心中有丝淡淡的敬畏，甚至是一些害怕吧
。 

整个队伍都知道我们即将取得突破。更重要的是，官员们也知道了这个情况，这也正是他
们逼着我们昼夜不停地工作的原因。 

珍妮用钩子钩起插到我们正在研究的文物里的电源，进行另一项测试。她注视着监视器，
突然出现一个尖峰信号，接着又什么都没有了。她丧气甩甩手：“又不知什么地方出错了
！真是难以捉摸啊！”她停了下来，懊恼地叹了口气。 

“至少它有反应，这就说明了一些问题，”我若有所思，“让我们再试试，我们昨天试过
的电源在哪？” 

她挥挥手：“在那儿，如果你直接用它，成功几率几乎是零，即使用上适配器也差不了多
少。这玩意儿换一种能源可能有用，如果在原理上不是完全不同的话。 

“它有反应，”我重复道，“我们又靠近了一步。有时你可以用个旧的，把它跟新的混在
一起让它工作，如果你能选用正确的适配器的话，有时你可以再试试……” 


-------------------------------------------------------------------------------
-

我和Guru正在进行代码回顾。当我俩正埋头于代码堆时，突然听到一种不同寻常的响声，
确实是不同寻常，至少在办公室里是这样。我望着Guru：“这声音象是……” 

“……婴儿！”我俩异口同声地说道。我站起身，扫视四周，发现温迪褐色的卷发正靠近
我的卧室。当她转过拐角，我发现她正推着一辆婴儿车，车上的小珍妮才满月，我们跑过
去跟她嘻嘘一番。虽然平常我并不太喜欢小孩，但温迪是我的亲密伙伴，对她的小孩我自
然要另眼相看。 

甚至连鲍勃也加入到人群中。“好了，好了，”他气喘吁吁地说道，仿佛他是孩子的父亲
似的：“我总是说小孩子要么象温斯顿.邱吉尔，要么象尤达，她象谁啊？”他把他那杯咖
啡放在我办公桌的一叠打印纸上，从温迪手中接过珍妮。他凝视着珍妮还有点皱的脸蛋：
“嗯…可能是个例外，跟我说的不一样。再过二十年，肯定是个大美人。”此时，珍妮不
安地挣扎起来，发出哼哼声。鲍勃吸吸鼻，把珍妮交回给温迪，顾不上他那杯咖啡便转身
离去。 

我扬了扬眉：“看上去你已经教会她怎样对付鲍勃了。” 

温迪笑了：“我最好改改她的脾气。” 

等这个主要魅力人物离去后，人群也散开了，Guru和我重新开始代码回顾。我小心翼翼地
将鲍勃的咖啡转移到一个安全一点的地方。一切都还顺利，直到我们碰到一个使用了strok
的解析函数。Guru斜视着我。 

“有没有比strtok更好的选择，我的孩子？”她问道。 

“但strtok正确地完成了我需要它完成的任务。您不是老提醒我C库函数也是C++标准的一
部分吗？” 

“是这样，我的学徒工。但记住，C标准对于库函数是不作承诺的。” 

“好了，如果你想跟我谈论多线程的话题的话…” 

“不，我的孩子，”Guru打断说，“我说的不是这个问题。神圣的C标准明确指出，strtok
是不可再入的（事实上没有一个标准C函数能够做到这点）。更糟的是，在你这个情况，st
rtok在各级调用中都保持全局状态，考虑一下你的函数所运行的上下文环境，它在另一个
解析函数的内部使用，而该解析函数也可能使用strtok。” 

我用我最擅长的如车灯前的小鹿般的目光注视着她，让她明白我没怎么搞懂。 

Guru点点头：“考虑一个类似的例子，”她边说边拿起干擦笔，在我的白书写板写道： 

void f()
{
    // ...

    strtok( charPtrA, delimiters ); 

    // ...

    strtok( 0, delimiters );

    // ...
}

void g()
{
    strtok( charPtrB, otherDelimiters );

    // ...

    f();

    // ...

    strtok( 0, otherDelimiters );
}

“当f()结束的时候，它就会使stortok内部状态变得无法预料，g()就无法以它所预期的方
式使用它。” 

“我明白了，”我说，“所以，解决方法是……？”我还不想把皮球接过来。 

“用你自己的算法，在必要时做些改变。例如，这里是基本的strtok函数，它在std::stri
ng上操作，而不是C风格的字符串，并经过修改，使之不改变源字符串。” 

std::string StringTok(const std::string* newSeq,const std::string& delim )
{
    // 象标准的strtok一样，在各级调用中保持全局状态。
    // 要搜索的序列

    static const std::string* seq = 0; 

    // 当前位置

    static std::string::size_type pos = 0; 

    if( newSeq )
    {
        seq = newSeq;
        pos = 0;
    }

    std::string token;

    if( seq && pos != std::string::npos )
    {
        pos = seq->find_first_not_of( delim.c_str(), pos );

        if( pos != std::string::npos )
        {
            std::string::size_type next =
            seq->find_first_of( delim.c_str(), pos );
            token = seq->substr( pos, next-pos );
            pos = next;

            if( pos != std::string::npos )
                 ++pos;

            if( pos >= seq->size() ) 
                pos =std::string::npos;
        }
    }

    return token;
}

（我承认上面这些并非照抄Guru所写的内容，我不得不修改一些错字，清除一些逻辑错误
。不过还是言归正传……） 

“这是它的实现，”Guru继续道，“它受到与我们前面所讨论的标准C strtok函数相同的
大部分限制，并且带来了另外一些令人不安的东西，象创建一份标志字符串的负担。” 

“但是难道不能采用copy-on-write吧？有些string的实现不是印证了这个情况，也就是说
返加值是现存string的一个子串，而且仅作了一个copy-on-write?” 

“有些实现可能是这样做的，但是已有名言：‘用copy-on-write使实现方法很难做到线程
安全[2]。’现在，更多的实现方法遵循了该指示，去除了这些优化措施。另外，这并不是
唯一的问题：该函数在异常安全方面做得也不好，比如在子串赋值给抛出的token的情况下
。” 

“所以，”我继续道，“我怎样克服各方面的问题呢？” 

Guru微斜的唇角流出一丝笑意：“我的孩子，如果你打算超越学徒工这个阶段，你必须自
己解决问题。克服这些问题的方法应该是，象我确信你的大学课本曾说过的，此题留作习
题。写一个StringTok函数，消除可再入性和嵌套问题，修正异常安全问题，并尽可能地通
过避免字符串拷贝来保持效率。下午我来看你的答案。” 

她转身离去，我接着干活。不久我就意识到要保持状态必须要使用一个对象。我写了个测
试程序，并为我的解决方案写出代码，修正了一些bug后，我回头去找Guru。我最终交给她
的代码如下： 

template<class T>
class StringTok
{
public:
    StringTok( const T& seq, 
    typename T::size_type pos = 0 )
    : seq_( seq ) , pos_( pos ) { }

    T operator()( const T& delim );

private:
    const T& seq_;
    typename T::size_type pos_;
};

template<class T>
T StringTok<T>::operator()( const T& delim )
{
    T token;

    if( pos_ != T::npos )
    {
    // 开始寻找标志

    typename T::size_type first =seq_.find_first_not_of( delim.c_str(), pos_ );
    if( first != T::npos )
    {
        // 所找到标志的长度

        typename T::size_type num =seq_.find_first_of( delim.c_str(), first ) 
- first;
        // 把所有的工作放在此处

        token = seq_.substr( first, num ); 

        //完成，现在提交只采用不抛出异常的操作

        pos_ = first+num; 
        if( pos_ != T::npos ) ++pos_; 
        if( pos_ >= seq_.size() ) pos_ = T::npos; 
    }
}

return token;
}

“用这种方法，”我解释道，“代码更简单了，因为我不必担心开始新序列。如果用户需
要，他只需分创建一个新的tokenizer对象。现在异常安全的bug也消除了，因为我‘把所
有的工作放在固定的地方，在提交时只采用不抛出异常的操作。’哦，我想应该使它模板
化……并不需要增加多少工作，只要多写几个typename罢了，用这种方法我们可以用宽字
符来使用它。” 

Guru压了压耳后一络银灰色的头发。“我知道了，”她狡黠地说，“StringTok使用了缺省
的拷贝构造函数和赋值操作。” 

我笑了，这次有充分的思想准备，不会上钩。“事实上，”我镇定地回答：“我故意保留
了缺省拷贝和赋值的用法，因为它们起到了书签的作用：用这种方法用户可以在标志化过
程的任一位置取得StringTok的一份拷贝，并可从该位置起探寻另外的标志化方法。事实上
，它在你原来的问题程序中工作良好，即使你通过使f和g独立解析这个非常相似的字符串
来增加问题的难度，它也毫无问题。” 

void f()
{
    // ...

    StringTok<std::string> x( stringA ); 

    // ...

    x( delimiters );

    // ...
}

void g()
{
    // ...

    // 这次字符串是一样的
    StringTok<std::string> y( stringA ); 

    // ...

    f();

    // ...

    // 记住我们的位置
    StringTok<std::string> z( y ); 
    y( otherDelimiters );
    if( DidntWork() )
    //再进入同一位置
    z( yetOtherDelimiters );
}

“不仅各种标志化操作可以并行工作，而且它们可以在同一字符串上独立工作。所有这些
，”我总结道，“不会增加任何开销，因为这些序列的字符串从不会被实际拷贝。”我双
手抱胸，又坐了下来。 

“说得好，”Guru微笑颔首，“当你进一步深入时，你可能考虑增加更强大的特性，象在
分隔符中使用vector<string>的能力，这样你就不会受限于单字符分隔符。” 

“或者，”我趁热打铁地说，“允许它具有辨认空字段的能力。我以前曾试过strtok，它
能解析出以逗号分隔的字段，但如果存在空字段，象A,B,,,C这样，就把它给搞糊涂了，st
rtok将会跳过两个空字段。” 

我们快速地对代码回顾作了总结，然后我就开始用修改后的解析函数来工作了。 


-------------------------------------------------------------------------------
-

“要让仪器能分析出这台东西，还有些工作要做。”珍妮摇摇头。 

“好了，跟上次测试比起来，我们还是有收获的。能量输入的各方面怎么样，跟上次我们
测试时比不是有变化吗？” 

珍妮点点头：“我知道了，让我们再试试。” 


-------------------------------------------------------------------------------
-

[参考文献] 
[1] To the tune of "I've Got Rhythm." 

[2] H. Sutter. More Exceptional C++, Items 15 and 16 (Addison-Wesley, 2001). 

--
才知道   
原来
自己需要的是   
100万
份勇气。。。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.80]