2011年11月26日
curlcommand line url
curl www.baidu.com 查看网页源码
假定文件上传的表单是下面这样:
<form method="POST" enctype='multipart/form-data' action="upload.cgi">
<input type=file name=upload>
<input type=submit name=press value="OK">
</form>
你可以用curl这样上传文件:
curl --form upload=@localfilename --form press=OK [URL]
curl --user-agent "[User Agent]" [URL] 模拟user agent
curl --user-agent "[User Agent]" [URL] 发送cookie
curl --user-agent "[User Agent]" [URL] 增加头
curl --user-agent "[User Agent]" [URL] http认证
tartar -xvf 解压
tar -cf target.tar.gz xxx压缩
tar -tvf target.tar.gz 查看压缩文件内容
PATHpath是命令行命令的选取路径。可以通过echo $PATH来查看。
有时候需要修改路径,则通过export PATH /usr/bin:/bin 来修改。
如果需要一直修改,则需要修改配置文件。在~/目录下有个.bash_profile文件,修改里面的PATH。
修改完成后运行source ~/.bash_profile刷新。
如果需要修改全局的,则可以修改/etc/profile。
chown 可以修改文件的拥有者要拥有root权限才可以进行修改
chown [-cfhvR] [--help] [--version] user[:group] file..
最常用的参数是-R,当前目录下所有文件和目录进行变更(递归进行)
posted @
2011-11-26 21:05 dead_horse 阅读(1019) |
评论 (0) |
编辑 收藏
connect是一个web server中间件。
使用方法:
var connect = require('connect');
connect(
connect.static(__dirname + '/public', { maxAge: 0 })
, function(req, res) {
res.setHeader('Content-Type', 'text/html');
res.end('<img src="/tobi.jpeg" />')
}
).listen(3000);
思路:
通过connect创建一个http|https server,提供http server的所有功能。
connect是原型继承于http server的,它会用use到的中间件替换掉server的requestListener。
通过connect.use(route, handle)来对每一个路由添加中间件,这些中间件handle会与route绑定保存在一个stack里面,每次有request请求的时候,遍历这个堆,找到对应route的handle,执行handle,如果handle最后调用了next(),就会继续寻找并执行下一个匹配的handle。
通过封装handle,可以很容易的在connect基础上添加更多的middleware。
connect.js
有一个createServer方法,可以通过connect()访问到。根据第一个参数,如果是object,就当作是https的选项,创建HTTPSServer,如果第一个参数不是object,则创建HTTPServer,所有的参数(除了https的选项)都是一个中间件handle,会在HTTPServer绑定到‘/’路径上。
HTTPSServer是在HTTPServer的基础上添加了一层,可以启用HTTPS服务。
同时,connect.js会读取middleware文件夹,把里面的中间件读取到,为他们创建getter,可以通过connect.static()访问到。
而每一个中间件文件暴露在外的函数都是返回一个handle。
http.js
HTTPServer:初始化的时候会把所有的参数当作handle存放进stack,然后以handle方法为requestListener调用http.Server方法。
HTTPServer随后会继承http.Server的原型。
use(route, handle)
把handle去除外壳之后绑定到route上面,存入stack中。
handle(req, res, next)
遍历整个stack,寻找到req.url与route匹配的元素,执行它的handle。当所有的元素都遍历完还有错误,则输出。
util.js
这是一个工具包,里面包含了用到的各种工具函数。
pause(obj)
把传递进来的obj对象的'data'和'end‘事件都保存下来,返回两个函数:end():不再保存事件。resume():停止保存并把之前保存的事件释放出去给obj再次捕获,达到暂停这个obj对象的效果。(感觉可能会有bug,如果在这里释放的时候又有'data'或者'end'事件触发会不会导致顺序变乱?)
parseCookie(str)
把str以;或者,为分隔符分开。每一个都是一个cookie键值对,然后再以=分开。去除value的引号。每个键只能被取得一次。
中间件:
router
connect的route使用方法和express类似。
1 connect(connect.route(function(app){
2 app.get('/:id', middle1, middle2, cb);
3 app.post('/admin', cbpost);
4 }));
route.js内有一个_methods数组,存放所有的route请求方法名称。(get/post/put/...)。
methods对象和routes对象根据_methods内的名称,包含着响应的元素,如:methods['get'], routes['get']。
methods对象,根据_methods数组内的方法名称,为每一个方法调用来一个生产函数,这个函数首先把routes对象内的成员赋值[],然后返回一个函数,这个函数用来产生routes的内容。
methods还有一个元素param,调用它可以为path中出现了某个param的时候设置对应的处理方法。
例如:
app.param('id', function(req, res, next, val){}),
当path中有param id出现的时候,会先调用这个注册的函数再进行后面的操作。
在进行完上述对象的初始化之后,route模块会进行fn.call(this, methods)的调用,即用methods作为参数调用传递进来的匿名函数。所以在app.get('/:id', cb, cb1);的时候,实际调用的是methods.get('/:id', cb, cb1),而methods.get即是之前生产函数的返回函数。
这个函数的处理:cb为这条路由的handle,middle1..middle2..等中间件函数将会存放在cb.middleware数组中(这里会产生一个bug)。然后把'/'转化成为正则对象,然后在转化正则的时候,可能会遇到路径里面有:id等key,会把这些key存放到keys里面。
最终的routes内将会多处一条routes['GET']的记录:
GET:
[ { fn: [Object],
path: /^\/(?:([^\/]+?))\/?$/i,
keys: [Object],
orig: '/:id',
method: 'GET' } ]
刚才说会产生一个bug,是当有两条以上的route以cb作为handle的时候:
app.get('/:id', middle1, middle2, cb);
app.get('/:id/test', middle3, cb);
因为最终的handle都是cb,此时cb的middleware数组会在第二次处理get的时候把第一次的覆盖掉,造成第一次的middleware被替换。
至此,所有的准备工作完成了,然后会返回一个router函数作为handle。
实际request请求触发的时候:
作为handle的router函数被调用,先通过match(req, routes, i)函数,查找req.method对应方法的route的path,与req.pathName匹配。找到路径匹配的把这个route内的这个对象内的fn,同时把keys params method存放到fn里面整合称为一个route返回。返回的route内容形式为
{ [Function]
middleware: [ [Function], [Function] ],
keys: [ 'id' ],
method: 'GET',
params: [ id: 'ca' ] }
然后函数去寻找是否通过methods.param定义了这条route中的param的处理函数,如果有,在这里就执行完对应param的处理函数。之后执行middleware数组内的函数,最后执行这个route。即上一段中说到的fn。这之中能够链式执行下去的条件是中间函数都执行了next(),继续调用下去,当然也可以其中某个函数就结束整个处理。
bodyParser
bodyParser用来解析post方法传递过来的参数。
只接受mime类型为
application/x-www-form-urlencoded
application/json
multipart/form-data
三种的非GET和HEAD请求。
application/x-www-form-urlencoded通过模块qs.parse来解析。application/json通过JSON.parse解析。
multipart/form-data是文件上传,通过formidable解析。
static
static是一个静态文件服务器。
connect.static(root, options)会产生一个handle,handle设置默认的options然后调用send函数。
options内容:
root:静态服务器的根路径,必须由connect.static传入。
path:访问的文件路径
getOnly:访问方法限制(默认是true:只允许get方法访问 )
maxAge:时间限制
redirect:在访问的路径是目录的时候,如果允许redirect,则会redirect到这个目录下的index.html文件,默认为true
callback:在每次静态服务之后调用的函数(包括发生错误,发生错误之后不会再调用next)。
hidden:是否允许访问隐藏文件(默认为false)
根据这些参数来决定访问限制。
支持conditional和range。
最终通过
var stream = fs.createReadStream(path, opts);
stream.pipe(res);
管道的方式来传送文件内容。
posted @
2011-11-26 21:01 dead_horse 阅读(3838) |
评论 (0) |
编辑 收藏
2011年10月15日
接触javascript应该有三个月了,但是一直没有认真去学习这门语言的一些特性,现在结合C++的语言特性来分析一下,对自己脑海中的知识做个总结。
1、C++是静态语言,js是动态语言。区别如下:
静态语言:
1.在不执行的时候也能够做类型检测,可以一定程度上的检测出一些逻辑错误。但是过多的声明使得程序变得冗余。
2.编写代码开始的时候就要考虑变量和算式应该是什么类型,有利于编写好的、高可用性的程序。
3.对编译器提示有作用,同时也对理解代码有作用。
问题:灵活性不够,不定义类型无法写程序。
动态语言:
1.最大优点是代码简洁。
2.十分灵活。
问题:运行速度相对会慢一些,要做类型检查。最大缺点是不执行就无法检测出错误。
2、C++是编译型语言,js是解释型语言。
C++的编译过程:预处理->编译优化->汇编->链接。
Js的解析机制:预处理(分段读取代码预处理)->解释执行
3、C++有指针,js无指针。
在C++中的赋值,所有的基本类型都是直接复制,而自定义类型因为有指针的存在,可以自己选择进行深复制(复制)还是浅复制(引用)。而在js中,所有的基本类型赋值都是复制,而所有的其他类型赋值都是引用。
4、js是函数式编程语言,C++不是。
Js把函数当作对象来处理,可以将它当作函数的输入参数和输出值(高阶函数)。
C++如果要把函数当作其他函数的输入参数,即实现高阶函数,必须要通过函数指针(经常还要多传递一个(void *)类型的参数作为参数的函数的参数)。
5、C++的继承是基于类的,js的继承基于原型
在C++中,继承是通过类来进行的。比较符合人的直观思维。同时在生成一个类之后,是不能够对它进行修改了,除非再去修改它的定义。(Ruby基于开放类的继承可以在定义之后任意追加类的内容)
在js中,继承则是通过原型链的方式来进行的。同样也可以在定义之后修改原型链。同时,也可以修改内置类型的原型链来扩展内置类型(慎用,monkey patching可能导致内置对象大幅度修改产生难以预期的行为)。
(JS特性)
6、js的一个重要特性是闭包(当前作用域可以访问并保存外部作用域的变量)。
Js的闭包在函数返回之后,还能够保持闭包引用到的变量不释放。其最大的用途有两个:一是可以函数返回闭包,让外面可以读取访问到函数内的值,二是让这些变量的值一直保存在内存之中不释放。
有闭包很容易实现内部迭代器(each方法),而C++没有闭包,共有循环外部信息比较麻烦,采取的是外部迭代器方法(vector<int>::iterator)。
注意事项:
1. 如果滥用闭包容易消耗大量内存,同时在IE中会有内存泄漏问题,所以在退出函数之前将不使用的局部变量全部删除。
2. 闭包也会在外部改变父函数内部的值,因此用闭包当共有方法的时候要注意不要随便改变内部的值。
7、js可以显示的设置上下文。
Js可以通过applay和call方法显示指定函数内的this。applay参数传递用数组,call参数分开传。
(未完待续)
上述浅薄个人看法,如果有错误希望大家能够指正。
posted @
2011-10-15 02:42 dead_horse 阅读(7473) |
评论 (0) |
编辑 收藏
2011年9月23日
最近在做nodejs的web开发,初次接触到mongoDB这个数据库。
其实之前对关系型数据库的接触也不是很多,不过在刚接触使用mongoDB的时候还是习惯性的把关系型数据库的设计思维带了进去。在设计数据库的时候,还是把一些关系型数据库设计的思维带进去了,没有发挥出mongoDB文档型数据库的优势。mongoDB可以方便的把一些本来mySQL需要通过一对多关系关联的数据通过数组+对象的方式作为一个文档存储到一个collections里面,并且提供了各种API支持对一个文档里面的数组进行操作。 此次实践选用的node中间件是mongoskin,不过惭愧的是基本没有用到mongoskin的太多特性,基本当作node-mongodb-native来使用。不过写完之后,对于mongoDB的查询API以及node同mongoDB的交互有了一定的了解。
MongoDB常用查询方法与在node中的体现:
1)数据库连接
mongoDB: mongo -u username -p password host:port/dbs
node+mongoSkin: require(“mongoskin”).db(username:password@host:port/dbs);
2)索引 person.ensureIndex({“name”:1},{“unique”:true}, callback);
第一个参数是selector,第二个参数是选项,有unique(唯一索引)等mongoDB索引选项。
ensureIndex先查找是否存在这个索引,如果不存在,则建立索引,因此不会出现重复建立的情况。
3)新建数据
person.save({“name”:”jobs”, age:32, gender:”male”}, callback);
person.save({“name”:”tim”, age:29, gender:”male”}, callback);
4)查询
findOne方法:查询符合selector条件的结果,取第一条给callBack,err是错误信息,如果没有错误,则为undefined,data数据为一个js对象。
person.findOne({“name“:”jobs”}), callBack(err, data));
find方法:查询符合selector条件,并且还可以加入一系列参数,最后通过toArray方法,把数据生成数组的方式传递给callback。
person.find({“gender”:”male”},{sort:[['name', 1]],skip:pageNum*(page-1), limit:pageNum}).toArray(callback(err, data){})
同时查询的时候可以通过$in,$gt,$lt等方式来确定selector的范围。
5)更改
有两点要注意:
1.update方法如果是要更新文档中的一个或几个属性的时候,必须要用形如{$set:{age:33}}的形式,如果写成{age:33}的形式,则这个文档的其他内容都会被删除,只剩{age:32}这一个属性。
2.update方法默认是只更新找到的第一个文档,如果需要所有的文档都更新,则需要在option部分再加上{multi:true},如果想要在查找不到这条记录的时候新增一条,则要在option部分加上{upsert:true}。
person.update({“name”:”jobs”}, {$set{“age”:33}}, {multi:true}, callback(err))
6)删除 person.remove({“name”:”jobs”},callback(err){});
7)selector中使用mongoDB自动生成的_id
mongoDB会为每一个文档生成一个_id属性,类似于mySQL的主键,是唯一的。_id的类型是mongoDB自己定义的objectID类型,因此尽管在查询的时候可以得到一个12位或者24位的_id字符串,但是如果想在selector里面通过_id进行查找或其他操作的时候,必须要先通过db.collection.id()方法进行类型转换。
person.remove({“_id”:person.id(stringID)}, callback(err){});
8)mongoDB对文档内的数组进行操作(通过update方法)
1.通过$addToSet方法向数组中插入记录,插入前该方法会先查找是否存在这条记录,如果存在则不插入。如果想要插入重复的值,则可以通过$push进行添加。
person.update({“name”:”jobs”}, {$addToSet: {
company: {
name: “google”,
address: USA,
workingTime: 3
}
}, function(err){});
2.修改数组中的数据:通过$符。如果在数组中查询的时候要匹配两个属性,必须要使用$elemMatch方法,如果只通过{"name":”google”, "address":USA}去查找,会选择到所有name为google或者address为USA的元素。在定位到这个元素之后,通过$来选定它进行修改。
person.update({
“name”:”jobs”,
company:{$elemMatch:{"name":”google”, "address":USA}}
}, {$set:{"company.$.workingTime":4}},function(){})
3.删除数组中的数据:通过$pull方法
person.update({
“name”:”jobs”,
},{$pull:{company:{“name”:”google”, “address”:”USA”}}},function(err){})
posted @
2011-09-23 15:15 dead_horse 阅读(14934) |
评论 (0) |
编辑 收藏
2011年9月22日
一、编译过程:
1)预处理,生成.i文件
2)转换成为汇编语言,生成.s文件
3)汇编变为目标代码(机器代码),生成.o文件
4)链接目标代码,生成可执行程序。
二、常用编译选项
tips:选项必须独立给出:‘-pg’和‘-p -g’完全不同
-c:编译或汇编源文件,不做连接。
G++ -c test.cpp输出test.o
-o file:制定输出文件为file
-Wall: 输出所有编译警告(最好加上)
-Dmacro=XXX:定义宏。
-shared:生成一个共享库文件
g++ -shared -o libtest.so test.o
-fPIC:生成位置无关目标代码,适用于动态连接。
-llibrarytest:连接名字为librarytest的库
真正名字是liblibrarytest.so(a) so是动态库,a是静态库。
严格按照文件名搜索,版本号要创建软连接。
编译搜索目录:
用户-L指定, LIBRARY_PATH,系统目录/lib /usr/lib
运行搜索目录:
LD_LIBRARY_PATH,ld.so.cache & /etc/ld.so.conf ,系统目录 /lib /usr/lib
动态库和静态库同名,优先动态库。
-Ldir:添加库文件搜索路径 -Idir(include):添加头文件搜索路径
-g:产生调试信息
-olevel:优化级别,一般用o2
三、静态库、共享库
静态库:一些.o文件打包,在被连接后成为程序的一部分。
编译方法
-g++ -c test.cpp
-ar res libtest.a test.o
链接方法:
-g++ -Wall -o test testMain.cpp -ltest -L./
共享库:链接的时候不会被复制到程序中。
编译方法:
g++ -c fPIC test.cpp
//要动态 g++ -shared -WI, -soname, libtest.so, -o libtest.so.1.0.1 test.o
mv libtest.so.1.0.1 /usr/lib
sudo ldconfig & || ll /user/lib/libtest.so //创建一个软连接。
链接方法:
g++ -o test test.cpp ./libtest.so -ldx_cxx
四、常用命令
ldd:显示程序依赖的同台共享库。
file:查看文件格式信息。
ldconfig:在搜寻目录下搜索出可以共享的动态链接库
posted @
2011-09-22 03:59 dead_horse 阅读(3726) |
评论 (0) |
编辑 收藏
2011年9月14日
mongoDB是不支持多表查询的,而nodeJS又是异步的,导致多表查询比较麻烦。
一个十分简陋的多表查询方法(只有一个关联条件):先从第一个collection中查询得到数据,将其中两个collection关联的field从中取出来并去重,通过$in在第二个collections中查询。
在写数组去重的时候,发现js语言特性写这种函数比C++轻松太多。
var users = [], uhash={};//uhash是辅助用hash表
for(var i=0, len=data.length; i<length; ++i){
if (!uhash[data[i].email]) {//只有hash表中不存在再插入
uhash[data[i].email] = true;
users.push(data[i].email);
}
}
hash可以非常方便的帮助完成一些辅助数组的任务。
posted @
2011-09-14 01:42 dead_horse 阅读(6015) |
评论 (1) |
编辑 收藏
2011年8月24日
这算是我第一个web的程序,写的各种丑陋不堪..记录一些不算收获的东西。看到哪写到哪。
1、路由中间件:用户登录检测和权限检测可以交给路由中间件去处理。
app.post("/application/manage/:id/coopmng", hasLogin, checkChangeAuth("infoRight"), manager.doCoopmng);
checkChangeAuth通过返回一个函数,所以可以在路由中间件中传递参数进去,更加灵活。
2、通过prototype,可以十分轻易的扩展内置的对象:扩展Date,添加format方法。
/**
* 时间对象的格式化;
*/
Date.prototype.format = function(format){
/*
* eg:format="YYYY-MM-dd hh:mm:ss";
*/
var o = {
"M+" : this.getMonth()+1, //month
"d+" : this.getDate(), //day
"h+" : this.getHours(), //hour
"m+" : this.getMinutes(), //minute
"s+" : this.getSeconds(), //second
"q+" : Math.floor((this.getMonth()+3)/3), //quarter
"S" : this.getMilliseconds() //millisecond
}
if(/((|Y|)+)/.test(format)) {
format = format.replace(RegExp.$1, (this.getFullYear()+"").substr(4 - RegExp.$1.length));
}
for(var k in o) {
if(new RegExp("("+ k +")").test(format)) {
format = format.replace(RegExp.$1, RegExp.$1.length==1 ? o[k] : ("00"+ o[k]).substr((""+ o[k]).length));
}
}
return format;
}
3、cookie处理:在登录的时候,给它设置一个cookie,设定好过期时间,内容包含:userName,timestamp,checkCode=md5(userName, password, timestamp, skey)。skey是保存在服务器端的一个私钥。在登录验证cookie的时候,先检测时间是否过期(不能只依靠cookie的自动失效),然后再取出user现在的password,重新计算checkCode。可以保证用户修改密码后之前的cookie会失效。
4、通过eventProxy,可以并行查询数据库,提高效率,同时让代码简洁。
checkEventProxy.assign("checkName", "checkEmail", function(goodName, goodEmail){
console.log(goodName);
if(!goodName)
return res.render("error", {message:"昵称已经被注册"});
if(!goodEmail)
return res.render("error", {message:"email已经被注册"});
else{
users.save({email:userEmail, nickName:userNickName, password:userPassword}, function(err){
if(err){
log.error(err);
return res.render("error", {message:"注册失败,请稍后再试"});
}
else{
req.session.email = userEmail;
req.session.nickName = userNickName;
res.redirect("/application");
}
});
}
});
//检查email是否已经存在
users.findOne({email:userEmail.toString()},function(err, item){
if(err){
log.error(err);
checkEventProxy.trigger("checkEmail", false);
}else{
if(item)
checkEventProxy.trigger("checkEmail", false);
else
checkEventProxy.trigger("checkEmail", true);
}
});
//检查昵称是否已经存在
users.findOne({nickName:userNickName.toString()}, function(err, item){
if(err){
log.error(err);
checkEventProxy.trigger("checkName", false);
}else{
if(item)
checkEventProxy.trigger("checkName", false);
else
checkEventProxy.trigger("checkName", true);
}
});
}
5、通过谷歌smtp.gmail.com或者其他的smtp服务提供商,可以发送邮件(不需要sendmail支持)。nodemailer模块(npm install nodemailer)可以十分简单的发送邮件以及附件。
6、mongoDB不支持多表查询,所以可能要有适当的数据表项冗余。同时mongoDB不提供事务,也无法完全保证原子性。
mongoDB选定collection后的增删查改操作:
db.collections("users").findOne({userEmail:email},{nickName:1/*查询结果包含nickName*/}, function(err,data){});
db.collections("users").find({userEmail:email},{skip:10/*跳过10条记录*/, limit:10/*结果最多10条,。实现分页功能*/}).toArray(function(err,data){});
db.collections("users").save({/*save的内容*/}, function(){})//插入
db.collections("users").remove({/*条件*/},function(){})
db.collections("users").update({/*条件*/},{$set:{/*内容*/}})
7、div通过float左右分屏的时候,必须要在它们的父div添加fixClear类。通过添加一个隐藏的元素在父div最下方,让浏览器检测到两个左右浮动的div的高度,从而不会出现显示错误。
.clearfix:after {
content: ".";
display: block;
clear: both;
visibility: hidden;
line-height: 0;
height: 0;
}
.clearfix {
display: inline-block;
}
8.express的session,默认是存为持久的,像cookie一样要到一定时间才过期。在存session的时候,通过把req.session.cookie.expires设置成为false,可以将session设置为非持久,这样在浏览器关闭的时候,session就会消掉。
posted @
2011-08-24 01:48 dead_horse 阅读(3228) |
评论 (1) |
编辑 收藏
2011年8月18日
摘要: 在写node.js的时候,经常会遇到要去数据库的多个地方取得多个数据,然后才能进行下一步的操作的情况。如果是线性执行的语言,通常的做法是一条一条去取,全部取到之后再进行下一步操作。然而在node里面,因为是基于事件的,所以只能够一层一层的在回调函数里面嵌套进去。取到第一个数据之后,执行回调函数去取第二条数据,然后再执行回调函数。
对于node来...
阅读全文
posted @
2011-08-18 15:24 dead_horse 阅读(3331) |
评论 (0) |
编辑 收藏
2011年8月12日
最近刚开始接触web开发,学习node.js,在写的时候经常会出现Can't set headers after they are sent这个错误。
发现是在redirect或者render之后,node并不会跳出代码段,中断下面的执行,而是继续往下执行,当再次redirect或者render的时候,就会出现这个错误。
要在redirect和render之前适时加上return,结束它们之后的代码执行,可以避免这个错误。
posted @
2011-08-12 01:08 dead_horse 阅读(7763) |
评论 (4) |
编辑 收藏
2011年6月8日
lower_bound&upper_bound是二分查找的一种版本,在已排序的区间中寻找可插入value的第一个位置和第一个不小于value的位置。
lower_bound的实现(forward_iteratror版本,其random_access_iterator版本不需要用distance函数,直接用+):
template<class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value,
Distance*,
forward_iterator_tag)
{
Distance len=0;
distance(first, last, len); //求整个区间的长度
Distance half;
ForwardIterator middle;
while(len>0)
{
half=len>>1; //除以二
middle=first;
advance(middle, half); //middle指向中间位置
if(*middle<value)
{
first = middle;
++first;
len=len-half-1; //修正len
}
else
len=half;
}
return first;
}
upper_bound的实现(forward_iterator版本):
template<class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value,
Distance*,
forward_iterator_tag)
{
Distance len=0;
distance(first, last, len); //求整个区间的长度
Distance half;
ForwardIterator middle;
while(len>0)
{
half=len>>1; //除以二
middle=first;
advance(middle, half); //middle指向中间位置
if(value<*middle)
{
len=half;
}
else
{
first = middle;
++first;
len=len-half-1; //修正len
}
}
return first;
}
upper_bound和lower_bound的区别在于取等号时的做法。upper_bound将等号放在大于号一起处理,lower_bound则相反,因此两者最终得到的结果也不同。binary_search()可以通过lower_bound得到。
排序算法(重点):
partial_sort:将一个区间内的前N个元素进行排序。
方法:堆排序:(从小到大排序)先将前N个元素make_heap,生成一个max_heap,然后对N+1~size的元素与max_heap的顶依次比较,如果比堆顶元素小,则交换两元素位置,再对堆进行重排。循环过后再对堆进行sort_heap。
make_heap(first, middle);
for(RandomAccessIterator i = middle; i<last; ++i) //只能是随机迭代器
if(*i<*first)
__pop_heap(first, middle, i ,T(*i), dfistance_type(first));
sort_heap(first, middle);
sort:对所给区间进行排序。
方法:快速排序(改进版),改进方法:结合插入排序、采用三点中值法选区pivot,使用内省式排序(在结合插入排序、三点中值法的同时,检测如果递归次数达到限定次数时,改为使用堆排序,防止出现二次的时间效率。)
sort接受两个随机迭代器作为参数(只有随机迭代器能够使用sort)
inline void sort(RandomAccessIterator first, RandomAccessIterator last)
{
if(first != last)
{
__introsort_loop(first, last, value_type(first) //内省式排序
__lg(last-first)*2);
__final_insertion_sort(first, last); //最终进行一次插入排序
}
}
__lg()用来控制最多的递归次数,找出2^k<n的最大K。当个数为40时,得到5。5*2=10为最多允许分割层数。
template<class Size>
inline Size __lg(size n)
{
Size k;
for(k=0; n>1; n>>=1) ++k;
return k;
}
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last.
T*, Size depth_limit)
{
while(last-first>__stl_threshold) //__stl_threshold=const int 16
{
if(depth_limit==0)
{
partial_sort(first, last, last); //改用heapsort
return;
}
--depth_limit;
RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first,
*(first+(last-first)/2,
*(last-1)))));
//cur为三点中值法求出来的pivot
//右半段递归
__introsort_loop(cut, last, value_type(first), depth_limit);
last=cut;//定位到左半段再递归处理(左右共用一个depth_limit)
}
}
分割方法:
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
RandomAccessIterator last,
T pivot)
{
while(true)
{
while(*first < pivot) ++first;
--last;
while(pivot < *last) --last;
if(!(first<last)) return first;
iter_swap(first, last);
++first;
}
}
在上述步骤做完以后,变将区间内元素分成了多个元素个数少于16的子序列,这个时候就进入到母函数,然后进行最后的插入排序。
SGI STL的最后插入排序是将其分成两部分:前一部分直接调用插入排序。后一部分再重写的一段插入排序(为什么这样做?)。
posted @
2011-06-08 01:06 dead_horse 阅读(1022) |
评论 (0) |
编辑 收藏