动态数组C++实现

vector是用动态数组实现的，所谓动态是指当存储在数组中的元素个数接近数组的容量时，vector机制会另外malloc一片空间，此空间的大小是原空间的两倍，然后再将原空间的数据复制过来，最后将原空间释放，这就是vector全部的机制。具体实现是结构体加上一些维护这些结构体的接口。

以下实现方式是STL中的vector实现方式。

serverExe : try_Vector_main.o try_Vector.o
	g++ -o Exe try_Vector_main.o try_Vector.o
main.o : try_Vector_main.cpp try_Vector.h
	g++ -g -c try_Vector_main.cpp
solution.o : try_Vector.h try_Vector.cpp
	g++ -g -c try_Vector.cpp
clean :
	rm try_Vector_main.o try_Vector.o Exe

#include 
#include 
#include 
using namespace std;



//vector与c的数组的区别仅在空间不用自动分配,其他相同
//标准库小写vector
class try_Vector
{
    public:
    try_Vector();
    ~try_Vector();
    //增
    void insert(int pos, int value);
    //尾插
    void push_back(int value);
    //删
    void pop();
    //根据位置删除
    void delete_by_pos(int pos);
    //根据值删除
    void delete_by_value(int value);
    //根据位置查找 值
    int find_by_pos(int pos);
    //查 根据值查找 位置
    int find_by_value(int value);
    //清空
    void clear();
    //获得数组容量
    int capacity();
    //显示当前元素个数
    int size();
    //扩容
    void expand_capacity();
    //打印
    void print_int();
    

    typedef struct Data
    {
        int* int_prt = NULL;
        int size = 66;
        int capacity =88; //try初始化 如果定义此结构体指针的化尽量不要赋初值,可能会引起段错误
    }DATA;
    DATA* data_bag = NULL;

};

#include "try_Vector.h"


try_Vector::try_Vector()
  {

      //申请空间
     data_bag = (DATA*)malloc(sizeof(DATA));
     data_bag->capacity = 4;
     data_bag->int_prt = (int*)malloc(sizeof(int) *                  data_bag->capacity); //sizeof是关键字,可以用类型作为参数 返回值是字节
        data_bag->size = 0;
         //try初始化
    }

    try_Vector::~try_Vector() //~是名字的一部分
    {
        // free(data_bag->int_prt);
        // data_bag->int_prt = NULL;
        // data_bag->size = 0;
        // data_bag->capacity = 0;
        // free(data_bag);
    }
//增
void try_Vector::insert(int pos, int value)
{
    //判断容量
    if(this->data_bag->size == this->data_bag->capacity)
    {
        expand_capacity();
    }
    int* int_prt_next = (int*)malloc(sizeof(int) * this->data_bag->capacity);
    for(int i = 0, j = 0; i < this->data_bag->size; i++, j++)
    {
        if(i == pos)
        {
            int_prt_next[i] = value;
            i++;
        }
        int_prt_next[i] = this->data_bag->int_prt[j];
    }
    data_bag->int_prt = int_prt_next;
    this->data_bag->size++;
}

//尾插
void try_Vector::push_back(int value)
{
    //扩容
    // cout
    if(this->data_bag->size == this->data_bag->capacity)
    {
        expand_capacity();
    }
    //插入
    data_bag->int_prt[data_bag->size] = value;
    data_bag->size++; 
}

//删
void try_Vector::pop()
{
    this->data_bag->size--;
}

//根据位置删除
void try_Vector::delete_by_pos(int pos) //这个位置为[pos]
{
    if(pos + 1 > this->data_bag->size)
    {
        cout << "___访问越界___" << endl;
        return ;
    }
    for(int i = pos; i + 1 < this->data_bag->size; i++)
    {
        this->data_bag->int_prt[i] = this->data_bag->int_prt[i + 1];
    }
    this->data_bag->size--;
}

//根据值删除
void try_Vector::delete_by_value(int value)
{
    for(int i = 0; i < this->data_bag->size; i++)
    {
        if(this->data_bag->int_prt[i] == value)
        {
            delete_by_pos(i);
            break;
        }
    }
}

//根据位置查找
int try_Vector::find_by_pos(int pos)
{
    if(pos + 1 > this->data_bag->size)
    {
        cout << "__访问越界__" << endl;
        return 0;
    }
    return this->data_bag->int_prt[pos];
}

//根据值查找 位置
int try_Vector::find_by_value(int value)
{
    for(int i = 0; i < this->data_bag->size; i++)
    {
        if(this->data_bag->int_prt[i] == value)
        {
            return i;
        }
    }
    cout << "__vector中不含有此值__" << endl;
    return 0;
}

//清空
void try_Vector::clear()
{
    this->data_bag->size = 0;
}

//扩容
void try_Vector::expand_capacity()
{
    int *int_prt_next = (int*)malloc(sizeof(int) * this->data_bag->capacity * 2);
    this->data_bag->capacity *= 2;
    for (int i = 0; i < this->data_bag->size; i++)
    {
        int_prt_next[i] = this->data_bag->int_prt[i];
    }
    void* temp_prt = this->data_bag->int_prt;
    this->data_bag->int_prt = int_prt_next;
    free (temp_prt); //malloc free是函数 new delete是关键字
}

//获得数组容量
int try_Vector::capacity()
{
    return this->data_bag->capacity;
}

//显示当前元素个数
int try_Vector::size()
{
    return this->data_bag->size;
}

//打印
void try_Vector::print_int()
{
    if(this->data_bag->size == 0)
    {
        cout << "___vector无元素___" << endl;
    }
    for(int i = 0; i < this->data_bag->size; i++)
    {
        cout << i << " : " << this->data_bag->int_prt[i] << endl;
    }
    
}

#include 
#include 
#include "try_Vector.h"
using namespace std;


int main(void)
{
    try_Vector try_vector;
    cout << "capacity(5) : " << try_vector.capacity() << endl;
    try_vector.push_back(0);
    try_vector.push_back(1);
    try_vector.push_back(2);
    cout << "size(5) : " << try_vector.size() << endl;
    try_vector.push_back(3);
    try_vector.push_back(4);
    try_vector.push_back(5);
    try_vector.print_int();
    try_vector.pop();
    cout << "size(5) : " << try_vector.size() << endl;
    cout << "find_by_pos(1) : " << try_vector.find_by_pos(1) << endl;
    cout << "find_by_value(2) : " << try_vector.find_by_pos(2) << endl;
    cout << "capacity(5) : " << try_vector.capacity() << endl;
    try_vector.delete_by_pos(4);
    try_vector.delete_by_value(3);
    try_vector.print_int();
    try_vector.clear();


    cout << "________________" << endl;
    // try_vector.insert(5, 8);
    // try_vector.print_int();
    return 0;
}