前言
在记录八 线性表的顺序存储结构中，我们了解了顺序存储结构的优缺点。我们注意到，其固定的静态特性对于日常来说特别不太友好。因为我们有时无法把握数据量的大小。如果我们存储大小定小了，那么存储空间可能不够。如果我们存储大小定义大了，那么又会造成空间浪费。所以，针对这种情况，我们可以使用链式结构(推荐)和动态顺序表(动态数组也是一样。)。所以，今天就来记录一下，动态顺序表。
动态顺序表原理
1.首先，我们要了解到，当我们申请了一个固定大小的空间时，我们是没有办法在其空间上往后面进行扩容。(不能原地扩容)
2.所谓的动态，其核心在与 ： 在另外一处重新开辟一个比原先空间还有大的空间，将原先的空间中的数据转移到新开的数据，再释放掉原先的空间即可。
扩容图
3.扩容有两种方式。
(1) 利用malloc,realloc,free这三个函数。
malloc : 原型：extern void *malloc(size_t size);传入参数为需要申请内存的大小，返回一个指针，需要将返回的指针强制转换成所需要的。
示例:
#include<iostream> //malloc函数因为常用，被包含在iostream中，C++可以直接使用。
//#include<stdlib.h> malloc是C语言的申请内存函数。其包含在stdliib.h头文件中。
using namespace std;
int main(){
//使用: 数据类型 * 指针变量名 = (数据类型 *) malloc (大小 * sizeof(数据类型) );
//注意强制转换和sizeof获取数据类型所需要的空间大小。
//例如int * p = (int *) malloc (sizeof(int)) ; 申请一个int类型的数据
int * p = (int *) malloc ( 10 * sizeof(int) );//申请一个int类型的数组。空间大小为10
for(int i=0;i<10;i++){
p[i] = i;
}
for (int i = 0; i < 10; i++){
cout<<p[i]<<endl;
}
free(p);
system("PAUSE");
}
malloc函数使用
realloc: 原型void realloc(void _Memory, size_t _NewSize)。传入的参数为需要动态调整的空间，以及新的空间大小，新的空间大小可以比原先的空间大小大，也可以比原先空间大小小。
使用总结 【百度百科 - realloc】
1. realloc失败的时候，返回NULL
2. realloc失败的时候，原来的内存不改变，不会释放也不会移动
3. 假如原来的内存后面还有足够多剩余内存的话，realloc的内存=原来的内存+剩余内存,realloc还是返回原来内存的地址; 假如原来的内存后面没有足够多剩余内存的话，realloc将申请新的内存，然后把原来的内存数据拷贝到新内存里，原来的内存将被free掉,realloc返回新内存的地址
4. 如果size为0，效果等同于free()。这里需要注意的是只对指针本身进行释放，例如对二维指针a，对a调用realloc时只会释放一维，使用时谨防内存泄露。
5. 传递给realloc的指针必须是先前通过malloc(), calloc(), 或realloc()分配的
6.传递给realloc的指针可以为空，等同于malloc。
举例:
#include<iostream> //realloc函数因为常用，被包含在iostream中，C++可以直接使用。
//#include<stdlib.h> realloc是C语言的动态内存调整函数。其包含在stdliib.h头文件中。
using namespace std;
int main(){
//使用: 数据类型 * 指针变量名 = (数据类型 *) realloc (需要调整空间的指针名 ,大小 * sizeof(数据类型) );
//注意强制转换和sizeof获取数据类型所需要的空间大小。以及调整空间的指针名。
int * p = (int *) malloc ( 10 * sizeof(int) );//申请一个int类型的数组。空间大小为10
for(int i=0;i<10;i++){
p[i] = i;
}//放入10个数据
//动态调整空间:扩容
p = (int *) realloc ( p, 20 * sizeof(int));//扩容。再增加10个空间。
for (int i = 10; i < 20; i++){
p[i] = i;
}
//输出
for (int i = 0; i < 20; i++){
cout<<p[i]<< " ";
}
cout<<endl;//回车
//动态调整空间:缩小
p = (int *) realloc (p ,10 * sizeof(int) );//缩小。回归到10个空间大小，会引发数据被丢失
//输出
for (int i = 0; i < 20; i++){//继续循环到20个，会引发错误。
cout<<p[i]<<" ";
}
cout<<endl;//回车
free(p);
system("PAUSE");
}
后面的数据被丢失了。
realloc函数使用
free :原型void free(void *ptr)。释放指针所执向的空间。（该不举例。）
(2)使用new，delete函数。和自己移动数据。(=-=)。
使用方法很简单。先new一个新的空间，然后把原先数据移动过去。再delete原先的空间。
动态顺序表结构类实现
(只是在顺序表结构类上重写了insert函数以及增加了一个addStorage()函数和返回容量大小的capacity()函数。=-=之前卡在了addStorage()函数那个释放那里，卡了将近4个小时。慢慢的了解到了new/delete，malloc/free的关系。new/delete是一对操作符，是对于对象进行的。delete在释放内存之前还会调用析构函数回收内存。malloc/free主要是针对内存的。唉，自己要走的路还很长呀。
推荐博客：浅谈 C++ 中的 new/delete 和 new[]/delete[]
C++ 动态内存管理(new /delete-new[]/delete[]-N次释放))
/**
* 动态顺序表类
*/
template<typename T>
class List : public ListSelf<T>{//List : 动态顺序表类 继承 顺序存储结构抽象类(ListSelf)
private:
const size_t SIZE = 10L;
T * data;//数据首地址
size_t length ;//数据长度大小
size_t storage;//整体大小
//核心函数
/**
* 扩容函数
*/
Status addStorage(T elem,size_t index){
const size_t len = length != 0 ? 2 * length : 1;
//利用三元运算符，如果原大小为0，则分配为1
//否则分配原大小的两倍
//分配内存
T * newData = new T[len];
if (!newData){
return FAIL;
}
//移动数据
size_t i = 0;
for (i = 1; i < index ; i++){//先移动前面的数据
newData[i] = data[i];//移动数据
}
//再将需要插入的输入放入新的内存数据中
newData[index] = elem;
++length;//长度增加
//再次移动后面的数据
size_t m = 0;
for ( m = i; m < length; m++){
newData[m+1] = data[m];
}
//释放原来的数据空间
//delete []data;不知道为什么，这边不能释放data。释放的话会造成严重的内存错误
//调整更新
data = newData;
storage = len;
return SUCCESS;
}
protected:
/**
* 构造一个线性表,申请内存
*/
Status init(){
data = new T[SIZE+1];//多申请一个空间,空余出第一个数据空间,默认大小为11
length = 0;//长度为0
storage = SIZE;//整体长度默认大小为11
if (!data){
exit(ERROR);//如果内存申请失败，退出
}
return SUCCESS;
}
/**
* 销毁线性表，回收内存。
*/
Status destroy(){
if (!data){
return FAIL;
}
delete []data;
return SUCCESS;
}
public:
/**
* 默认的构造函数
*/
List(){
init();
}
/**
* 析构函数
*/
~List(){
destroy();
}
/**
* 在相应的位置上插入新的数据
*/
Status insert(T elem,size_t index){
if(index < 1 || index > length+1 ){//判断下标是否合法
return ARRAY_OUT_OF_BOUNDS;//返回下标越界错误
}
if (storage == length){ //判断空间是否满了
return addStorage(elem,index);
}
size_t i = 0;
for (i = length; i >= index; --i){//将数据往后面移动
data[i+1] = data[i];//将数据往后移动
}
data[i+1] = elem;//插入数据
++length;//长度增加
return SUCCESS;
}
/**
* 在线性表的末尾插入新的数据
*/
Status insert(T elem){
if (storage == length){ //判断空间是否满了
return addStorage(elem,length);
}
data[++length] = elem;//放入数据
return SUCCESS;
}
/**
* 返回整体容量大小
*/
size_t capacity(){
return storage;
}
/**
* 取出线性表的数据元素
*/
T at(size_t index){
if(index < 1 || index > length){
throw std::out_of_range("Array out of bounds");//返回下标越界错误
}
return data[index];
}
/**
* 返回数据的索引下标
*/
int local(T elem) {
//安排哨兵
data[0] = elem;
size_t i= 0;
for(i = length;data[i]!=elem;--i);//查询位置。数据相等就退出。
if (i == 0){
return -1;//查找失败，返回-1
}
return i;//返回位置
}
/**
* 修改指定位置的数据
*/
Status updateIndex(T newElem,size_t index){
if(index < 1 || index > length ){
return ARRAY_OUT_OF_BOUNDS;//返回数组下标错误
}
data[index] = newElem;//修改数据
return SUCCESS;//返回成功
}
/**
* 修改匹配的数据
*/
Status update(T oldElem,T newElem){
int index = local(oldElem);//先查询老数据的位置
if (index == -1){
return FAIL;//如果没有查询到，就修改错误
}
data[index] = newElem;//更新数据
return SUCCESS;//返回成功
}
/**
* 在相应的位置上删除数据
*/
Status removeIndex(size_t index){
if(index < 1 || index > length ){
return ARRAY_OUT_OF_BOUNDS;//返回数组下标错误
}
for (size_t i = index; i <= length; ++i){//数据往前面移动，覆盖掉原来的数据
data[i] = data[i+1];
}
--length;//长度减一
return SUCCESS;
}
/**
* 移除线性表中相同的元素
*/
Status remove(T elem){
int index = local(elem);//先查询数据的位置
if(index == -1){
return FAIL;//没有数据就返回假
}
for (size_t i = index; i < length; ++i){//同removeIndex()
data[i] = data[i+1];
}
--length;
return SUCCESS;
}
/**
* 返回查找元素的直接前驱
*/
T * prior(T elem){
if (data[0] == elem){
return NULL;//第一个元素没有直接前驱
}
int index = local(elem);
if(index == -1){
return NULL;//没有前驱返回空
}
return &data[index-1];
}
/**
* 返回查找元素的直接后驱
*/
T * next(T elem){
if (elem == data[length]){
return NULL;//最后一个数据没有
}
int index = local(elem);
if (index == -1){
return NULL;
}
return &data[index+1];
}
/**
* 返回线性表中元素的个数
*/
size_t size(){
return length;
}
/**
* 将线性表重置为空表，清空所有数据
*/
void clear(){
length = 0;//直接长度清空即可
}
/**
* 判断线性表是否为空表，如果是空表，返回true，否则返回false
*/
bool isEmpty(){
return length==0;
}
/**
* 遍历线性表
*/
Status show(){
for (size_t i = 1; i <= length; i++){
std::cout<<"data["<<i<<"]="<<data[i]<<"\n";
}
return SUCCESS;
}
};
STL(Standard Template Library)标准模板库中的动态顺序表:向量
Vector
Vector(向量)是一个能够动态扩容的顺序容器（Sequence Container）。可以简单的认为，其就是一个动态数组。
(Vector使用推荐博客:C++ Vector 使用说明)
Vector的内部结构(gcc version 8.1.0 (x86_64-win32-sjlj-rev0, Built by MinGW-W64 project)
(通过看候捷老师的《STL 源码剖析》，了解到在G2.9之前，Vector就是单独的一个类，其结构比较清晰。而到了G4.9的版本后，其结构进行了改变。复杂了。在这里先附上我看的STL源码解析视频链接,老师讲的特别的棒！)
首先，我们先了解一下vector是如何工作的。
1.在vector中拥有3个指针。分别是_M_start、_M_finish、_M_end_of_storage。
2.这三个指针所占的空间是vector所占的空间。
3._M_start是指向第一个数据的指针。
4._M_finish是指向最后一个数据的下一个指针。(没有数据)
5._M_end_of_storage是整个容器的末尾指针。
6.当_M_finish == _M_end_of_storage时，容器将会扩容。扩容大小是原先大小的2倍。
7.扩容是不会在原空间上直接往后面开辟空间，而是另外寻一处空间进行存储，将原空间的数据移动过去后，释放原空间。
vector原理图
其次，Vector被分成了三个部分。_Vector_base、_Vector_impl、Vector。其中_Vector_base是一个结构体,_Vector_base的结构体中又包含着_Vector_impl：结构体,而_Vector_impl公有继承allocator分配器。最后，由Vector类保护继承_Vector_base结构体。大致如下：
Vector框架图
_Vector_base结构体:Vector的父类。主要是Vector的数据存储部分以及内存分配管理部分。
_Vector_impl结构体:公有继承allocator分配器。主要是三个指针就放在该结构体中。Vector其主要的空间大小就是其3个指针。在32位系统中，一个指针为4个字节。所以sizeof(vector<T>)的结果是12，而在64位系统中，sizeof(vector<T>)的结果是24.)
Vector类：主要的Vector实现类。
（从里之外说明,且只说明重要部分.=-=因为自己也在学习。）
_Vector_impl
_Vector_impl
_Vector_base
(因为_Vector_impl被_Vector_base所包含，所有该代码将会被剔除_Vector_impl部分)
template<typename _Tp, typename _Alloc>//数据类型为_Tp,分配器为_Alloc
struct _Vector_base
{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Tp>::other _Tp_alloc_type;//重命名分配器为_Tp_alloc_type,其实就是allocator<_Tp>
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
pointer;//分配器指针
//_Vector_base的公有部分
public:
typedef _Alloc allocator_type;//重命名分配器为allocator_type
_Tp_alloc_type&//返回分配器的引用 _M_impl是_Vector_impl类型;
_M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
{ return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
const _Tp_alloc_type&//返回分配器常量的引用。
_M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
{ return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
allocator_type//返回分配器的类型
get_allocator() const _GLIBCXX_NOEXCEPT
{ return allocator_type(_M_get_Tp_allocator()); }
//默认的构造函数，调用_Vector_impl的构造函数
_Vector_base()
: _M_impl() { }
//带参数的构造函数，调用_Vector_impl的带参数的构造函数，选择分配器。
_Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT
: _M_impl(__a) { }
//由默认分配器分配空间的的构造函数
_Vector_base(size_t __n)
: _M_impl()
{ _M_create_storage(__n); }
//即由指定分配器分配空间的构造函数。
_Vector_base(size_t __n, const allocator_type& __a)
: _M_impl(__a)
{ _M_create_storage(__n); }
//析构函数，释放内存。
~_Vector_base() _GLIBCXX_NOEXCEPT
{
_M_deallocate(_M_impl._M_start,
_M_impl._M_end_of_storage - _M_impl._M_start);
}
public:
_Vector_impl _M_impl;//_Vector_impl结构体对象 _M_impl
//分配内存函数。如果传入参数为0，就直接返回一个空的指针。否则由分配器返回一个空间大小为__n的指针
pointer
_M_allocate(size_t __n)
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
}
//释放内存函数。如果释放的指针__p存在，就释放。__n是其释放的空间大小。_M_impl是其释放的分配器。
//即，使用_M_impl分配器对__p释放__n个空间大小。
void
_M_deallocate(pointer __p, size_t __n)
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
if (__p)//如果指针存在，就释放其指针
_Tr::deallocate(_M_impl, __p, __n);
}
private:
void
_M_create_storage(size_t __n)//创建存储空间函数。
{
//申请空键给_M_start指针
this->_M_impl._M_start = this->_M_allocate(__n);
//初始化时没有数据，_M_finish指针即等于_M_start指针
this->_M_impl._M_finish = this->_M_impl._M_start;
//空间存储容量尾指针即开始的指针+整个容量
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}
};
Vector
(类的声明)
Vector类的声明
(重命名定义)
Vector类重命名定义
(构造函数与析构函数：剔除了一部分，简化了。)
//默认的构造函数
vector(): _Base() { }
//指定分配器的构造函数
vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
: _Base(__a) { }
//指定空间大小和分配器的构造函数
vector(size_type __n, const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_default_initialize(__n); }//使用_M_default_initialize()来初始化数据
/*void _M_default_initialize()函数
_M_default_initialize(size_type __n)
{
this->_M_impl._M_finish =
std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
_M_get_Tp_allocator());//初始化数据
}*/
//指定空间大小和默认值以及分配器
vector(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_fill_initialize(__n, __value); }
//指定空间大小和默认值以及分配器(默认值和分配器可以不用传入)
vector(size_type __n, const value_type& __value = value_type(),
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_fill_initialize(__n, __value); }
//深拷贝默认构造函数
vector(const vector& __x)
: _Base(__x.size(),
_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
{
this->_M_impl._M_finish =
std::__uninitialized_copy_a(__x.begin(), __x.end(),
this->_M_impl._M_start,
_M_get_Tp_allocator());
}
//双引用？？？这个不清楚。
vector(vector&& __x) noexcept
: _Base(std::move(__x)) { }
/// 带备用分配器的复制构造函数
vector(const vector& __x, const allocator_type& __a)
: _Base(__x.size(), __a)
{
this->_M_impl._M_finish =
std::__uninitialized_copy_a(__x.begin(), __x.end(),
this->_M_impl._M_start,
_M_get_Tp_allocator());
}
/// 使用备用分配器移动构造函数
vector(vector&& __rv, const allocator_type& __m)
noexcept(_Alloc_traits::_S_always_equal())
: _Base(std::move(__rv), __m)
{
if (__rv.get_allocator() != __m)
{
this->_M_impl._M_finish =
std::__uninitialized_move_a(__rv.begin(), __rv.end(),
this->_M_impl._M_start,
_M_get_Tp_allocator());
__rv.clear();
}
}
//初始化一个列表作为向量数据带有默认分配器
vector(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__l.begin(), __l.end(),
random_access_iterator_tag());
}
/**
*dtor只删除元素，并注意如果元素本身是指针，指向内存的是没有任何接触。
*管理指针是用户的责任。
*/
//上面的原注释翻译过来的。这是析构函数
~vector() _GLIBCXX_NOEXCEPT
{
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
_M_get_Tp_allocator());
_GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
}
（重要部分！！！扩容部分：只分析扩容部分算了，后面的不想分析了。有时间再分析。）
push_back扩容
(如何定义扩容后大小的函数。)
_M_check_len
简化版扩容大小函数
size_t _M_check_len()
{
if(max_size - size() < 1){//没有容量了
return 错误。
}
size_t len = (size()!=0) ? 2*size() : 1;//如果size()为0，就返回1，否则就扩容两倍。
if(len > max_size)//如果len大于最大容量，就返回最大容量
return max_size;
return len;
}
(如何扩容的函数?！！！！！！！我简化了。去除了Vector中不需要的成分)
template<typename _Tp, typename _Alloc>
template<typename... _Args>
void
vector<_Tp, _Alloc>:://扩容函数！！注意！！在push_back()中调用的_M_realloc_insert(end(), __x);
_M_realloc_insert(iterator __position, _Args&&... __args)//__position为_M_finish。_Args为扩充时需要添加的函数。
{
const size_type __len =
_M_check_len(size_type(1), "vector::_M_realloc_insert");//获取扩容后的大小。
pointer __old_start = this->_M_impl._M_start;//保存指针
pointer __old_finish = this->_M_impl._M_finish;//保存指针
//这个地方其实就是end()-begin()。其实就是size():当前容量。也就是说。__elems_before为当然容量。
const size_type __elems_before = __position - begin();
pointer __new_start(this->_M_allocate(__len));//分配一个新的空间
pointer __new_finish(__new_start);//这个地方其实就是_new_finish = _new_start;
__try
{
//原来的注释 ： 三个操作的顺序由C++ 11决定。如果移动可以改变属于现有向量。这是一个只有来电者才有的问题使用LVREF REF元素（参见C++ 11的最后一个子弹）[关于论点的决议]）。
//初始化新空间.将新空间的数据元素设置初值为__x.
_Alloc_traits::construct(this->_M_impl,
__new_start + __elems_before,
#if __cplusplus >= 201103L
std::forward<_Args>(__args)...);
#else
__x);
#endif
__new_finish = pointer();//将_new_finish指针重置
//将原先的数据移动到新空间来。
__new_finish
= std::__uninitialized_move_if_noexcept_a
(__old_start, __position.base(),
__new_start, _M_get_Tp_allocator());
//赋值之后，数据的结尾指针++
++__new_finish;
//移动安插点后面的数据。(因为会被insert()所调用)
//当被push_back()调用时，上面的那个移动函数就已经完成了。
//这个是给insert()使用的。当被insert()使用时。__position就不是当前容量。而是插入点和起点的距离。
//届时上面是移动插入点到起点之间的数据。后面这个是移动插入点到数据终点的数据。
__new_finish
= std::__uninitialized_move_if_noexcept_a
(__position.base(), __old_finish,
__new_finish, _M_get_Tp_allocator());
}
__catch(...)
{
//如果失败，就回收开辟后的内存。抛出异常。
if (!__new_finish)
_Alloc_traits::destroy(this->_M_impl,
__new_start + __elems_before);
else。
std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
_M_deallocate(__new_start, __len);
__throw_exception_again;
}
_GLIBCXX_ASAN_ANNOTATE_REINIT;
//销毁原空间。
std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
_M_deallocate(__old_start,
this->_M_impl._M_end_of_storage - __old_start);
//重新调整指针。
this->_M_impl._M_start = __new_start;
this->_M_impl._M_finish = __new_finish;
this->_M_impl._M_end_of_storage = __new_start + __len;
}
(部分函数)
//返回_M_start指针
iterator begin()
{ return iterator(this->_M_impl._M_start); }
//返回_M_finish指针
iterator end()
{ return iterator(this->_M_impl._M_finish); }
//通过_M_finish-_M_start得到容量大小。
size_type size()
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
//通过_M_end_of_storage - _M_start来得到整个容量
size_type capacity()
{ return size_type(this->_M_impl._M_end_of_storage
- this->_M_impl._M_start); }
//通过_M_finish是否等于_M_start来判断是否为空
bool empty()
{ return begin() == end(); }
//其实就是通过_M_start+下标长度来获取值的引用
reference operator[](size_type __n)
{
__glibcxx_requires_subscript(__n);
return *(this->_M_impl._M_start + __n);
}
//返回_M_start值的引用
reference front() { return *begin(); }
//返回_M_finish-1的引用(为什么要-1？因为_M_finish指向的空间是没有数据的。它是最后一个数据的下一个数据。所以要-1)
reference back() { return *(end() - 1); }
总结
Vector是向量。其行为像动态数组。（说动态数组好像也可以。）当我们在实现动态顺序表时，主要注意以下一点。
在扩容时，不能原地扩容。需要新开辟空间，再将数据转移过去。
另外。这是rebind分配器的一个链接。STL源码阅读（2）–allocator::rebind
.
个人后话
嘛呀，终于写完了。今天卡在释放内存那边卡了4个多小时。可以说是今天写了一天了。好累啊。明天不会更新数据结构的类容。太烧脑了。看源代码也是。明天放假一天！
网友评论