从快速排序的递归方式和非递归方式来看函数调用帧栈
#include<iostream>
#include<vector>
#include<stack>
#include<cstdlib>
#include<algorithm>
using namespace std;
//根据轴分开两边
template <typename Data>
int partition(vector<Data> &vec,int low,int high){
Data pivot=vec[low]; //第一个为轴
while(low < high){
while(low < high && vec[high]>=pivot)high--;
vec[low]=vec[high];
while(low < high && vec[low]<=pivot)low++;
vec[high]=vec[low];
}
vec[low]=pivot;
return low;
}
//递归快速排序
template<typename Data>
void quicksort_recurcive(vector<Data> &vec,int low,int high){
if(low<high){
int mid=partition(vec,low,high);
quicksort_recurcive(vec,low,mid-1);
quicksort_recurcive(vec,mid+1,high);
}
}
//非递归快速排序
template<typename Data>
void quicksort_no_recurcive(vector<Data> &vec,int low,int high){
stack<pair<int,int>> st;
int mid;
if(low<high){
st.push(make_pair(low,high));
//栈用来保存区间
while(!st.empty()){
low = st.top().first;
high = st.top().second;
st.pop();
mid=partition(vec,low,high);
if(low < mid - 1){
st.push(make_pair(low,mid-1));
}
if(mid + 1 < high){
st.push(make_pair(mid+1,high));
}
}
}
}
int main(){
int len=1000000;// 100w 1000000
vector<int> vec;
for(int i=0;i<len;i++) vec.push_back(rand());
{
clock_t t1=clock();
quicksort_recurcive(vec,0,len-1);
clock_t t2=clock();
cout<<"quicksort_recurcive "<<double(t2-t1)/CLOCKS_PER_SEC<<endl;
//for (auto i:vec) cout<<" "<< i<<endl;
}
{
random_shuffle(vec.begin(),vec.end());//重新打乱顺序
clock_t t1=clock();
quicksort_no_recurcive(vec,0,len-1);
clock_t t2=clock();
cout<<"quicksort_no_recurcive "<<double(t2-t1)/CLOCKS_PER_SEC<<endl;
//for (auto i:vec) cout<<" "<< i<<endl;
}
return 0;
}
/*
quicksort_recurcive 0.46
quicksort_no_recurcive 0.55
*/
可以看出的是非递归使用的时间比递归的还长一些。
递归的消耗主要在于函数的调用栈。如果函数调用帧栈的消耗 不及用户自己创建的栈的，则递归方式使用的时间会更短。
以下分析的是函数调用帧栈的使用
下图是函数调用压栈的变量和顺序
ESP是栈顶指针， EBP是栈底指针， 根据两个的偏移量就可以指定栈当中的内容。
栈理解为函数调用开辟的一个空间，但是该空间可以在用完后销毁。
空间保存的变量包括：
主调函数的实参N~1→主调函数返回地址(EIP,下一条要执行的命令的代码的地址)→主调函数帧基指针EBP→被调函数局部变量1~N ->下个函数的实参（如果有）
实参是从右往左压入栈，而局部变量是由创建的顺序依次压入栈的。
另外， 静态局部变量是在编译时就保存在数据区的，不是在栈中。
若当前函数调用另一个函数，新调用函数有关的内容会从当前ESP所指向位置开始压栈，压栈完成后，ESP会指向新函数栈帧的栈顶。
EBP为前帧栈的开始地址。
对于快排函数quicksort_recurcive，编译器对其上一个函数的EBP寄存器、局部变量和实参和返回地址、当前函数的ebp寄存器、局部变量和返回地址，对这些压栈的消耗，相比较快排函数quicksort_no_recurcive中的栈stack的压入和弹出前后下标的消耗，前者没有后者的消耗大。
所以递归的快排就更快了。
quicksort_recurcive中前一个函数和当前没有局部变量，有调用函数寄存器ebp、eip，和实参vec、low、high，和被调函数ebp、eip，被调函数的对下个被调函数的实参。
quicksort_no_recurcive使用了栈stack,其默认构造为deque的适配器
template<typename _Tp, typename _Sequence = deque<_Tp> >
deque双向开口可进可出的容器
我们知道连续内存的容器不能随意扩充,因为这样容易扩充别人那去
deque却可以,它创造了内存连续的假象.
其实deque由一段一段构成 ,他是分段连续,而不是内存连续 当走向段的尾端时候自动跳到下一段 所以支持迭代器++ 操作,自动跳到下一段的方法由operator++实现
deque每次扩充 申请一个段
其压栈和弹栈需要修改map和连续内存中的后面的指针。
测试过使用vector做呢用户的栈，结果是一样的。可以证明编译器操作帧栈，在操作数量级相似的情况下，效率会高于stl的容器或者适配器。