欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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++了。以前在學(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)文章

  • C++基本組件之內(nèi)存池詳解

    C++基本組件之內(nèi)存池詳解

    這篇文章主要為大家詳細(xì)介紹了C++中的基本組件——內(nèi)存池的相關(guān)知識,文中的示例代碼講解詳細(xì),對我們學(xué)習(xí)C++有一定的幫助,需要的可以參考一下
    2023-03-03
  • OpenCV中findContours函數(shù)參數(shù)詳解

    OpenCV中findContours函數(shù)參數(shù)詳解

    Opencv中通過使用findContours函數(shù),簡單幾個的步驟就可以檢測出物體的輪廓,很方便。本文將和大家一起探討一下findContours方法中各參數(shù)的含義及用法,感興趣的可以了解一下
    2022-08-08
  • C語言中new與malloc的區(qū)別詳解

    C語言中new與malloc的區(qū)別詳解

    這篇文章主要介紹了C語言中new與malloc的區(qū)別詳解,new是運算符,可以用于動態(tài)分配,如果想要撤銷內(nèi)存使用delete,new運算符使用的一般格式為new類型,用new分配數(shù)組空間時不能指定初值,需要的朋友可以參考下
    2023-10-10
  • 華為云開發(fā)工具CodeArts IDE for C/C++開發(fā)使用指南

    華為云開發(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ū)別

    一篇文章讓你輕松理解C++中vector和list區(qū)別

    對于學(xué)c語言的同學(xué)來說,vector和list這兩個東西經(jīng)常會搞錯,下面這篇文章主要給大家介紹了關(guān)于C++中vector和list區(qū)別的相關(guān)資料,需要的朋友可以參考下
    2022-01-01
  • Qt連接MySQL數(shù)據(jù)庫的實現(xiàn)(保姆級成功版教程)

    Qt連接MySQL數(shù)據(jù)庫的實現(xiàn)(保姆級成功版教程)

    本文主要介紹了Qt連接MySQL數(shù)據(jù)庫的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • C語言中雙鏈表的基本操作

    C語言中雙鏈表的基本操作

    這篇文章主要介紹了C語言中雙鏈表的基本操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • vector,map,list,queue的區(qū)別詳細(xì)解析

    vector,map,list,queue的區(qū)別詳細(xì)解析

    如果我們需要隨機訪問一個容器則vector要比list好得多。如果我們已知要存儲元素的個數(shù)則vector 又是一個比list好的選擇。如果我們需要的不只是在容器兩端插入和刪除元素則list顯然要比vector好
    2013-09-09
  • C++回溯算法之深度優(yōu)先搜索詳細(xì)介紹

    C++回溯算法之深度優(yōu)先搜索詳細(xì)介紹

    回溯在迷宮搜索中使用很常見,就是這條路走不通,然后返回前一個路口,繼續(xù)下一條路。回溯算法說白了就是窮舉法,下面讓我們一起來看看回溯算法中深度優(yōu)先搜索吧
    2023-01-01
  • C語言實現(xiàn)字母大小寫轉(zhuǎn)換的方法

    C語言實現(xiàn)字母大小寫轉(zhuǎn)換的方法

    這篇文章主要介紹了C語言實現(xiàn)字母大小寫轉(zhuǎn)換的方法,涉及C語言字符串的遍歷與轉(zhuǎn)換技巧,非常簡單實用,需要的朋友可以參考下
    2015-07-07

最新評論