我造的轮子——山寨版vector

昨天看C++里面的容器部分，发现vector的特性很独特：

• vector对于随机访问有很好的效率，猜想可能是顺序存储
• vector对随机插入和删除的效率不高，这种特性也是由顺序存储引起的
• vector容器的容量是自增长的，并不是一开始申请很大一块内存然后直到撑满，而是满了后容量加倍。

这种特性跟delphi的TList特别像，在delphi里面，放一个array of pointer的指针，

这个指针所指向的空间的内存是动态增长的，容量到达后就增加一个delta，它的增删改查，分别是这么实现的：

• 增加分为两种情况：

（1）在末尾增加：首先判断容量满了没有，如果没有满则直接在数组后面赋值，如果满了就要增加容量后赋值

（2）在中间插入：首先要移出空位给需要insert的元素，然后赋值，移动之前要判断容量是否充足，++size

• 删除：删除操作就是将要删除的元素后面的内存单元向前面移动一格，--size
• 查，非常简单，只要index在范围内，直接用数组的index就可以查到元素，非常高效

我实现的代码基本上是仿照delphi的TList实现的，顺便加入了模板编程，插入的元素是泛型的。

这点较delphi有较大改进。delphi只支持管理pointer类型的。我插入的时候用的都是对象的副本，因为所有需要传元素

的地方都没有用引用，对于基本类型来说，空间损耗很小，但是对于对象来说有可能会空间损耗很大。

另外这个例子也没有实现delphi里面的notify机制，delphi考虑扩展性，加入了notify，方便派生类操作。

头文件：

头文件

#ifndef CLASSES_H #define CLASSES_Hconst int MAXCAPACITY = 100000;template <class Type>class my_vector{private:    typedef Type(*PType_Array)[MAXCAPACITY];    PType_Array data_list;    int    count;    int capacity;    void grow();public:    my_vector():count(0), capacity(0){}    ~my_vector(){clear();}    void set_Capacity(int cap);    int get_capacity();    void set_count(int count);    int get_count();    int add(Type t);    void clear();    void remove_by_index(int index);    void remove(Type t);    int index_of(Type t);    void insert(int index, Type t);    Type first();    Type last();    Type operator[](int i);};#endif

源文件

#include "stdafx.h"#include "classes.h"#include <cstdlib>template<class Type> void my_vector<Type>::grow(){    int delta;    if (capacity <= 8)        delta = 4;    else if (capacity <= 64)        delta = 16;    else        delta = capacity/4;    set_Capacity(capacity + delta);}template<class Type> void my_vector<Type>::set_Capacity(int new_capacity){    if (new_capacity<count || new_capacity>MAXCAPACITY){        std::cerr<<"Capacity Invalid"<<endl;        exit(0);    }    if(count == 0){        data_list = (PType_Array)malloc(sizeof(Type)*new_capacity);        capacity = new_capacity;    }    else if (new_capacity != capacity){        data_list = (PType_Array)realloc(data_list, sizeof(Type)*new_capacity);        capacity = new_capacity;    }}template<class Type> int my_vector<Type>::get_capacity(){    return capacity;}template<class Type> void my_vector<Type>::set_count(int new_count){    if (new_count<0 || new_count > MAXCAPACITY){        std::cerr<<"Capacity Invalid"<<endl;        exit(0);    }    if (new_count > capacity)        set_Capacity(new_count);    if (new_count > count)        memset((*data_list)+count, 0, sizeof(Type)*(new_count - count));    else{        int i=0;        for(i=count-1; i>=new_count; --i)            remove_by_index(i);    }    count = new_count;}template<class Type> int my_vector<Type>::get_count(){    return count;}template<class Type> void my_vector<Type>::remove(Type t){    int index = index_of(t);    if (index >= 0)        remove_by_index(index);}template<class Type> void my_vector<Type>::remove_by_index(int index){    if (index < 0 || index >= count)    {        std::cerr<<"out of bound"<<endl;        exit(0);    }    --count;    memcpy(*data_list + index, *data_list + index+1, (count-index)*sizeof(Type));}template<class Type> int my_vector<Type>::add(Type t){    int res;    res = count;    if (res == capacity)        grow();    (*data_list)[res] = t;    ++count;    return res;}template<class Type> void my_vector<Type>::insert(int index, Type t){    if(index < 0 || index > count){        std::cerr<<"out of bound"<<std::endl;        exit(0);    }    if (count == capacity)        grow();    memcpy((*data_list) + index + 1, (*data_list) + index, count-index);    (*data_list)[index] = t;    ++count;}template<class Type> Type my_vector<Type>::first(){    if (count > 0)        return (*data_list)[0];    else    {        cerr<<"no element"<<endl;        exit(0);    }}template<class Type> Type my_vector<Type>::last(){    if (count > 0)        return ((*data_list)[count - 1]);    else    {        cerr<<"no element"<<endl;        exit(0);    }}template<class Type> Type my_vector<Type>::operator[](int i){    if(i>=count || i<0){        cerr<<"No element"<<endl;        exit(0);    }    return (*data_list)[i];}template<class Type> void my_vector<Type>::clear(){    set_count(0);    set_Capacity(0);}template<class Type> int my_vector<Type>::index_of(Type t){    int i(-1), res(-1);    for (i = 0; i<count; ++i)    {        if((*data_list)[i] == t)        {            res = i;            break;        }    }    return res;}

主函数

#include "stdafx.h"#include "classes.cpp"#include "classes.h"#include <iostream>#include <string>using namespace std;void display_vector(my_vector<char*> vec){    int i;    for(i=0;i<vec.get_count();++i)        cout<<vec[i]<<" ";    cout<<endl;}int _tmain(int argc, _TCHAR* argv[]){    my_vector<char*> vec;    /////test add    for(int i = 0; i< 50; ++i){        char *str = new char[10];        sprintf(str, "%d", i);        vec.add(str);    }    ////test remove;    cout<<vec.get_count()<<endl;    vec.remove_by_index(5);    cout<<vec.get_count()<<endl;    ////test remove    cout<<vec.get_count()<<endl;    vec.remove(0);    cout<<vec.get_count()<<endl;    ////test insert;    vec.insert(12, "asss");    cout<<vec.get_count()<<endl;    vec.first();    vec.last();    display_vector(vec);}

另外关于泛型编程，要特别注意工程的链接方式，因为没有确定类型的时候，编译器不知道如何编译泛型函数，只有当确定类型后，

才会去找源文件。可以说泛型的编译是一种懒编译。

所以在用的时候要确保能链接到header对应的源文件。c++ primer里面用的是在header文件里面#include "xxxx.cpp"的方式

我用的这种方式比较挫一点，直接在主函数的cpp文件里 #include "xxx.cpp"的方式。
原文链接: https://www.cnblogs.com/lovelyxia/archive/2010/12/23/1915290.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍