huaxiazhihuo

 

基于堆栈上的字符串实现

           C++中,由于字符串一开始并非内置的类型,于是,史前时代,江湖上出现了种种的字符串,各有各的优点,但自然,也各有各的缺陷,群雄割据,天下大乱,民不聊生。大伙儿盼星星,盼月亮,盼着真正的字符串能出来一统江湖,好不容易,等到1998C++标准出来了,官方的字符串string终于露面了,自然,它并不是语言内置支持的,而是在STL库中。当然,字符串这东西,就算要在C++编译器的层面上给予支持,其实也很不容易。可是,这个官方的string,单纯它复杂的模板定义和那一大陀函数成员,就足以吓退众多意志不坚定之人。好了,好不容易,鼓起勇气,再仔细瞅瞅string中的东西,发现它也不是很美妙,既不强大,部分函数的功能存在重复又或者STL的算法中已有提供,更要命的是,效率也不怎么高。总之,不能说string的设计不如史前的各种stringS,但也强不到那里去。当然,官方的总比非官方的更具权威,但每次使用string时,想到它背地里除了正常字符串操作之外,还可能做了各种的低效的内存分配释放的操作,又或者线程安全,又或者引用计数,内心就一直惴惴不安。于是,宁愿一再小心翼翼地用着字符数组。但是,用得多了,也很郁闷,字符数组自然高效、灵活,但总是要千编一律地一再写着容易出错的代码,我脆弱的心灵终于头晕眼花了。于是,我决定按照自己的意愿写一个字符串,不敢欲与群雄争锋,只是,为了能够在自己的代码中,替换字符数组。我对它的要求是,字符数组能做到的事情,它也要做到,并且,效率上,绝不妥协。

          俗话说,过早的优化是万恶之源。但在此,在设计本家字符串时,一开始,就要考虑到效率的细节上去了。首先,它要支持堆栈变量的形式,不要它进行内存的分配释放操作,就好像堆栈上的字符数组那样。咦,好像很神奇,其实,只要想到TR1中那个经典的array,通过使用神奇的模板技术,就有办法做到了。所以,此字符串的使用好比这样子,CStackString <MAX_PATH> sFile,暂时假定这个字符串的名字叫CStackString

          但是,使用模板之后,字符串的字符数组的长度只要不一样,它们就都属于不同类型变量,并且之间还都不兼容呢,虽然它们都是字符串。此外,还会编译器还将生产出一堆重复的代码。这无论如何,都不能忍受。于是,自然而然,就想到了继承。CStackString模板类继承于非模板的mybasestringmybasestring中实现了CStackString的各种各样的操作,而CStackString只要仿照array那样子,定义好自己的数据成员即可。嗯,还是看看代码,马上就明白到底是怎么一回事了。


class CMyBaseString
{
public:
    typedef size_t size_type;
    typedef 
char *pointer;
    typedef 
const char *const_pointer;
    typedef CMyBaseString _Myt;

public:
    
char operator[](size_type nPos)const
    
{
        assert(nPos 
< m_nLen);
        
return m_str[nPos];
    }


    const_pointer c_str()
const return m_str; }

    const_pointer right(size_type nLen)
const
    
{
        assert(nLen 
< m_nLen);
        
return m_str+m_nLen-nLen;
    }


    
int compare(const_pointer str)const
    
{
        
return strcmp(m_str, str);
    }


    _Myt
& assign(const char* str)
    
{
        m_nLen 
= strlen(str);
        assert(m_nLen 
< m_nBuffSize);
        strcpy(m_str, str);
        
return *this;
    }


    _Myt
& append(const_pointer str)
    
{
        size_type nLen 
= strlen(str);
        assert(m_nLen 
+ nLen < m_nBuffSize);
        strcpy(m_str
+m_nLen, str);
        m_nLen 
+= nLen;
        
return *this;
    }


    _Myt
& format(const_pointer sFormat,  )
    
{
        va_list argList;
        va_start( argList, sFormat );
        m_nLen 
= vsprintf(m_str, sFormat, argList);
        va_end( argList );
        assert(m_nLen 
< m_nBuffSize);
        
return *this;
    }


    
//.

protected:
    CMyBaseString(pointer sBuf, size_type nBuffSize)
    
{
        m_nBuffSize 
= nBuffSize;
        m_nLen 
= 0;
        m_str 
= sBuf;
        m_str[
0= 0;
    }


private:
    size_type m_nBuffSize;
    size_type m_nLen;
    pointer m_str;
}
;

template
<size_t _size>
class CStackString : public CMyBaseString
{
public:
    CStackString(
const char* str) : CMyBaseString(m_sMine, _size) { assign(str);}
    CStackString() : CMyBaseString(m_sMine, _size) 
{}

private:
    
char m_sMine[_size];
}
;
int main()
{
    CStackString
<20> sTest("hello");
    cout 
<< sTest.c_str() << endl;
    cout 
<< sTest.right(3<< endl;
    
return 0;
}

          于是通过基类mybasestring,各种不同类型的template CStackString就又联系在一块了。Mybasestring可看成定义了数据接口的基类,其子类的头部数据必须与它保持一致,嗯,很好。然后,在mybasestring中实现的各种功能,都可以用在mystring身上了,而CStackString中无须实现任何功能,它只负责在堆栈上分配内存。所以,mybasestring不仅可以用在堆栈上,还能用于堆上,只要再继续定义一个能在堆上分配内存的mybasestring的子类即可,然后都能相容于堆栈上的CStackString字符串。

          ……。 经过一番努力,这个字符串类几乎包含了字符数组的一切基本功能,基本上可代替字符数组了。为了能够用到STL中的各种算法,再在其上增加一些返回迭代器的函数,好比beginendrbeginrend,它们都很容易实现。还有,为了使用起来更加友好方便更具效率,貌似应该再实现一些全局操作符的重载运算;……;好了,打住。如果打算将这个字符串很好地融入到STL中,需要做出更多的努力。原本只打算代替字符数组而已。代码在VC2005以上版本编译时,会出现一些警告,可以用#pregma的指令将其disable掉,或者使用其中的所谓的安全字符串操作函数。

          好不容易,终于就实现了一个基于堆栈上的字符串,它是窄字符的。别忘了,还有宽字符的字符串呢。这也没什么,只须将mybasestring重命名为CMyBaseStringACStackString改为CStackStringA。然后再分别实现与CMyBaseStringACStackStringA同样接口的CMyBaseStringWCStackStringW。然后,再针对UNICODETypedefdefined一对CMyBaseStringTCStackStringT。在这里,并不想模仿STL中的stringMFC中的CString那样子,template一个basic_stringsimple_string),然后分别进行模板特化,近来越看越觉得这种模板特化的方式相当恶心,只是将代码搞得更加复杂,却没带来多大的好处。

          相比于其他的字符串实现,这个mybasestring不过是将内存分配拱手让人罢了。这样一来,就带来一些新的问题。首先,它要假设其子类给它分配了足够的内存,不过,在C++传统,经常假设用户分配了足够的内存;然后,因为脱离了内存管理,有一些功能自然也就无法实现出来了,C的字符串函数也还不是这样,当缓冲溢出时,该崩溃就还得崩溃。

          再次向C++的无所不能顶礼膜拜。C++,你是电,你是光, 你是唯一的神话, 我只爱你,You are my Super Star

          再次声明,本字符串只为取代字符数组,至于其它的种种无理要求,均不在本座的考虑范围之内。

posted on 2012-06-08 01:11 华夏之火 阅读(2705) 评论(13)  编辑 收藏 引用 所属分类: c++技术探讨

评论

# re: 高效、实用、安全的字符串,语法糖?奇技淫巧? 2012-06-08 08:39 Richard Wei

依赖于编译器的内存布局, 不敢用。
C++11新增了array类来替代C型的原始数组。  回复  更多评论   

# re: 高效、实用、安全的字符串,语法糖?奇技淫巧? 2012-06-08 09:04 华夏之火

是的,这个设计很丑陋很限制。我已作了修改@Richard Wei
  回复  更多评论   

# re: 高效、实用、安全的字符串,语法糖?奇技淫巧?[未登录] 2012-06-08 09:20 春秋十二月

内存分配存储方式可作为一种策略,作为字符串的模板参数,形如std::allocator。不必弄子类定制。  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-06-08 09:52 华夏之火

代码中,我又作了修改。至于形如std::allocator的那种定制,也有其不足,比如,vector,因为采用不同的std::allocator的容器,都属于不同的类型的vector,并且vector之间还不兼容呢@春秋十二月
  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-06-08 12:05 春秋十一月

用alloc来分配嘛,也是堆栈,一样的效果,只要不是用malloc/HeapAlloc就行。这样模板都不需要了。  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-06-08 13:19 zgpxgame

会导致代码膨胀,如果只是内存问题可以考虑换一个基于栈的内存分配器  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-06-08 13:46 华夏之火

基于栈的内存分配器?在下也想看到,能否推荐一下。至于代码膨胀,在这里的实现中,自然不会存在,你应该知道WHY的@zgpxgame
  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-06-08 13:58 华夏之火

_alloca,在C++中,貌似并不是很推荐,据说会带来一些什么问题@春秋十一月
  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-09-03 02:28 zgpxgame

我想说的代码膨胀是指如果代码中使用了CStackString<1>......CStackString<N>会导致编译器生成N个类,当然如果只取一个最大N使用这个类也就不存在这个问题了。 我个人不主张去重新实现一个栈string,而是去实现一个栈分配器,这里有现成的例子:http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h@华夏之火
  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-09-05 11:01 华夏之火

CStackString<1>......CStackString<N>会导致编译器生成N个类,确实会生成这么多类,但是,这些类的函数都在基类中了,只有一分。C++中,最后的执行文件中,不存在类这个概念,只有类的函数,也即是函数。至于构造函数,则全部被内联@zgpxgame
  回复  更多评论   

# re: 基于堆栈上的字符串实现 2012-09-05 17:35 zgpxgame

恩,可以。 如果字符串类实现的再完善些也未尝不可 @华夏之火
  回复  更多评论   

# re: 基于堆栈上的字符串实现[未登录] 2012-10-20 11:32 无名

这也许会使每个字符串对象多用掉四字节内存  回复  更多评论   

# re: 基于堆栈上的字符串实现[未登录] 2012-10-20 11:35 无名

所以根据情况做不同取舍吧  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜