1.STL源码学习（3）- vector详解
2.从源码理解vector赋值操作符的源码实现
3.八数码C++源代码
4.STL源码剖析总结笔记（3）：vector初识

STL源码学习（3）- vector详解

       STL源码学习（3）- vector详解

       vector的迭代器与数据类型：vector内部的连续存储结构使得任何类型的数据指针都可以作为其迭代器。通过迭代器，实例可以执行诸如指针操作，源码如访问元素值。实例

       vector定义了两个迭代器start和finish，源码分别指向元素的实例火车管家源码起始和终止地址，同时还有一个end_of_storage标记空间的源码结束位置。vector的实例容量保证大于等于已分配元素空间，提供了获取空间大小的源码函数，如front和back的实例值以引用返回，更高效。源码

       空间配置原理：STL中的实例vector使用SGI STL容器的二级空间配置器。vector头部包含配置信息，源码如data_allocator作为空间配置器的实例flash 旅游源码别名。简单配置器（simple_alloc）是源码封装了高级和低级配置器调用的抽象类。

       构造函数与内存管理：vector通过空间配置器创建元素。构造函数允许预分配并初始化元素，fill_initialize用于调整空间范围，allocate_and_fill则分配空间并填充。这个过程涉及data_allocator的allocate函数，分配空间并返回起始地址。

       vector析构时，调用deallocate函数释放空间。pop_back和erase方法会移除元素并销毁相应空间，clear则清除全部元素。insert操作复杂，根据元素数量和容器状态可能需要扩容。java 传奇 源码

       插入与扩展操作：push_back在末尾插入元素，如果空间不足，可能需要扩容。insert接受三个参数，根据情况处理插入操作，可能抛出异常并销毁部分元素。

从源码理解vector赋值操作符的实现

       深入解析vector赋值操作符实现逻辑

       通过基准测试得知，vector赋值操作符具有最高效率。接下来，我们将从源代码角度探讨实现细节。

       先看测试代码，构建一个包含个元素的vector作为源数据，并声明目标vector，wampserver 显示源码将源数据赋值给目标vector。

       STL源码中，非自复制情况，首先拷贝内存分配器，然后调用内部函数assign。assign函数接收数据起始和终止指针作为参数，注意指针而非迭代器，这在后续文章中有详述。

       assign关键实现，计算源数据元素总数，通过两个指针减法得出，这一步骤对理解复制过程至关重要。

       distance函数实现，华为emui源码通过迭代器类型萃取判断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和掌握容器结构的理想选择。其清晰的内部机制和丰富的功能特性，为程序设计提供了强大的支持。