1.STL源码学习(3)- vector详解
2.从源码理解vector赋值操作符的源码实现
3.八数码C++源代码
4.STL源码剖析总结笔记(3):vector初识
STL源码学习(3)- vector详解
STL源码学习(3)- vector详解
vector的迭代器与数据类型:vector内部的连续存储结构使得任何类型的数据指针都可以作为其迭代器。通过迭代器,实例可以执行诸如指针操作,源码如访问元素值。实例 vector定义了两个迭代器start和finish,源码分别指向元素的实例infuse pro 源码起始和终止地址,同时还有一个end_of_storage标记空间的源码结束位置。vector的实例容量保证大于等于已分配元素空间,提供了获取空间大小的源码函数,如front和back的实例值以引用返回,更高效。源码 空间配置原理:STL中的实例vector使用SGI STL容器的二级空间配置器。vector头部包含配置信息,源码如data_allocator作为空间配置器的实例-35 64的源码补码别名。简单配置器(simple_alloc)是源码封装了高级和低级配置器调用的抽象类。 构造函数与内存管理:vector通过空间配置器创建元素。构造函数允许预分配并初始化元素,fill_initialize用于调整空间范围,allocate_and_fill则分配空间并填充。这个过程涉及data_allocator的allocate函数,分配空间并返回起始地址。 vector析构时,调用deallocate函数释放空间。pop_back和erase方法会移除元素并销毁相应空间,clear则清除全部元素。insert操作复杂,根据元素数量和容器状态可能需要扩容。thinkphp即时到账源码 插入与扩展操作:push_back在末尾插入元素,如果空间不足,可能需要扩容。insert接受三个参数,根据情况处理插入操作,可能抛出异常并销毁部分元素。从源码理解vector赋值操作符的实现
深入解析vector赋值操作符实现逻辑
通过基准测试得知,vector赋值操作符具有最高效率。接下来,我们将从源代码角度探讨实现细节。
先看测试代码,构建一个包含个元素的vector作为源数据,并声明目标vector,jar包 反编译源码将源数据赋值给目标vector。
STL源码中,非自复制情况,首先拷贝内存分配器,然后调用内部函数assign。assign函数接收数据起始和终止指针作为参数,注意指针而非迭代器,这在后续文章中有详述。
assign关键实现,计算源数据元素总数,通过两个指针减法得出,这一步骤对理解复制过程至关重要。
distance函数实现,带微视代挂源码通过迭代器类型萃取判断vector是否支持随机访问,返回元素数量。此函数通过指针直接减法计算元素个数。
了解容器容量概念,vector有size和capacity两个参数,分别表示当前元素数和最大容量。
assign中,通过capacity比较源数据大小,若容量足够,则直接写入数据,否则需申请新内存。
复制过程分两步:先记录复制后vector的size是否增长,然后将源数据范围内的元素复制至当前容器,最后根据size变化决定是否执行析构或构造操作。
复制前后容器状态示意图,展示容器大小增长和不增长两种情况。
疑惑点:在C语言中,数据直接拷贝无需对象概念,而在C++中,对象包含数据和行为,复制涉及构造和析构。
C++对象生命周期管理,构造和析构遵循特定调用规则,复制操作需手动执行构造或析构以适应内存变化。
当源数据小于容器容量时,直接复制;容量不足时,释放当前内存,申请新内存进行复制。
vector复制过程细节繁多,设计复杂。后续文章将探讨其他复制方法,并横向对比性能差异。
八数码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
STL源码剖析总结笔记(3):vector初识
vector是c++中常用且重要的容器之一。相较于固定大小的array,vector拥有动态分配内存的特性,允许它在使用过程中随着元素的增删而自行调整大小。这种动态性使得vector在处理不可预知数据量时更为便捷。
内部结构上,vector使用了数组作为存储基础,并通过start, finish和end of storage三个迭代器进行访问和管理空间。其中,start和finish分别指向可用空间的首端和尾端,end of storage则指向内存块的末尾。在vector大小为字节(位系统下,一个指针占4字节)的情况下,其大小为3。因此,vector可以灵活地通过迭代器定位数据的大小与位置。
内存管理机制是vector的精华之一。当空间耗尽时,vector会自动扩展为二倍的内存容量,以容纳新增元素。此过程涉及创建新空间,复制原有数据,然后释放旧空间,确保资源的有效利用。
vector提供了丰富的迭代器,遵循随机访问的行为,允许直接获取和修改数据,增强操作的效率。这些迭代器简化了对数据结构的遍历与修改操作。
在添加与删除数据时,vector提供了pop_back(), erase, insert等高效方法。例如,pop_back()简单地删除尾部元素,erase允许清除一个范围内的数据,并通过复制来维持数据的连续性。insert操作根据具体需求进行数据的插入与调整,确保结构的完整性与数据的正确性。
综上,vector以其灵活的内存管理和高效的数据操作,成为学习STL和掌握容器结构的理想选择。其清晰的内部机制和丰富的功能特性,为程序设计提供了强大的支持。