皮皮网

1.std vector Դ??
2.std::sort 宕机源码分析
3.八数码C++源代码

std vector Դ??

       #include <iostream>

       #include <vector>

       #define MAX

       using namespace std;

       //重载函数：求数组元素的平均值

       double average(int arr[], int n)

       {

        double sum = 0.0;

        for(int i=0; i<n; i++)

        {

        sum += arr[i];

        }

        return sum / n;

       }

       //重载函数：求vect集合元素的平均值

       double average(vector<int> vect)

       {

        double sum = 0.0;

        for(int i=0; i<vect.size(); i++)

        {

        sum += vect.at(i);

        }

        return sum / vect.size();

       }

       int main()

       {

        int arr[MAX]; //数组

        int *p; //指针

        vector<int> vect; //向量对象

        int n; //整数数量

        int i;

        cout<<"n : ";

        cin>>n;

        for(i=0; i<n; i++)

        {

        cin>>arr[i]; //使用数组存储整数

        vect.push_back(arr[i]); //使用vect存储整数

        }

        p = arr; //使用指针存储整数（指向数组地址）

        //输出数组元素及平均值

        cout<<"数组元素：";

        for(i=0; i<n; i++)

        {

        cout<<arr[i]<<"  ";

        }

        cout<<endl<<"平均值："<<average(arr, n)<<endl;

        //输出指针指向数组的元素及平均值

        cout<<"指针指向数组的元素：";

        for(i=0; i<n; i++)

        {

        cout<<*(p+i)<<"  ";

        }

        cout<<endl<<"平均值："<<average(p, n)<<endl;

        //输出vector集合的元素及平均值

        cout<<"vector集合的元素：";

        for(i=0; i<vect.size(); i++)

        {

        cout<<vect.at(i)<<"  ";

        }

        cout<<endl<<"平均值："<<average(vect)<<endl;

        return 0;

       }

       运行测试：

std::sort 宕机源码分析

       公司项目代码中发生了一次宕机事件，原因在于使用了std::sort，下面是具体的代码片段。

       编译命令：g++ sort.cpp -g -o sort，执行结果如下。淘助手 源码

       最初存储的早起打卡源码下载元素序列为：(0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(-1)(-1)(-2)(-1)(-2)(-2)(-2)

       在调用std::sort的过程中，出现了非法元素：-0

       (-0)(-2)(-2)(-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(-1)(-1)(-1)(0-1)(6-1)(5-1)

       生成了core文件，使用gdb进行调试，发现是在删除操作时发生了宕机，具体原因是在std::sort排序过程中将vector写坏了。

       接下来，我们来分析一下std::sort的工作原理。

       std::sort的学校表白网站源码排序思想基于QuickSort，其基本思路是将待排序的数据元素序列中选取一个数据元素为基准，通过一趟扫描将待排序的元素分成两个部分，一部分元素关键字都小于或等于基准元素关键字，另一部分元素关键字都大于或等于基准元素关键字。失信登记网源码然后对这两部分数据再进行不断的划分，直至整个序列都有序为止。

       std::sort的空间复杂度最好为O(log2N)，最坏为O(N)，动漫之家网站源码时间复杂度平均复杂度为O(NLog2N)，稳定性为不稳定。

       HeapSort是std::sort中的一种实现，其建堆过程是建立大顶堆，时间复杂度平均为O(nLog2N)，空间复杂度O(1)，稳定性同样为不稳定。

       __partial_sortInsertSort是基于插入排序的一种改进，其基本思路是将待排序的数据元素插入到已经排好的有序表中，得到一个新的有序表。经过n-1次插入操作后，所有元素数据构成一个关键字有序的序列。

       __final_insertion_sort是插入排序的一种不稳定性解决方案，其空间复杂度为O(1)，时间复杂度为O(n^2)，稳定性为稳定。

八数码C++源代码

       #include<cstdio>

       #include<vector>

       #include<queue>

       #include<ctime>

       #define maxhash

       #define hash(x) x%maxhash

       using namespace std;

       typedef unsigned long long ULL;

       vector<ULL>list[maxhash];

       vector<int>dist[maxhash];

       inline int abs(int x)

       {

       return x<0?-x:x;

       }

       int hval[][];

       void fill_hval(int *d)

       {

       for(int i=0;i<=8;i++)//number i

       {

       int pos;

       for(int k=1;k<=9;k++)//i's position

       if(d[k]==i)

       {

       pos=k;

       break;

       }

       for(int j=1;j<=9;j++)

       {

       hval[i][j]=abs((j-1)/3-(pos-1)/3)+abs((j-1)%3-(pos-1)%3);

       }

       }

       }

       int h(ULL d)

       {

       int answer=0;

       for(int i=9;i>=1;i--)

       {

       int x=d%;

       d/=;

       answer+=hval[x][i];

       }

       return answer;

       }

       int ToARR(ULL s,int *d)

       {

       int z=0;

       for(int i=9;i>=1;i--)

       {

       d[i]=s%;

       if(d[i]==0) z=i;

       s/=;

       }

       return z;

       }

       ULL ToULL(int *d)

       {

       ULL ans=0;

       for(int i=1;i<=9;i++)

       ans=ans*+d[i];

       return ans;

       }

       void insert(ULL x,int di)

       {

       ULL hx=hash(x);

       list[hx].push_back(x);

       dist[hx].push_back(di);

       }

       int find(ULL x)

       {

       ULL hx=hash(x);

       int size=list[hx].size();

       for(int i=0;i<size;i++)

       if(x==list[hx][i]) return dist[hx][i];

       return -1;

       }

       inline void swap(int &x,int &y)

       {

       int t=x;

       x=y;

       y=t;

       }

       struct state{

       int step;

       ULL x;

       friend bool operator <(state a,state b)

       {

       return a.step>b.step;

       }

       };

       int cnt=0;

       void AStar(int *from,int *to)

       {

       priority_queue<state>q;

       ULL x=ToULL(from);

       ULL y=ToULL(to);

       fill_hval(to);

       q.push((state){ h(x),x});

       insert(x,0);

       int d[];

       while(!q.empty())

       {

       cnt++;

       state s=q.top();

       ULL i=s.x; q.pop();

       int step=find(i);

       int z=ToARR(i,d);

       //printf("%lld %d %d\n",i,step,z);

       if(i==y) return;

       if(z-3>0)

       {

       swap(d[z],d[z-3]);

       ULL j=ToULL(d);

       swap(d[z],d[z-3]);

       if(find(j)!=-1) goto out1;

       q.push((state){ step+h(j),j});

       insert(j,step+1);

       }

       out1:

       if(z+3<)

       {

       swap(d[z],d[z+3]);

       ULL j=ToULL(d);

       swap(d[z],d[z+3]);

       if(find(j)!=-1) goto out2;

       q.push((state){ step+h(j),j});

       insert(j,step+1);

       }

       out2:

       if(z%3!=0)

       {

       swap(d[z],d[z+1]);

       ULL j=ToULL(d);

       swap(d[z],d[z+1]);

       if(find(j)!=-1) goto out3;

       q.push((state){ step+h(j),j});

       insert(j,step+1);

       }

       out3:

       if(z%3!=1)

       {

       swap(d[z],d[z-1]);

       ULL j=ToULL(d);

       swap(d[z],d[z-1]);

       if(find(j)!=-1) continue;

       q.push((state){ step+h(j),j});

       insert(j,step+1);

       }

       }

       }

       int from[],to[];

       void work()

       {

       for(int i=1;i<=9;i++)

       scanf("%d",&from[i]);

       for(int i=1;i<=9;i++)

       scanf("%d",&to[i]);

       AStar(from,to);

       ULL y=ToULL(to);

       printf("%d ",find(y));

       #ifdef DEBUG

       printf("%d ",clock());

       printf("%d ",cnt);

       #endif

       }

       int main()

       {

       #ifdef DEBUG

       freopen("debug.in","r",stdin);

       freopen("debug.out","w",stdout);

       #endif

       work();

       return 0;

       }

       这是基于曼哈顿距离的估价函数的Astar