当前位置:  编程技术>c/c++/嵌入式

C++实现的泛型List类分享

    来源: 互联网  发布时间:2014-10-25

    本文导语:  额,不要说我三心二意:一边在看.NET和CLR的原理、一边在看JavaScript、一边在看Java;有时看算法有时看Unity、Hibernate;有时看Hadoop有时看Redis;现在又开始看C++了。 以前觉得无论什么语言嘛,其实都差不多,核心思想基本一致...

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

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

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

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

主要实现了如下功能:

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

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

直接贴代码:

#include 
#include "stdafx.h"
#include 

#pragma once
template  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  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 = _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编译):

1.添加500万个元素到列表里,C#的类库耗时86毫秒,C++的vector库耗时64毫秒,山寨类(就是我写的类)耗时81毫秒。看起来都差不多,因为扩容的时候似乎都是把原来的东西复制到新的地方去。

2.在表头插入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++的时候不断适应吧。


    
 
 

您可能感兴趣的文章:

  • Base64编码原理详解及c++编码解码实现
  • 我实现了个J2EE技术的服务器,支持TCP、UDP和数据库,由于性能的原因,需要改为C或C++实现,我是C、C++新手,我该如何入手呢?看什么样的
  • c++实现MD5算法代码示例
  • java 与 C++ 实现后绑定的方法
  • c++通用模板类(template class)定义实现详细介绍
  • Qt实现的C++框架 qtioccontainer
  • 用C或C++实现主存的分配与回收
  • 在linux系统上,如何用C++实现获取和设置系统时间?
  • 文本压缩算法C++实现 Golden Huffman
  • C++标准库实现 libc++
  • C++的XMLRPC实现 XMLRPC++
  • Java/JavaScript API 的 C++ 实现 libj
  • c++ 连接两个字符串实现代码 实现类似strcat功能
  • c++在unix中如何实现CString的方法?或者说有没有替换CString的类?
  • 请问:java中如何实现C++中的sizeof()方法?
  • 用C或C++编程,模拟可变分区存储管理且首次适应的算法实现存储器的分配与回收
  • vim中如何实现c++代码编写的自动格式化和语法高亮的功能?
  • C++实现CreatThread函数主线程与工作线程交互的方法
  • 请教为什么在C++编译通过并实现的程序,在linux下就会出错
  • linux下c++怎样实现回调(CALLBACK)函数?
  • 在linux下如何用c++实现建立一个文件夹
  • 修改.htaccess实现301域名重定向示例分享
  • strcpy函数实现简示例命分享
  • Android实现关机重启的方法分享
  • shell脚本实现拷贝大文件显示百分比的代码分享
  • Shell脚本实现检测文件是否被修改过代码分享
  • java实现fibonacci数列学习示例分享(斐波那契数列)
  • python实现网页链接提取的方法分享
  • php实现水仙花数代码分享
  • sql server中通过查询分析器实现数据库的备份与恢复方法分享
  • php实现水仙花数示例分享
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 通过javascript实现DIV居中,兼容各浏览器版本
  • socket实现多文件并发传输,求助多线程实现问题?
  • Python GUI编程:tkinter实现一个窗口并居中代码
  • interface 到底有什么用???实现接口,怎么实现??
  • 通过javascript库JQuery实现页面跳转功能代码
  • 怎么用Jsp实现在页面实现树型结构?
  • sharepoint 2010 使用STSNavigate函数实现文件下载举例
  • windows 下的PortTunnel 在linux下怎么实现?或者相应的已经实现的软件?端口映射
  • php实现socket实现客户端和服务端数据通信源代码
  • 网站重定向用C语言实现iptables,ACL实现
  • flash AS3反射实现(describeType和getDefinitionByName)
  • 在linux下如何编程实现nslookup命令实现的IP地址和域名互相转换的功能?
  • boost unordered_map和std::list相结合的实现LRU算法
  • 求在freebsd+Squid下实现pc上网的透明代理的实现方法!给出具体配置方法的高分谢!
  • c#通过委托delegate与Dictionary实现action选择器代码举例
  • linux下如实现与window下的驱动器实现文件共享??
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • qt如何实现:操作键盘实现数据的滚动?
  • iphone cocos2d 精灵的动画效果(图片,纹理,帧)CCAnimation实现
  • 我想用APPLET实现读取客户端的图片文件,该如何实现?
  • c语言判断某一年是否为闰年的各种实现程序代码
  • PING是用TCP,还是用UDP来实现的?或是采用其它协议实现的?


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3