AI 助理
备案控制台
开发者社区 计算巢 文章 正文

模拟实现c++中的vector模版

2025-02-14 56
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 模拟实现c++中的vector模版

一·vector简述：
它可以认为是一个动态容器，即一种顺序表。通过给这个模版实例化可以得到一种任意类型的顺序表，故可以放进去数据，则使用前应该先实例化类型。

二·vector的一些接口函数：
1·初始化：
无参构造：
vector v1;

有参：
vector v2(10,1);
v2拷贝构造给v3
vectorv3(v2);
迭代器初始化：
vector v4(++v2.begin(),v2.end()--);//把v2部分范围给v4初始化
2.vector增长：
如：size；capacity（vs是1.5倍扩，g++为2倍）；empty；resize；reserve（不缩容）；等函数接口用法类似于上篇string用法。

3·vector增删查改：
如：push_back;pop_back;find(这时algorithm算法库内的函数，也是使用迭代器区间：找到了返回指向那个位置的迭代器，否则返回右区间)；insert;erase;swap;operator[],v.front;v.back等用法和string相差不大，可以说是string的下标换成vector的迭代器了。

注：这里对于vector的重载函数没有cin和cout。

三·vector模拟实现部分主要函数：
首先要知道这个模拟过程如图一样：

由于是类模版，一般定义和声明不能分文件，故可以都写在.h文件：

首先先不写构造，但是编译器默认生成的构造来，可能会给成员变量野指针，故给它一个缺省值为nullptr； 提前也要写好析构。

这里的iterator是迭代器类型可以粗略认为是指针，假设模版参数是T，故typedef一下：

typedef T* iterator;

typedef const T* const_iterator;

iterator begin() {
return _start;
}

iterator end() {
return _finish;
}

const_iterator cbegin()const {
return _start;
}

const_iterator cend() const {
return _finish;
}

分别对可以修改和不允许修改的对象都有了对应的迭代器。

1.size,capacity,empty,clear接口：

size_t size() const
{
return _finish - _start;
}

size_t capacity() const
{
return _end_of_storage - _start;
}

bool empty()
{
return _start == _finish;
}

void clear()
{
_finish = _start;
}

2.reverse的实现：

注：①这里用了一个oldsize记录为扩容之前的size；因为假设进行第一次扩容 ，_start更新后;_finish+的size（）（_finish-_start）就会不是原来的size了；故需要保存一下这个相对位置。

②这里一开始用的是string.h里的memcpy ，利用的是浅拷贝，如果让里面的类型是自定义（有资源申请已经释放的）发现浅拷贝这样会出问题，故后面改正。

3.resize的实现：
void resize(size_t n, const T& value = T()) {
if (n < size()) {
size_t tmp = size();
while (tmp > n) {
_finish--;
tmp--;
}

 }
 else {
     reserve(n);
     for (size_t i = size(); i < n; i++)
     {
         push_back(value);
     }
 }

}

如果size小于给的n，就扩大size（capacity()也要跟上）；后面用value填充，如果大于就相当于截断。对于缺省参数：如果未给值就会掉此类型默认构造（T（）为匿名对象）,对于内置类型如：char，int等这就是'\0',0。如果是自定义类型：就是它的默认构造函数构造出的对象。

4.访问运算符重载operator[]的实现：
T& operator {
assert(pos < size());
return _start[pos];
}

const T& operatorconst {
assert(pos < size());
return _start[pos];
}
分别对应的是const类型对象和普通对象的调用。

5.push_back与pop_back的实现：
void push_back(const T& x) {
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}

 *_finish = x;
 _finish++;

}

void pop_back() {
assert(!empty());
_finish--;

 }

6.erase的实现：
iterator erase(iterator pos) {
assert(pos < _finish&&pos>=_start);
iterator end = pos + 1;
while (end < _finish) {
(end - 1) = end;
end++;
}
_finish--;
return pos;
}
7.insert的实现：
这里以insert的实现为例子，把它进行类内声明，类外定义；

//类内：
iterator insert(iterator pos, const T& x);

//类外：
template
typename vec::vector::iterator vec::vector::insert(typename vec::vector::iterator pos, const T& x)
//类模版未初始化不能进类内确定它是静态成员变量还是类型，故若是类型要typename一下

{
size_t len = 0;
if (_finish == _end_of_storage)
{
len = pos - _start;//迭代器失效：由于空间变了，pos无法找到指向原来空间，而数据早已被移到了新空间，原来的也被释放
reserve(capacity() == 0 ? 4 : capacity() 2);
}
if (len != 0) {
pos = _start + len;
}
iterator end = _finish;
while (end >= pos) { end = (end - 1);
end--;
} pos = x;
_finish++;
return pos;
}

这里和erase一样涉及迭代器失效问题于后面总结进行讲解。

8·swap的实现：
swap也为后面对于拷贝构造和赋值重载的现代版本使用奠定基础。

void swap(vector& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
9.拷贝构造的实现：
//拷贝构造：：
vector(const vector& v) {
reserve(v.capacity);
for(auto a:v ){
push_back(a);
}

    }

可能前面写的函数程序都运行正常，当写完这个拷贝构造发现编译器会报错：

原因：其实拷贝构造函数也是一种构造函数，而当我们写了拷贝构造，编译器自己就不会生成它的默认构造了（普通构造也没写）；因此他会走这个拷贝构造，但发现参数不匹配，就会报错，因此这时要再把默认构造或者传参的构造写上就可以了。

10.赋值重载的实现：
//s1=s3
vector& operator= (vector v) {
swap(v);//如果不引用参数，则会进行拷贝再swap，这时候s3给s1赋值后它自身不会变。
return *this;

     }

11.构造和析构函数的实现：
//默认构造1：
/*vector() {

}*//如果这个默认构造{}内可以没有，只用它的初始化列表，但也有缺省值了就可以这么写。
// 默认构造2：（c++11）
vector() = default;

 vector(int n, const T& value = T()) {
     reserve(n);
     for (size_t i = 0; i < n; i++)
     {
         push_back(value);
     }
 }

//迭代器区间初始化：
//模版函数，可以用别的类型的函数，故完成一个容器数据到另一个容器转换
template
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);//一个容器数据放另一个，数据类型要匹配，否则进不去。
first++;
}
}

//析构：
~vector() {
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}

这里用了类模版内套着模版函数：方便了不同类型 的迭代器区间去放入这个容器，如list：

12.vector以及容器通用打印的实现：
//vector专属的打印：
template
void Print(const vec::vector& t) {
//未实例化的模版无法去访问内部，区分不了是静态成员变量还是类型
//typename vec::vector ::const_iterator it = t.cbegin();
auto it = t.cbegin();
while (it != t.cend())
{
std::cout << it << " ";
++it;
}
std::cout << std::endl;
}
template
void Print_container(const C &cr ) {
auto it = cr.cbegin();
while (it != cr.cend())
{
std::cout << it << " ";
++it;
}
std::cout << std::endl;

}

四·vector模拟实现过程中遇到的问题总结：
1.迭代器失效问题简述：
失效分为两种，第一种是迭代器指向无效内存了即空间变化了，第二种是所引用的对象发生变化了，都是迭代器失效。这时候建议不要在对它这个位置迭代器进行访问了；否则程序崩溃。

这里举erase和insert的例子：

这里如果对insert插入如果没有空间开辟也可以认为迭代器失效，但是有的时候可以继续访问，但是一般建议用返回值重新赋值再使用，而开辟空间了则一定失效，必然要重新赋值。

erase的迭代器如果此位置对象被删除，也要重新赋值再用此迭代器。

例子：

这里就涉及到了erase造成的迭代器失效：前面正常打印当到0；之后由于继续访问就崩掉了。

这时候要想正常需要利用它的返回值来重新赋值进行后面的访问：

2.vector类内类型省略问题：
如果在类内那么对于类型vector可以在类内变成vector等价代替，但是如果在类外就不可能了。

3.迭代器运算符问题：

这里如果first和last如果是迭代器的话那么为什么不用大于小于呢，理论上针对vector是可以的，但是比如它空间不是连续的list链表就是反例，这时候大于小于就没概念了。前提还得是空间要连续。

五·模拟vector代码汇总：

pragma once

pragma once

include

include

include

include

namespace vec

{ 

template<class T>

class vector

{

public:

    // Vector的迭代器是一个原生指针

    typedef T* iterator;

    typedef const T* const_iterator;

    iterator begin() {
        return _start;
    }

    iterator end() {
        return _finish;
    }

    const_iterator cbegin()const {
        return _start;
    }

    const_iterator cend() const {
        return _finish;
    }




    //默认构造1：

/*vector() { 

  }*/
  //  默认构造2：（c++11）
    vector() = default;

    vector(int n, const T& value = T()) {
        reserve(n);
        for (size_t i = 0; i < n; i++)
        {
            push_back(value);
        }
    }
    //模版函数，可以用别的类型的函数，故完成一个容器数据到另一个容器转换
     template<class InputIterator>
     vector(InputIterator first, InputIterator last) {
         while (first != last) {
             push_back(*first);//一个容器数据放另一个，数据类型要匹配，否则进不去。
             first++;
         }
     }




     //拷贝构造：：
    vector(const vector<T>& v) {
        reserve(v.capacity);
        for(auto a:v ){
            push_back(a);
      }

           }
    //s1=s3
    vector<T>& operator= (vector<T> v) {
        swap(v);//如果不引用参数，则会进行拷贝再swap，这时候s3给s1赋值后它自身不会变。
        return *this;

           }

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



        //    // capacity

    size_t size() const
    {
        return _finish - _start;
    }

    size_t capacity() const
    {
        return _end_of_storage - _start;
    }

    bool empty()
    {
        return _start == _finish;
    }

    void clear()
    {
        _finish = _start;
    }
    void reserve(size_t n) {
        if (n > capacity()) {
            size_t oldsize = size();//开辟空间前后导致指针指向空间不同
            T * tmp = new T [n];
           // memcpy(tmp, _start, sizeof(T) * size());一个个字节的浅拷贝
            for (int i = 0; i < size(); i++) {
                tmp[i] = _start[i];//利用string库里的赋值运算符重载
            }//自定义类型使用深拷贝
            delete[]_start;
            _start = tmp;
            _finish = tmp + oldsize;//防止_start已经更新，而这里要的是以前的相对位置，故保存一下
            _end_of_storage = _start + n;
        }
    }

    void resize(size_t n, const T& value = T()) {
        if (n < size()) {
            size_t tmp = size();
            while (tmp > n) {
                _finish--;
                tmp--;
            }

        }
        else {
            reserve(n);
            for (size_t i = size(); i < n; i++)
            {
                push_back(value);
            }
        }
    }



    //    ///access///

    T& operator[](size_t pos) {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos)const {
        assert(pos < size());
        return _start[pos];
    }



    //    ///modify/

    void push_back(const T& x) {
        if (_finish == _end_of_storage)
        {
            reserve(capacity() == 0 ? 4 : capacity() * 2);
        }

        *_finish = x;
        _finish++;
      }

    void pop_back() {
        assert(!empty());
        _finish--;

        }

    void swap(vector<T>& v) {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
          }

    iterator insert(iterator pos, const T& x);


    iterator erase(iterator pos) {
        assert(pos < _finish&&pos>=_start);
        iterator end = pos + 1;
        while (end < _finish) {
            *(end - 1) = *end;
            end++;
        }
        _finish--;
        return pos;
        }

private:

    iterator _start = nullptr; // 指向数据块的开始

    iterator _finish = nullptr; // 指向有效数据的尾

    iterator _end_of_storage = nullptr; // 指向存储容量的尾

};

}

template
typename vec::vector::iterator vec::vector::insert(typename vec::vector::iterator pos, const T& x)
//类模版未初始化不能进类内确定它是静态成员变量还是类型，故若是类型要typename一下

{
size_t len = 0;
if (_finish == _end_of_storage)
{
len = pos - _start;//迭代器失效：由于空间变了，pos无法找到
reserve(capacity() == 0 ? 4 : capacity() 2);
}
if (len != 0) {
pos = _start + len;
}
iterator end = _finish;
while (end >= pos) { end = (end - 1);
end--;
} pos = x;
_finish++;
return pos;
}

//vector专属的打印：
template
void Print(const vec::vector& t) {
//未实例化的模版无法去访问内部，区分不了是静态成员变量还是类型
//typename vec::vector ::const_iterator it = t.cbegin();
auto it = t.cbegin();
while (it != t.cend())
{
std::cout << it << " ";
++it;
}
std::cout << std::endl;
}
template
void Print_container(const C &cr ) {
auto it = cr.cbegin();
while (it != cr.cend())
{
std::cout << it << " ";
++it;
}
std::cout << std::endl;

}

文章标签：
C++
容器
编译器
算法
关键词：
C++ vector
C++模版
羑悻的小杀马特
目录
相关文章
羑悻的小杀马特
|
1月前
|
算法 C++ 容器
模拟实现c++中的list模版
模拟实现c++中的list模版
羑悻的小杀马特
47 23
ephemerals__
|
4月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
218 4
oioihoii
|
3月前
|
存储 对象存储 C++
C++ 中 std::array＜int, array_size＞ 与 std::vector＜int＞ 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`，从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求，而 `std::vector` 则提供了动态调整大小的灵活性，适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
oioihoii
129 0
ephemerals__
|
3月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
109 0
白子寰
|
5月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
55 1
半截诗
|
5月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化2
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
104 6
半截诗
|
5月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化1
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
143 7
努力学习的小廉
|
5月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
努力学习的小廉
61 1
禁默
|
5月前
|
Unix 编译器 Linux
C++之模版进阶篇（下）
C++之模版进阶篇（下）
禁默
57 0
禁默
|
5月前
|
编译器 C++
C++之模版进阶篇（上）
C++之模版进阶篇（上）
禁默
34 0