一家著名公司面试试题
使用VC，写一个类要求实现对半查找，实现链表插入，删除，在1-2个小时内完成
答对者，我将告诉他是哪家公司
问题点数：20、回复次数：126Top
1 楼ender（ender）回复于 2001-01-16 12:28:00 得分 0
哈哈，又是华为吧？
这个不算难的了！Top
2 楼Mahyar（自由事业）回复于 2001-01-16 12:38:00 得分 0
easy 呀，做不出来的请举手。。。Top
3 楼yoci（阿呸）回复于 2001-01-16 13:19:00 得分 0
我做不出，全忘了。Top
4 楼Kaile（领头羊）回复于 2001-01-16 13:20:00 得分 0
还有哪些更难的？
我没有系统学过数据结构，平时编程都是调用现在模块，我先举手
请乘风先生指教Top
5 楼rocks_lee（石子儿）回复于 2001-01-16 13:25:00 得分 0
本公司试题：
c或java，打印给定目录的树结构，半小时。
哈哈，会者不难。Top
6 楼kincaid（IT苦行僧）回复于 2001-01-16 13:49:00 得分 0
太简单的问题，小儿科。Top
7 楼latakia（）回复于 2001-01-16 13:55:00 得分 0
微软亚洲技术支持中心笔试题，找规律：
O T T F ___
A: O; B: B； C: F; D: E; E: H;
答对有奖！Top
8 楼alfwolf（木马煞）回复于 2001-01-16 13:56:00 得分 0
我在应聘的时候被要求用vc做一个蛇吃鸡蛋的游戏
想必大家都玩过。Top
9 楼Kaile（领头羊）回复于 2001-01-16 14:07:00 得分 0
答latakia
E：H
原因是H三笔且为F的增序Top
10 楼oo（为了名副其实，努力学习oo技术ing）回复于 2001-01-16 14:11:00 得分 0
C:F
1,2,3,4,5的英文第一个字母
呵呵。。。Top
11 楼AtCsdn（）回复于 2001-01-16 14:28:00 得分 0
这种题目最多30分钟就能实现并调通！Top
12 楼Kaile（领头羊）回复于 2001-01-16 14:39:00 得分 0
别光说不练，那就请给我们一个完整的程序，让我们这些低手一睹大侠风范
还有蛇吃鸡蛋的游戏
还有哪位知道CA ，IBM ，M$ , 金山等的面试题目请不要独享
Top
13 楼gameboy999（-'_'-）回复于 2001-01-16 15:34:00 得分 0
实现对半查找的前提是该链表必须是有序的，数据结构书里有不少这样的例子类。
不过在面试的时候写出来还真有点挑战力：）Top
14 楼A_SOSO（SOSO）回复于 2001-01-16 15:43:00 得分 0
这种题目，允许我查资料还差不多，要我在考试时，现场做出，我看是做不到。
出这种题面试，简直是变态，我FtTop
15 楼Kaile（领头羊）回复于 2001-01-16 15:48:00 得分 0
我也觉得没必要，真要用拿一本资料或网上现成的还少吗？
话又说回来，如果真能现场做出来，可见他的数据结构以及C的熟悉程序
Top
16 楼Kaile（领头羊）回复于 2001-01-16 16:11:00 得分 0
sorry, 程序应为程度Top
17 楼ender（ender）回复于 2001-01-16 16:14:00 得分 0
其实真的不难的啊？况且时间给的多啊！Top
18 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-16 16:18:00 得分 0
出这种题的人一般是自命不凡，而又无人欣赏的人，借此机会显示一下，也就是说脑袋有病。
我的朋友遇到过一道面试题：用一上午用VC写出一个类：任意多项式除法，带输入输出。
也许不难，（也许很难）但当时不查资料还真弄不出来。
哪位大侠可指教一二。Top
19 楼acute（毛头)(食堂帅哥）回复于 2001-01-16 16:24:00 得分 0
我终于在这里看到了牛人了，我还是快去补课吧。Top
20 楼personnel（无忌）回复于 2001-01-16 16:54:00 得分 0
牛人太多了，小弟有礼了，多多指教。Top
21 楼yes_start（刚刚开始）回复于 2001-01-16 16:55:00 得分 0
我也要好好的补课了Top
22 楼rocks_lee（石子儿）回复于 2001-01-16 18:03:00 得分 0
多项式除法要是懂一点编译原理，倒也不难Top
23 楼yoci（阿呸）回复于 2001-01-16 18:58:00 得分 0
谁能给个多项式除法的思路？
我笨Top
24 楼chinani（chinani）回复于 2001-01-16 19:40:00 得分 0
问题本身并不难，我想这个公司是想看看大家解决问题的思路吧！Top
25 楼com235（com235）回复于 2001-01-16 20:02:00 得分 0
*&&**&&&^||******
是什么意思？？
我一道题都不会，可我搞工业集散控制两个大系统，第一个养1000余人的国运企业3年。
（非我一人之功）
第二个，呵呵，也已经1000多万吧。
Top
26 楼zames（zhang）回复于 2001-01-16 20:09:00 得分 0
very easyTop
27 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-16 20:33:00 得分 0
各位老弟，多谢回复，那个多项式问题，我的朋友现在也没有知道 答案，不妨各位能告之一二，
关键面试的人员问了我的朋友二个问题以后（纯虚函数和普通函数有什么区别，与先期联编和后期联编有什么关系,另一道是静态函数是做什么用的）,他都答上了，（各位觉得这个难度怎样，不够难是吧），然后从出了一道题，就是那道 题，答不上走人，答上再说，不准换题。和我朋友同去的其它人在另一个人那里面试，所问的题是最基础的问题，（内联函数，封装，public和private有何区别）然后做了一篇小题，我朋友看了一眼，都会，但没有他答的份。他呆了一上午，走人了，其它人也都有意到别人那里面试，不去面试他的那人面前。我想高人是有的，也许以前解决过这种问题，所以能够答上，但要是没遇到过的，也不准查资料，是有点难度吧，我朋友直说那人变态，你们认为呢？Top
28 楼lzl（jdkylix）回复于 2001-01-16 20:55:00 得分 10
//我真想不通，当今还要考这种题目， 如果我的项目组里发生还要自己写
//排序和查找之类的方法我绝对不能容忍。
//至少Standard C++ Library没有学好
//用结构模式的适配器实现
#include<list>
using namespace std;
template<class T> class CList
{
private:
list<T> m_list;
public:
const T* find(const T& v) {
sort(m_list.begin(), m_list.end());
list<T>::iterator i = lower_bound(m_list.begin(), m_list.end(), v);
return (i != m_list.end() && !(value < *i)) ? &(*i) : NULL;
}
//插入删除那就太简单了。
bool del(const T& v);
void ins(const T& v);
};
Top
29 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-16 21:48:00 得分 0
知已也，看来俺是一个白笨蛋!Top
30 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-16 21:51:00 得分 0
to lzl：请问老哥如何学习STL，推荐几本经典书籍吧！，电子书也行。Top
31 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-16 21:56:00 得分 0
老兄们，给个答案吧，我也想知道多项式除法的答案。Top
32 楼dragonfly（猴子）回复于 2001-01-16 23:14:00 得分 0
首先声明，以下是自己的见解，各位大虾指教：
多项式的除法，我觉得问题的出发点应该是出发上做文章，是不是？
无论什么样的多项式除法，最后都可以转化成 ： ExpressA /ExpressB 的最简形式
然后你的问题就变成对ExpressA和ExpressB两个表达式进行解析的标注算式解析的过程。
这个过程，我想学过编译原理的同志应该比较明白了吧。
赫赫！
看来问题的关键是如何从给入的表达式，转化到标准最简式ExpressA /ExpressB，
这一步，大家应该是各有各的方法了吧，提是一下，用堆栈应该是一个不错的选择，赫赫Top
33 楼keboy（青鸟）回复于 2001-01-17 08:21:00 得分 0
STL真是太爽了！！！
其实各位不妨想一想，这些题（MS那道除外）都是典型的数据结构试题，做不出肯定是功力不够，
也许你也可以做一个系统出来，但是技术含量有多少呢？
请各位讨论！！Top
34 楼horris（僧推月下门）回复于 2001-01-17 09:19:00 得分 0
这道题并不很容易，这是数据结构中比较复杂的平衡二叉排序树，刚毕业的人也许能做出，要是我，呵呵，得先翻翻书。Top
35 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-17 09:22:00 得分 0
不好意思，我没学过编译原理，但我想用椎栈或线性表的方法应该是有道理的，但请您给个堆栈解多项式除法的sample.我相信各种兵器都能使出上成功夫的大侠有得是，但我不是，还请多多指教。如您不觉得少，小弟可给您50分。不过我想，面试只考一道硬性指定的大题，应该不够科学。Top
36 楼horris（僧推月下门）回复于 2001-01-17 09:23:00 得分 0
to lzl:
我想考官对你的答案不会满意的，因为他想看的是你如果实现二叉排序树，如何查找，如何增减。当然用模板类来实现的思路是对的。Top
37 楼Kaile（领头羊）回复于 2001-01-17 09:38:00 得分 0
horris说的对， 面试目的是为了考查你对基本算法的掌握程度，以及C语言的熟练程度，当然是用自己写的排序和查找算法了Top
38 楼ccsheng（海盗汤汤）回复于 2001-01-17 09:57:00 得分 0
去翻翻程序员和高程的历年试题，我做到过多项式除法的题目。Top
39 楼jz_x（徐景周）回复于 2001-01-17 10:28:00 得分 0
又是数据结构和算法的题目。。。。。。Top
40 楼netsong（Edwin）回复于 2001-01-17 10:58:00 得分 0
这道题目并不难，我想公司是看你对数据结构和c++的认识和熟悉程度。
因为这些思想在程序设计中随处可见。如果这都用不熟，呵呵。。。
lzl(槐树）高手！！! :)
(仅个人观点）
Top
41 楼firewwq（l_vc）回复于 2001-01-17 11:16:00 得分 0
我要重修数据结构Top
42 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-17 11:32:00 得分 0
大家都是高手，小弟这里有礼了，但不知哪位能真正给一个完整的程序？查不查资料都可以，如果不查资料就能做出来，那一定是数据结构和C++的高手，我一定不会让您白忙的。
（要求：无论是除数、被除数、商、余数的系数都是整数，可正可负，不用多元，只要一元x即可，幂是整数，可正，可负）。
小弟的软件公司虽说不大，也有二千余人吧，刚才请教了几位身边的同志，因为都有任务在身，一时也编不出来，关键是谁都没做过这种题，（与编译原理的关系，也都不甚了了，希望也能给一个用编译原理解题的例子。希望ccshent和netsong多多帮忙。)Top
43 楼Kaile（领头羊）回复于 2001-01-17 11:57:00 得分 0
从这里可以看出基础扎实的高手很多，我没有修过数据结构和算法，但做过一些项目，都不需要基本的什么编译原理、数据结构、算法知识，对MSDN 数据库熟悉就行，所以这方面很欠缺。
这些知识确实很重要，我现在的公司整天做MIS，行业软件，只要熟悉业务，SQL语句就能干活，我不喜欢这样的，我希望能到金融 、或者做底层Ｃ编程的公司去。
我决定补上数据结构和算法的课，至于编译原理就算了吧。
Top
44 楼TurboX（刘江涛）回复于 2001-01-17 12:17:00 得分 0
我也给各位出个题，我不调您的胃口，就是华为的一个变态出的题，
给你两个变量A和B，变量类型不一定，就是说可以是INT可以是FLOAT，现在要你不用中间变量把A和B的值交换一下，各位有什么高招？Top
45 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-17 12:51:00 得分 0
我也不调胃口，那道题也是huawei的。不过即使在那，这道题别人也没遇到过，只有我的那位朋友足够的幸运，遇到了那个没人敢去面试的变态。（其实我朋友的一个手下，跟他学了些皮毛，考了几道虚函数的问题就去了华为）不过我还是想知道 答案，想道理，只要学过数据结构的都知道 一点，我看不出它和编译原理有什么直接关系，恕我脑袋不够尖锐，还请哪位高人能够花一些时间，给一个例子，分数好说。关键是里面的算法，而不是调用现成的STL。Top
46 楼Kaile（领头羊）回复于 2001-01-17 12:53:00 得分 0
用2个指针， 分别指向A 和B，再分别调换2个指针所指向的地址Top
47 楼oo（为了名副其实，努力学习oo技术ing）回复于 2001-01-17 12:59:00 得分 0
a=a+b;
b=a-b;
a=a-b;Top
48 楼wyzegg（蛋）回复于 2001-01-17 13:02:00 得分 0
又不是太难Top
49 楼yaw（）回复于 2001-01-17 13:03:00 得分 0
上初一为计算机比赛老师教的，
a = a + b
b = a - b
a = a- bTop
50 楼cber（cber）回复于 2001-01-17 13:04:00 得分 0
A=A+B;
B=A-B;
A=A-B;Top
51 楼ecore（电子内核）回复于 2001-01-17 13:08:00 得分 0
呵呵，华为真TMD有够傻的。
用双向链把数据链起来后，还要用折半查找？？？？？？？
这不是耍人么？折半快就快在直接定位下一个要查的数据以一次性跳过一半。
现在。。。。。你移动到下一个数据。。。要遍历到整个链的中间耶!!!!真TMD好奇怪.
(我的理解而已.当然,考题而已,怎么出都可以啦.)
多项式除法用编译的角度来说,就是一个有限自动机.但其实,关键在于要适合所有的多项式(就是说不是固定死了的几项),在前期判断上有些小处理要做.
也只是我的看法而已,没有怎么去想.要是有什么漏洞的地方,也不比太在意.
第三个是异或的思想.(A,B对调)Top
52 楼rocks_lee（石子儿）回复于 2001-01-17 13:08:00 得分 0
你这里的多项式除法到底是什么意思？
能给个具体的例子吗？Top
53 楼ecore（电子内核）回复于 2001-01-17 13:15:00 得分 0
to lzl:
哎呀,是STL高手么?我好想和一个STL高手学习学习STL呢.没有什么资料.我只有SGI的help.
靠!能推荐些资料么?啊,我还看了jjhou网站上的那些东西.Top
54 楼mahan2000（Bill）回复于 2001-01-17 13:22:00 得分 0
a=a+b
b=a-b
a=a-b
Top
55 楼mahan2000（Bill）回复于 2001-01-17 13:22:00 得分 0
a=a+b
b=a-b
a=a-b
Top
56 楼jimconrad（jimmy）回复于 2001-01-17 13:24:00 得分 0
a=a-b;
b=a+b;
a=b-a;
a=a*b;
b=a/b;
a=a/b;Top
57 楼alaofangel（天使之翼）回复于 2001-01-17 13:32:00 得分 0
如果是华为，就没有什么了，这样的公司当然是提出这种问题，无聊，试想如果一个已经有了2，3年工作经验（做项目，编程）的人还会记得这些基础的东西更别说立即做出来了
还是MS的题目有创意，不知有无最终答案，亦或讲出答案在说出理由？Top
58 楼flyingxu（阿飞）回复于 2001-01-17 14:25:00 得分 0
to gameboy999:
链表能折半查找吗？
我好象记得不能。
Top
59 楼bluesky_dgd（改革开放的副设计师）回复于 2001-01-17 15:02:00 得分 0
to:rocks_lee(石子儿)
例如任一个多项式：
aX(n)是X的n次幂。
在程序中要对X进行降幂排序(最好能有一个较合理的输入输出)。
被除数：aX(n)+bX(n-1)+cX(n-2)+...+dX(0)
除数 : AX(m)+BX(m-1)+CX(m-2)+...+DX(0)
a,A（代表不同变量)为任意整系数，可正，可负。
m,n(代表不同变量)为任意整次幂，可正，可负。
编程把商和余数求出来(商和余数必须是整数，实在不行，先将被除数系数扩大一定倍数，最后再除以这个倍数。像：(X(2)+X)/(2X+1)=[1/2(2X(2)+2X)]/(2X+1)）
石大侠能帮忙吗？（仅仅提供一点思路，我想学过计算机的一般都能有一些，只是不大一样罢了）。我要完整的程序，是否可以？（如不查资料可能要浪费您一些时间，不过您能查出来，也请告诉我一声，我给您加分。）。
Top
60 楼lzl（jdkylix）回复于 2001-01-17 15:04:00 得分 0
同志们：
有一点我们一定要记住， 我们的最终目的是什么， 是需要一个稳定的、维护性好的软件（其他的指标我就不说了）， 目前国内很多企业维护工作量太大， 对企业负担很重， 回头看看为什么， 多半是设计的不灵活，模型不合理。我看了《设计模式》一书，得到的最深体会就是，几乎所有模式都是围绕这可扩充性和可维护性。
如果一个考官出一个题目， 让应聘人员建立相应的类模型， 我到是非常赞同的。
另外， STL中几乎包含了所有的数据结构， 其中的Set和Map就是建立在二叉树上的，非常好用，另外用它有一个好处， 内存分配已经经过优化。
最后向大家推荐一本书《掌握标准C++类》，人民邮电出版社。
Top
61 楼hustmouse（mouse）回复于 2001-01-17 15:14:00 得分 0
To LZL:
您的做法应该是不对的。使用STL，您能保证那个类是使用的链表吗？
其次，您能保证它有折半查找的效率吗？在每次查找时还的排序？
我想，如果在不知道源码的情况下，应该是不知道的。（C++的封装？）
使用二叉排序树应该是正确的。Top
62 楼pannap（平底锅）回复于 2001-01-17 15:14:00 得分 0
我也聚首,我不会.Top
63 楼pannap（平底锅）回复于 2001-01-17 15:15:00 得分 0
我也聚首,我不会.Top
64 楼rocks_lee（石子儿）回复于 2001-01-17 15:23:00 得分 0
bluesky_dgd(都市夜):
原来是这个意思，我还以为是表达式分析呢。
不会不会，我高数最差了。
更是没处查资料去，高数书早就扔掉了……Top
65 楼ghostzjy（鬼精灵）回复于 2001-01-17 15:24:00 得分 0
折半??链表???好象不是一回事吧??链表我认为用c 比c++简单但可靠性不强!Top
66 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-17 15:46:00 得分 0
to lzl:谢谢你的推荐书！，马上去买！Top
67 楼dongdacun（东大村）回复于 2001-01-17 15:55:00 得分 0
只要&a<>&b
a^=b^=a^=b 能实现a、b值交换Top
68 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-17 15:57:00 得分 0
to lzl:《掌握标准C++类》是人民邮电出版社出版的吗？，我在网上人民邮电出版社没查到呀！，而且连华储与当当都没有呀！Top
69 楼cropcoco（曼_柯）回复于 2001-01-17 16:08:00 得分 0
我真傻，真的，单知道...Top
70 楼lzl（jdkylix）回复于 2001-01-17 16:24:00 得分 0
什么时候用vector: 主要是在相对静止的资料， 用map或set：主要在相对动态的情况下。
譬如：拿计费来， 资料类相对静止，调入内存，sort一下就可以了（如果是多个排序方法， 可以对指向改资料的指针排序）。对于帐目汇总， 就需要用set，因为它内部是实现在二叉树上的，效率高。
我们应该提倡重用， 如果我们还把精力花在前辈早已经研究出来的成果上的话（搞研究的除外）， 那么我们还有多少精力花在我们的领域问题上。
Top
71 楼lzl（jdkylix）回复于 2001-01-17 16:29:00 得分 0
to vcmfc: 去一下书店， 肯定有。 如果没有， 我可以发一份英文帮助给你。 Top
72 楼lzl（jdkylix）回复于 2001-01-17 16:42:00 得分 0
To hustmouse(mouse)
类其中很重要的一个就是封装性， 我们不必了解它是怎么实现的， 只需要知道怎么使用它、功能和性能符合要求就可以了， 譬如说前些年我写UNIX的motif程序， 我用了一个类库，很快就完了，顺利交付用户使用。 到目前我还不知道全部用motif怎么写， 但目的已经达到了， 我想只就是我们所需要的。
Top
73 楼hustmouse（mouse）回复于 2001-01-17 17:10:00 得分 0
to lzl
对啊，您说的很对，但从题目本身来看，（我们就只对本题目讨论）
是要求用“链表”的，所以，您能保证那个类是用的链表吗？
从结果上来看，您的程序是实现了功能，但您能保证其中的效率吗？
我想，此题目是想插入，删除方便，同时要查找快速。
OOP 是要只提供接口就可以了，但有时候，太多的封装也失去了效率。
（ 请不要介意我使用“您”，因为我原来一直是使用“你”的，但我的一个同事
给我写信就使用了“您”，他说表示尊重，我就也这么用了，并无其他意思）Top
74 楼rocks_lee（石子儿）回复于 2001-01-17 17:26:00 得分 0
怎么，“您”原来不是表示尊重的吗？Top
75 楼Sam_Yang（Sam）回复于 2001-01-17 17:46:00 得分 0
我考，出这种题Top
76 楼FoolBoy（倚剑问情）回复于 2001-01-17 18:06:00 得分 0
有链表搞多项式除法其实很简单,我想在1个小时内可以编制调试成功Top
77 楼foxnt（吴剑明★天马幻想）回复于 2001-01-17 18:40:00 得分 0
出这种题目的人真是笨的可爱Top
78 楼myan（）回复于 2001-01-17 18:49:00 得分 0
我本来以为只有C/C++区里才讨论STL, 没想到这也有!
代lzl回答hustmouse: 当然, 如果你使用list<T>, 肯定是双链表.
VC里的STL实现是P.J. Plauger的Dinkumware STL, 效率不是最高,
但肯定比我们大多数人写的手写代码要高, 甚至比手写汇编代码还要快.
因为其中一些算法采用的技术是混成的, 比如sort, 先进行标准quick
sort, 等到基本有序之后再用insert sort. 什么叫基本有序, 这又是遵
循Jon Bentley的一片经典论文的结论. 总而言之, 一般的程序员写出的
代码效率绝对不敌STL, 除非你用它的算法手写C/C++代码, 耗上巨长的时间.
VC里的STL缺点就是可执行代码尺寸太大, 而且没有单链表和哈希表. 我推荐
使用基于SGI STL的STLport, 可以使可执行代码长度缩小一半, 而且有新增的
集中数据结构.
To lzl兄:
你对于STL的推崇令我深受鼓舞, 以后可多联系. 不过你的代码下了我一跳,
因为我还不知道STL里有del()和ins()算法呢. 到是二分查找有binary_search算法
可以直接用, 可你又没用. 我是搞GCC的, 在VC这边不敢瞎说, 但请你再查查手册,
确证一下. 另外, 你推荐的那本书我也有, 只能说是山中无老虎, 实在谈不上是什么
好书. ecore已经有了SGI STL的help, 另外Thinking in C++第二版中都有更好的
解释.
诸位如果对于STL感兴趣, 可以多去C/C++那边逛逛, 我正在翻译Think in C++第二版
的C++标准库部分, 分期发表, 以解大家对于STL的迫切渴望.Top
79 楼bush（bush）回复于 2001-01-17 18:54:00 得分 0
真热烈！个位高手的讨论是我受益匪浅！！感谢！！
Top
80 楼zhangzhonghua（）回复于 2001-01-17 18:57:00 得分 0
关注。Top
81 楼monkeyfu（大圣）回复于 2001-01-17 20:13:00 得分 0
这不算难。
当初我考3级B的时候，上机题跟这个差不多也是个排序查找题，我用了
不到20分钟就做完了。（当时我在上初二）Top
82 楼wnn（蓝色海洋）回复于 2001-01-17 20:43:00 得分 0
I will tell how to do 3 years later:)Top
83 楼wnn（蓝色海洋）回复于 2001-01-17 20:45:00 得分 0
大圣，你真能耐，吹牛吧Top
84 楼mfc_boy（小c）回复于 2001-01-17 21:04:00 得分 0
其实并不难，我在华为应聘的时候，在30分钟答完了，不过我觉的这种考试有点变态。Top
85 楼James_G（恶人谷）回复于 2001-01-17 21:42:00 得分 0
C我不是非常懂，但是我觉得‘多项式’的题目可能和 <辗转相除法> 有关。
如果，谁有需要我可以研究研究，
都忘了！有兴趣的可以去回忆回忆《高中数学教程》Top
86 楼James_G（恶人谷）回复于 2001-01-17 21:50:00 得分 0
不好意思，是《高中数学竞赛教程》Top
87 楼TurboX（刘江涛）回复于 2001-01-17 22:52:00 得分 0
CSDN的人就是聪明！！
可是我面试的时候脑袋转了三圈还是没答对，考完了脑袋只转了一圈就想出来了。Top
88 楼rampig（）回复于 2001-01-17 23:24:00 得分 0
不用STL的全是傻冒。
Top
89 楼liangml（果子）回复于 2001-01-18 00:36:00 得分 0
凡是自己不懂的题目，就埋怨是出题者水平不行。我已经是第N次看到这种论调了。可休矣!Top
90 楼darkay（火凤凰）回复于 2001-01-18 09:20:00 得分 0
看见大家对stl有点看法，我转一文章（已经不记得是在什么地方找到的）
STL之父访谈录(一万二千字的大块头）
翻译者 : myan
出处: http://www.sgi.com/technology/stl
stl之父访谈录
1995年3月，dr.dobb's journal特约记者, 著名技术书籍作家al stevens采访了stl创始人alexander
stepanov. 这份访谈纪录是迄今为止对于stl发展历史的最完备介绍, 侯捷先生在他的stl有关文章里
推荐大家阅读这篇文章. 因此我将该文全文翻译如下:
q: 您对于generic programming进行了长时间的研究, 请就此谈谈.
a: 我开始考虑有关gp的问题是在7o年代末期, 当时我注意到有些算法并不依赖于数据结构的
特定实现，而只是依赖于该结构的几个基本的语义属性. 于是我开始研究大量不同的算法，
结果发现大部分算法可以用这种方法从特定实现中抽象出来, 而且效率无损. 对我来说,
效率是至关重要的, 要是一种算法抽象在实例化会导致性能的下降, 那可不够棒.
当时我认为这项研究的正确方向是创造一种编程语言. 我和我的两个朋友一起开始干起来.
一个是现在的纽约州立大学教授deepak kapur, 另一个是伦塞里尔技术学院教授david musser.
当时我们三个在通用电器公司研究中心工作. 我们开始设计一种叫tecton的语言. 该语言
有一种我们称为"通用结构"的东西, 其实不过是一些形式类型和属性的集合体, 人们可以
用它来描述算法. 例如一些数学方面的结构充许人们在其上定义一个代数操作, 精化之,
扩充之, 做各种各样的事.
虽然有很多有趣的创意, 最终该项研究没有取得任何实用成果, 因为tecton语言是函数型
语言. 我们信奉backus的理念，相信自己能把编程从von neumann风格中解放出来. 我们
不想使用副效应, 这一点限制了我们的能力, 因为存在大量需要使用诸如"状态", "副效
应"等观念的算法.
我在70年代末期在tecton上面所认识到了一个有趣的问题: 被广泛接受的adt观念有着根本
性的缺陷. 人们通常认为adt的特点是只暴露对象行为特征, 而将实现隐藏起来. 一项操作
的复杂度被认为是与实现相关的属性, 所以抽象的时候应予忽略. 我则认识到, 在考虑一
个(抽象)操作时, 复杂度(或者至少是一般观念上的复杂度)必须被同时考虑在内. 这一点
现在已经成了gp的核心理念之一.
例如一个抽象的栈stack类型, 仅仅保证你push进去的东西可以随后被pop出来是不够的,
同样极端重要的是, 不管stack有多大, 你的push操作必须能在常数时间内完成. 如果我
写了一个stack, 每push一次就慢一点, 那谁都不会用这个烂玩艺.
我们是要把实现和界面分开, 但不能完全忽略复杂度. 复杂度必须是, 而且也确实是横陈
于模块的使用者与实现者之间的不成文契约. adt观念的引入是为了允许软件模块相互可
替换. 但除非另一个模块的操作复杂度与这个模块类似, 否则你肯定不愿意实现这种互换.
如果我用另外一个模块替换原来的模块, 并提供完全相同的接口和行为, 但就是复杂度不
同, 那么用户肯定不高兴. 就算我费尽口舌介绍那些抽象实现的优点, 他肯定还是不乐意
用. 复杂度必须被认为是接口的一部分.
1983年左右, 我转往纽约布鲁克林技术大学任教. 开始研究的是图的算法, 主要的合作伙
伴是现在ibm的aaron kershenbaum. 他在图和网络算法方面是个专家, 我使他相信高序(high
order)的思想和gp能够应用在图的算法中. 他支持我与他合作开始把这些想法用于实际的
网络算法. 某些图的算法太复杂了, 只进行过理论分析, 从来没有实现过. 他企图建立一个
包含有高序的通用组件的工具箱, 这样某些算法就可以实现了. 我决定使用lisp语言的一个
变种scheme语言来建立这样一个工具箱. 我们俩建立了一个巨大的库, 展示了各种编程技术.
网络算法是首要目标. 不久当时还在通用电器的david musser加了进来, 开发了更多的组件,
一个非常大的库. 这个库供大学里的本科生使用, 但从未商业化. 在这项工作中, 我了解到
副效应是很重要的, 不利用副效应, 你根本没法进行图操作. 你不能每次修改一个端点(vertex)
时都在图上兜圈子. 所以, 当时得到的经验是在实现通用算法时可以把高序技术和副效应结
合起来. 副效应不总是坏的, 只有在被错误使用时才是.
1985年夏, 我回到通用电器讲授有关高序程序设计的课程. 我展示了在构件复杂算法时这项
技术的应用. 有一个听课的人叫陈迩, 当时是信息系统实验室的主任. 他问我是否能用ada语
言实现这些技术, 形成一个工业强度的库, 并表示可以提供支持. 我是个穷助教, 所以尽管我
当时对于ada一无所知, 我还是回答"好的". 我跟dave musser一起建立这个ada库. 这是很重
要的一个时期, 从象scheme那样的动态类型语言(dynamically typed language)转向ada这
样的强类型语言, 使我认识到了强类型的重要性. 谁都知道强类型有助于纠错. 我则发现在
ada的通用编程中, 强类型是获取设计思想的有力工具. 它不仅是查错工具, 而且是思想工具.
这项工作给了我对于组件空间进行正交分解的观念. 我认识到, 软件组件各自属于不同的类别.
oop的狂热支持者认为一切都是对象. 但我在ada通用库的工作中认识到, 这是不对的. 二分查找
就不是个对象, 它是个算法. 此外, 我还认识到, 通过将组件空间分解到几个不同的方向上, 我
们可以减少组件的数量, 更重要的是, 我们可以提供一个设计产品的概念框架.
随后, 我在贝尔实验室c++组中得到一份工作, 专事库研究. 他们问我能不能用c++做类似的事.
我那时还不懂c++, 但当然, 我说我行. 可结果我不行, 因为1987年时, c++中还没有模板, 这玩意儿在通用编程中是个必需品. 结果只好用继承来获取通用性, 那显然不理想.
直到现在c++继承机制也不大用在通用编程中, 我们来说说为什么. 很多人想用继承实现数据结构
和容器类, 结果几乎全部一败涂地. c++的继承机制及与之相关的编程风格有着戏剧性的局限. 用
这种方式进行通用编程, 连等于判断这类的小问题都解决不了. 如果你以x类作为基类, 设计了
一个虚函数operater==, 接受一个x类对象, 并由x派生类y, 那么y的operator==是在拿y类对象与
x类对象做比较. 以动物为例, 定义animal类, 派生giraffe(长颈鹿)类. 定义一个成员函数
mate(), 实现与另一个哺乳动物的交配操作, 返回一个animal对象. 现在看看你的派生类giraffe,
它当然也有一个mate()方法, 结果一个长颈鹿同一个动物交配, 返回一个动物对象. 这成何体统?
当然, 对于c++程序员来说, 交配函数没那么重要, 可是operator==就很重要了.
对付这种问题, 你得使用模板. 用模板机制, 一切如愿.
尽管没有模板, 我还是搞出来一个巨大的算法库, 后来成了unix system laboratory standard
component library的一部分. 在bell lab, 我从象andy koenig, bjarne stroustrup(andrew
koenig, 前iso c++标准化委员会主席; bjarne stroustrup, c++之父 -- 译者)这类专家
身上学到很多东西. 我认识到c/c++的重要, 它们的一些成功之处是不能被忽略的. 特别是我发
现指针是个好东东. 我不是说空悬的指针, 或是指向栈的指针. 我是说指针这个一般观念. 地
址的观念被广泛使用着. 没有指针我们就没法描述并行算法.
我们现在来探讨一下为什么说c是一种伟大的语言. 通常人们认为c是编程利器并且获得如此成功,
是因为unix是用c写的. 我不同意. 计算机的体系结构是长时间发展演变的结果, 不是哪一个聪明
的人创造的. 事实上是广大程序员在解决实际问题的过程中提出的要求推动了那些天才提出这些
体系. 计算机经过多次进化, 现在只需要处理字节地址索引的内存, 线性地址空间和指针. 这个
进化结果是对于人们要求解决问题的自然反映. dennis ritchie天才的作品c, 正反映了演化了
30年的计算机的最小模型. c当时并不是什么利器. 但是当计算机被用来处理各种问题时, 作为
最小模型的c成了一种非常强大的语言, 在各个领域解决各种问题时都非常高效. 这就是c可移植
性的奥秘, c是所有计算机的最佳抽象模型, 而且这种抽象确确实实是建立在实际的计算机, 而
不是假想的计算机上的. 人们可以比较容易的理解c背后的机器模型, 比理解ada和scheme语言背
后的机器模型要容易的多. c的成功是因为c做了正确的事, 不是因为at&t的极力鼓吹和unix.
c++的成功是因为bjarne stroustrup以c为出发点来改进c, 引入更多的编程技术, 但始终保持在
c所定义的机器模型框架之内, 而不是闭门造车地自己搞出一个新的机器模型来. c的机器模型非
常简单. 你拥有内存, 对象保存在那里面, 你又有指向连续内存空间的指针, 很好理解. c++保留
了这个模型, 不过大大扩展了内存中对象的范畴, 毕竟c的数据类型太有限了, 它允许你建立新的
类型结构, 但不允许你定义类型方法. 这限制了类型系统的能力. c++把c的机器模型扩展为真正
类型系统.
1988年我到惠普实验室从事通用库开发工作. 但实际上好几年我都是在作磁盘驱动器. 很有趣但跟
gp毫不相关. 92年我终于回到了gp领域, 实验室主任bill worley建立了一个算法研究项目, 由我
负责. 那时候c++已经有模板了. 我发现bjarne的模板设计方案是非常天才的. 在bell lab时, 我参
加过有关模班设计的几个早期的讨论, 跟bjarne吵得很凶, 我认为c++的模板设计应该尽可能向ada的
通用方案看齐. 我想可能我吵得太凶了, 结果bjarne决定坚决拒绝我的建议. 我当时就认识到在c++
中设置模板函数的必要性了, 那时候好多人都觉得最好只有模板类. 不过我觉得一个模板函数在使用
之前必须先显式实例化, 跟ada似的. bjarne死活不听我的, 他把模板函数设计成可以用重载机制来
隐式实例化. 后来这个特别的技术在我的工作中变得至关重要, 我发现它容许我做很多在ada中不可能
的任务. 非常高兴bjarne当初没听我的.
q: 您是什么时候第一次构思stl的, 最初的目的是什么?
a: 92年那个项目建立时由8个人, 渐渐地人越来越少, 最后剩下俩, 我和李梦, 而且李小姐是这个领域的新
手. 在她的专业研究中编译器是主要工作, 不过她接受了gp研究的想法, 并且坚信此项研究将带给软件开
发一个大变化, 要知道那时候有这个信念的认可是寥寥无几. 没有她, 我可不敢想象我能搞定stl, 毕竟
stl标着两个人的名字:stepanov和lee. 我们写了一个庞大的库, 庞大的代码量, 庞大的数据结构组件,
函数对象, 适配器类, 等等. 可是虽然有很多代码, 却没有文档. 我们的工作被认为是一个验证性项目,
其目的是搞清楚到底能不能在使算法尽可能通用化的前提下仍然具有很高的效率. 我们化了很多时间来
比较, 结果发现, 我们算法不仅最通用, 而且要率与手写代码一样高效, 这种程序设计风格在性能上是
不打折扣的! 这个库在不断成长, 但是很难说它是什么时候成为一个"项目"的. stl的诞生是好几件事情
的机缘巧合才促成的.
q: 什么时候, 什么原因促使您决定建议使stl成为ansi/iso标准c++一部分的?
a: 1993年夏, andy koenig跑到斯坦福来讲c++课, 我把一些有关的材料给他看, 我想他当时确实是很兴奋.
他安排我9月到圣何塞给c++标准委员会做一个演讲. 我演讲的题目是"c++程序设计的科学", 讲得很理
论化, 要点是存在一些c++的基本元素所必须遵循的, 有关基本操作的原则. 我举了一些例子, 比如构
造函数, 赋值操作, 相等操作. 作为一种语言, c++没有什么限制. 你可以用operator==()来做乘法.
但是相等操作就应该是相等操作. 它要有自反性, a == a; 它要有对称性, a == b 则 b == a; 它还
要有传递性. 作为一个数学公理, 相等操作对于其他操作是基本的要素. 构造函数和相等操作之间的联
系就有公理性的东西在里边. 你用拷贝构造函数生成了一个新对象, 那么这个对象和原来那个就应该是
相等的. c++是没有做强行要求, 但是这是我们都必须遵守这个规则. 同样的, 赋值操作也必须产生相等
的对象. 我展示了一些基本操作的"公理", 还讲了一点迭代子(iterator), 以及一些通用算法怎样利用迭
代子来工作. 我觉得那是一个两小时的枯燥演讲, 但却非常受欢迎. 不过我那时并没有想把这个东西塞在
标准里, 它毕竟是太过先进的编程技术, 大概还不适于出现在现实世界里, 恐怕那些做实际工作的人对它
没什么兴趣.
我是在9月做这个演讲的, 直到次年(1994)月, 我都没往ansi标准上动过什么脑筋. 1月6日, 我收到
andy koenig的一封信(他那时是标准文档项目编辑), 信中说如果我希望stl成为标准库的一部分, 可以
在1月25日之前提交一份建议到委员会. 我的答复是:"andy, 你发疯了吗?", 他答复道:"不错, 是的我
发疯了, 为什么咱们不疯一次试试看?"
当时我们有很多代码, 但是没有文档, 更没有正式的建议书. 李小姐和我每星期工作80小时, 终于在
期限之前写出一份正式的建议书. 当是时也, 只有andy一个人知道可能会发生些什么. 他是唯一的支
持者, 在那段日子里他确实提供了很多帮助. 我们把建议寄出去了, 然后就是等待. 在写建议的过程
中我们做了很多事. 当你把一个东西写下来, 特别是想到你写的可能会成为标准, 你就会发现设计中
的所有纰漏. 寄出标准后,我们不得不一段一段重写了库中间的代码, 以及几百个组件, 一直到3月份
圣迭戈会议之前. 然后我们又重新修订了建议书, 因为在重新写代码的过程中, 我们又发现建议书中
间的很多瑕疵.
q: 您能描述一下当时委员会里的争论吗? 建议一开始是被支持呢, 还是反对?
a: 我当时无法预料会发生些什么. 我做了一个报告, 反响很好. 但当时有许多反对意见. 主要的意见是:
这是一份庞大的建议, 而且来得太晚, 前一次会议上已经做出决议, 不在接受任何大的建议. 而这个
东西是有史以来最大的建议, 包括了一大堆新玩艺. 投票的结果很有趣, 压倒多数的意见认为应对
建议进行再考虑, 并把投票推迟到下次会议, 就是后来众所周知的滑铁卢会议.
bjarne stroustrup成了stl的强有力支持者. 很多人都通过建议、更改和修订的方式给予了帮助。
bjarne干脆跑到这来跟我们一起工作了一个礼拜。andy更是无时无刻的帮助我们。c++是一种复杂
的语言，不是总能搞得清楚确切的含义的。差不多每天我都要问andy和bjarne c++能不能干这干那。
我得把特殊的荣誉归于andy， 是他提出把stl作为c++标准库的一部分；而bjarne也成了委员会中
stl的主要鼓吹者。其他要感谢的人还有：mike vilot，标准库小组的负责人； rogue wave公司的
nathan myers(rogue wave是boland c++builder中stl方案的提供商 —— 译者)，andersen咨询公
司的larry podmolik。确实有好多人要致谢。
在圣迭戈提出的stl实际与当时的c++，我们被要求用新的ansi/iso c++语言特性重写stl，这些特性
中有一些是尚未实现的。为了正确使用这些新的、未实现的c++特性，bjarne和andy花了无以计数的
时间 来帮助我们。
人们希望容器独立于内存模式，这有点过分，因为语言本身并没有包括内存模式。所以我们得要想出
一些机制来抽象内存模式。在stl的早期版本里，假定容器的容积可以用size_t类型来表示，迭代子
之间的距离可以用ptrdiff_t来表示。现在我们被告知，你为什么不抽象的定义这些类型？这个要求
比较高，连语言本身都没有抽象定义这些类型，而且c/c++数组还不能被这些类型定义所限定。我们
发明了一个机制称作"allocator"，封装了内存模式的信息。这个机制深刻地影响了库中间的每一个
组件。你可能疑惑：内存模式和算法或者容器类接口有什么关系？如果你使用size_t这样的东西，你
就无法使用 t* 对象，因为存在不同的指针类型(t*, t huge *, 等等)。这样你就不能使用引用，因
为内存模式不同的话，会产成不同的引用类型。这样就会导致标准库产生庞大的分支。
另外一件重要的事情是我们原先的关联类型数据结构被扩展了。这比较容易一些，但是最为标准的东
西总是很困难的，因为我们做的东西人们要使用很多年。从容器的观点看，stl做了十分清楚的二分
法设计。所有的容器类被分成两种：顺序的和关联的，就好像常规的内存和按内容寻址的内存一般。
这些容器的语义十分清楚。
当我到滑铁卢以后，bjarne用了不少时间来安慰我不要太在意成败与否，因为虽然看上去似乎不会成功，
但是我们毕竟做到了最好。我们试过了，所以应该坦然面对。成功的期望很低。我们估计大部分的意见
将是反对。但是事实上，确实有一些反对意见，但不占上风。滑铁卢投票的结果让人大跌眼镜，80%赞
成，20%反对。所有人都预期会有一场恶战，一场大论战。结果是确实有争论，但投票是压倒性的。
q: stl对于1994年2月发行的ansi/iso c++工作文件中的类库有何影响？
a: stl被放进了滑铁卢会议的工作文件里。stl文档被分解成若干部分，放在了文件的不同部分中。mike
vilot负责此事。我并没有过多地参与编辑工作，甚至也不是c++委员会的成员。不过每次有关stl的
建议都由我来考虑。委员会考虑还是满周到的。
q: 委员会后来又做了一些有关模板机制的改动，哪些影响到了stl？
a: 在stl被接受之前，有两个变化影响到了我们修订stl。其一是模板类增加了包含模板函数的能力。stl
广泛地使用了这个特性来允许你建立各种容纳容器的容器。一个单独的构造函数就能让你建立一个能容
纳list或其他容器的vector。还有一个模板构造函数，从迭代子构造容器对象，你可以用一对迭代子
当作参数传给它，这对迭代子之间的元素都会被用来构造新的容器类对象。另一个stl用到的新特性是
把模板自身当作模板参数传给模板类。这项技术被用在刚刚提到的allocator中。
q: 那么stl影响了模板机制吗？
a: 在弗基山谷的会议中，bjarne建议给模板增加一个“局部特殊化”(partial specialization)的特性。
这个特性可以让很多算法和类效率更高，但也会带来代码体积上的问题。我跟bjarne在这个建议上共同
研究了一段时间，这个建议就是为了使stl更高效而提出的。我们来解释一下什么是“局部特殊化”。
你现在有一个模板函数 swap( t&, t& )，用来交换两个参数。但是当t是某些特殊的类型参数时，你想
做一些特殊的事情。例如对于swap( int&, int& )，你想用一种特别的操作来交换数据。这一点在没有
局部特殊化机制的情况下是不可能的。有了局部特殊化机制，你可以声明一个模板函数如下：
template <class t> void swap( vector<t>&, vector<t>& );
这种形式给vector容器类的swap操作提供了一种特别的办法。从性能的角度讲，这是非常重要的。如果
你用通用的形式去交换vector，会使用三个赋值操作，vector被复制三次，时间复杂度是线性的。然而，
如果我们有一个局部特殊化的swap版本专门用来交换两个vector，你可以得到一个时间复杂度为常数的，
非常快的操作，只要移动vector头部的两个指针就ok。这能让vector上的sort算法运行得更快。没有局
部特殊化，让某一种特殊的vector，例如vector<int>运行得更快的唯一办法是让程序员自己定一个特殊
的swap函数，这行得通，但是加重了程序员的负担。在大部分情况下，局部特殊化机制能够让算法在某
些通用类上表现得更高效。你有最通用的swap，不那么通用的swap，更不通用的swap，完全特殊的swap
这么一系列重载的swap，然后你使用局部特殊化，编译器会自动找到最接近的那个swap。另一个例子是
copy。现在我们的copy就是通过迭代子一个一个地拷贝。使用模板特殊化可以定义一个模板函数：
template <class t> t** copy( t**, t**, t** );
这可以用memcpy高效地拷贝一系列指针来实现，因为是指针拷贝，我们可以不必担心构造对象和析构
对象的开销。这个模板函数可以定义一次，然后供整个库使用，而且用户不必操心。我们使用局部特殊
化处理了一些算法。这是个重要的改进，据我所知在弗基山谷会议上得到了好评，将来会成为标准的一
部分。(后来的确成了标准的一部分 —— 译者）
q: 除了标准类库外，stl对那一类的应用程序来说最有用处？
a: 我希望stl能够引导大家学习一种新的编程风格：通用编程。我相信这种风格适用于任何种类的应用程
序。这种风格就是：用最通用的方式来写算法和数据结构。这些结构所要求的语义特性应该能够被清楚
地归类和分类，而这些归类分类的原则应该是任何对象都能满足的。理解和发展这种技术还要很长时间，
stl不过是这个过程的起点。
我们最终会对通用的组件有一个标准的分类，这些组件具有精心定义的接口和复杂度。程序员们将不必
在微观层次上编程。你再也不用去写一个二分查找算法。就是在现在，stl也已经提供了好几个通用的
二分查找算法，凡是能用二分查找算法的场合，都可以使用这些算法。算法所要求的前提条件很少：你
只要在代码里使用它。我希望所有的组件都能有这么一天。我们会有一个标准的分类，人们不用再重复
这些工作。
这就是douglas mcilroy的梦想，他在1969年关于“构件工厂”的那篇著名文章中所提出来的东西。stl
就是这种“构件工厂”的一个范例。当然，还需要有主流的力量介入这种技术的发展之中，光靠研究机
构不行，工业界应该想程序员提供组件和工具，帮助他们找到所需的组件，把组件粘合到一起，然后
确定复杂度是否达到预期。
q: stl没有实现一个持久化(persistent)对象容器模型。map和multimap似乎是比较好的候选者，它们可以
把对象按索引存入持久对象数据库。您在此方向上做了什么工作吗，或者对这类实现有何评论？
a：很多人都注意到这个问题。stl没实现持久化是有理由的。stl在当时已经是能被接受的最巨大的库了。
再大一点的话，我认为委员会肯定不会接受。当然持久化是确实是一些人提出的问题。在设计stl，特别
是设计allocator时，bjarne认为这个封装了内存模式的组件可以用来封装持久性内存模式。bjarne的
洞察秋毫非常的重要和有趣，好几个对象数据库公司正在盯着这项技术。1994年10月我参加了object
database management group的一个会议，我做了一个关于演说。他们非常感兴趣，想让他们正在形成
中的组件库的接口与stl一致，但不包括allocator在内。不过该集团的某些成员仔细分析了allocator
是否能够被用来实现持久化。我希望与stl接口一致的组件对象持久化方案能在接下来的一年里出现。
q：set，multiset，map和multimap是用红黑树实现的，您试过用其他的结构，比如b*树来实现吗？
a：我不认为b*适用于内存中的数据结构，不过当然这件事还是应该去做的。应该对许多其他的数据结构，
比如跳表(skip list)、伸展树(splay tree)、半平衡树(half-balanced tree)等，也实现stl容器的标
准接口。应该做这样的研究工作，因为stl提供了一个很好的框架，可以用来比较这些结构的性能。结口
是固定的，基本的复杂度是固定的，现在我们就可一个对各种数据结构进行很有意义的比较了。在数据
结构领域里有很多人用各种各样的接口来实现不同的数据结构，我希望他们能用stl框架来把这些数据
结构变成通用的。
（译者注：上面所提到的各种数据结构我以为大多并非急需，而一个stl没有提供而又是真正重要的数据
结构是哈希结构。后来在stepanov和matt austern等人的sgi*stl中增补了hashset，hashmap和
hashtable三种容器，使得这个stl实现才比较完满。众所周知，红黑树的时间复杂度为o(logn), 而理
想hash结构为o(1)。当然，如果实现了持久化，b+树也是必须的。）
q：有没有编译器厂商跟您一起工作来把stl集成到他们的产品中去？
a：是的，我接到了很多厂家的电话。borland公司的peter becker出的力特别大。他帮助我实现了对应
borland编译器的所有内存模式的allocator组件。symantec打算为他们的macintosh编译器提供一个stl
实现。edison设计集团也很有帮助。我们从大多数编译器厂商都得到了帮助。
（译者注：以目前的stl版本来看，最出色的无疑是sgi*stl和ibm stl for as/390，所有windows下的
的stl实现都不令人满意。根据测试数据，windows下最好的stl运行在piii 500mhz上的速度远远
落后与在250mhz sgi工作站（irix操作系统）上运行的sgi*stl。以我个人经验，linux也是运行stl
的极佳平台。而在windows的stl实现中，又以borland c++builder的rogue wave stl为最差，其效率
甚至低于jit执行方式下的java2。visual c++中的stl是著名大师p. j. plauger的个人作品，性能较
好，但其queue组件效率很差，慎用）
q：stl包括了对ms-dos的16位内存模式编译器的支持，不过当前的重点显然是在32位上线性内存模式
(flat model)的操作系统和编译器上。您觉得这种面向内存模式的方案以后还会有效吗？
a：抛开intel的体系结构不谈，内存模式是一个对象，封装了有关指针的信息：这个指针的整型尺寸和
距离类型是什么，相关的引用类型是什么，等等。如果我们想利用各种内存，比如持久性内存，共享
内存等等，抽象化的工作就非常重要了。stl的一个很漂亮的特性是整个库中唯一与机器类型相关的
部分——代表真实指针，真实引用的组件——被封装到大约16行代码里，其他的一切，容器、算法等
等，都与机器无关（真是牛啊！）。从移植的观点看，所有及其相关的东西，象是地址记法，指针等
等，都被封装到一个微小的，很好理解的机制里面。这样一来，allocator对于stl而言就不是那么
重要了，至少不像对于基本数据结构和算法的分解那么重要。
q：ansi/iso c标准委员会认为像内存模式这类问题是平台相关的，没有对此做出什么具体规定。c++委员
会会不会采取不同的态度？为什么？
a：我认为stl在内存模式这一点上跟c++标准相比是超前的。但是在c和c++之间有着显著的不同。c++有构造
函数和new操作符来对付内存模式问题，而且它们是语言的一部分。现在看来似乎让new操作符像stl容器
使用allocater那样来工作是很有意义的。不过现在对问题的重要性不像stl出现之前那么显著了，因为
在大多数场合，stl数据结构将让new失业。大部分人不再需要分配一个数组，因为stl在做这类事情上
更为高效。要知道我对效率的迷信是无以复加的，可我在我的代码里从不使用new，汇编代码表明其效率
比使用new时更高。随着stl的广泛使用，new会逐渐淡出江湖。而且stl永远都会记住回收内存，因为当
一个容器，比如vector退出作用域时，它的析构函数被调用，会把容器里的所有东西都析构。你也不必
再担心内存泄漏了。stl可以戏剧性地降低对于垃圾收集机制的需求。使用stl容器，你可以为所欲为，
不用关心内存的管理，自有stl构造函数和析构函数来对付。
q：c++标准库子委员会正在制订标准名空间（namespace）和异常处理机制。stl类会有名空间吗，会抛出异
常吗？
a：是的。该委员会的几个成员正在考虑这件事，他们的工作非常卓越。
q：现在的stl跟最终作为标准的stl会有多大不同？委员会会不会干预某些变化，新的设计会不会被严格地控
制起来？
a：多数人的意见看起来是不希望对stl做任何重要的改变。
q：在成为标准之前，程序员们怎样的一些stl经验？
a：他们可以从butler.hpl.hp.com/stl当下stl头文件，在borland和ibm或其他足够强劲的的编译器中使用它。
学习这种编程技术的唯一途径是编程，看看范例，试着用这种技术来编程。
q：您正在和p. j. plauger合作一本stl的书。那本书的重点是什么？什么时候面世？
a：计划95年夏天面世，重点是对stl实现技术的详解，跟他那本标准c库实现和标准c++库实现的书类似。他是
这本书的第一作者。该书可以作为stl的参考手册。我希望跟bjarne合作另写一本书，在c++/stl背景下介绍
语言与库的交互作用。
好多工作都等着要做。为了stl的成功，人们需要对这种编程技术进行更多的试验性研究，更多的文章和书籍
应该对此提供帮助。要准备开设此类课程，写一些入门指南，开发一些工具帮助人们漫游stl库。stl是一个
框架，应该有好的工具来帮助使用这个框架。
（译者注：他说这番话时，并没有预计到在接下来的几年里会发生什么。由于internet的大爆炸和java、
vb、delphi等语言的巨大成功，工业界的重心一下子从经典的软件工程领域转移到internet上。再加上
标准c++直到98年才制订，完全符合要求的编译器直到现在都还没有出现，stl并没有立刻成为人们心中的
关注焦点。他提到的那本书也迟迟不能问世，直到前几天（2001年元旦之后），这本众人久已期盼的书
终于问世，由p. j. plauger, alexander stepanov, meng lee, david musser四大高手联手奉献，
prentice hall出版。不过该书主要关注的是stl的实现技术，不适用于普通程序员。
另外就p. j. plauger做一个简介：其人是标准c中stdio库的早期实现者之一，91年的一本关于标准
c库的书使他名满天下。他现在是c/c++ use's journal的主编，与microsoft保持着良好的，甚至是
过分亲密的关系，visual c++中的stl和其他的一些内容就是出自他的那只生花妙笔。不过由于跟ms
的关系已经影响到了他的中立形象，现在有不少人对他有意见。
至于stepanov想象中的那本与stroustrup的书，起码目前是没听说。其实这两位都是典型的编程圣手，
跟ken thompson和dennis ritchie是一路的，懒得亲自写书，往往做个第二作者。如果作为第一作者，
写出来的书肯定是学院味十足，跟标准文件似的，不适合一般程序员阅读。在计算机科学领域，编程
圣手同时又是写作高手的人是凤毛麟角，最著名的可能是外星人d. e. knuth, c++领域里则首推前面
提到的andrew koenig。可惜我们中国程序员无缘看到他的书。）
q：通用编程跟oop之间有什么关系？
a：一句话，通用编程是oop基本思想的自然延续。什么是oop的基本思想呢？把组件的实现和接口分开，并
且让组件具有多态性。不过，两者还是有根本的不同。oop强调在程序构造中语言要素的语法。你必须
得继承，使用类，使用对象，对象传递消息。gp不关心你继承或是不继承，它的开端是分析产品的分类，
有些什么种类，他们的行为如何。就是说，两件东西相等意味着什么？怎样正确地定义相等操作？不单
单是相等操作那么简单，你往深处分析就会发现“相等”这个一般观念意味着两个对象部分，或者至少
基本部分是相等的，据此我们就可以有一个通用的相等操作。再说对象的种类。假设存在一个顺序序列
和一组对于顺序序列的操作。那么这些操作的语义是什么？从复杂度权衡的角度看，我们应该向用户提
供什么样的顺序序列？该种序列上存在那些操作？那种排序是我们需要的？只有对这些组件的概念型分
类搞清楚了，我们才能提到实现的问题：使用模板、继承还是宏？使用什么语言和技术？gp的基本观点
是把抽象的软件组件和它们的行为用标准的分类学分类，出发点就是要建造真实的、高效的和不取决于
语言的算法和数据结构。当然最终的载体还是语言，没有语言没法编程。stl使用c++，你也可以用ada
来实现，用其他的语言来实现也行，结果会有所不同，但基本的东西是一样的。到处都要用到二分查找
和排序，而这就是人们正在做的。对于容器的语义，不同的语言会带来轻微的不同。但是基本的区别很
清楚是gp所依存的语义，以及语义分解。例如，我们决定需要一个组件swap，然后指出这个组件在不同的
语言中如果工作。显然重点是语义以及语义分类。而oop所强调的（我认为是过分强调的）是清楚的定义
类之间的层次关系。oop告诉了你如何建立层次关系，却没有告诉你这些关系的实质。
（这段不太好理解，有一些术语可能要过一段时间才会有合适的中文翻译——译者）
q：您对stl和gp的未来怎么看?
a：我刚才提到过，程序员们的梦想是拥有一个标准的组件仓库，其中的组件都具有良好的、易于理解的和标
准的接口。为了达成这一点，gp需要有一门专门的科学来作为基础和支柱。stl在某种程度上开始了这项
工作，它对于某些基本的组件进行了语义上的分类。我们要在这上面下更多的功夫，目标是要将软件工程
从一种手工艺技术转化为工程学科。这需要一门对于基本概念的分类学，以及一些关于这些基本概念的定
理，这些定理必须是容易理解和掌握的，每一个程序员即使不能很清楚的知道这些定理，也能正确地使用
它。很多人根本不知道交换律，但只要上过学的人都知道2+5等于5+2。我希望所有的程序员都能学习一些
基本的语义属性和基本操作：赋值意味着什么？相等意味着什么？怎样建立数据结构，等等。
当前，c++是gp的最佳载体。我试过其他的语言，最后还是c++最理想地达成了抽象和高效的统一。但是
我觉得可能设计出一种语言，基于c和很多c++的卓越思想，而又更适合于gp。它没有c++的一些缺陷，特别
是不会像c++一样庞大。stl处理的东西是概念，什么是迭代子，不是类，不是类型，是概念。说得更正式
一些，这是bourbaki所说的结构类型（structure type），是逻辑学家所说的理念（theory），或是类型
理论学派的人所说的种类（sort），这种东西在c++里没有语言层面上的对应物（原文是incarnation，直译
为肉身——译者），但是可以有。你可以拥有一种语言，使用它你可以探讨概念，精化概念，最终用一种
非常“程序化”（programmatic，直译为节目的，在这里是指符合程序员习惯的——译者）的手段把它们
转化为类。当然确实有一些语言能处理种类（sorts），但是当你想排序（sort）时它们没什么用处。我们
能够有一种语言，用它我们能定义叫做foward iterator（前向迭代子）的东西，在stl里这是个概念，没有
c++对应物。然后我们可以从forword iterator中发展出bidirectional iterator（双向迭代子），再发展
出random iterator。可能设计一种语言大为简化gp，我完全相信该语言足够高效，其机器模型与c/c++充分
接近。我完全相信能够设计出一种语言，一方面尽可能地靠近机器层面以达成绝对的高效，另一方面能够处
理非常抽象化的实体。我认为该语言的抽象性能够超过c++，同时又与底层的机器之间契合得天衣无缝。我认
为gp会影响到语言的研究方向，我们会有适于gp的实用语言。从这些话中你应该能猜出我下一步的计划。
mengyan
译于2001年1月Top
91 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-18 09:36:00 得分 0
to lzl:翻遍深圳书城，电子科技书店，海天书店，查之无，老哥，能E一些资料吗？,mail:vcmfc@sina.com
to myan:我将lzl的代码看一遍又一遍，好像list有insert与erase(),哪有ins与del,在你的提示下想到lzl老哥在代码中少了实现部分。
本人非常想与各位高手交流，能告诉你的Mial吗?Top
92 楼LeeFrank（大力）回复于 2001-01-18 10:34:00 得分 10
针对：
例如任一个多项式：
aX(n)是X的n次幂。
在程序中要对X进行降幂排序(最好能有一个较合理的输入输出)。
被除数：aX(n)+bX(n-1)+cX(n-2)+...+dX(0)
除数 : AX(m)+BX(m-1)+CX(m-2)+...+DX(0)
a,A（代表不同变量)为任意整系数，可正，可负。
m,n(代表不同变量)为任意整次幂，可正，可负。
编程把商和余数求出来(商和余数必须是整数，实在不行，先将被除数系数扩大一定倍数，最后再除以这个倍数。像：(X(2)+X)/(2X+1)=[1/2(2X(2)+2X)]/(2X+1)）
石大侠能帮忙吗？（仅仅提供一点思路，我想学过计算机的一般都能有一些，只是不大一样罢了）。我要完整的程序，是否可以？（如不查资料可能要浪费您一些时间，不过您能查出来，也请告诉我一声，我给您加分。）。
我是个只会C的人，我想可以用下面的方法进行设计，因为时间紧，可能会有很多的BUG，请指教。
#include <stdlib.h>
#include <stdio.h>
#define NumOfMum 6
#define NumOfSon 10 /* 定义分子分母的数目，可以根据需要进行再定义 */
main( )
{
int mum[NumOfMum], son[NumOfSon];
int shang[NumOfSon-NumOfMum+1], last[NumOfMum];
int mi, val;
int temp;
int scale = 1;
int place;
int i;
/* 输入分子系数的数组 */
for(i=0; i<NumOfSon; i++)
{
printf("请输入分子中X的幂和对应的系数:\n");
scanf("%d, %d", &mi, &val);
mum[mi] = val;
}
/* 输入分母系数的数组 */
for(i=0; i<NumOfSon; i++)
{
printf("请输入分母中X的幂和对应的系数:\n");
scanf("%d, %d", &mi, &val);
son[mi] = val;
}
place = NumOfSon;
do
{
if((son[place] % mum[NumOfMum]) != 0)
{
scale *= mum[NumOfMum];
for(i=0; i<=place; i++)
son[i] *= mum[NumOfMum];
for(i=NumOfSon-NumOfMum+1; i>NumOfSon-place+1; i--)
shang[i] *= NumOfMum;
}
shang[NumOfMum-place+1] = son[place]/mum[NumOfMum];
for(i=0; i<NumOfMum; i++)
{
son[place-i-1] = son[place-1-i]
- mum[NumOfMum-i-1]*shang[NumOfMum-place-1];
}
place --;
} while(place < NumOfMum);
printf("需要扩大%d倍\n", scale);
printf("商为：\n");
for(i=NumOfSon-NumOfMum; i>=0; i--)
printf("%dx(%d) ", shang[i], i);
printf("\n余数为\n");
for(i=NumOfMum-1; i>=0; i--)
printf("%dx(%d) ", son[i], i);
}
Top
93 楼prefix（MtSC）回复于 2001-01-18 10:34:00 得分 0
你问的这个问题，中学生的程度。半个小时就能完成。Top
94 楼LeeFrank（大力）回复于 2001-01-18 10:37:00 得分 0
抱歉，应该是：
#include <stdlib.h>
#include <stdio.h>
#define NumOfMum 6
#define NumOfSon 10 /* 定义分子分母的数目，可以根据需要进行再定义 */
main( )
{
int mum[NumOfMum], son[NumOfSon];
int shang[NumOfSon-NumOfMum+1], last[NumOfMum];
int mi, val;
int temp;
int scale = 1;
int place;
int i;
/* 输入分子系数的数组 */
for(i=0; i<NumOfSon; i++)
{
printf("请输入分子中X的幂和对应的系数:\n");
scanf("%d, %d", &mi, &val);
son[mi] = val;
}
/* 输入分母系数的数组 */
for(i=0; i<NumOfMum; i++)
{
printf("请输入分母中X的幂和对应的系数:\n");
scanf("%d, %d", &mi, &val);
mum[mi] = val;
}
place = NumOfSon;
do
{
if((son[place] % mum[NumOfMum]) != 0)
{
scale *= mum[NumOfMum];
for(i=0; i<=place; i++)
son[i] *= mum[NumOfMum];
for(i=NumOfSon-NumOfMum+1; i>NumOfSon-place+1; i--)
shang[i] *= NumOfMum;
}
shang[NumOfMum-place+1] = son[place]/mum[NumOfMum];
for(i=0; i<NumOfMum; i++)
{
son[place-i-1] = son[place-1-i]
- mum[NumOfMum-i-1]*shang[NumOfMum-place-1];
}
place --;
} while(place < NumOfMum);
printf("需要扩大%d倍\n", scale);
printf("商为：\n");
for(i=NumOfSon-NumOfMum; i>=0; i--)
printf("%dx(%d) ", shang[i], i);
printf("\n余数为\n");
for(i=NumOfMum-1; i>=0; i--)
printf("%dx(%d) ", son[i], i);
}
--------------------------------------------------------------------------------
我要回复： 有人参与讨论这个问题，请用EMail通知我
Top
95 楼realcedar（void）回复于 2001-01-18 11:08:00 得分 0
《掌握标准C++类》一书我在深圳书城到是买过一本，8、9月分巴，不知vcmfc是否找的这一本书？人民邮电出版社的，作者：Cameron Hughes,Tracey Hughes 翻译：健莲科技
Top
96 楼realcedar（void）回复于 2001-01-18 11:16:00 得分 0
惭愧惭愧，这么多高人，看来以后要经常来逛逛了。Top
97 楼hugos（疯狂老鼠）回复于 2001-01-18 11:29:00 得分 0
多项式除法的算法可以参考CRC（循环冗余码）的算法。因为CRC的检错和纠错原理就是利用多项式的除法。该算法通过一个简单的硬件电路就可以实现，软件亦然。Top
98 楼gun2（）回复于 2001-01-18 12:41:00 得分 0
《掌握标准C++类》一书其实写得很不好.此书的两个作者水平很一般.专门出些入门性质的书.另外,此书的印刷质量也很差.读起来很不舒服.
Top
99 楼yudi1226（雨滴1226）回复于 2001-01-18 15:15:00 得分 0
华为试题
屋里3盏灯,在门外有三个开关,看不到里面情形,只开1盏灯,判断那个开关控制那盏灯,我是按照脑筋急转弯答的:拉开一个按钮,点一会儿,关掉.再开一盏,可以判断出一个.开门,摸余下两盏灯,看那盏热,就是打开有关掉的,
可面试人说不对,不知道还有什么程序算法在里面呢?
Top
100 楼vcmfc（【痛苦的虫虫】）回复于 2001-01-18 15:31:00 得分 0
to realcedar:再去翻一次!Top
101 楼sxbyl（sxbyl）回复于 2001-01-18 15:34:00 得分 0
？？？
那不是微软的题吗？微软的答案就是那样。Top
102 楼monkeyfu（大圣）回复于 2001-01-18 15:50:00 得分 0
To wnn:
什么叫吹牛，再说了，这有什么可吹的。这类问题不需要什么高深的数学知识，
只要你数据结构玩的好，这类考试就能玩的转。Top
103 楼xfyxq（小小旗) (抵制日货）回复于 2001-01-18 16:06:00 得分 0
太好了，看以上的题目，我应聘有信心了！！！！！感谢大家！！！！！！！！Top
104 楼wjm2000（）回复于 2001-01-18 16:32:00 得分 0
这是哪个鸟公司!
这种题只要看两页数据结构的书不就行了!
不过我自己也刚刚经力过!
只是比这容易!
写一练表的操作!
我5分钟搞定!
搞得老板叫我马上上班!
所以我现在坐在这个公司电脑旁边了!Top
105 楼DoDong（东东）回复于 2001-01-18 17:53:00 得分 0
这种题也要用几小时来做，真是浪费我们程序员的宝贵青春！
唉，青春一去不复返！Top
106 楼jack_fu（）回复于 2001-01-19 16:46:00 得分 0
今天刚去此公司，要求写一两分法查找程序。我的原码如下：
int Find(int p[],int a,int N)
{
int n = N;
int nTemp,nPoint,nDiv;
nPoint = N/2;
nDiv = 2; &n