posts - 16,  comments - 34,  trackbacks - 0
共10页: First 2 3 4 5 6 7 8 9 10 
re: Dictionary的囧状 OwnWaterloo 2009-10-15 23:14
C#的template能做什么我不太清楚。

C++支持编译时的ducking type机制。
抛弃这种强大的抽象机制不用, 转而在C++这种暂不提供GC的语言中使用接口来作为数据结构之间的纽带 ……
所以…… 我说这不是C++的style ……

还有一些小地方。 比如main 的返回类型是int, 而不是C#中的void。
以单下划线接大写字母开头,以及以双下划线开头的标识符在C++中是被保留的。
最好不要将C#中的那些习惯带到C++中来……
用Type, Type_, 别用_Type。

这些被保留的标识符不会被永远保留。 _Bool, _LongLong, _Complex已经出现。



http://www.cppblog.com/Streamlet/
这位同学, 和你在做类似的事情, 也遇到了类似的问题。
你可以参考参考……
re: Dictionary的囧状 OwnWaterloo 2009-10-15 22:52
我说具体一点吧……
如果用GP(代码一切从简):
 
template<typename T>
class /*array*/list {
    T *first,*last_;
public:
    typedef T* iterator;
    typedef const T* const_iterator;
 
    iterator begin() { return first_; }
    iterator end() { return last_; }
    const_iterator begin() const { return first_; }
    const_iterator end() const { return last_; } 
    // ...
};
 
要迭代一个容器:
list<int> l;
for ( list<int>::iterator first = l.begin(), last = l.end(), first!=last; ++first)
    visit_element( *first );
 
而你遇到的问题就是:
list<pair<key,value> > d;
如何得到一个迭代器, 仅仅访问key部分, 而不访问value部分。
 
template<class It>
class project_first {
    It it_;
public:
    project_first( It it ) : it_(it) {}
    typename std::iterator_traits<It>::value_type::first_type&
        operator*() const { return it->first; }
    // 再实现 ++, -- +n 等操作...
};
 
for ( project_first first = d.begin(), last = d.end(); first!=last; ++first)
    visit_key( *first );
 
 
如果d是 list<tuple<key,value> > 类型, project_iterator还可以做得更范化一些。
 
没有虚函数调用,没有动态内存分配。
并且,和stl的算法,boost的算法,以及其他C++组件合作良好。
re: Dictionary的囧状 OwnWaterloo 2009-10-15 22:30
@Lyt
你也发现问题了不是? 内存不好管理。

如果你用GP的思想去实现Dictionary, GetKeys可以很简单,并且很高效的实现。
用OOP? 就等着承受虚函数开销以及内存管理的困扰吧。。。
然后,你又会为此去写智能指针, 写内存池, 写锁 ……

你可以把这些当作练习…… 但这不是C++的style ……
re: Dictionary的囧状 OwnWaterloo 2009-10-15 13:43
1.
error C2682: cannot use 'dynamic_cast' to convert from 'const Lyt::Collection::List<_Type> *' to 'Lyt::Collection::IList<_Type>
 
明白了吗?
 
2.
IDictionary.h  include  List.h
Dictionary.h include IDictionary.h
相互包含在哪?
 
 
 
C++不是这么用的……  被C#熏昏头的同学……
玩模板,就不要用vc6 ……

拷贝构造函数的正确写法是:
Test(const Test<T>& );
@陈梓瀚(vczh)
需求是iterator类型推导iterator解引用后的类型?
嘿嘿,真的不能吗?

#include <iterator>
MyIt it1,it2;
typename std::iterator_traits<MyIt>::value_type // 这就是你要的
v = *it1;

// 除此之外还有其他几种类型信息。
typename std::iterator_traits<MyIt>::pointer p = &v;
typename std::iterator_traits<MyIt>::reference r = v;
typename std::iterator_traits<MyIt>::difference_type d
= std::distance(it1,it2);

typename std::iterator_traits<MyIt>::iterator_category tag;
tag决定了iterator能做什么。

algorithm中的所有需要iterator的算法,都和容器完全无关。
和iterator相关的类型信息都是这么取得的。
自然不存在M*N(M=算法的数量,N=容器的数量)的说法。
而是M(M=算法数量)。


给你举个例子可能比较明显:
需要value_type的算法我一时还想不出来……
来个其他的需要difference_type的意思意思:
template<typename InIt,typename T>
typename iterator_traits<InIt>:: difference_type // 返回类型
count(InIt first,InIt last,const T& v) {
typename iterator_traits<InIt>:: difference_type c = 0;
for (;first!=last; ++first) if (*first==v) ++c;
return c;
}



这是GP的类型推导方式 —— 嵌入类型。这用法漂亮吗?


实现这一魔法的工作:
iterator_traits只需实现一次。
各个容器其实不需要做什么工作。
工作在每一个iterator类型上,它必须有这几种嵌套类型。
当然,iterator头文件中提供了std::iterator, 可以继承自它而得到这几种嵌套类型。
不过我一般喜欢自己写,继承可能会影响空基类优化。
多吗?


而且,有一点OOP是办不到的。 所有的iterator都不需要有一个"基类"。
T arr[size];
&arr[0] 类型是T*, 是iterator,而且还是random_access。但是它的基类应该是什么才好呢?
它只有4字节。OOP就那个vptr就4字节了,加点数据再加上padding,8字节至少。



"反而vector<int>也想要支持的话,你会发现所有的容器都要写一遍……"
这是什么需求? 需要所有容器都写一遍? 说出来看看?
re: 二分查找学习札记 OwnWaterloo 2009-10-10 14:16
@唐僧

mix没有右移?
不过嘛…… 右移是除法的子集…… 没有也挺合理的…

嗯,在你介绍之前, 我完全不知道有uniform这回事……
高爷爷的书有时间一定得去看看……

sgi的stl中有非公开的红黑树实现。4中关联容器其实是红黑树的adapter...
就像std::stack,queue,priority_queue一样…… 尴尬……

我觉得吧,二分只要写正确就行了…… 复杂度肯定是lgN的。
lgN已经很猛了…… 常数稍微差点也坏不到哪去…… 优化是无底洞……
不记得在哪本书上看到过这么一句话"只需要让软件足够快"
re: 二分查找学习札记 OwnWaterloo 2009-10-09 15:27
@唐僧

对对,我忘了说了,如果查找目标不在区间中,2-way肯定比3-way高效。


-------- 关于 uniform --------
"因为”动态“寻找二分点要比预先生成静态二分点多增加很多运算,而且这种增加是随着搜索空间的增大而增长的(这句话我不太确定,直觉上一倍左右的差距)。"

上次我就说了嘛, 关于uniform这个词。
如果只从源代码(维基上的那份)入手uniform优化的实质就预处理一个delta,每次免去除法运算。
不管高爷爷是怎么一步一步想到这里来的(那本书我没看……), 源代码中已经不怎么能体现出来了。


但实际上,效果并不一定很显著, 我瞎猜的啊。
因为除数是2, 实际上并不需要做除法, 只是移位。

-------- 注意 --------
一次移位的写法有(但不限于)以下2种:
int m = lower + ( (upper - lower) >> 1);
int m = lower + (upper - lower) / 2u; /* 这个u很关键 */

第1种使用sar,第2种使用shr。 只要upper>=lower, sar,shr都是正确的。

而楼主和饭中淹使用的代码
int m = lower + (upper - lower) /2;
会被翻译为3条指令。
饭中淹的代码还没有考虑溢出的情况。

-------- 注意完毕 --------


那么,不使用uniform的方式, 每次计算middle的消耗就是:
减法,移位,加法。
lower, upper都是缓存在寄存器中的。
具体可以见上一篇文章的评论中我发的汇编代码。


而uniform的方式:
i += delta[++d];
大概就是
mov r1, delta[r2(d)*4+4]
add r3(i),r1

一次加法;一次内存访问;d需要多占用一个寄存器(否则更慢),++d还需要要一次加法。


这个静态存储区的内存访问很讨厌。
非uniform方式lower,upper所在页面肯定是被加载的,因为它们是函数参数,处在栈顶。
uniform的方式,delta就不一定在页面中,有可能被置换出去了。这种情况一旦发生,说不定效率就是数量级的下降,和非uniform完全没得比。
并且,这种情况,通过这种小的测试程序还不一定能测得出来 —— 怎么模拟一个大的、长期运行的、偶尔调用二分查找的程序,它已经将delta所在页面置换出去了?

从本质上来说, uniform的方式的一个直接缺陷就是造成数据的局部性不如非uniform的方式。而且这缺陷是无法修正的。 缺陷造成的影响可能会被uniform的其他优势所掩盖, 但缺陷始终存在。


当然, 上面全都是臆测,臆测。 需要实际测试一下。
我觉得只要非uniform的注意移位问题, 效率应该不会比uniform的差太多。即使不缺页,内存访问也是比较伤的。
一旦缺页,我觉得uniform就没什么可比性的了。



ps:
关于两种方式的对比:
1. 增加happy path的效率,不管unfortunate的效率
2. 兼顾所有情况的效率

除了uniform和非uniform,我还想起一个……
不知道hash表和红黑树算不算这种对比的例子之一……
re: 二分查找学习札记 OwnWaterloo 2009-10-08 16:23
@饭中淹
2-way和3-way的对比,通常和输入有关。
3-way一旦命中,就可以提前退出循环, 但每次循环要多一次compare。
2-way总是执行lgN次比较后才退出循环,再测试是否命中。
严格计算需要概率统计知识。
这种蛮力测试我也做过, 3-way通常表现得比2-way更优秀。


但2-way有一个决定性的优势,是3-way无法相比的。
"存在相同键的有序区间中查找键属于某个区间的所有值",对这种需求,2-way可以继续保持O(lgN)的复杂度, 而3-way会退化至O(N)。


stl中使用2-way而不是3-way,可能就是基于这种考虑吧 —— 即使在最坏情况下也要足够好, 在最好的情况也不算坏。
@溪流
我out了……

boost 已经有 intrusive 容器的实现了……
http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html

我这里的boost版本非常老…… 1.33…… 所以没发现……
上上面关于interface和concepts的比较, 是因前不久给一个项目经理解释ducking type和以函数为单位的抽象形式, 但没成功……

现在算是想得比较清楚了, 但好像没表达清楚…… 那么多文字, 我自己都不愿意看第2遍……


整理一下:

对单个"契约"的设计而言, 通过interface或是concepts没有什么区别。
并且interface比concepts更广为人知。
所以当时怎么都没能说服他……

interface的劣势(也就是concepts的优势)体现在"如何拆解与组合契约"上。
如何拆分,设计interface, 是门学问。
那几个方法通常是应该整体提供的?
这就是interface的劣势的本质 —— 它总是要将若干方法"打包"到一起才可以。
极端情况, 只含有一个方法的interface也很常见, Dispose所属接口就是。

interface更麻烦的地方在于组合。
当一个f需要若干种interface的功能时, 要么必须将一些interface继续"打包", 形成一个新的, 要么运行时检查。


而concepts打从一开始, 就仅仅依赖所需要的东西, 不需要"打包"这一过程。
拆分和组合是自由的。
从某种程度上来说, 这也容易造成晦涩的设计。
但什么设计不是学问呢…… interface的设计同样需要经验。


concepts相比interface来说, 限制更少, 也更灵活。
这种灵活性是本质上的 —— 因为不存在"打包"这一限制 ——是不以现实编程中是否需要这种程度的灵活性,以及这种灵活性是否会被人们普遍接受而转移的。


灵活的事物通常难以掌握, 如果现实编程中不需要, 人们不理解、不接受, 也只能算是当前条件下的劣势 —— 对太多数人来说晦涩、复杂, 无法被广泛使用。
如果哪天人们接受了呢?



还有一点, 上面说的GP和OO、OOP概念太广泛。 OO、OOP的定义到底是什么, 各有各的说法。
所以改为 concepts 和 interface( in java and C# )的比较, 比较准确。
并且某些其他支持OO的语言 —— 现在是个语言都要说自己支持OO, 不支持的也要改为支持... ——中, 是不需要interface这种"契约打包器"的。



楼主啊, 我自我感觉比较好的建议, 就只有建议你实现一套侵入式容器(包括树式堆)而已, 既锻炼了技巧, 又不陷入"重复发明轮子"。

其他的, 都是自说自话 …… 不必想太多-_-

因为做上这行了,没什么时间总结平时的一些零散想法。
如果是中学做习题, 会因为做着做着, 就累了 …… 就转而"总结一下吧,比单纯做来得有效, 同时休息休息"。
而写代码…… 是没有累的感觉的…… 就会一直写下去……
只有在讨论的时候, 才会想去总结一些东西。
把你的blog评论区当吐槽了…… sorry ...
@溪流
嗯嗯, 你说得很对。

假设多态的使用者与多态抽象之间的层面叫A, 还有多态提供者与多态抽象之间的层面叫B。
OOP中的A和OB很相似, 只有B是新加的内容。
而GP中, 无论A、B, 都是新鲜内容。

所以这样比较是不公平的~_~


我至今没有完全明白rbtree的实现, 但不妨碍我使用map和set。
对一般的内建类型, 或者符合STL规范的值类型, 直接使用即可。
如果需要放自定义类型,需要了解的就是key_compare和严格弱序。
也不算多吧? OOP同样离不开比较准则, 只是key_compare换成了ICompare。
如果还想高级一些, 还可以去了解allocator, 那是篇幅更长的一套规范。
OOP没见有这功能, 不比较了。

boost中有一些库, 我知道实现原理, 但不知道对付各种编译器的trick。
还有一些隐约知道原理, 更多的是不知道。
boost的源代码我一份都没看过(坚持不下去…… 确实很丑陋, 但很多代码都是为了对付不同编译器而已)

举个例子, any。 即使没看源代码, 我也知道这个库应该在何时使用, 以及如何使用 —— 因为我看了文档…… 不多的。 interface也需要看文档的吧?

但就是这么一个小东西, 使得我可以通过一个参数传递任何东西。
并且不再需要继承自某个基类……

"一切皆为Object" —— 我觉得这是很可笑的事情。
Finder.find?
p1.fuck(p2); 还是 p2.fuck(p1);? 3p呢?
太可笑了……

而且在java和C#中实现free function其实并不难, 只是它们固执, 不愿意加入而已。

OOP根本就不是一种纯粹的编程范式。 不结合其他范式, OOP根本就写不出程序来。 不知道那些追求所谓"纯OO"的家伙是怎么想的 ……
在我眼里, OO只有oo analysis, oo design, oo programming只是oo design而已。 实现design时, 是命令式的。
至少对java, c#的OO来说是如此。

不是我一人这么说, 你还可以去看看《冒号课堂》。


上面有点小错误, 纠正一下:
C/C++中本来就可以以单一参数传递任何东西……
any 是使得这一作法类型安全而已。
当然, 既然使用C/C++写代码, 不同与那些保姆语言, 程序员自己就要对类型安全负责。 所以any通常是为了堵住那些对类型安全尤为重视的人的嘴而已。
我还是更喜欢void* ...

真不知道那些成天叫嚣着类型安全, 却视generic加入java是一种退步, 使得java不纯粹的人是怎么想的……
难道"不犯错", 比"犯了错总有人补救" 更重要?
OO为什么被人吹捧?
可以说, 是它开创了一个历史,人们开始普遍采用 "对抽象的、多态的事物编程"。
 
在那之前, 无论是OP还是OB, 都只能完成模块化, 方便分工开发与测试。很少使用多态技术。

OB编程(OP就省了…… OP->OB依然能完成一定复用,但方式不同):
void f_ob(T v) { v.f(); }
 
f是针对一个具体的T进行编程。
f的行为和T的行为紧紧绑定在一起。
f想要表现出不同行为, 必须要T表现出不同行为。
但无论T如何改变,T和f都只具有一种行为,最后一次改变后具有的行为。
 

OO编程:

void f_oo(I& i) { i.f(); }
 
f现在的行为, 仅仅与i所表现出的契约绑定在一起。
而i可以有各种各样的满足契约的方式
这样的一大好处就是, 对不同的D : I, f可以被复用
得到这一好处的前提就是, D 满足 I与f之间的契约。
 

GP编程:
template<typename T>
void f_gp(T v) { v.f(); }
 
同样提供了多态行为:以不同的T带入f, 就能得到不同的行为。
使得f能被复用。STL中的组件, 大部分是通过这种方式被复用的。
并且,STL组件之间, 也大部分是通过这种方式复用的。
 

1.
无论是GP还是OOP都是组合组件的方式。
它们(典型地)通过concepts 和 interface来抽象出组件多态行为。
对这种抽象事物编程得到的结果(函数/类模板,包),可以被复用(软件工程一大目标)。
-------- -------- -------- -------- -------- -------- -------- --------
 

上面提到契约。
无论是OP、OB、OO、GP, 组件间要能协同工作, 都是需要契约的。
 
OP:
free 可以接受空指针, 而printf 不行。
前者是free对调用者定下的约束, 后者也是printf对调用者定下的约束
—— 要使用我就必须这样做。
 
malloc 失败返回空指针, 而new 抛异常, 否则返回可用动态内存。
这是它们对调用者的承诺。
—— 使用我, 你能得到什么。

T* p = new T;
if (!p)  这种代码只在古董编译器上才可能有意义。
 
"加上NULL判断更好" , 也只有"C++方言"的古董学者才说得出来。
 
new[] 要 delete[] , new 要 delete, 这也是契约。
"因为char是基础类型,所以可以new[] , delete", 只有不懂软件契约的白痴学者才说得出来。
 

OB:
要将CString s 转换为 TCHAR*, 一定要用 s.GetBuffer  而不是 (TCHAR*)&s[0]
CString 的约束。
 
basic_string.c_str() 一定以'\0'结尾, 而data() 则不是。
basic_string  的承诺。
 

OOP:
我用的OOP库、框架不多……  举不出什么例子。
但它的契约和通常OB"非常类似" : 完成什么、需要调用什么、调用顺序、 参数合法性。
 

GP:
GP总共有哪些契约形式, 我总结不出来。
但至少有一条 —— 它不再对T有完全限定, 而只作最小限定
 

还是上面的代码:
void f_oo(I& i ) { i.f(); }
D d;
f(d); // 要求 D : I

template<typename T>
void f_gp(T v) { v.f(); }
要求  v.f(); 合乎语法 :比如, 它既可以是non-static member function, 也可以是static member function。
并且仅仅要求这一点
 
 
2.
契约是普遍存在的, 不仅仅是GP、 其他范式都有。
它是合作与复用的前提。
-------- -------- -------- -------- -------- -------- -------- --------
 
 
3.
为什么GP饱受争议, 而OO没有?
我觉得, 是因为从OB到OO过度比较自然
 
 
要求一个I需要怎样, 一个I需要使用者怎样的时候,
通常也会有类似的需求 —— 要求一个C怎样, 一个C需要使用者怎样。
注意, 这只是 client 与 I, 以及 client 与 C之间的契约。
在这个层面上, 不需要学习新的思想。
而下面会提到OO引入的新的契约形式。
 

而GP的契约形式, 都是一些全新的形式
其中最主要的形式是: T 是否具有一个叫f的函数(操作符也可以理解为一种调用函数的方式)。
在C++中, 还有必须有某个名字的嵌套类型, 通过T::f强制static member function等形式。

OO比较流行、支持OO的语言比较多,是目前主流。
C++,Java,C#的开发者总共占了多少比例?
 
GP支持的语言其实也多。
但抛开C++(或者算上C++用户中理解GP的人)怎么都比不上上面3个巨头。
 

批评自己不熟悉的事物是不严谨的。
遇见STL编译错误, 要么就去学习GP的方式, 要么就抛弃STL。
抱怨STL是种傻逼行为 —— 明明是自己不会用, 要怪只能怪自己。
 
 
-------- -------- -------- -------- -------- -------- -------- --------
4.
如同GP、 OO同样需要学习、 需要文档、 否则会充满陷阱
 
上面提到的client 与 I的契约形式通常和 clinet 与 C之间的形式相同。
使得OO的一个方面可以"温固"。
 
而client 与 D之间的契约? 这个层面不"知新"是不行的。
并且这个层面上的契约常常是出bug的地方 —— 因为这是语法检查不了的, 必须有程序员自己去满足语意。
 
举个例子 :
看见一个虚函数,它是否可以被覆盖? 覆盖它的实现是否需要同时调用基类实现?
除非是约定俗成的一些情况, 比如 OnNotify、OnXXXEvent这种名字比较明显。
其他情况, 不去看文档, 依然是不知道的。
 
 
我刚刚就犯了一个错。
python 中 继承HTMLParser , 覆盖__init__ 时, 必须调用基类实现。
我确实不知道构造函数也可以被完全覆盖……(原谅我…… 第1次使用python……)
在C++中, 基类的构造函数是无论如何都会被调用的。
 
 
我没有调用基类的__init__, 然后报了一个错。
好在报错清晰, 源代码的位置都有, 源代码也可见, 源代码也清晰。问题很容易就找出来了。
 
 
如果
4.1.
它不是构造函数, 只是一个普通的虚函数?
名字也看不出什么蹊跷?
 
4.2.
文档也没有记载是否需要调用基类?
(HTMLParser中的文档没有说要调用__init__, 这应该是python的惯例, 所以就没有记载了)
没有严格的错误检查?
没有完整的、信息丰富的call stack trace?
等发现错误时, 也许都离题万里了。
 
4.3.
没有清晰的源代码(其实到了要查看源代码的时候, 已经是……)?
 

这些问题在OO中同样是存在的, 只是它没引起编译错误, 或者说编译错误比较明显, 容易修改。
而更多的语意检查, OO中 client 与 D之间的层次, 依然要靠程序员的学识 —— 主要是查阅文档的习惯。

对比GP
4.1之前的4.0(OnNotify, OnXXXEvent之流), 同样存在一些约定俗成。
 
对4.1, 同样是查文档。
 
对4.2, 没有文档同样犯错。
C++中, 一部分错误可以提前到编译时(C++只在持编译时支持ducking type)
 
对4.3
同样需要去查看源代码。
 
GP的代码比OOP难看? 
同上面, 只是因为不熟悉、不信任、不需要这种抽象方法, 这些契约的形式。
 

STL中的契约形式其实并不多。
[first,last) 左闭右开区间;
iterator的几个种类;
(adaptable)binary(unary)_function;boost只是将其提升到N-nary,还省去了adaptable的概念;
相等、等价、严格弱序。
多吗?
 
而且, 我不觉得为了比较要去实现一个IComparable 有何美感可言……
 
 
-------- -------- -------- -------- -------- -------- -------- --------
5. 这些新的契约形式、 抽象方式, 有没有其优势
当然有 —— 最小依赖带来的灵活性
上面也提到, GP只依赖于其需要的契约, 对其不需要的, 通通不关心。
 
 
现在详细解释上面
D d;
f_oop(d); // D : I
 
T v;
f_gp(v);    // v.f
 
为什么后者比前者灵活。因为后者只依赖所需要的东西。
 
5.1
template<typename T>
void f123_gp(T v) { v.f1(); v.f2(); v.f3(); }
 
可以使用
struct T123_1 { void f1(); void f2(); void f3(); }
struct T123_2 { void f1(); void f2(); void f3(); }
 

void f123_oop(I& i) { i.f1(); i.f2(); i.f3(); }
必须有一个
struct I { virtual void f1(); virtual void f2(); virtual void f3(); };
然后是:
D1 : I; D2 : I; ...
 
 
5.2
如果现在需要实现另一个函数, 它对T的需求更少 :

template<typename T>
void f12_gp(T v) { v.f1(); v.f2(); }

T123_1, T123_2 可以使用
 
新增一个:
struct T12_1 { void f1(); void f2(); }
依然可以使用
 

OOP就必须重构了:

struct I12 { virtual void f1(); virtual void f2(); };
struct I123 : I12 { virtual void f3(); }
struct D12 : I12 {};
 
5.3
再看 :
template<typename T>
void f23_gp(T v) { v.f2(); v.f3(); }

T123_1, T123_2 依然可以使用
T12_1 不行。
 
但新增的
struct T23_1 { void f2(); void f3(); }; 可以使用
 
 
OOP又必须重构:
总体趋势是这样的, OOP需要极端灵活的时候, 就会变成这样:
一个接口, 一个函数
struct I1 { virutal void f1(); };
struct I2 { virutal void f2(); };
struct I3 { virutal void f3(); };
现在接口设计是极端灵活了。

但使用接口时, 依然逃不过2种都不太优雅的作法:
1. 接口组合
struct I12 : I1, I2;
struct I23 : I2, I3;
struct I31 : I3, I1;

2. 接口查询
不组合出那些中间接口, 但运行时作接口查询:
void f12(I1* i1) {
  i1->f1();
  if (I2* i2 = dynamic_cast<I2*>(i1) {
     i2->f2();
  }
  else { 将一部分编译时错误留到了运行时。 }
}
这不是故意找茬, 而是将STL中的iterator换个简单的形式来说明而已。
 

也许绝大部分情况下, 是不需要灵活到每个接口一个函数, 而是一个接口3、4个相关的函数。通常它们会被一起使用。

即使没有上面如此极端, 假设IPerfect1、IPerfect2都是设计得十分合理的, 3、4个函数的接口, 通常这3、4个函数要么必须一起提供, 要么都不提供, 单独提供是不符合语意的, 提供太多又是不够灵活的。
这需要经验, 相当多的经验。 但总是可以完成的事情。
 
但组合接口, 依然是OOP的痛处。
我记不清C#和Java中的interface是否继承自多个interface
如果不行, 它们就可能需要运行时接口查询。
而C++, 要在这种"组合接口"与接口查询之前作一个选择。
 
反观GP, 它一开始就不是以接口为单位来提供抽象,而是按需而定
所以, 它既不需要仔细的拆分接口, 也不需要组合接口。
STL中数据、容器、算法相互无关、可任意组合。
应该是前无古人的突破。
后面有没有来者? 上面已经说了, OOP要达到这种灵活性, 同样也有其代价。
并且, OOP代价体现在丑陋, 而不是难以理解
 

灵活的事物肯定比不那么灵活的事物难理解,抽象总比具体难理解。
所以抽象出一个合理的、广泛接受的语意很重要。

* 就是解引用, ++ 就是前迭代, -- 就是后迭代。
支持--就是双向, 支持 + n 就是随机。
 
GP也不会胡乱发明一些语意不清晰的概念。
window w;
control c;
w += c; 这种代码在GP界同样是收到批评的。
 
 
最后, 软件工程中, 是否真正需要灵活到如此程度, 以至于大部分人难以(或者不愿意去)理解的事物, 我就不知道了……
显示让用户知道么……
有约定俗成
再不成就文档
再不成…… 只能看源代码了……

好消息是, 违反concepts一般都错在编译时,不会将错误留在运行时……
re: 开始把库搞起来了 OwnWaterloo 2009-09-28 00:40
@溪流
nullptr是《eff cpp》中提到的。

对于int和指针的重载:
void f(int );
void f(void* );

f(0); // f(int );
f(NULL); // 如果是stddef.h 中的NULL, f(int );
f(nullptr); // 书中提到的那个nullptr, 会选中 f(void* );

如果还有另一种指针:

void f(int* ); nullptr 会引起歧义。

当然, 最好是避免这种重载……

re: 开始把库搞起来了 OwnWaterloo 2009-09-28 00:17
@溪流
这个…… 其实是个口味问题 …… all fine.
我比较懒…… 有现成的就喜欢用现成的…… so ……

re: 开始把库搞起来了 OwnWaterloo 2009-09-27 22:45
@溪流
用stdint.h。 把这个棘手的工作交给编译器提供商。
并且, 你实现容器库的时候, 需要DWORD么……


> 只要他们的定义是兼容的,传入的值就可以用。
你要去检查。 是否每个库都是兼容的。

另一种方式是只依赖于一处定义。比如stdint.h


msvc没有提供stdint.h, 因为它不支持C99。
网上有一个stdint.h for msvc, 使用BSD3条款的许可证。

或者自己写:

msvc 提供了 __intN扩展。
所以 intN_t uintN_t 很好处理
int_leastN_t, 这个本来就不能假设它的宽度, 按字面来即可。

uintptr_t, intptr_t 可以包含basetsd.h
typedef INT_PTR intptr_t;
typedef UINT_PTR uintptr_t;


现在你代码中依赖的就是:
(u)intN_t, (u)int_fastN_t ,, (u)intptr_t, (u)intmax_t 等等。
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 19:10
上面贴的代码有问题, 重新贴一下……
 
template<typename T,  >
class vector {
    T
* first_;
    T
* last_;
public:
    template
<class ForIt>
    vector(ForIt first,ForIt last) {
        difference_type d 
= distance(first,last);
        first_ 
= new T[ d + padding ];
        last_ 
= first_ + d;
        
for (T* p = first;first!=last;++first,++p)
            
*= *first;
    }
};
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 19:10
不叫"跨容器"的iterator。
而是iterator符合特定的concepts。
不过你说对了, 它确实和模板有关。
 
比如,使用一对forwarding_iterator构造vector的伪代码:
concepts
 
vector有一个构造函数模板。
只要FotIt 满足forwarding_iterator的概念,上面的构造函数就可以生成。
forwarding_iterator 要支持(但不限于)++, *, 因为上面的代码使用了这2个操作符。
vector的实现也不会是上面那样, 不会调用new 去默认构造一次。
会使用其allocator来分配,并使用uninitialized_copy。
不过那样就看不到vector() 对forwarding_iterator的要求了。
 
 
这是C++中的方式,GP的,基于concepts的方式。C#中可是没得这么爽的哦。
并且, GP的、基于concepts的方式, 也可以退化成OOP的,基于interface的方式。
反之不行, 因为concepts的偶和性更低。
 
 
不仅仅是容器。 整个STL中的组件都是通过concepts来协作而非interface。
如果你喜欢struct Iterator的方式, 或者IComparable , 也可以这么搞一套。
代码不会比GP来得少, 效率不会比GP来得高, 也不会比GP灵活 —— GP可以退化为基于interface, 反之不行。
 
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 18:51
const VOID *NULL = 0;
在C++中, 这样定义NULL是行不通的。
 
普遍的做法是直接使用0,或者stddef.h, cstddef 中的NULL宏:
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void*)0) /* 这是C中的做法 */
#endif
 
void* 在C中可以隐式转换到其他类型指针。
但C++不行。
 
 
或者, 更激进一点, 使用nullptr:
nullptr
因为C++0x将引入nullptr作为关键字。
使用nullptr,算是"向前兼容"吧…… 等转到C++0x时,就可以直接使用真正的nullptr了。
 
上面最后一种nullptr和C++0x中的语意最相似, 不过不一定能在所有编译器中都通过。
至少要支持成员函数模板才行。
如果不支持匿名类可以改用别的方式实现。
 
 
 
 typedef struct interface;
这是什么语法?
这也是徒增概念的地方。
 
C++程序员如果不知道下面的代码是一个interface
struct Ixxx {
    virtual ~Ixxx();
    virtual ...
};
 
将struct 换成interface对他的帮助也不大。
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 18:26
@溪流

各种现有的流行的库中, 实现了侵入式容器的比较少。
大都是非侵入式容器。

侵入式容器我只在如下一些库中见到过:
linux/list.h, linux/rbtree.h
sourceforge有个叫libaasdl的项目,有一个GDST(generic data-structure template)子库中的一些是侵入式的(还有一些我没看完)

SGI-STL中4种关联容器底层使用的是同一种容器,_Rb_tree。
它是非侵入式的。
但是构建它的_Rb_tree_base、_Rb_tree_base_iterator都是非侵入式的。
SGI-STL没有构建出一个侵入式的RbTree层, 而是直接使用侵入式的_Rb_tree_base,和_Rb_tree_base_iterator构建出了非侵入式的_Rb_tree。
稍微有点可惜。
不过即使有一个侵入式的RbTree, SGI-STL也是不会将其公开出来的。


如果想练手, 可以考虑构建一套侵入式的容器, 比仅仅重复STL中的东西来得有意义。

还有, STL中没有树式的堆。
heap相关的那几个函数都是对random_access的线性表使用的。
也可以考虑在这里做做文章。
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 18:10
@溪流
2:不再加前缀

其实vczh同学放出来的代码中的VL_前缀……
我觉得看上去是很伤眼的……
当然, 这是口味问题。


关于这个问题:
"但是,问题是,当 using namespace xl 并 #include <Windows.h> 以后,随手写一个“DWORD”,就会有歧义了。如果用的时候要写成 xl::DWORD,那还不如现在就命名成 XL_DWORD 好了"

首先, 不必定义xl::DWORD。
对于其他情况, 名字空间相对于前缀是有一些优势的。
1. 如果存在歧义, 无论是名字空间,还是前缀, 都必须使用全称。
2. 不存在歧义的时候, 名字空间可以打开, 可以别名。 而前缀必须时刻都带着, 永远逃不掉。
3. 如果不小心, 两个使用前缀的库都出现了相同名字, 前缀技术就很麻烦。
A库是个做网络的, 有一个 net_f,
B库也是个做网络的, 依然一个 net_f,
要同时使用两个库, 就需要自己去写转发函数。

而名字空间, 可以一开始就很长。
namespace net_byA { void f() }
namespace net_byB { void f() }


只使用A(或B)的用户,就可以使用别名:
namepsace net = net_byA(B);
net::f;

如果同时使用A、B的用户, 只好:
net_byA::f;
net_byB::f;

也比自己写转发函数要强。

总之, 名字空间是一种更灵活的方式。

如果决定使用C++编写库, 而且不考虑过分古董的编译器, 就应该选用名字空间。
re: 开始把库搞起来了 OwnWaterloo 2009-09-27 18:00
@溪流
1. 如非必要,不typedef基础类型

为什么要typedef?
typedef是为了提供语意。

DWORD, WORD, BYTE的语意是固定长度整数。
stdint.h, cstdint, sys/stdin.h, windows.h 中已经有这样的功能, 就尽可能去复用。
自己省事 —— 你有精力去为不同平台定义出对应的DWORD, WORD, BYTE吗?
既然上面的几个文件中已经给出了这种功能, 并且在各个平台下都测试过, 为什么不直接使用呢?

别人也省事。
需要明白一点:用户与其依赖的库通常不是线性结构,而是树形结构。
A库为了可移植性的去typedef DWORD, WORD, BYTE,
B库也为了可移植性去typedef DWORD, WORD, BYTE,
一个客户C, 同时需要A、B, 他该用哪个库的DWORD?
这种作法是徒增不必要的概念。


对自己库独有, 并有可能改变的概念, 才可以考虑使用typedef 来建立一个语意。
比如time.h中的time_t, clock_t, 代表了两个独立的概念。
@唐僧
高爷爷还用汇编实现算法的……
他别那么牛好不好……
 
我贴一下上面的c代码用gcc生成的汇编代码吧,不过是intel格式的,因为at&t格式的汇编我看不懂……
.globl _binary_search
    .def    _binary_search;    .scl    
2;    .type    32;    .endef
                               
_binary_search:               
    push    ebp                    
    mov    ebp, esp
    mov    edx, DWORD PTR [ebp
+16]     ;edx = lower
    push    esi                    
    mov    ecx, DWORD PTR [ebp
+20]     ;ecx = upper
    mov    esi, DWORD PTR [ebp
+8]      ;esi = keys
    push    ebx                     
    mov    ebx, DWORD PTR [ebp
+12]     ;ebx = target
    .p2align 
4,,15
L8:
    cmp    edx, ecx                    ;
if (lower!=upper)
    je    L2
L10:
    mov    eax, ecx                    ;middle 
= eax = ecx = upper
    sub    eax, edx                    ;eax 
-= edx, eax = upper-lower
    shr    eax                         ;eax 
/= 2
    add    eax, edx                    ;eax 
+= edx, eax = lower + (upper-lower)/2u
    cmp    DWORD PTR [esi
+eax*4], ebx  ;if (keys[middle] < target)
    jge    L3
    lea    edx, [eax
+1]                ;lower(edx) = middle(eax) + 1
    cmp    edx, ecx                    ;
if ( lower!=upper)
    jne    L10                         ;(keys,target,middle
+1,upper)
L2:
    pop    ebx
    mov    eax, edx                    ;
return lower
    pop    esi
    pop    ebp
    ret
    .p2align 
4,,7
L3:
    mov    ecx, eax                    ;upper(ecx)
=middle
    jmp    L8                          ;f(keys,targer,lower,middle)

迭代生成的汇编代码仅仅是标号取了不同的名字而已……
 
 
理论上是的, 因为理论上也可以转为迭代的吧。
实际上,写出为尾递归形式就是需要引入一些额外参数作为计算时的变量。
只要能写出尾递归形式,手动转迭代都不难了。
 
比如:
int factorial(int x) { return x>2? x*factorial(x-1): 1; }

不是一个尾递归, 因为factorial中对factorial调用后,需要取得结果并与x相乘才能返回。
 
转化为尾递归形式,需要引入一个额外参数:
int factorial_tail_recursion(int x,int acc) {
    
return x>2? factorial_tail_recursion(x-1,acc*x): acc;
}

int factorial(int x) { return factorial_tail_recursion(x,1); }

 

而factorial_tail_recursion“手动”转迭代都不是难事了:
int factorial_iteration(int x,int acc) {
    
while (x>2)
        acc 
*=x , --x;
    
return acc;
}
int factorial(int x) { return factorial_tail_recursion(x,1); }

再把2个函数合二为一, 始终以1作为累积的初始值:
int factorial_iteration_final(int x) {
    
int acc = 1;
    
while (x>2)
        acc 
*=x , --x;
    
return acc;
}

 
还是比较形式化的。 证明估计要留给vczh来做了。
@唐僧
gcc确实牛逼…… 怎么会有这种怪物……
对C/C++新标准支持很快……
compiler collection... 不知道它对非C/C++语言支持得怎样。
还支持这么多平台……


如果函数f返回前的最后一个步骤是调用另一个函数g,也就说g返回f后,f确实无事可做,再返回f的调用者;
那么,从理论上说,总是可以优化为:被调用函数g不再返回调用函数f,而直接返回f的调用者。
这样就可以在g中"复用"f的所使用栈资源。
这被称为尾调用。
http://en.wikipedia.org/wiki/Tail_call

如果尾调用恰好是调用的自身,就是尾递归(调用)。连使用的参数数量都是相同的…… 应该说是比较容易优化的。
并且,如果能将递归转换为尾递归形式, 通常"手动"转化为迭代形式就很简单了……


上面的递归代码符合尾调用。 我只是想验证一下是否真的会被编译器优化。
其实我预想是不行的,结果…… 还真的可以……
这样就有了一个理由:如果出于演示的目的,如果递归比迭代形式更优美,就不提供迭代形式了 —— 转迭代留作练习、或者换gcc ~_~
@唐僧
看来就我是夜猫了……
说点题外话……
因为上面给出的是递归代码, 所以就稍微查看了一下各种编译器的优化情况, 有点吃惊……
使用递归求阶乘的代码,msvc8,9; gcc 3.4.x可以优化为迭代,vc6不行。
对上面提到的二分搜索的递归形式:
tail_recursion

gcc也能将为递归优化为迭代。
下面是一个转化为迭代的版本:
iteration

gcc对这两者生成的代码,除了标号不同,其他地方完全一样……
msvc系列就不行了…… 老老实实的递归了……
 
re: Collection::List OwnWaterloo 2009-09-23 18:35
@陈梓瀚(vczh)
支持推倒……
re: Collection::List OwnWaterloo 2009-09-23 14:56
如果以GP而非OOP的方式构建集合,你会发现C++的template即使没有delegate也会很爽。C#没得这么爽。
@唐僧
再回一贴 ……

Uniform binary search中需要的那个table —— delta, 好像可以用template meta programming在编译时计算完毕 ……
C++太强大了~_~

否则, 如果运行时计算的话:
1. 将make_delta的工作留给client(就像链接中的示例代码一样)
会使得unisearch不太好用。多次调用make_delta虽然不会错, 但赔本了。
如果只调用一次, 时机不好掌握。
如果在main中, main前的执行代码不能使用unisearch, 而且如果每个库都要求在main中这么初始化一次, main会受不了的……

2. unisearch自己处理好make_delta
那每次对unisearch的调用,会有一次额外的运行时检测 if (!is_init) 是逃不掉了。
@唐僧

哦 ……

int a[] = { 7, 3, 5, 7, 2 }; 用Uniform binary search可以如下处理……
binary_search(keys=a+1, target=5, count=3 );

快天亮了, 头有点晕……
@唐僧
4点58分的回复……

The art of computer programming …… 一直没下决心去啃……

这个Uniform binary search是不是将除法操作缓存一下?
其实聪明点的编译器同样可以将
i /= 2u; 优化成 shr i
它使用一个预先计算好的middle值的缓存, 即使真能提高一点速度, 但能处理这种情况吗?
int a[] = { 7, 3, 5, 7, 2 }; 整个a无序, 但a[1] - a[3]升序。
binary_search(keys=a, target=5, lower=1,upper=3 );


确实two-way不好写。 12点多的时候就去问了一个拿过2次ACM金牌的室友,让他写一个二分搜索。
他回答“让我想一想”时, 我还有点惊喜 —— 之前我也问过一些人, 但终于有一个不是张口(随手)就给出代码的人了, 大牛果然不同凡响。
等了一会后, 得到一个3-way的……

打算将数据结构重新学一遍…… 透彻理解一下……
以前学的那叫啥…… 所以嘛, 只能看着室友拿金牌-_-。

@唐僧
谢谢~~

我想到一个证明3-way不可能实现确定取向的方法。 其实非常简单……

因为一个binary-search算法,必须对所有输入数据都有确定的取向,才能说该算法有确定取向。
故证明某个binary-search算法不具有确定取向只要构造出一个反例,即可……

比如…… 一个极端的数据:键全部相同。 3-way肯定是第1次就退出查找了, 肯定不具有确定取向了。

@陈梓瀚(vczh)
你再次偏题。怎么又扯上列表了?

多重值的map? 比如std::multimap?
如果使用的是std::multimap, 我相信用得更多的也是lower_bound、upper_bound、equal_range, 而不是find。
同样说明了对存在相等键的序列,查找的取向是有用的。


如果需要一个仅仅构建一次,查找多次,并且含有等值键的序列,并不一定需要multimap。
std::lower_bound,std::upper_bound同样可以对数组或者list查找,仅仅需要序列有序,并不要求序列有其他什么特性, 列表的负担又从何说起?


如果待查找的序列有相等的键, 那么查找算法有一定的取向就是一个有用的需求。跟序列是array、list还是map无关。

re: ACE vs Boost: Singleton的实现 OwnWaterloo 2009-09-22 17:44
@陈梓瀚(vczh)
这跟singleton有什么关系?
@那谁
第2版还是第1版的编程珠玑? 书中有证明取向性么?
取向其实也只算个附加需求。 只对多值才有用……

我不知道three-way如何写出固定取向……
只考虑过two-way的几种区间划分的取向。
期待你的研究成果~~~

@陈梓瀚(vczh)
存在相同键的有序序列中,查找取向是有用的。
它能解决:“找键等于k的所有值”,“找键大于等于p,小于等于q的所有值”, 这种常见的需求。
@唐僧
编程珠玑上有讲这个? 第2版中? 第1版已出版很久、很多细节记不清了……
wiki是指编程编程珠玑的wiki? 给个链接撒~~~

我第1次发现这个问题是在看《代码之美》时,当时困惑了很久“难道我以前不是这样写的?”。我的确是写成three-way了。
确实, 如果three-way是听说二分查找思想后,就能立即编码的话, two-way就需要深入考究考究才能编写出来。


two-way就能有明确的取向啊。
对区间[lower,upper]:
1. 如果取中值 m = (lower+upper)/2
将区间划分为[lower,m],[m+1,upper]
直到区间只有一个元素:[lower,lower]
取向就是从lower到upper, 第1个大于等于target的index。

2. 如果取中值 m = (lower+upper+1)/2
将区间划分为[lower,m-1],[m,upper]
直到区间只有一个元素:[lower,lower]
取向就是从upper到lower,第1个小于等于target的index。

上面给出了一份代码的链接, 我觉得挺优雅的……
re: ACE vs Boost: Singleton的实现 OwnWaterloo 2009-09-22 14:29
@陈梓瀚(vczh)
没明白。 这个条件能保证什么? 编译时的依赖关系?
re: ACE vs Boost: Singleton的实现 OwnWaterloo 2009-09-22 02:44
boost够机灵的, 避重就轻。


singleton可能会遇到的问题, 以及如何解决, 最详尽的资料在《modern c++ design》中有介绍。 问题大致有如下几个方面:
1. 限制实例数量
2. singleton相互引用
3. dead-reference
4. 线程安全


C++中:
singleton这种模式能"直接"解决的问题只有1;利用C++语言机制 —— private —— 来限制实例数量。
而问题1也是众多文章讨论得最多的, 简单嘛……

解决1问题,并不一定需要singlet这种模式;而其他问题又不是singleton这种"模式"本身能解决的。
综上, singleton in cplusplus is bullshit ……



boost这种实现,只能解决1, 在一定条件下,能解决4。
如果遇见2、3, 同样完蛋。

boost.singleton解决4,需要满足如下条件:
"The classes below support usage of singletons, including use in program startup/shutdown code, AS LONG AS there is only one thread running before main() begins, and only one thread running after main() exits."
如果这种条件能被满足, 直接使用全局变量同样是线程安全的。

如果真的需要解决问题1,以及难看的全局变量:
可以将这个全局变量以及类的定义放在单一翻译单元中,并在该翻译但与实现若干wrapper函数即可。

同样, 对于问题2和3, 全局变量也通常会坏事。

综上, boost.singleton, 简直就是为模式而模式。
@那谁
cpp的rss比较快。。。


这里有一份代码:
http://www.cnblogs.com/Devfly/archive/2009/09/18/can-you-write-a-right-binary-search-algorithm.html#1651172

是将闭区间[lower,upper], 取m = (lower + upper)/2
分为2个区间[lower,m] ; [m+1,upper]

递归边界是区间只含一个元素: [lower,lower]

取向是返回[lower,upper]中大于等于target的index。
递归边界一定能达到很好证明, 取向比较麻烦。


而其他一些常见的区间取法, 比如[first,last),
还有中值的取法,比如 (lower + upper + 1)/2, 或者用那个什么黄金分割……
以及多值时的取向, 随机, 第1个, 最后1个。
它们与stl中lower_bound, upper_bound的关系
等等…… 都挺有意思的……
不过最近有其他事要忙…… 只好终止了……

你感兴趣的话可以研究研究, 我就直接捡个现成了~~~
因为二分查找的思想很简单, 很多人稍微看看就开始编码了, 没有考虑:
1. 每次递归中,区间如何划分
2. 递归的边界有哪些,是否能达到
3. 查找的值存在多个时, 将取得哪一个

仔细推敲边界的人不多。 大多都是随手写写, 最多加几个测试数据。
区间划分, 我只在少数几个地方看到是被“二分”, 普遍做法是“三分”。
少数几个地方是《代码之美》;cplusplus网站中lower_bound,upper_bound的伪代码。
讨论多值取向的文章就更少了。
> 原来如果把这个十进制数考虑成2进制
在C/C++中,整数本来就是按2进制而不是按10进制存储的。
不存在考虑成2进制的说法。

> 突然想起了将10进制转化成2进制的方法
10进制是表象, 2进制才是本质。
10进制只存在于输入输出的过程中, 变量最终是按2进制存储。



> 右移一位相当于除以2,模除2就是把最后那一位给取出来了
> 不断的模除2,就把这个2进制数一位一位的取出。
int i,d;
d = i % 2u;
i /= 2u;

如果你使用的编译器不是古董,第2、3行代码也会分别被编译为位与、移位—— 不一定真的需要写为 & , >>= —— 而不是除法。

re: std 容器 assign的注意之处 OwnWaterloo 2009-09-17 17:18
需要注意的是(int*)buf这个转型,而不是assign。
每写下一个转型时,问问自己“我到底在干什么”。
re: 关于while(cin) OwnWaterloo 2009-09-06 19:06
>> 控制结构中的布尔条件值并不是非得直接转换为bool不可,只要能够转换为某个整数型别或指针型别就够了。

选void* 而不是整数类型是有原因的。 可以避免如下代码被编译通过:
cin<< xxx;


streambuf是重点之一。
istream 负责格式化输入, ostream负责格式化输出。
streambuf 如其名那样, 作为格式化结果与最终输出目的地之间的缓存。

而stringstream, fstream, 没有太多的功能。
格式化功能是继承自iostream。
而它们使用的是stringbuf, filebuf, 是streambuf的子类, 提供一些额外功能。
stringstream, fstream比iostream多的功能, 正是其buf提供的。
目前C++是没有region 这种东西的, C++0x也没听说有这么个东西。
这是msvc提供的一个扩展。

你自己也试过vs2003了。


这是gcc编译的情况:
warning: ignoring #pragma region name
warning: ignoring #pragma endregion comment
warning: ignoring #pragma region Region_1
warning: ignoring #pragma endregion Region_1


这是vc6编译的情况:
warning C4068: unknown pragma
warning C4068: unknown pragma
warning C4068: unknown pragma
warning C4068: unknown pragma

re: 一个有趣的小问题 OwnWaterloo 2009-09-01 23:11
@莫失莫忘
> OwnWaterloo,你是不是一直等在CPP BLOG上?

有个"有回复时邮件通知我"。
我通常都开着邮箱, so ……


> 在JAVA中,通过无效的地址去访问是绝对会出错的
java中不能随意操作指针。 除了null, 如何能产生一个无效地址?
array 都是一个所谓的"对象", 记录着大小, 随时可以检查边界。
JNI可以吗?


> 这只是常人的一个思维:通过不存在的去访问当然会出错
这是javaer的思维。

现在使用的计算机中, 冯诺依曼架构是主流。
所以, 当cpu真正进行运算的时候, 一切都是地址。

硬件会提供一些手段, 区分一些地址是否有效。
但通常是软件, 通过"指令流"而产生"控制流", 来判断某地址是否有效。


C/C++不提供这些保姆功能。
这个例子充分说明了,正因为没有这些保姆功能, C/C++中, 程序员要尤其小心, 不能依赖于"编译器、OS、CPU"提供的"功能有限、可有可无(标准未定义)"的保护手段, 而要自己注意越界问题。
re: 一个有趣的小问题 OwnWaterloo 2009-09-01 22:58
@莫失莫忘
> 语意上的解引用?实际上的解应用?

这真的不是搞笑。

S sa[12];
int ia[12]
那么sa[100]; ia[26]; 这2
个表达式, 按C++的说法, 其结果类型就是 S& 和 i&。

如果给一些C程序员看, 他们还会告诉你,
sa[100]; 等效于 *(sa+100);
ia[26]; 等效于 *(ia+26);

所以, 我说这里有一个语意上的解引用。


但实际在, 在i386下, msvc和gcc编译器, 都不会理睬
sa[100]; ia[26]; 这么一个孤单的表达式。

只有当
int i = ia[26]; /* int i = *(ia+26); */ 读
ia[26] = 1212; /* *(ia+26) = 1212 */ 写
的时候, 才会真正产生"解引用"的代码 —— mov指令

并且, 只有 int* p = ia + 26; p的地址没有相应权限(将未提交也理解为缺陷缺失的话), 才会引发错误。


对自定义类型:
sa[100].a(); 调用处都不会产生解引用代码。

只有在
S::a() { // 定义处
才有可能产生解引用代码—— 如果操作非静态数据成员的话。
}


按C++标准来说, 表达式:
sa[100]; ia[26];
已经是未定义行为了。 只是在i386上, 通常不会造成什么问题。

又因为S::a()没有操作非静态数据成员, 就不会产生实际的mov指令, 也不会有问题。


-----------------------------------------
sum是S的静态数据成员, sum本来就是在静态存储区中的。
即使是按C++标准, 无论是
S::sum
this->sum

都是对S::sum——静态存储区中的一个变量——的操作。
没有问题是自然的。

for (int i=0;i<1212;++i) sa[i].sum
只要 sa[i]表达式不出问题, sa[i].sum 依然是访问的S::sum , 没有问题还是显然的。

re: 一个有趣的小问题 OwnWaterloo 2009-09-01 22:42
@莫失莫忘
> 如果代码中越界了,那编译不会出错。但是如果运行就会报错
对数组越界, C++标准中的描述是“未定义”。

据说有一些平台(我只用过i386和ppc), 确实会检查无效地址——甚至只是获取,而没有进行操作, 例如:
int a[12];
int* p = &a[13]; // 就会引发错误。

而在i386下, 后一句代码只会产生一个无效(无效的准确含义是越界)地址, 不会引发错误 —— 甚至对无效地址的访问(读写)是否会引发错误, 都要看运气。

首先, &a[13]肯定不是nullptr。 nullptr检测区就不会起作用。

其次, vc可能会在a[12]附近安插一些guard。
int read = *p; // 无法检测
*p = 1212; // 检测出写, 如果guard的恰好是1212,越界写都判断不出
guard的值好像是0xcc。

三, vc的release配置不会安插guard。

四, 还有一种能检测到错误的情况。
p 指向的地址还没有被保留或提交。

因为i386 下windows的栈通常是向下增长,
p = &a[ /* 这里需要一个很大的正数 */ ]; 才能越过栈底, 达到保护区。

p = &a[ /* 如果这里是负数 */ ] ; 越过以提交的栈顶, 达到保护区就容易许多。


如果p误指的不仅仅是栈上变量, 那还可以增加一些错误检测的机会。
没有被保留与提交的页, 读写都会错。
已提交的页, 还得看页的保护属性。


说了这么多, 就是想说所谓的“运行就会报错”, 是不靠谱的。
如你所见, 上面已经列举出许多运行时不会报错的情形——这种情形还不少。

所以, 大家写代码还是要按照规范来……
为什么这种不合乎规范的代码不会出现错误, 只能作为茶余饭后的谈资……
re: 一个有趣的小问题 OwnWaterloo 2009-09-01 22:05
@莫失莫忘
> 自己去看看博主的解释吧!

我又看了一遍。
只有对S::sum有语意上以及实现上的解引用。
对 sa[100].a(); 有语意上的解引用。
Chuck 这文章正是想得出 —— s[100].a(); 只存在语意上的解引用, 实际上没有进行解引用, 所以才不会出错 —— 的观点。


> 代码中出现无效地址,那通过无效地址去访问有效地址按理说也是错的哟~~
> 如果不解引用就不出错的话,但是博主的解释中就有解引用了。
依然不明白你在说什么……
共10页: First 2 3 4 5 6 7 8 9 10 
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(8)

随笔档案(16)

链接

搜索

  •  

积分与排名

  • 积分 - 196688
  • 排名 - 132

最新随笔

最新评论

阅读排行榜

评论排行榜