C++實現(xiàn)的泛型List類分享

更新時間：2014年07月16日 09:19:33 投稿：junjie

這篇文章主要介紹了C++實現(xiàn)的泛型List類分享,參考C#的List功能實現(xiàn),需要的朋友可以參考下

額，不要說我三心二意：一邊在看.NET和CLR的原理、一邊在看JavaScript、一邊在看Java；有時看算法有時看Unity、Hibernate；有時看Hadoop有時看Redis；現(xiàn)在又開始看C++了。

以前覺得無論什么語言嘛，其實都差不多，核心思想基本一致?，F(xiàn)在又不這么想了，其實語言的選擇對軟件的性能、可靠性、開發(fā)成本之類的關(guān)系很大，所以覺得還是要多接觸一些比較核心的東西——那么自然是C++了。以前在學校學的C++完全是醬油，太水了基本沒啥用，用來用去和C差不多，所以現(xiàn)在要自己學啦。

廢話不說了，第一個任務就是山寨.NET類庫里面的List<T>泛型類，還偷看過它的源代碼。那么現(xiàn)在就開始用C++進行“山寨”吧。（所以這個類的名字就是ListSZ，SZ=山寨，不是“單維零下標”數(shù)組。）

當然剛?cè)胧诌€是碰了不少釘子，最主要的是模版的實現(xiàn)為啥不支持放在cpp里?。扛愕梦艺垓v了老半天。（感謝KC提供技術(shù)支持，所以KC要趕快請我吃飯）

主要實現(xiàn)了如下功能：

1.自動擴容（直接抄的List的實現(xiàn)方式，容量不夠時翻倍，但InsertRange的時候除外）；
2.Add添加到末尾，AddRange在末尾添加多個，Insert在中間插入一個或多個；
3.Remove刪除最后一個或其中一個，RemoveRange刪除其中一片。

MakeRoom是在中間生成一片空的區(qū)域，原來的元素全往后移。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; }
};

作為剛?cè)胧謱懙臇|西算是不錯了。當然不能忘記了我比較關(guān)心的性能問題，于是做了如下測試（都是在release環(huán)境下，且是第二次運行保證不會被JIT編譯）：

1.添加500萬個元素到列表里，C#的類庫耗時86毫秒，C++的vector庫耗時64毫秒，山寨類（就是我寫的類）耗時81毫秒。看起來都差不多，因為擴容的時候似乎都是把原來的東西復制到新的地方去。

2.在表頭插入500個元素（在原有500萬個元素的基礎(chǔ)上），C#的類庫和山寨類都基本上耗時4秒左右。vector類沒測試，估計也差不多。

可以看到，經(jīng)過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++的慢（當然疊加了各種功能，甚至濫用了各種特性導致性能變低的除外），如果設(shè)計得好的話完全可以放心地用。

最后要說一句，在特定環(huán)境下.NET的程序甚至比C++寫的程序更快，因為JIT會根據(jù)運行平臺（比如CPU的架構(gòu)類型等）生成對應的Native Code，而編譯式的程序就沒有這個優(yōu)勢，除非是針對了特定的平臺做過優(yōu)化，否則為了兼容各平臺只能選用最小的指令集。

無論如何，作為山寨的這個類我認為還不錯（不過不論從風格上還是其他方面貌似我還是.NET的風格），以后在學習C++的時候不斷適應吧。

您可能感興趣的文章: