cocos2dx学习笔记：CCArray

最近学习了下CCArray，想看下它的内部实现，搞清楚存储方式，以便后面使用起来更高效。

打开CCArray的源码，看了下，发现它其实内部是数组的实现形式，而且CCArray的所有函数只是包装了下ccArray的实现。

CCArray.h:

class CC_DLL CCArray : public CCObject
{
public:
    static CCArray* create();
。。。。。
。。。。。
public:
    ccArray* data;
。。。。。
。。。。。
};

通过.h文件可以发现，CCArray的所有操作其实最后都是操作的它的变量data，这个变量data的类型为ccArray，它是个结构体，真正的实现了Array的各种方法。

ccCArray.h:
typedef struct _ccArray {
	unsigned int num, max;
	CCObject** arr;
} ccArray;

/** Allocates and initializes a new array with specified capacity */
ccArray* ccArrayNew(unsigned int capacity);
/** Frees array after removing all remaining objects. Silently ignores nil arr. */
void ccArrayFree(ccArray*& arr);
/** Doubles array capacity */
void ccArrayDoubleCapacity(ccArray *arr);
。。。。。。
。。。。。。

到这里就很清楚了，ccArray是一个结构体，里面封装了一个数组的指针。因此通过CCArray进行的各种操作其实内部是操作的一个数组指针。
那么就很容易的得出结论：

1）随机查找和修改的速度很快。
2）在指定的位置插入和删除元素速度很慢。
3）扩容消耗很大。
后续使用时要注意。不过个人感觉cocos2dx代码中仍然有问题，那就是替换：

void CCArray::replaceObjectAtIndex(unsigned int index, CCObject* pObject, bool bReleaseObject/* = true*/)
{
    ccArrayInsertObjectAtIndex(data, pObject, index);
    ccArrayRemoveObjectAtIndex(data, index+1);
}

ccCArray.cpp:
/** Inserts a value at a certain position. Behavior undefined if array doesn't have enough capacity */
void ccCArrayInsertValueAtIndex( ccCArray *arr, void* value, unsigned int index)
{
	CCAssert( index < arr->max, "ccCArrayInsertValueAtIndex: invalid index");
	
	unsigned int remaining = arr->num - index;
    // make sure it has enough capacity
    if (arr->num + 1 == arr->max)
    {
        ccCArrayDoubleCapacity(arr);
    }
	// last Value doesn't need to be moved
	if( remaining > 0) {
		// tex coordinates
		memmove((void *)&arr->arr[index+1], (void *)&arr->arr[index], sizeof(void*) * remaining );
	}
	
	arr->num++;
	arr->arr[index] = value;
}

/** Removes object at specified index and pushes back all subsequent objects.
 Behavior undefined if index outside [0, num-1]. */
void ccArrayRemoveObjectAtIndex(ccArray *arr, unsigned int index, bool bReleaseObj/* = true*/)
{
    CCAssert(arr && arr->num > 0 && index < arr->num, "Invalid index. Out of bounds");
    if (bReleaseObj)
    {
        CC_SAFE_RELEASE(arr->arr[index]);
    }
    
	arr->num--;
	
	unsigned int remaining = arr->num - index;
	if(remaining>0)
    {
		memmove((void *)&arr->arr[index], (void *)&arr->arr[index+1], remaining * sizeof(CCObject*));
    }
}

void ccArrayDoubleCapacity(ccArray *arr)
{
	arr->max *= 2;
	CCObject** newArr = (CCObject**)realloc( arr->arr, arr->max * sizeof(CCObject*) );
	// will fail when there's not enough memory
    CCAssert(newArr != 0, "ccArrayDoubleCapacity failed. Not enough memory");
	arr->arr = newArr;
}

通过上述代码可以发现，移除，插入，扩容都有内存操作，因此最好在使用CCArray时考虑好初始容量。

另外，CCArray为了提供更快速的删除功能，增加了方法 fastremove*，这里分析下实现：

void ccArrayFastRemoveObjectAtIndex(ccArray *arr, unsigned int index)
{
	CC_SAFE_RELEASE(arr->arr[index]);
	unsigned int last = --arr->num;
	arr->arr[index] = arr->arr[last];
}

根据代码可知，快速删除的实质是将数组的最后一个元素添加到这个空缺来，这样就要注意的是数组内部的顺序已经变了。
测试代码如下：

	CCArray *arr = CCArray::createWithCapacity(5);
	arr->addObject(CCString::create("A"));
	arr->addObject(CCString::create("B"));
	arr->addObject(CCString::create("C"));
	arr->addObject(CCString::create("D"));
	arr->addObject(CCString::create("E"));

	CCLOG("init");
	CCObject *itemStr = NULL;
	CCARRAY_FOREACH(arr, itemStr)
	{
		CCLOG("%s", ((CCString *)itemStr)->getCString());
	}

	CCLOG("fast remove");
	arr->fastRemoveObjectAtIndex(2);
	CCARRAY_FOREACH(arr, itemStr)
	{
		CCLOG("%s", ((CCString *)itemStr)->getCString());
	}

 输出：

init
A
B
C
D
E
fast remove
A
B
E
D

如下图：