C++實現(xiàn)的泛型List類分享
額,不要說我三心二意:一邊在看.NET和CLR的原理、一邊在看JavaScript、一邊在看Java;有時看算法有時看Unity、Hibernate;有時看Hadoop有時看Redis;現(xiàn)在又開始看C++了。
以前覺得無論什么語言嘛,其實都差不多,核心思想基本一致?,F(xiàn)在又不這么想了,其實語言的選擇對軟件的性能、可靠性、開發(fā)成本之類的關(guān)系很大,所以覺得還是要多接觸一些比較核心的東西——那么自然是C++了。以前在學(xué)校學(xué)的C++完全是醬油,太水了基本沒啥用,用來用去和C差不多,所以現(xiàn)在要自己學(xué)啦。
廢話不說了,第一個任務(wù)就是山寨.NET類庫里面的List<T>泛型類,還偷看過它的源代碼。那么現(xiàn)在就開始用C++進(jìn)行“山寨”吧。(所以這個類的名字就是ListSZ,SZ=山寨,不是“單維零下標(biāo)”數(shù)組。)
當(dāng)然剛?cè)胧诌€是碰了不少釘子,最主要的是模版的實現(xiàn)為啥不支持放在cpp里啊?搞得我折騰了老半天。(感謝KC提供技術(shù)支持,所以KC要趕快請我吃飯)
主要實現(xiàn)了如下功能:
1.自動擴容(直接抄的List的實現(xiàn)方式,容量不夠時翻倍,但I(xiàn)nsertRange的時候除外);
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è)胧謱懙臇|西算是不錯了。當(dāng)然不能忘記了我比較關(guān)心的性能問題,于是做了如下測試(都是在release環(huán)境下,且是第二次運行保證不會被JIT編譯):
1.添加500萬個元素到列表里,C#的類庫耗時86毫秒,C++的vector庫耗時64毫秒,山寨類(就是我寫的類)耗時81毫秒??雌饋矶疾畈欢?,因為擴容的時候似乎都是把原來的東西復(fù)制到新的地方去。
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++的慢(當(dāng)然疊加了各種功能,甚至濫用了各種特性導(dǎo)致性能變低的除外),如果設(shè)計得好的話完全可以放心地用。
最后要說一句,在特定環(huán)境下.NET的程序甚至比C++寫的程序更快,因為JIT會根據(jù)運行平臺(比如CPU的架構(gòu)類型等)生成對應(yīng)的Native Code,而編譯式的程序就沒有這個優(yōu)勢,除非是針對了特定的平臺做過優(yōu)化,否則為了兼容各平臺只能選用最小的指令集。
無論如何,作為山寨的這個類我認(rèn)為還不錯(不過不論從風(fēng)格上還是其他方面貌似我還是.NET的風(fēng)格),以后在學(xué)習(xí)C++的時候不斷適應(yīng)吧。
相關(guān)文章
OpenCV中findContours函數(shù)參數(shù)詳解
Opencv中通過使用findContours函數(shù),簡單幾個的步驟就可以檢測出物體的輪廓,很方便。本文將和大家一起探討一下findContours方法中各參數(shù)的含義及用法,感興趣的可以了解一下2022-08-08華為云開發(fā)工具CodeArts IDE for C/C++開發(fā)使用指南
CodeArts IDE是一個集成開發(fā)環(huán)境(IDE),它提供了開發(fā)語言和調(diào)試服務(wù),本文主要介紹了華為云開發(fā)工具CodeArts IDE for C/C++ 開發(fā)使用指南,感興趣的可以了解一下2023-08-08一篇文章讓你輕松理解C++中vector和list區(qū)別
對于學(xué)c語言的同學(xué)來說,vector和list這兩個東西經(jīng)常會搞錯,下面這篇文章主要給大家介紹了關(guān)于C++中vector和list區(qū)別的相關(guān)資料,需要的朋友可以參考下2022-01-01Qt連接MySQL數(shù)據(jù)庫的實現(xiàn)(保姆級成功版教程)
本文主要介紹了Qt連接MySQL數(shù)據(jù)庫的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06vector,map,list,queue的區(qū)別詳細(xì)解析
如果我們需要隨機訪問一個容器則vector要比list好得多。如果我們已知要存儲元素的個數(shù)則vector 又是一個比list好的選擇。如果我們需要的不只是在容器兩端插入和刪除元素則list顯然要比vector好2013-09-09