1.从应用到源码理解STL反向迭代器
2.八数码C++源代码
从应用到源码理解STL反向迭代器
在实际应用中,源码我们可能需要从序列容器(如vector)的源码尾部移除不满足特定条件的部分元素。这通常涉及从尾部开始的源码迭代操作。然而,源码容器成员函数erase不接受反向迭代器作为参数。源码因此,源码商标生成源码我们需要将反向迭代器转换为普通迭代器。源码先来看看STL迭代器的源码分类和转换关系。
STL迭代器主要分为用途迭代器,源码它们之间存在转换关系,源码但不是源码所有迭代器类型都可以相互转换。转换关系需通过迭代器的源码构造函数定义,有些可以直接转换,源码有些则需调用特定方法。源码
特别地,源码溯源码被撕了反向迭代器到普通迭代器的转换可以通过调用反向迭代器的base()方法实现。但初版代码存在缺陷,未能按预期将元素正确删除。通过跟踪代码并参考cpp reference文档,我们发现base()方法返回的迭代器实际上比预期位置靠后一个元素。
为了修正这个问题,我们需要将通过base()方法得到的风起源码指标迭代器向前移动一个位置,以正确指向第一个符合移除条件的元素。修改代码后,可以确保元素按约定进行删除。
在一般场景下,迭代器的使用主要涉及遍历访问和遍历修改元素值。对于删除和插入操作,可能需要将反向迭代器转换为普通迭代器。阿凡达源码STL容器的erase和insert成员函数仅接受普通迭代器作为参数。
在执行插入操作时,直接使用base()将反向迭代器转换为普通迭代器,并传入insert函数,其语义是一致的。而在删除操作中,直接使用base()转换后的软件源码跑码迭代器可能无法正确执行,因为反向迭代器和普通迭代器在终止位置上的处理存在差异。为了修正此问题,需要手动调整,确保迭代器的有效性。
对于反向迭代器,通过正确的反向迭代操作得到的迭代器,在不等于rend()返回的迭代器时,都是指向有效值的。因此,除了rend().base()-1操作可能导致问题外,其他转换通常都是安全的。
讨论end()迭代器的前移操作时,需要考虑是否能够安全地访问容器的尾端元素。对于随机访问迭代器,如vector容器,end()返回的迭代器可以进行前移操作,但需确保移动操作的合法性。对于双向访问迭代器如list,同样可以进行前移操作以访问尾端元素。
结束讨论前,还需要确认iterator的-1操作是否对指向容器尾端元素的迭代器有效。在vector容器中,通过end成员函数返回的迭代器通过-1操作可以得到指向尾端元素的普通迭代器。对于list容器,其end成员函数返回的迭代器也支持前移操作。
总结来说,支持向前移动操作的迭代器访问容器内元素的容器,其end成员函数通过前移操作可以得到一个指向容器尾端元素的迭代器。这符合双向迭代器的设定语义。通过反向迭代器的原理,我们也能验证end()函数返回的迭代器可以进行反向移动。
八数码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
2024-11-28 17:10
2024-11-28 17:01
2024-11-28 16:51
2024-11-28 16:40
2024-11-28 16:37
2024-11-28 15:55