【C++】vector容器初步模拟

linbojue
• 阅读 270

今天我我来进行vector的模拟实现,先简单的实现一下初步功能,使其对内置类型可以适配。(大部分与string很类似)
1 认识vector 开始了解 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。 vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。 使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习

底层实现 我们来了解一下vector的底层实现是如何做到,首先就要了解其类成员是如何定义的,这样我们才能更好的复刻vector(以下是1996年的STL版本,还比较简单):

protected: typedef simple_alloc<value_type, Alloc> data_allocator; iterator start; iterator finish; iterator end_of_storage //容量结束; 复制 可以看到受保护的内部成员变量是由三个迭代器构成的。 迭代器的底层是:

typedef T value_type; typedef value_type* iterator; 复制 也就是说底层是指针,T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分):

vector() : start(0), finish(0), end_of_storage(0) {} vector(size_type n, const T& value) { fill_initialize(n, value); } vector(int n, const T& value) { fill_initialize(n, value); } vector(long n, const T& value) { fill_initialize(n, value); } 复制 这个fill_initialize又是什么呢???是初始化函数,(在工程文件中,经常使用一层又一层的嵌套,由于我还没有丰富的工程经验,我看起来还是很费劲,晕乎乎的)。我们看一部分即可,现在我们开始手搓vector,针对内置类型进行操作。

2 开始实现 我们开始逐步进行实现。

成员变量 根据我们刚才所查看的源码,我们要使用三个迭代器,要使用迭代器,我们可以使用指针进行模拟。

//使用模版 兼容各种类型 template class vector { public: //重命名 指针即可模拟迭代器 常量与非常量都要提供哦 typedef T* iterator; typedef const T* const_iterator; private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end = nullptr; }; 复制 写出三个迭代器(指针)后,我们对构造函数应该也有了大致思路:需要初始化三个迭代器,所以我们给与初始值nullptr。让后进行开辟空间。

构造函数 析构函数 这里的构造函数我设置三个接口,一个是空构造,一个是开辟 N 个空间并初始化为val,一个是拷贝构造:

//空构造 vector() {} //开辟 N 个空间并初始化为val vector(size_t n,T val = T()) { iterator tmp = new T[n]; _start = tmp; for (iterator it = begin(); it < _start + n ;it++) { *it= val; } _finish = _start + n; _end = tmp + n ;

} /拷贝构造 vector(vector& v) { //依次尾插即可完成操作 for (auto s : v) { push_back(s); } } 复制 析构函数就是简单的释放空间即可:

~vector()
{
    delete[] _start;
    _start = _finish = _end = nullptr;
}

复制 我们完成了构造函数和析构函数,为了能够进行测试,我们现在来实现尾插操作:

尾插 尾插操作之前,根据我们实现string的经验来说,我们需要做一些准备工作,实现一些常用接口(size(),capacity(),reserve(),resize()): 注意:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

    //注意const 保证不会进行权限的放大
    size_t size() const{
        return _finish - _start;
    }
    size_t capacity() const{
        return _end - _start;
    }
    bool empty(){
        return size() == 0;
    }
    //扩容
    void reserve(size_t newcapacity) {
        //记录位置
        size_t n = _finish - _start;
        T* tmp = new T[newcapacity];
        //拷贝
        memcpy(tmp, _start, size() * sizeof(T));
        _start = tmp;
        _finish = _start + n;
        _end = _start + newcapacity;
    }
    //改变大小
    void resize(size_t n, T val = T()) {
        //x需要扩容
        if ( n > size())
        {
            reserve(n);
             ;
            while (_finish != _end) {
                *_finish = val;
                _finish++;
            }

        }
        //不需扩容
        else 
        {
            _finish = _start + n;
        }
    }

复制 实现了这些接口,就可以顺畅的进行尾插的书写,通过size()和capacity()可以判断是否需要扩容,reserve可以进行扩容。然后再_finish位置插入新的数据,再移动_finish即可。

    //尾插
    void push_back(T val) 
    {
        if (size() == capacity()) {
            //扩容
            reserve(capacity() == 0 ? 4 : 2 * capacity());
        }
        *_finish = val;
        _finish++;
    }

复制 接下来我们在完善一下迭代器。

迭代器 迭代器的实现很简单,对指针进行重命名即可(真正的迭代器没有这么简单)

typedef T* iterator; typedef const T* const_iterator;

//迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const{ return _start; } const_iterator end() const{ return _finish; } 复制 完成了begin() 和end()函数,就可以使用基于范围的for循环了。 我们进行一个简单的测试,来看看我们写的构造,尾插是否正常。

template void print_vector(const vector v) { for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } //构造,尾插测试 void vector_test1() { cout << "---------构造 ,尾插测试---------\n"; vector v1; vector v2(4);

v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);

print_vector(v2);

v1.push_back(5);
v1.push_back(6);
print_vector(v1);
cout << v1.size() << endl;
cout << v1.capacity() << endl;

vector<int> v3(v1);
print_vector(v3);

} 复制 看一下效果:

没有问题!!!

插入 删除 寻找操作 这个也很简单,对数据进行挪动就可以完成:

//任意位置插入 void insert(size_t pos = 0,T val = T()) { //保证在数据范围之内 assert(pos >= 0); assert(pos <= size()); //检查 if (size() == capacity()) { //扩容 reserve(capacity() == 0 ? 4 : 2 * capacity()); }

iterator it = end();
//依次后移 然后插入
while (it >= begin() + pos) {
    *(it + 1) = *it;
    it--;
}
it++;
*it = val;
_finish++;

} void erease(size_t pos) { //保证在数据范围之内 assert(pos >= 0); assert(pos <= size());

iterator it = begin() + pos;
//依次前移
while (it < end()) {
    *it = *(it + 1);
    it++;
}
_finish--;

} //尾删 void pop_back() { erease(size());

} size_t find(T val = T()) { //依次寻找 for (iterator it = _start; it < _finish;it++) { if (*it == val) return it - _start; } return -1; } 复制 操作符重载 vector容器最重要的操作符应该就是[ ]操作了吧,此外重载一个 = :

//提供常量与非常量 T& operator[](size_t n) { assert(n >= 0); assert(n < size()); return *(_start + n); } const T& operator[](size_t n) const { assert(n >= 0); assert(n < size()); return *(_start + n); } //类似拷贝 vector& operator=(vector& v){

T* tmp = new T[v.capacity()];
memcpy(tmp, v._start, v.size() * sizeof(T));
size_t pos = v.size();
size_t n = v.capacity();

_start = tmp;
_finish = _start + pos;
_end = _start + capacity();

return *this;

} 复制 这样就完成了: 我们进行一个测试来看看是否可行:

void vector_test2() { cout << "---------resize find insert erase测试---------\n";

vector<int> v1;

v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
print_vector(v1);
cout << v1.find(2) << endl;

v1.resize(10, 0);
print_vector(v1);
v1.insert(0, 0);
print_vector(v1);
v1.erease(5);
print_vector(v1);

} 复制 来看效果:

成功!!!

swap函数 接下来在提供一个swap 函数以供交换,注意一定是深拷贝!!!

    void swap(vector& v) {

        T* tmp = new T[v.capacity()];
        memcpy(tmp, v._start, v.size() * sizeof(T));
        size_t pos = v.size();
        size_t n = v.capacity();

        v._start = _start;
        v._finish = _finish;
        v._end = _end;

        _start = tmp;
        _finish = _start + pos;
        _end = _start + capacity();


    }

复制 来进行一个简单测试:

//交换测试 void vector_test3() { cout << "---------swap 测试---------\n"; vector v1;

v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
print_vector(v1);
vector<int> v2(4);

v2.push_back(1);
v2.push_back(3);
v2.push_back(1);
v2.push_back(4);
print_vector(v2);
v2.swap(v1);

print_vector(v1);
print_vector(v2);

}

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
java 面试
1、ArrayList、Vector、LinkedList之间的区别?ArrayList:底层数组,查询快,增删慢,线程不安全,效率高Vector:底层数组,查询快(由于线程安全,其实查询也不快),增删慢,线程安全,效率低LinkedList:底层双重链表,查询慢,增删快,线程不安全,效率高。3、列举Co
Wesley13 Wesley13
3年前
Unity3d Transform.forward和Vector3.forward的区别!
在Unity中有两个forward,一个是Transform.forward一个是Vector3.forward。对于Vector3来说,它只是缩写。没有其它任何含义。Vector3.forward,(0,0,1)的缩写。//在transform.Translate()中使用时,如果不表明坐标系,则为物体的局部坐标,即物体自身的正前方。
Stella981 Stella981
3年前
Eigen库
MatrixXd表示任意size的矩阵,元素类型为double;VectorXd表示任意size的向量,元素类型为double.//创建31的向量v,并赋值为1,2,3VectorXdv(3);v<<1,2,3;使用固定尺寸的Matrix,Vector相比于可变尺寸的Matrix,Vector,例如Matri
Stella981 Stella981
3年前
C++中vector的使用
在c中,vector是一个十分有用的容器。作用:它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据。vector在C标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类(https://www.oschina.net/action/GoToLink?url
Stella981 Stella981
3年前
C++STL容器deque
deque简介deque属于序列式容器,和vector十分相似,采用dynamicarray来管理元素,提供随机访问,但是deque的dynamicarray头尾两端都开放,可以在头尾两端快速安插和删除。!(https://img2018.cnblogs.com/blog/1520224/201902/15202242019
Wesley13 Wesley13
3年前
C++:模板类
22.模板类22.1模板类模板是泛型编程的基础,那什么是泛型编程呢?泛型编程是一种独立于任何特定数据类型编写代码的方式。C标准模板库中的数据容器、迭代器和算法,都是泛型编程的例子,它们都使用了模板的概念。比如动态数组vector是可以存放任何类型数据的容器,我们可以定义许多不同类型的vector,比如vector<int或vect
Stella981 Stella981
3年前
C++ STL Vector
前言vector,是C中的向量,也可以把他理解成为一个可变数组。熟练的应用好vector,可以提高算法设计的速度。在使用vector前,请先添加头文件。include<vectorvector的初始化vector<inta(10);//创建一个含是个元素的向量,元素值未知
Wesley13 Wesley13
3年前
Vector, ArrayList, LinkedList 区别与用法
ArrayList和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,
Stella981 Stella981
3年前
26 函数形参值回传问题——C++解决多个return的一般方法
0引言在使用数组和vector作为函数的参数进行参数传递并希望得到值的回传时,由于不知道怎么写数组函数形参的引用形式,一直采用vector的引用形式。但是,刚刚测试了一下,发现数组作为参数本身就是指针,根本不需要采用引用形式把值回传啊,把测试结果写下来。1 关于数组作为函数参数的值传递问题——数组和容器的对比  数组直接作为
Stella981 Stella981
3年前
C++vector,stack,queue,deque, list基本使用
vector初始化  (1)vector<inta(10);//定义了10个整型元素的向量(尖括号中为元素类型名,它可以是任何合法的数据类型),但没有给出初值,其值是不确定的。  (2)vector<inta(10,1);//定义了10个整型元素的向量,且给出每个元素的初值为1  (3)vector