1.std vector Դ??
2.std::sort 宕机源码分析
3.八数码C++源代码
std vector Դ??
C++代码：#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，执行结果如下。裂变分享源码
最初存储的emmcffu源码元素序列为：(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的chroot源码排序思想基于QuickSort，其基本思路是将待排序的数据元素序列中选取一个数据元素为基准，通过一趟扫描将待排序的元素分成两个部分，一部分元素关键字都小于或等于基准元素关键字，另一部分元素关键字都大于或等于基准元素关键字。novipnoad源码然后对这两部分数据再进行不断的划分，直至整个序列都有序为止。
std::sort的空间复杂度最好为O(log2N)，最坏为O(N)，74源码时间复杂度平均复杂度为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
