随笔-90  评论-947  文章-0  trackbacks-0

陆陆续续搞了一个多月了,不过其实也就一开始的几天和最近几天在好好搞。

前两天把 Set、Map 写完的时候,突然发现我还是完全没有理解 STL 的迭代器所玩的花样。其中的类型萃取我看出来了,其余的都没有。我这里的迭代器是很土的,每个容器自顾自的(尽管很“巧合”有几个一样的接口)。

String 类我还想继续拓展功能。不过没想好的就是要不要有 Format 功能:如果没有,使用上或许偶尔会有一点点不方便(如果也不提供数值和字符串相互转换的函数的话);如果有,基本上不会去手工解释 %d、%s 之类的了,那么势必要用到 sprintf 之类的东西了,那么我的零依赖的设想就落空了。

MultiSet 和 MultiMap 有点儿倾向于不提供了,真有需求的到时候去 Set<List<T>>、Map<List<T>> 好了。

文件在此,点击下载(还没测试仔细,可能有不少 Bug,甚至可能某些函数有语法错误没测到,这点请谅解)

 

请各位给点意见~

posted on 2009-11-09 22:01 溪流 阅读(2128) 评论(32)  编辑 收藏 引用 所属分类: C++

评论:
# re: XL Library Preview,诚征指点 2009-11-09 22:57 | CornerZhang
既然是在写自己的容器类和String,又何必考虑stl样的接口。
是个DynamicArray时像个DynamicArray的样子
是个StaticArray时像个StaticArray的样子
是个Stack时像个Stack的样子
是个KDTree时像个KDTree的样子
是个HashTable时像个HashTable的样子
何必要考虑,stl中的那种iterator, begin, end之类,毕竟每个容器的使用方式不一样,当然接口定义的需求就不一样

至于String的格式化输出,是用语言本有的多参数,自己实现一个printf就行了!  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-09 23:22 | expter
这种练手 很不错,,支持  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-09 23:41 | lo
不想printf 直接抄ctr库里的代码就行了  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-09 23:43 | OwnWaterloo
1.
"尽管很“巧合”有几个一样的接口"
stl组件之间的通信就是通过这种"巧合"。


2.
为什么要零依赖? 这个需求很怪……

想练习发明轮子的心情可以理解……
再给你提供一个练习而又不是重复发明的东西吧:
将printf和scanf的解析过程抽象出来。
这样,string就只是管理内存就可以了。
format交给别的地方去做。
相互之间保持正交。

这样,format的src和dst可以是FILE*,socket, 以及任何可扩展长度的顺序结构,比如各种string,std::vector,std::deque,std::list。
不要将format的功能"埋葬"到你那个string中,太可惜了。将它剥离出来。


还有stl中的反向迭代器其实是有单独一个模板的,在<iterator>中,通常不需要自己手工编写。
你可以重复发明它一次,然后应用于你的各种容器之上,而不是重复发明多次。



3.
至少std::multiset<T>和 std::set<std::list<T> > 或 std::set<std::vector<T> > 语意都是不同的。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-09 23:57 | OwnWaterloo
再给你说个玄乎一些,不那么实际的理论吧……

一种设计倾向是"添加直到无法添加"。
一种设计倾向是"减少直到无法减少"。

我倾向于后者。也相信你写过一些代码之后会对前者感到反感。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 00:16 | 溪流
@CornerZhang

是。追溯到很久以前,其实我发明轮子的最初动力是 STL 里的 string 太难用。我就是想提供不一样的使用方式。也排斥迭代器。最早写的是一个类 vector 的东西,就不提供迭代器,照样可以用得很爽。到要写 List 的时候,就不行了,如果要不暴露结点,那么必须有类似迭代器的一套东西了。于是回过头来想想 STL 的这套方式,觉得倒真不错。所以又反过来学着它了。  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 00:17 | 溪流
@expter

谢谢支持!  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 00:18 | 溪流
@lo

呵呵,虽然其实一样,不过也算个手段~  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 00:31 | 溪流
@OwnWaterloo
1、这种巧合就是你先前说的GP中的“契约”吧。我心里就是有道坎跨不过去,觉得没法在语法层面显式呈现这个契约,,,唉

2、关于零依赖
我知道很多东西不可能做到零依赖,或者做到零依赖代价很大。
只是我的设想是,在一套东西里,有一个基础部分,它只和语言特性有关、只有逻辑意义,这一部分要保持零依赖。其它实现各种实际功能的东西,可以有选择的去依赖别的。如果把 Format 看成 String 的一种扩展功能,我本身在写 String,为了实现 String 的一个功能,去使用了现有库的这种功能,那我不过在做包装而已,而不是写东西了。

也许 Format 也算不上纯属 String 的功能,你后面给我的启示看上去很有意义……

3、
multimap 确实不是这个语义,可能可以勉强凑合吧。只是我想不到非用 multimap 的场合……

我原本想搞个
template <typename IFirst, typename ISecond>
class ComplexIterator

想先 ISecond ++ 上去,到 End() 了 IFirst++,ISecond=IFirst->Begin()

然后直接 typedef ComplexIterator<typename Set<List<T>>::Iterator, typename List<T>::Iterator> MultiSet::Iterator

后来发现需要迭代器自己确定自己是否是 Begin,于是暂时放弃

关于反向迭代器,以及正向的,我一开始想各个容器能否以某种形式提供某一个 ++,-- 的机制,然后统一实现 Iterator,但是想不好用怎样的形式……



  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 00:34 | 溪流
@OwnWaterloo

添加到无法再添加 我并不十分支持。
但是 减少直到无法减少,我也不尽赞同。我觉得 STL 里的东西,就是这种状况,要什么没什么,只能根据已有的少得可怜的东西去凑出来,换句话说,要用到日常开发中来,经常需要自己再包一层。

我觉得还是以方便使用为原则合理添加一些可有可无的东西比较好。。。

——目前的观点,呵呵
  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 01:06 | OwnWaterloo
@溪流
1.
这是C++的缺陷…… 当初可能没想到模板会被这么用,所以模板的功能其实还比较弱。
即使比较弱,也比java和C#强大,它是真正的代码生成器……
C#的模板有一些约束,java的根本就是垃圾……
所以,模板还是很复杂的……

更本质的说,其实体现的是一种ducking type,以单一函数作为组件之间交互的接口,而不是整个类型。ruby、python、lua这种动态类型语言都支持ducking type。而C++的模板只支持编译时的ducking type。
C++社区给这种使用方式取了一个新的名字,叫concepts……

ducking type可能属于新东西,而且很可能是意外产物(比如C++、python、lua;ruby好像是设计之初就考虑到这种用法),所以没有提供专门的、显示的通过短小的代码(比如interface声明)就可以表达的方式。只能通过文档了……

说穿了,那些抵触这种设计的,要么是偷懒不想看文档,要么是已经学会OO就不想学任何其他新事物,要么就是理解能力不够……

心里疙瘩放下吧……
1.1. 虽然没有专门的语法支持,但语言还是会检查的,比如C++编译时出错,其他3个语言运行时出错。
1.2. 比如python标准库中,序列就没有单独的size()成员。所有的序列都通过len得到长度。已经开始向这种思想靠拢了。
1.3. stl也这么多年了……



2
我对0依赖的看法不是"难",而是"通常没有必要"。
应该尽可能复用已有的优秀的代码。
尽可能向已有的,还过得去不算垃圾的标准靠拢,而不是自己独立发明一套,结果在实际应用中无法融合。

当然,这和练习编程技巧相抵触……
所以我想提出一些建议,既可以练习;并且练习的结果是可以真正派上用场的。

比如,你可以考虑实现这样一个函数:
int vprintf_parse(void (*handler)(const char* s,void* context),void* context
const char* format, va_list arg );

按vprintf的标准去解析format与arg。每处理完一个%就调用handler一次。
由handler去考虑将s"输出"到哪里。
这样的话,vprintf_parse就可以用于很多很多地方:传递不同的hanlder给它就行。
当然,你也可以用它来实现string.format。 但一定要将vprintf_parse暴露出来,否则窝在string.format中太暴殄天物了。


更进一步…… 还可以提供一些让客户代码扩展的机制,让它自己定义%后的转义符,以及处理方式。



3
我的意思是,这种方式是行不通的。
你要插入的元素是T吧?
std::set<std::list<T> > 元素是 std::list<T> 哦, 不是T了。
比较也是按std::less<std::list<T> >比较,而不是T。

不管multiset的底层实现是rbtree还是rbtree+list,都需要真正定义一个类,将底层实现的接口adapt一下才行。仅仅typedef是不够的……

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 01:29 | OwnWaterloo
@溪流
你就没领会后者的精妙~_~

后者的精妙之处在于:增加的东西不可能轻易拿掉 —— 否则会破坏旧有代码。
反之,加入原本不存在的东西是很容易的事情……

如果某个功能确实很常用,你可以再得到这种反馈之后将其作为aux添加进去。
反之,如果一开始就有某个设计糟糕的功能存在了,你得到反馈之后也很难将其去掉,并且还要一直维护这个糟糕设计…… 很恶心


我很欣赏lua的设计,将lua库分为core和aux两个层次,而不是混淆在一起。
加上client,总共就是3个层次。
保持core的精简对维护是非常重要的。
aux本身实现就不难,多提供一些对维护影响不大。是否提供完全看需求 —— 这是否是很常见的一种使用方式。

以unix的机制、策略论来说:core就仅仅提供机制,aux将一些常用策略打包,方便client使用。


设计之初就要考虑如何将core精简到最小。这对日后维护是非常有帮助的。
一种精简的大方向就是仅提供机制。比如vprintf_parse,就是一种机制。

客户会如何使用它?就是策略了。客户可以非常多的方式(dst不同)使用它。
可以预见:将string作为dst是一种很常见的使用策略。
仍然可以先不提供它…… 万一这种估计错误了呢-_-
如果估计正确,大量代码的使用者向你抱怨"为什么不提供string.format?",你再提供也来得及~

其他的精简方式…… 再慢慢总结吧……

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-10 08:24 | 溪流
@OwnWaterloo
这点有点明白了,一开始多了,而以后必须向下兼容,于是肩上的包袱就永远卸不下来了,是吗?  回复  更多评论
  
# re: XL Library Preview,诚征指点[未登录] 2009-11-10 14:45 | foxriver
"这点有点明白了,一开始多了,而以后必须向下兼容,于是肩上的包袱就永远卸不下来了,是吗?" 支持+赞同KISS原则。

真正0依赖意义并不大,自己写的程序难免有BUG,要完善势必花很多精力,时间,你真的觉得自己花上几年完善一个LIB是值得的?如果不是研究院,还是按照具体工程来扩展自己的类比较实在些。

程序写多写大,最大的感受是以前程序一切速度优先,有些看起来杂乱的语法,现在都会用简单慢速明了的语句去表达。。速度越来越不是重点了,结构清晰才是程序长久生命之源。  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 14:57 | zdhsoft
建议使用code.google.com上面开源
我的也在写,不过我写的已经在我的很多项目中使用了。面对标准的STL的string,再实现一个实用的string是非常有必要的  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 20:04 | 溪流
@zdhsoft

google那个规则怎么样的?别人可以改我的吗?  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 20:35 | OwnWaterloo
@溪流
别人只能check out不能commit。除非你授权。或者把补丁发给你。
用git吧,趋势……

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 22:09 | 梦芭莎
虽然其实一样,不过也算个手段~  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 22:39 | 溪流
@OwnWaterloo

就是传说中可以打包提交的?
我以前有一阵子一直在找代码托管,可惜都开源的,google code 只允许有一个私人项目。。。可我哪有那么多东西能拿出手呀,,于是,只好在自己机器搭了个svn。。  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-11 22:45 | OwnWaterloo
@溪流
一个google帐号好像可以建5个项目。每个项目好像可以有2g空间。但是只能放和代码相关的哦,否则被发现了google帐号会被禁用。

每个项目可以传文件上去,比如打包好的代码。

还有一个repository。原来只提供svn的,后来加入了hg。不过没有加git。
svn的repository就是上面说的那样,拥有者才有commit权限以及授权的权限。
普通用户只有check out的权限。要么只看不改,要么找你要授权,要么给你发补丁。


自己机器上做一个svn repository的事…… 我也这样干过……
所以很痛恨svn,所以打算用git。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-13 17:01 | OwnWaterloo
有个重要的地方忘记说了……
虚析构函数是不需要的

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-13 21:59 | 溪流
@OwnWaterloo

放着让好事者(也就是将来某一时刻的我自己)去继承...  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-13 22:03 | OwnWaterloo
@溪流
一个虚函数都没有,继承来做啥?

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-13 23:20 | 溪流
@OwnWaterloo

定义一个相似的类?  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-13 23:57 | OwnWaterloo
@溪流
何时需要虚析构函数?当通过父类类指针delete子类时。
String这种类型不应该作为基类,也不应该被多态使用,所以虚析构函数是不必要的。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 12:32 | 溪流
@OwnWaterloo

一般来说,虚析构函数用于告诉使用者该类“可继承”,是吗?既然这里没有什么不可告人的秘密,那么就随他去好了。(当然,如果有人真要继承,则必须了解里面的运作机制。这是他自己的事。)这样理解可以吗?  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 15:26 | OwnWaterloo
@溪流
我再使用上面的观点狡辩一次吧……

1. 非虚析构
如果、假设、万一真的出现了这样的需求 —— 几乎不可能 —— 需要被继承而且以父类指针delete子类。

还可以这样:
class StringDerivable {
String s_;
public:
virtual ~StringDerivable();
};
并从StringDerivable继承。


2. 虚析构
如果一开始就使用虚析构,无论是否需要被继承 —— 几乎不可能 —— 用户都必须承担一个虚指针的代价。


非虚析构对于不需要继承的客户来说,没有额外的代价。对需要继承的变态客户来说,也有办法实现 —— 多一个步骤。
这是贯穿整个C++语言设计的一个重要原则:0代价原则。
虚析构无论客户是否需要,多态的代价都必须承受。


设计不单单只是你做了什么,也包括你没有做什么。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 19:11 | 溪流
@OwnWaterloo

这么说来好像也很有道理...发现OOP的影子被你砍得一点不剩了,哈哈  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 19:15 | OwnWaterloo
@溪流
哈哈,被你看出来了……
我就是一anti-OOP者……

其实也不是完全是这样。只是太多人将OOP当作万能药了。
以为OOP的设计,就一定是好的设计。OOP成分越多,设计越好。
我反对的是这种态度。

  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 19:18 | 溪流
@OwnWaterloo

其实我个人基本不怎么会去继承,也基本不会去多态,我喜欢用组合。但是难保别人不会,所以我经常随手丢下虚析构函数
  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-14 19:20 | 溪流
@OwnWaterloo

那个反向迭代器,是不是可以把正向迭代器当模板参数,在++里让正向迭代器--,在--里让正向迭代器的++,正向迭代器的end状态当成反向迭代器的end状态?  回复  更多评论
  
# re: XL Library Preview,诚征指点 2009-11-17 20:21 | OwnWaterloo
@溪流
某人犯傻去继承string,那是他的责任。
没有必要为了避免他的错误,让所有人让步,承受虚指针的开销。

反向迭代器,我猜的也是这么回时。
不过具体没看。
去看看代码吧,应该不多。
可能会有一些细节,大致想的时候会被忽略。

  回复  更多评论
  

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