随笔-16  评论-7  文章-0  trackbacks-0
  2011年11月26日
curl
command line url

curl www.baidu.com    查看网页源码

curl -o 【文件名】 www.baidu.com  保存网页,跟wget一样
curl -L www.baidu.com 如果网址是自动跳转的,这样就会跳转到新的网页
curl -i www.baidu.com 显示网页头信息和网页源代码
curl -I www.baidu.com 只显示网页头信息
curl -v www.baidu.com 显示整个http通信过程
curl www.baidu.com?q=test get表单提交
curl --data "q=test" www.baidu.com post表单提交

假定文件上传的表单是下面这样:

  <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 --referer http://www.example.com http://www.example.com 表示从哪里跳转过来
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认证
tar
tar -xvf 解压
tar -cf target.tar.gz xxx压缩
tar -tvf target.tar.gz 查看压缩文件内容


PATH
path是命令行命令的选取路径。可以通过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 阅读(742) | 评论 (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 阅读(3339) | 评论 (0)编辑 收藏
  2011年10月15日


接触javascript应该有三个月了,但是一直没有认真去学习这门语言的一些特性,现在结合C++的语言特性来分析一下,对自己脑海中的知识做个总结。

 

1C++是静态语言,js是动态语言。区别如下:

静态语言:

1.在不执行的时候也能够做类型检测,可以一定程度上的检测出一些逻辑错误。但是过多的声明使得程序变得冗余。

2.编写代码开始的时候就要考虑变量和算式应该是什么类型,有利于编写好的、高可用性的程序。

3.对编译器提示有作用,同时也对理解代码有作用。

问题:灵活性不够,不定义类型无法写程序。

动态语言:

1.最大优点是代码简洁。

2.十分灵活。

问题:运行速度相对会慢一些,要做类型检查。最大缺点是不执行就无法检测出错误。

 

2C++是编译型语言,js是解释型语言。

C++的编译过程:预处理->编译优化->汇编->链接。

Js的解析机制:预处理(分段读取代码预处理)->解释执行

 

3C++有指针,js无指针。

C++中的赋值,所有的基本类型都是直接复制,而自定义类型因为有指针的存在,可以自己选择进行深复制(复制)还是浅复制(引用)。而在js中,所有的基本类型赋值都是复制,而所有的其他类型赋值都是引用。

 

4js是函数式编程语言,C++不是。

Js把函数当作对象来处理,可以将它当作函数的输入参数和输出值(高阶函数)。

C++如果要把函数当作其他函数的输入参数,即实现高阶函数,必须要通过函数指针(经常还要多传递一个(void *)类型的参数作为参数的函数的参数)。

 

5C++的继承是基于类的,js的继承基于原型

C++中,继承是通过类来进行的。比较符合人的直观思维。同时在生成一个类之后,是不能够对它进行修改了,除非再去修改它的定义。(Ruby基于开放类的继承可以在定义之后任意追加类的内容)

js中,继承则是通过原型链的方式来进行的。同样也可以在定义之后修改原型链。同时,也可以修改内置类型的原型链来扩展内置类型(慎用,monkey patching可能导致内置对象大幅度修改产生难以预期的行为)。

 

JS特性)

6js的一个重要特性是闭包(当前作用域可以访问并保存外部作用域的变量)。

Js的闭包在函数返回之后,还能够保持闭包引用到的变量不释放。其最大的用途有两个:一是可以函数返回闭包,让外面可以读取访问到函数内的值,二是让这些变量的值一直保存在内存之中不释放。

有闭包很容易实现内部迭代器(each方法),而C++没有闭包,共有循环外部信息比较麻烦,采取的是外部迭代器方法(vector<int>::iterator)。

注意事项:

1.        如果滥用闭包容易消耗大量内存,同时在IE中会有内存泄漏问题,所以在退出函数之前将不使用的局部变量全部删除。

2.        闭包也会在外部改变父函数内部的值,因此用闭包当共有方法的时候要注意不要随便改变内部的值。

 

7js可以显示的设置上下文。

Js可以通过applaycall方法显示指定函数内的thisapplay参数传递用数组,call参数分开传。

(未完待续) 

上述浅薄个人看法,如果有错误希望大家能够指正。

posted @ 2011-10-15 02:42 dead_horse 阅读(4234) | 评论 (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 阅读(14058) | 评论 (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 阅读(2535) | 评论 (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 阅读(4546) | 评论 (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 阅读(2787) | 评论 (1)编辑 收藏
  2011年8月18日
     摘要:    在写node.js的时候,经常会遇到要去数据库的多个地方取得多个数据,然后才能进行下一步的操作的情况。如果是线性执行的语言,通常的做法是一条一条去取,全部取到之后再进行下一步操作。然而在node里面,因为是基于事件的,所以只能够一层一层的在回调函数里面嵌套进去。取到第一个数据之后,执行回调函数去取第二条数据,然后再执行回调函数。    对于node来...  阅读全文
posted @ 2011-08-18 15:24 dead_horse 阅读(2796) | 评论 (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 阅读(6990) | 评论 (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 阅读(706) | 评论 (0)编辑 收藏
仅列出标题  下一页