正式入坑C++(1)——山寨的泛型List

额,不要说我三心二意:一边在看.NET和CLR的原理、一边在看JavaScript、一边在看Java;有时看算法有时看Unity、Hibernate;有时看Hadoop有时看Redis;现在又开始看C++了。

以前觉得无论什么语言嘛,其实都差不多,核心思想基本一致。现在又不这么想了,其实语言的选择对软件的性能、可靠性、开发成本之类的关系很大,所以觉得还是要多接触一些比较核心的东西——那么自然是C++了。以前在学校学的C++完全是酱油,太水了基本没啥用,用来用去和C差不多,所以现在要自己学啦。

废话不说了,第一个任务就是山寨.NET类库里面的List<T>泛型类,还偷看过它的源代码。那么现在就开始用C++进行“山寨”吧。(所以这个类的名字就是ListSZ,SZ=山寨,不是“单维零下标”数组。)

当然刚入手还是碰了不少钉子,最主要的是模版的实现为啥不支持放在cpp里啊?搞得我折腾了老半天。(感谢KC提供技术支持,所以KC要赶快请我吃饭)

主要实现了如下功能:

  • 自动扩容(直接抄的List的实现方式,容量不够时翻倍,但InsertRange的时候除外);
  • Add添加到末尾,AddRange在末尾添加多个,Insert在中间插入一个或多个;
  • Remove删除最后一个或其中一个,RemoveRange删除其中一片。

MakeRoom是在中间生成一片空的区域,原来的元素全往后移。EnsureCapacity在容量不够时扩容……

直接贴代码:

#include <stdexcept>
#include "stdafx.h"
#include <algorithm>

#pragma once
template <typename T> class ListSZ
{
private:
	T* _mArray;
	int _capacity;
	int _elementCount;

	const int DEFAULT_CAPACITY = 8;

	void EnsureCapacity(int newCount)
	{
		if ((__int64) _elementCount + newCount >= INT_MAX)
			throw std::out_of_range("ListSZ supports up to 2^31 - 1 elements.");

		//If _elementCount = _capacity - 1, the buffer is full
		if (_elementCount + newCount > _capacity)
		{

			int new_capacity = _capacity >= INT_MAX / 2 ? INT_MAX : _capacity << 1;

			if (new_capacity < _elementCount + newCount)
				new_capacity = std::min((__int64) INT_MAX, (__int64) (_elementCount + newCount) << 1);

			/*if (new_capacity < _elementCount + newCount)
				new_capacity = ((__int64) (_elementCount + newCount) << 1) >= INT_MAX ? INT_MAX, (_elementCount + newCount) << 1;
*/
			T* new_buffer = new T[new_capacity];
			memcpy(new_buffer, _mArray, sizeof(T) * _elementCount);

			delete [] _mArray;

			_mArray = new_buffer;
			_capacity = new_capacity;
		}
	}

	void MakeRoom(int index, int count)
	{
		if (index >= _elementCount - 1) return;

		EnsureCapacity(count);

		int move_count = _elementCount - index;

		memmove(_mArray + index + count, _mArray + index, move_count * sizeof(T));
		memset(_mArray + index, 0, count * sizeof(T));

	}

public:
	ListSZ() : ListSZ(DEFAULT_CAPACITY){};

	ListSZ(int capacity)
	{
		if (capacity <= 0)
			throw std::invalid_argument("The capacity of the list cannot be less than 1.");

		_capacity = capacity;

		_mArray = new T[_capacity];
		//_mArray = (T*) malloc(sizeof(T) * _capacity);
		memset(_mArray, 0, _capacity * sizeof(T));
	}

	ListSZ(const T* source, int elementCount) : ListSZ(elementCount)
	{
		Insert(source, 0, elementCount, 0);
	}

	~ListSZ()
	{
		delete [] _mArray;
	}

	T GetElement(int index)
	{
		if (index < 0 || index >= _elementCount)
			throw std::invalid_argument("The index is outsize of the boundary of list.");

		return *(_mArray + index);
	}

	void Add(T value)
	{
		EnsureCapacity(1);

		*(_mArray + _elementCount) = value;
		_elementCount++;
	}

	void AddRange(T* source, int count)
	{
		Insert(source, 0, count, _elementCount);
	}

	void Insert(T value, int index)
	{
		if (index < 0 || index >= _elementCount)
			throw std::invalid_argument("The index is outsize of the boundary of list.");

		MakeRoom(index, 1);

		*(_mArray + index) = value;
		_elementCount++;
	}

	void Insert(const T* source, int elementCount, int insertIndex)
	{
		Insert(source, 0, elementCount, insertIndex);
	}

	void Insert(const T* source, int startIndex, int count, int insertIndex)
	{
		if (count <= 0)
			throw std::invalid_argument("The count of elements to be inserted cannot less than 1.");

		if (insertIndex < 0 || insertIndex > _elementCount)
			throw std::invalid_argument("The target index is outside of the boundary of list.");

		EnsureCapacity(_elementCount + count);

		MakeRoom(insertIndex, count);

		memcpy(_mArray + insertIndex, source + startIndex, count * sizeof(T));

		_elementCount += count;
	}

	T Remove()
	{
		if (_elementCount > 0)
		{
			_elementCount--;
			return *(_mArray + _elementCount);
		}

		return NULL;
	}

	T Remove(int index)
	{
		if (index < 0 || index >= _elementCount)
			throw std::invalid_argument("The index is outsize of the boundary of list.");

		T ret_value = *(_mArray + index);

		RemoveRange(index, 1);

		return ret_value;
	}

	void RemoveRange(int startIndex, int count)
	{
		if (count <= 0)
			throw std::invalid_argument("The removing count must greater than 0.");

		if (startIndex < 0 || startIndex + count >= _elementCount)
			throw std::invalid_argument("The arguments are removing elements outsize the boundary of the list.");

		memmove(_mArray + startIndex, _mArray + startIndex + count, (_elementCount - startIndex - count) * sizeof(T));

		_elementCount -= count;
	}

	inline int Count() { return _elementCount; }
};

作为刚入手写的东西算是不错了。当然不能忘记了我比较关心的性能问题,于是做了如下测试(都是在release环境下,且是第二次运行保证不会被JIT编译):

  • 添加500万个元素到列表里,C#的类库耗时86毫秒,C++的vector库耗时64毫秒,山寨类(就是我写的类)耗时81毫秒。看起来都差不多,因为扩容的时候似乎都是把原来的东西复制到新的地方去。
  • 在表头插入500个元素(在原有500万个元素的基础上),C#的类库和山寨类都基本上耗时4秒左右。vector类没测试,估计也差不多。

可以看到,经过M$手的.NET类库的性能是很高的,基本上接近C++的原生库了。至于为什么,List类大量用到了Array.Copy方法,这个方法就是:

[MethodImpl(MethodImplOptions.InternalCall), ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail), SecurityCritical]
internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);

这个InternalCall和Native Code一样,都是C++写的,因此性能差不多。

所以说.NET的程序不一定比C++的慢(当然叠加了各种功能,甚至滥用了各种特性导致性能变低的除外),如果设计得好的话完全可以放心地用。

最后要说一句,在特定环境下.NET的程序甚至比C++写的程序更快,因为JIT会根据运行平台(比如CPU的架构类型等)生成对应的Native Code,而编译式的程序就没有这个优势,除非是针对了特定的平台做过优化,否则为了兼容各平台只能选用最小的指令集。

无论如何,作为山寨的这个类我认为还不错(不过不论从风格上还是其他方面貌似我还是.NET的风格),以后在学习C++的时候不断适应吧。

正式入坑C++(1)——山寨的泛型List”的一个响应

  1. memcpy(new_buffer, _mArray, sizeof(T) * _elementCount);

    这个不对,如果 T 是 non-POD,而且其 operator == 不是简单的复制,你直接 memcpy 就跪了。

    可以考虑用 std::copy 或者手写 for 循环。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s