CArray原理分析

xiaoxiao2021-02-28  14

MFC的CArray(数组)功能主要包括插入,删除,扩容,获取,因为是数组数据结构的设计,所以插入,删除效率较低,需要对元素进行移动。快速对用下标进行获取和设置(赋值)是优势。但是使用不当会产生不易发现的内存碎片。从源码来看,并不支持查找操作,只能增删改下面来分析源码:

CArray同样用模板设计,先看声明

template<class TYPE, class ARG_TYPE = const TYPE&>

第一个就是数组里保存对象的类型,第二个,通过之后的代码,决定了在插入,追加等操作中传入对象是用引用传递还是值传递,给使用者一个可选的选择

//以下内容截取自MFC源码中Afxtempl.h

类声明

/*============================================================================*/ // CArray<TYPE, ARG_TYPE> template<class TYPE, class ARG_TYPE = const TYPE&> class CArray : public CObject { public: // Construction CArray(); // Attributes INT_PTR GetSize() const; INT_PTR GetCount() const; BOOL IsEmpty() const; INT_PTR GetUpperBound() const; void SetSize(INT_PTR nNewSize, INT_PTR nGrowBy = -1); // Operations // Clean up void FreeExtra(); void RemoveAll(); // Accessing elements const TYPE& GetAt(INT_PTR nIndex) const; TYPE& GetAt(INT_PTR nIndex); void SetAt(INT_PTR nIndex, ARG_TYPE newElement); const TYPE& ElementAt(INT_PTR nIndex) const; TYPE& ElementAt(INT_PTR nIndex); // Direct Access to the element data (may return NULL) const TYPE* GetData() const; TYPE* GetData(); // Potentially growing the array void SetAtGrow(INT_PTR nIndex, ARG_TYPE newElement); INT_PTR Add(ARG_TYPE newElement); INT_PTR Append(const CArray& src); void Copy(const CArray& src); // overloaded operator helpers const TYPE& operator[](INT_PTR nIndex) const; TYPE& operator[](INT_PTR nIndex); // Operations that move elements around void InsertAt(INT_PTR nIndex, ARG_TYPE newElement, INT_PTR nCount = 1); void RemoveAt(INT_PTR nIndex, INT_PTR nCount = 1); void InsertAt(INT_PTR nStartIndex, CArray* pNewArray); // Implementation protected: TYPE* m_pData; // the actual array of data INT_PTR m_nSize; // # of elements (upperBound - 1) INT_PTR m_nMaxSize; // max allocated INT_PTR m_nGrowBy; // grow amount public: ~CArray(); void Serialize(CArchive&); #ifdef _DEBUG void Dump(CDumpContext&) const; void AssertValid() const; #endif };

本节抽出几个典型函数进行分析

先看成员变量

TYPE* m_pData; // 指向数据内存空间的指针 INT_PTR m_nSize; // 数组有效数据的个数 INT_PTR m_nMaxSize; // 数组所能保存最大数据的个数 INT_PTR m_nGrowBy; // 预留空间

前面几个参数比较好理解,是数组的基本参数,最后一个参数先不管,先看源码。 先看构造函数与析构函数:构造函数用来初始化,析构函数用来清内存

template<class TYPE, class ARG_TYPE> CArray<TYPE, ARG_TYPE>::CArray() { m_pData = NULL; \\初始化数组内存指针为NULL m_nSize = m_nMaxSize = m_nGrowBy = 0; \\其余三个参数为0 } //什么内存也没有开,指向数组内存的成员变量指针是空指针。。数组大小的参数都是0 template<class TYPE, class ARG_TYPE> CArray<TYPE, ARG_TYPE>::~CArray() { ASSERT_VALID(this); if (m_pData != NULL) { for( int i = 0; i < m_nSize; i++ ) (m_pData + i)->~TYPE(); delete[] (BYTE*)m_pData; } }

析构函数用来清理内存,首先对内存保存的对象循环强行调用析构函数,把数组内的对象析构掉(调用保存在数组内的对象的析构函数),在调用 完这些析构函数后,这块内存就相当于不代表任何对象的一块普通的堆内存,然后 delete整块数组的堆内存,把数组内存释放掉。

几个常用简单函数(赋值,获取等操作)

下来看几个常用函数先从简单的看起: /*============================================================================*/ // CArray<TYPE, ARG_TYPE> inline functions template<class TYPE, class ARG_TYPE> AFX_INLINE INT_PTR CArray<TYPE, ARG_TYPE>::GetSize() const { return m_nSize; } template<class TYPE, class ARG_TYPE> AFX_INLINE INT_PTR CArray<TYPE, ARG_TYPE>::GetCount() const { return m_nSize; } template<class TYPE, class ARG_TYPE> AFX_INLINE BOOL CArray<TYPE, ARG_TYPE>::IsEmpty() const { return m_nSize == 0; } template<class TYPE, class ARG_TYPE> AFX_INLINE INT_PTR CArray<TYPE, ARG_TYPE>::GetUpperBound() const { return m_nSize-1; } template<class TYPE, class ARG_TYPE> AFX_INLINE void CArray<TYPE, ARG_TYPE>::RemoveAll() { SetSize(0, -1); } template<class TYPE, class ARG_TYPE> AFX_INLINE TYPE& CArray<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex) { ASSERT(nIndex >= 0 && nIndex < m_nSize); if(nIndex >= 0 && nIndex < m_nSize) return m_pData[nIndex]; AfxThrowInvalidArgException(); } template<class TYPE, class ARG_TYPE> AFX_INLINE const TYPE& CArray<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex) const { ASSERT(nIndex >= 0 && nIndex < m_nSize); if(nIndex >= 0 && nIndex < m_nSize) return m_pData[nIndex]; AfxThrowInvalidArgException(); } template<class TYPE, class ARG_TYPE> AFX_INLINE void CArray<TYPE, ARG_TYPE>::SetAt(INT_PTR nIndex, ARG_TYPE newElement) { ASSERT(nIndex >= 0 && nIndex < m_nSize); if(nIndex >= 0 && nIndex < m_nSize) m_pData[nIndex] = newElement; else AfxThrowInvalidArgException(); } template<class TYPE, class ARG_TYPE> AFX_INLINE const TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(INT_PTR nIndex) const { ASSERT(nIndex >= 0 && nIndex < m_nSize); if(nIndex >= 0 && nIndex < m_nSize) return m_pData[nIndex]; AfxThrowInvalidArgException(); } template<class TYPE, class ARG_TYPE> AFX_INLINE TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(INT_PTR nIndex) { ASSERT(nIndex >= 0 && nIndex < m_nSize); if(nIndex >= 0 && nIndex < m_nSize) return m_pData[nIndex]; AfxThrowInvalidArgException(); } template<class TYPE, class ARG_TYPE> AFX_INLINE const TYPE* CArray<TYPE, ARG_TYPE>::GetData() const { return (const TYPE*)m_pData; } template<class TYPE, class ARG_TYPE> AFX_INLINE TYPE* CArray<TYPE, ARG_TYPE>::GetData() { return (TYPE*)m_pData; } template<class TYPE, class ARG_TYPE> AFX_INLINE INT_PTR CArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement) { INT_PTR nIndex = m_nSize; SetAtGrow(nIndex, newElement); return nIndex; } template<class TYPE, class ARG_TYPE> AFX_INLINE const TYPE& CArray<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex) const { return GetAt(nIndex); } template<class TYPE, class ARG_TYPE> AFX_INLINE TYPE& CArray<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex) { return ElementAt(nIndex); }

以上几个函数都是数组中的常用功能函数: GetSize,GetCount函数获取当前数组中已经保存对象的个数(是保存的有效对象,而不是所能保存的最大对象)。

IsEmpty函数通过m_nSize来判断数组是否为空。

GetUpperBound返回数组的最大索引边界,值就是 数组中已经保存对象的个数 - 1

RemoveAll函数调用了SetSize(0, -1);来清空数组,SetSize(0, -1)后面再说。总之清空数组之后,CArray 成员变量m_pData指向为数组开辟内存被释放内存,并且在释放内存之前会为已经在数组中保存的对象挨个调用析构函数。在调用此函数之后,m_nSize,m_nMaxSize,m_nGrowBy都变成了0。

GetAt,SetAt 函数是按索引来获取数组保存的对象和设置某一个位置的数组对象(赋值),数组的常规get,set操作从这里就可以看出: m_pData[nIndex] = newElement; m_pData[nIndex]; 赋值的时候回自动调用对象的拷贝构造函数。

ElementAt与GetAt功能相同

GetData可以获取m_pData (TYPE*类型))指针,用于获取为保存多个对象而开辟一块内存空间的首地址,也就是数组中第一个对象的地址。当然在数组为空时,这个返回值是空。即m_pData为空。

Add通过调用SetAtGrow来对数组的内容进行追加,把要追加的对象放在数组的末尾。SetAtGrow后面再说

数组也重载了[],operator[]可以方便的用数组下标的格式(如arr[i])来获取对象,内部也是调用GetAt,功能和GetAt等价

以上成员函数除了调用SetAtGrow,SetSize的函数之外,其余函数如何写法都是一目了然,下面来重点看看SetAtGrow,SetSize两个函数

SetSize函数

先看SetSize:

void CArray<TYPE, ARG_TYPE>::SetSize(INT_PTR nNewSize, INT_PTR nGrowBy)

从函数的参数可以知道,第一个参数是nNewSize新需求的存储容量大小(这里容量是按照对象个数来衡量),常规的话,如果这个nNewSize比现在数组的对象个数要大,那么数组就会进行扩容操作,把数组所能容纳的对象数扩大到nNewSize,如果比现有容量的小,那么就会缩减数组容量。那么第二个参数的含义是什么?从命名来看与成员变量m_nGrowBy有关。字面理解是扩充内存时增长的元素个数?什么意思,源码看看。 SetSize比较差,看看关键部分 源码关键部分

if (nGrowBy >= 0) m_nGrowBy = nGrowBy; // 先设置增量

第一种情况,nNewSize为零,表示要设置数组容量为零

看看是如何处理的

if (nNewSize == 0) { // shrink to nothing if (m_pData != NULL) { /*哦,如果数组已经保存有对象了,那么就强行把现有保存的对象给析 构掉,然后delete掉整个数组内存空间,最后m_pData置为NULL, 然后把关于数组对象个数的成员变量都置0*/ for( int i = 0; i < m_nSize; i++ ) (m_pData + i)->~TYPE(); delete[] (BYTE*)m_pData; m_pData = NULL; } m_nSize = m_nMaxSize = 0; }

第二种情况,数组本身就是空的,那么就表示要首次分配内存

else if (m_pData == NULL) { /**在增量和nNewSize之间取最大值,当做新的m_nMaxSize,也就是 nAllocSize ,之后开辟一块内存,大小能容纳nAllocSize 个对 象**/ size_t nAllocSize = __max(nNewSize, m_nGrowBy); m_pData = (TYPE*) new BYTE[(size_t)nAllocSize * sizeof(TYPE)]; /**依次在新开辟的内存上new新的对象,默认调用对象的无参构造,至于new 多少个对象,取决于参数nNewSize,也就是希望扩展的对象数**/ for( int i = 0; i < nNewSize; i++ ) #pragma push_macro("new") #undef new ::new( (void*)( m_pData + i ) ) TYPE; #pragma pop_macro("new") //此时nNewSize代表新开辟内存所保存的有效对象数 m_nSize = nNewSize; //m_nMaxSize小时新开辟内存所保存的最大对象数,这个取决于 //__max(nNewSize, m_nGrowBy),与增量有关 m_nMaxSize = nAllocSize; }

第三种情况数组已经分配内存,且nNewSize > 0

这样就分为两种

1.nNewSize 比m_nSize大

对于第一种情况,只需要从索引为m_nSize 的对象起创建nNewSize- m_nSiz个对象即可

memset((void*)(m_pData + m_nSize), 0, (size_t)(nNewSize-m_nSize) * sizeof(TYPE)); for( int i = 0; i < nNewSize-m_nSize; i++ ) ::new( (void*)( m_pData + m_nSize + i ) ) TYPE;

2.nNewSize 比m_nSize小

这是要缩减对象个数,也就是从索引为nNewSize 的对象开始清掉m_nSize-nNewSize个对象:

for( int i = 0; i < m_nSize-nNewSize; i++ ) m_pData + nNewSize + i)->~TYPE();

最后再设置m_nSize 为新的nNewSize m_nSize = nNewSize;

第四种情况,也是比较复杂的情况,那就是nNewSize > m_nMaxSize

哦,当前所能保存的最大对象个数不够了,按照常规的做法,此时要

1.开辟更大的内存空间

2.把之前的内存的数据拷贝的新的空间中

来看看是怎么做的

nGrowBy = m_nGrowBy; if (nGrowBy == 0) { /* 保证内存增量有值,通过下面这种方法让nGrowBy 限制在4到1024之 间 */ nGrowBy = m_nSize / 8; nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy); } INT_PTR nNewMax; if (nNewSize < m_nMaxSize + nGrowBy) nNewMax = m_nMaxSize + nGrowBy; // granularity else nNewMax = nNewSize; // no slush //新开辟的内存空间的大小在m_nMaxSize + nGrowBy与nNewSize之间取一最大值 //new出能保存nNewSize个对象的内存空间 TYPE* pNewData = (TYPE*) new BYTE[(size_t)nNewMax * sizeof(TYPE)]; //保存旧的m_nSize个对象的内存空间拷贝到新的内存空间中(对象的字节拷贝) ::ATL::Checked::memcpy_s(pNewData, (size_t)nNewMax * sizeof(TYPE),m_pData, (size_t)m_nSize * sizeof(TYPE)); memset((void*)(pNewData + m_nSize), 0, (size_t)(nNewSize-m_nSize) * sizeof(TYPE)); //在索引为m_nSize的对象上开始new出nNewSize-m_nSize个对象(调用对象的无参构造) for( int i = 0; i < nNewSize-m_nSize; i++ ) ::new( (void*)( pNewData + m_nSize + i ) ) TYPE; //delete掉旧的内存空间 delete[] (BYTE*)m_pData; //更新参数 m_pData = pNewData; m_nSize = nNewSize; m_nMaxSize = nNewMax;

画图总结一下 第一种情况(nNewSize == 0) 清空数组 第二种情况,m_pData为NULL

第三种情况nNewSize >0,但是小于m_nMaxSize,也就是说之前开辟的内存够用 1.nNewSize 比m_nSize大 2.nNewSize 比m_nSize小 第四种情况 nNewSize > m_nMaxSize 内存不够用了,需要重新分配内存 综上所述: 所以,在SetSize函数中,新设置内存大小之后,数组内所保存的有效对象的个数(m_nSize)一定是nNewSize,但是所能保存的最大对象个数(m_nMaxSize)却和参数nGrowBy 有关,当数组之前是空时,m_nMaxSize取决于 __max(nNewSize, nGrowBy),当数组不是空但是需要新开辟更大的内存空间时,m_nMaxSize取决于原来的m_nMaxSize+nGrowBy 与 nNewSize的最大值,但是涉及到需要new出新对象的,每个具体new的方法由使用者的无参构造函数如何去写有关,凡是在扩容的时候需要把对象从旧的内存拷贝到新的内存的,都是简单的把对象当成bit进行位拷贝,并不调用拷贝构造函数。

SetAtGrow函数

template<class TYPE, class ARG_TYPE> void CArray<TYPE, ARG_TYPE>::SetAtGrow(INT_PTR nIndex, ARG_TYPE newElement) { ASSERT_VALID(this); ASSERT(nIndex >= 0); if(nIndex < 0) AfxThrowInvalidArgException(); if (nIndex >= m_nSize) SetSize(nIndex+1, -1); m_pData[nIndex] = newElement; }

从代码可以看出SetAtGrow函数就是把一给定索引位置的对象进行赋值(会调用拷贝构造函数)但如果给定的索引比当前所保存的有效对象最大索引还要大,就调用SetSize(nIndex+1, -1);来调整数组中所能保存有效对象的个数(类似于扩容,对象个数一定会扩充),然后对索引位置的对象赋值, 如果如果给定的索引比当前所保存的有效对象最大索引还要大,那么对象个数扩充之后,在原先的m_nSize -1 与新的nIndex之间的对象,根据之前对SetSize的分析,会new出新对象(调用对象的无参构造函数) 之前的Add就是用SetAtGrow实现追加功能的

最后分析下两个插入函数和删除函数 在数组当中,插入和删除某一个位置的一个或者几个元素都涉及到其他元素内存位置的移动

RemoveAt分析

void CArray

template<class TYPE, class ARG_TYPE> void CArray<TYPE, ARG_TYPE>::RemoveAt(INT_PTR nIndex, INT_PTR nCount) { //删除的最后一个对象的索引 + 1,即是删除对象随引的后边界 INT_PTR nUpperBound = nIndex + nCount; if(nIndex < 0 || nCount < 0 || (nUpperBound > m_nSize) || (nUpperBound < nIndex) || (nUpperBound < nCount)) //需要移动对象的个数 INT_PTR nMoveCount = m_nSize - (nUpperBound); //析构需要删除的对象 for( int i = 0; i < nCount; i++ ) (m_pData + nIndex + i)->~TYPE(); if (nMoveCount) { //移动对象前移 ::ATL::Checked::memmove_s(m_pData + nIndex, (size_t)nMoveCount * sizeof(TYPE), m_pData + nUpperBound, (size_t)nMoveCount * sizeof(TYPE)); } //从新设置m_nSize m_nSize -= nCount; }

熟悉了之前的函数,Append函数和之前的原理类似,暂不描述

InsertAt分析

void CArray

template<class TYPE, class ARG_TYPE> void CArray<TYPE, ARG_TYPE>::InsertAt(INT_PTR nIndex, ARG_TYPE newElement, INT_PTR nCount /*=1*/) { if (nIndex >= m_nSize) { //对有效对象个数进行扩充 SetSize(nIndex + nCount, -1); } else { //对有效对象个数进行扩充 INT_PTR nOldSize = m_nSize; SetSize(m_nSize + nCount, -1); //把新扩充的对象先析构掉(因为刚刚我们只是希望得到扩 //充保存有效对象个数的内存,并不希望在新增的内存是新 //建对象) for( int i = 0; i < nCount; i++ ) (m_pData + nOldSize + i)->~TYPE(); //把需要进行移动的对象向后移动(位拷贝) ::ATL::Checked::memmove_s(m_pData + nIndex + nCount, (nOldSize-nIndex) (nOldSize-nIndex) * sizeof(TYPE)); memset((void*)(m_pData + nIndex), 0, (size_t)nCount * sizeof(TYPE)); //空出的位置new对象(new的对象之后要被参数设定的对象覆盖) for( int i = 0; i < nCount; i++ ) ::new( (void*)( m_pData + nIndex + i ) ) TYPE; } //插入对象赋值--要调用拷贝对象函数 while (nCount--) m_pData[nIndex++] = newElement; }

这里需要注意,插入对象时会先在空出的内存是new出新对象,然后再通过拷贝构造函数复制参数传进来的对象到new出的新对象上。所以,如果无参构造函数中存在有类似成员变量指针指向了一块堆内存空间的情况,那么在对象的拷贝构造函数中设计者可能就要去先释放之前分配的堆内,然后再去对成员变量进行拷贝了,处理不当会产生内存碎片。

InsertAt另一个重载版本

功能是**把一个CArray插入到另一个CArray中。 关键代码如下**

template<class TYPE, class ARG_TYPE> void CArray<TYPE, ARG_TYPE>::InsertAt(INT_PTR nStartIndex, CArray* pNewArray) { if (pNewArray->GetSize() > 0) { //先把pNewArray指向CArray的第一个元素(先默认把他 //当做插入元素)对象插入到本CArray中,插入 //pNewArray->GetSize()个 InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize()); //然后把pNewArray指向CArray数组中保存的对象赋值到 //插入空间中的对应对象上(会为每一个对象调用拷贝构造 //函数) for (INT_PTR i = 0; i < pNewArray->GetSize(); i++) SetAt(nStartIndex + i, pNewArray->GetAt(i)); } } /* 由代码可以看出,把一个CArray插入到另一个CArray中的思路是,先取一个默认的对象就是pNewArray->GetAt(0)作为插入对象,连续插入pNewArray->GetSize()个,然后再挨个的用for循环把pNewArray指向的CArray对刚刚插入过的对象进行赋值 */

注意,拷贝构造函数,妥善处理内存,防止内存碎片

其他

还有MFC特性的串行化函数Serialize。后面专门讨论串行化

转载请注明原文地址: https://www.6miu.com/read-1400002.html

最新回复(0)