后台开发:核心技术与应用实践3.3.4 Vector类的简单实现

3.3.4 Vector类的简单实现

实现一个vector,绝对是C++中的重点知识。下面例3.13中提供了类的简单实现。

【例3.17】 vector类的简单实现。

#include<algorithm>

#include<iostream>

#include
<assert.h>

using namespace
std;

template<typename
T>

class myVector

{

private:

    /*walk length*/

    /*myVector each time increase space
length*/

    #define WALK_LENGTH 64;

 

public:

    /*default constructor*/

   
myVector():array(0),theSize(0),theCapacity(0){    }

    myVector(const T& t,unsigned int
n):array(0),theSize(0),theCapacity(0){

        while(n--){

            push_back(t);

        }

    }

 

    /*copy constructor*/

    myVector(const myVector<T>&
other):array(0),theSize(0),theCapacity(0){

        *this = other;

    }

 

    /*= operator*/

    myVector<T>& operator
=(myVector<T>& other){

        if(this == &other)

            return *this;

        clear();

        theSize = other.size();

        theCapacity = other.capacity();

        array = new T[theCapacity];

        for(unsigned int i = 0
;i<theSize;++i)

        {

            array[i] = other[i];

        }

        return *this;

    }

 

    /*destructor*/

    ~myVector(){

        clear();

    }

 

    /*the pos must be less than
myVector.size();*/

    T& operator[](unsigned int pos){

        assert(pos<theSize);

        return array[pos];

    }

 

    /*element theSize*/

    unsigned int size(){

        return theSize;

    }

 

    /*alloc theSize*/

    unsigned int capacity(){

        return theCapacity;

    }

 

    /*is 
empty*/

    bool empty(){

        return theSize == 0;

    }

 

    /*clear myVector*/

    void clear(){

        deallocator(array);

        array = 0;

        theSize = 0;

        theCapacity = 0;

    }

 

    /*adds an element in the back of myVector*/

    void push_back(const T& t){

        insert_after(theSize-1,t);

    }

 

    /*adds an element int the front of
myVector*/

    void push_front(const T& t){

        insert_before(0,t);

    }

 

    /*inserts an element after the pos*/

    /*the pos must be in [0,theSize);*/

    void insert_after(int pos,const T& t){

        insert_before(pos+1,t);

    }

 

    /*inserts an element before the pos*/

    /*the pos must be less than the
myVector.size()*/

    void insert_before(int pos,const T& t){

        if(theSize==theCapacity){

            T* oldArray = array;

            theCapacity += WALK_LENGTH;

            array = allocator(theCapacity);

           
/*memcpy(array,oldArray,theSize*sizeof(T)):*/

            for(unsigned int i = 0
;i<theSize;++i){

                array[i] = oldArray[i];

            }

            deallocator(oldArray);

        }

 

        for(int i =
(int)theSize++;i>pos;--i){

            array[i] = array[i-1];

        }

        array[pos] = t;

    }

 

    /*erases an element in the pos;*/

    /*pos must be in [0,theSize);*/

    void erase(unsigned int pos){

        if(pos<theSize){

            --theSize;

            for(unsigned int i =
pos;i<theSize;++i){

                array[i] = array[i+1];

            }

        }

    }

 

private:

    T* 
allocator(unsigned int size){

        return new T[size];

    }

 

    void deallocator(T* arr){

        if(arr)

            delete[] arr;

    }

private:

    T*                                array;

    unsigned int    theSize;

    unsigned int    theCapacity;

};

 

void
printfVector(myVector<int>& vector1){

    for(unsigned int i = 0 ; i <
vector1.size();++i){

       
cout<<vector1[i]<<",";

    }

    cout<<"alloc size =
"<<vector1.capacity()<<",size =
"<<vector1.size()<<endl;

}

 

int main(){

    myVector<int> myVector1;

    myVector<int> myVector2(0,10);

    myVector2.push_front(1);

    myVector2.erase(11);

    printfVector(myVector2);

    myVector1.push_back(2);

    myVector1.push_front(1);

    printfVector(myVector1);

    myVector1.insert_after(1,3);

    printfVector(myVector1);

 

    myVector2 = myVector1;

    myVector2.insert_before(0,0);

    myVector2.insert_before(1,-1);

    printfVector(myVector2);

    return 0;

}

程序的执行结果为:

1,0,0,0,0,0,0,0,0,0,0,alloc
size = 64,size = 11

1,2,alloc size =
64,size = 2

1,2,3,alloc size
= 64,size = 3

0,-1,1,2,3,alloc
size = 64,size = 5

STL库中vector是一个自动管理的动态数组,只要明白vector的类型是一个数组,至于怎么去实现它其实不难。例3.17中选择了一种简单的方式去实现它:定义一个步长WALK_LENGTH,在数组空间不够时,再重新申请长度为theCapacity +WALK_LENGTH的内存,这样就避免了每次当myVector元素增加的时候,需要去重新申请空间的问题,当然不好的地方就是会浪费一定的空间,但是时间效率上会提高很多。因为vector可以支持下标访问,所以就不用单独构造一个iterator,从而提高效率。

例3.17中,myVector拥有3个成员变量:元素的个数theSize、容量theCapacity和一个指针数组array。

默认构造函数里,把元素的个数theSize、容量theCapacity都赋值为0,数组赋值为空,代码如下:

myVector():array(0),theSize(0),theCapacity(0){    }

用几个相同的值赋值给myVector,那应该是逐个添加的:

    myVector(const T& t,unsigned int
n):array(0),theSize(0),theCapacity(0){

        while(n--){

            push_back(t);

        }

    }

进行重载:

    myVector<T>& operator
=(myVector<T>& other){

        if(this == &other)

            return *this;

        clear();

        theSize = other.size();

        theCapacity = other.capacity();

        array = new T[theCapacity];

        for(unsigned int i = 0
;i<theSize;++i)

        {

            array[i] = other[i];

        }

        return *this;

    }

如果参数与本myVector相同,那就无需赋值了;不相同时才需要赋值,并需要分别对3个成本变量进行赋值,元素个数、容量大小和数组内容。

析构函数里直接调用clear函数,如下所示:

    ~myVector(){

        clear();

    }

用下标的方式访问myVector中的元素,其实就是访问数组array中的元素,注意下标必须小于元素个数,如下所示:

    T& operator[](unsigned int pos){

        assert(pos<theSize);

       
return array[pos];

    }

获得元素个数和容器大小,直接返回成员变量即可,如下所示:

    /*element theSize*/

    unsigned int size(){

        return theSize;

    }

 

    /*alloc theSize*/

    unsigned int capacity(){

        return theCapacity;

    }

判断myVector是否为空,直接判断元素个数是否等于0即可,如下所示:

    bool empty(){

        return theSize == 0;

    }

清空myVector中的元素,需要删除掉数组指针,并把元素个数和容量大小都置0,如下所示:

    void clear(){

        deallocator(array);

        array = 0;

        theSize = 0;

        theCapacity = 0;

    }

push_back、push_front都可以归根于insert,在哪个位置插入,如下所示:

    void push_back(const T& t){

        insert_after(theSize-1,t);

    }

 

    void push_front(const T& t){

        insert_before(0,t);

    }

 

    void insert_after(int pos,const T& t){

        insert_before(pos+1,t);

    }

 

    void insert_before(int pos,const T& t){

        if(theSize==theCapacity){

            T* oldArray = array;

            theCapacity += WALK_LENGTH;

            array = allocator(theCapacity);

            /*memcpy(array,oldArray,theSize*sizeof(T)):*/

            for(unsigned int i = 0
;i<theSize;++i){

                array[i] = oldArray[i];

            }

            deallocator(oldArray);

    }

 

        for(int i =
(int)theSize++;i>pos;--i){

            array[i] = array[i-1];

        }

        array[pos] = t;

}

myVector通过一个连续的数组存放元素,如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,再插入新增的元素。这个元素后面的所有元素都向后移动一个位置,在空出来的位置上存入新增的元素。

删除某个元素,则要把这个元素后面的都往前挪,并把元素个数-1,如下所示:

void
erase(unsigned int pos){

    if(pos<theSize){

        --theSize;

        for(unsigned int i = pos;i<theSize;++i){

            array[i] = array[i+1];

        }

    }

}

通过分析代码,可以发现vector的特点,如下所述。

(1)随即访问元素效率很高。

(2)push_back的效率也会很高。

(3)push_front的效率非常低,不建议使用。

(4)insert需要把插入位置以后的元素全部后移,效率比较低,不建议使用。

(5)erase需要把删除位置后面的元素全部前移,效率比较低,不建议使用。

(6)当内存不够时,需要重新申请内存,再把以前的元素复制过来,效率也比较低。

3.4 map

时间: 2017-05-16
Tags: 函数, pos, 数组, void, Other

后台开发:核心技术与应用实践3.3.4 Vector类的简单实现的相关文章

后台开发:核心技术与应用实践

后台开发:核心技术与应用实践 徐晓鑫 著 图书在版编目(CIP)数据 后台开发:核心技术与应用实践 / 徐晓鑫著. -北京:机械工业出版社,2016.8 ISBN 978-7-111-54339-8 I. 后- II. 徐- III. 网络-开发 IV. TP393.092 中国版本图书馆CIP数据核字(2016)第167884号 后台开发:核心技术与应用实践 出版发行:机械工业出版社(北京市西城区百万庄大街22号 邮政编码:100037) 责任编辑:李 艺 责任校对:董纪丽 印 刷: 版 次:

后台开发:核心技术与应用实践导读

后台开发:核心技术与应用实践 徐晓鑫 著 图书在版编目(CIP)数据 后台开发:核心技术与应用实践 / 徐晓鑫著. -北京:机械工业出版社,2016.8 ISBN 978-7-111-54339-8 I. 后- II. 徐- III. 网络-开发 IV. TP393.092 中国版本图书馆CIP数据核字(2016)第167884号 后台开发:核心技术与应用实践 出版发行:机械工业出版社(北京市西城区百万庄大街22号 邮政编码:100037) 责任编辑:李 艺 责任校对:董纪丽 印 刷: 版 次:

Java后台开发精选知识图谱

引言: 学习一个新的技术时,其实不在于跟着某个教程敲出了几行.几百行代码,这样你最多只能知其然而不知其所以然,进步缓慢且深度有限,最重要的是一开始就对整个学习路线有宏观.简洁的认识,确定大的学习方向,这样才能事半功倍. 我们经常会遇到这样的情况: 一开始学习一门新技术的时候,面对着很多很多陌生的名词,无从下手,一度想要放弃. 本文首先会给出关于java后台开发和前端适配的一些建议学习路线,接着简单解释一些应用到的高频技术,帮助大家理解和学习,算是一个入门篇. Java后台开发知识一览 1.后端

Android开发:优化ListView实践解析

 在看了一些vogella的文章之后,发现关于android listview性能优化这一段很有意思,于是实践了一下,经过优化,性能确实提升不少! 先看看优化前和优化后的比较: 优化前的log截图: 开发:优化ListView实践解析-"> 优化后的log截图: 并且,在不停滚动ListView的过程中,优化之前会出现ANR现象,在AVD上特别容易复现: 然后,优化后显得很流畅,附上对于的log截图: 下面附上相关代码分析: ListView中的每一个Item由一个ImageView 和一

android-Android后台开发相关书籍资料

问题描述 Android后台开发相关书籍资料 Android APP后台搭建过程,如何使用开发语言实现,请推荐相关书籍,谢谢. 解决方案 <第一行代码> <疯狂Android讲义> <Android群英传> <Android开发艺术探究> 解决方案二: 后台开发相关书籍Android各层开发推荐书籍及资料(转)Android相关开发资料汇总 解决方案三: http://www.jikexueyuan.com/course/2208.html 解决方案四: 深

mysql-app后台开发,如何做好安全性?

问题描述 app后台开发,如何做好安全性? app后台开发一枚,现在要对整个项目做一些安全性,比如拦截非法请求,sql注入什么的 后台开发技术:spring + mybatis + mysql 求一些思路.麻烦了. 解决方案 比如检查密码的sql语句一定要处理特殊字符? = ' 等等,最后还是要写file.将你所设想到的情况全写下来.后期安全还有问题再添加. 解决方案二: 最好安卓请求时要带上自己的用户信息 解决方案三: 接口的话,多加一些加密处理了,然后在登录的时候带token,再就是服务器的

linux 后台开发-后台开发需要些什么东西

问题描述 后台开发需要些什么东西 我是一名大三的学生,想做后台开发,但是又不知道该从哪方面做起.目前Linux c/c++都学的不错,数据结构也学过,SQL.socket网络通信也学过,TCP/IP协议也有一定了解,然后,下一步不知道该干嘛了,我觉得自己学的这些东西比较基础,都不知道怎么怎么能把它们应用实际.望各位大牛能指点迷津 解决方案 这看你想做哪方面的了.linux服务器开发维护,数据库开发维护,网站后台web开发(javawebphp.net等) 解决方案二: 你所学的仅仅是基础,多看看

Linux 后台开发工作中常用的开源库

后台开发,语言主要是 c 和 c++ , 这里简单罗列一下工作中用的很频繁的那些开源软件 1. OpenSSL openssl OpenSSL 是一个安全套接字层密码库,囊括主要的密码算法.常用的密钥和证书封装管理功能及SSL协议,并提供丰富的应用程序供测试或其它目的使用. 下载地址: https://www.openssl.org/source/ 2.TinyXML tinyxml 简单,高效,灵活的一套操作 XML 文件的开源库. 下载地址: http://www.grinninglizar

javascript-App后台开发用哪种语言

问题描述 App后台开发用哪种语言 我想问开发一个APP的后台,想实现的功能有实时聊天,图片,视频的上传和下载等, 用java写好,还是其他的好 解决方案 java.php.python.c++.....很多,建议使用java,轮子多,效率高,也可以用python,简单,效率也不低 解决方案二: 后台有很多选择,如果你熟悉android,那么当然选java,那是你熟悉的语言,如果你熟悉js,可以用node.js,其它的语言还有C# VB PHP Ruby Python Go ... 解决方案三: