AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【c++丨STL】vector模拟实现

2024-12-13 50
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。

前言

       之前我们学习了vector的常用接口及其使用方法：


https://developer.aliyun.com/article/1642469?spm=a2c6h.24874632.expert-profile.18.ad5d29be0lIo0j


本篇文章，我们将深入探讨vector的底层实现原理，并尝试模拟实现其结构以及一些常用接口。


一、vector底层刨析

       之前已经提到，vector的底层是动态顺序表，我们使用c语言实现顺序表的结构时赋予了它三个成员变量：

typedef int SLDataType;
 
//动态顺序表
typedef struct SeqList
{
    SLDataType* arr;//定义起始指针，后续动态开辟内存空间
    int size;//有效数据的个数
    int capacity;//数组的空间大小
}SL;

可以看到，我们定义了一个起始指针指向分配的内存，然后用size和capacity两个变量分别记录元素个数和空间容量。接下来，我们再看看SGI版本的STL源码：



为了提高程序的兼容性和灵活性，源码并没有使用size和capacity等属性，而是使用了三个迭代器（指针）来维护数组。这三个迭代器分别指向数组的不同位置：


start：指向首元素

finish：指向末尾元素的“后一位”

end_of_storage：指向可用空间的末尾


图示：



那么，接下来我们在模拟实现vector时，将仿照SGI版本的做法，通过定义相应的成员变量（即三个迭代器）来构建其内部结构。


       另外，由于vector本质上是一个类模板，允许我们存储任意类型的数据元素，因此在接下来模拟实现vector的过程中，我们也将采用类模板来进行定义。由于类模板成员函数的定义和声明分离到两个文件会造成链接错误，我们选择在头文件中同时完成这些成员函数的声明与定义。


二、模拟实现

1. 属性、迭代器以及函数声明

       首先是属性、迭代器的声明以及我们需要实现的接口：

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
 
template<class T>
class Vector
{
public:
    //vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;
 
    //迭代器接口
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
 
    //无参构造
    Vector();
    //初始化器构造
    Vector(initializer_list<T> l);
    //迭代器区间构造
    template<class InputIterator>
    Vector(InputIterator first, InputIterator last);
    //n个val值构造
    Vector(size_t n, const T& val = T());
    //拷贝构造
    Vector(const Vector<T>& v);
    //赋值重载
    Vector<T>& operator=(Vector<T> v);
    //析构
    ~Vector();
 
    //下标引用
    T& operator[](size_t i);
    const T& operator[](size_t i) const;
 
    //容量接口
    size_t size() const;
    size_t capacity() const;
 
    //判空
    bool empty() const;
 
    //交换
    void swap(Vector<T>& tmp);
 
    //调整大小
    void resize(size_t n, const T& val = T());
 
    //增容
    void reserve(size_t n);
 
    //插入和删除
    void push_back(const T& x);
    void pop_back();
    iterator insert(iterator pos, const T& x);
    iterator erase(iterator pos);
private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
};


     由于vector和string的数据元素都是采用顺序存储的方式，它们在功能实现上存在相似之处。因此，建议先阅读string模拟实现之后，再来阅读本文，否则其中的一些实现过程可能会较难理解。


2. 功能实现

       接下来，我们将正式开始实现上述接口的功能。


交换两个容器的内容

       与之前实现string时相同，直接交换它们的成员变量就可以完成数据的交换，无需重新开辟空间。



代码实现：

//交换
void swap(Vector<T>& tmp)
{
    std::swap(_start, tmp._start);
    std::swap(_finish, tmp._finish);
    std::swap(_end_of_storage, tmp._end_of_storage);
}

构造函数

       这里我们实现了四个构造函数的重载：分别是：无参构造、初始化器构造、迭代器区间构造和n个val值构造：

//无参构造
Vector()
{}
//初始化器构造
Vector(initializer_list<T> l)
{
    reserve(l.size());
    for (auto& e : l)
    {
        push_back(e);
    }
}
//迭代器区间构造
template<class InputIterator>
Vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        first++;
    }
}
//n个val值构造
Vector(size_t n, const T& val = T())
{
    reverse(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}

不难发现，由于我们在成员变量声明时已经赋初值，所以无参构造中什么都不用做。这样无参构造也可以写成如下形式：

Vector() = default;//强制生成无参构造

我们显示写了构造函数后，编译器就不会默认生成无参构造函数。我们用这条语句就可以强制让编译器生成一个无参的构造函数。


       其余的构造函数都是通过遍历来访问每个元素，并将它们依次尾插到数组中的。push_back、reverse等函数我们之后实现。这里特别注意一下n个val值构造函数，如果我们不传val参数，则会调用T类型的默认构造函数，生成一个匿名对象并赋值给val。


拷贝构造

       与初始化器构造的原理相似，我们遍历被拷贝数组的每个元素，并将它们逐一尾插到当前数组中。

//拷贝构造
Vector(const Vector<T>& v)
{
    reverse(v.capacity());
    for (auto& e : v)
    {
        push_back(e);
    }
}

赋值重载

       这里我们使用新式写法（string使用过），构造新对象然后交换，完成赋值操作。

//赋值重载
Vector<T>& operator=(Vector<T> v)
{
    swap(v);
    return *this;
}

析构函数

//析构
~Vector()
{
    if (_start)//避免多次释放
    {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }
}

下标引用operator[ ]

       下标引用重载可以让我们像访问数组元素一样访问容器内容。

//下标引用
T& operator[](size_t i)
{
    assert(i < size());//防止越界
    return _start[i];
}
const T& operator[](size_t i) const
{
    assert(i < size());
    return _start[i];
}

容量接口

       使用指针减指针的方式来实现容量接口size和capacity功能。

//容量接口
size_t size() const
{
    return _finish - _start;
}
size_t capacity() const
{
    return _end_of_storage - _start;
}

迭代器接口

       由于string和vector底层都是顺序存储，所以它们的迭代器相对简单，都是直接使用指针实现。之后我们学习list（链表）时，就会接触到更加复杂的迭代器实现。

//迭代器接口
iterator begin()
{
    return _start;
}
iterator end()
{
    return _finish;
}
const_iterator begin() const
{
    return _start;
}
const_iterator end() const
{
    return _finish;
}

判空

       当start与finish指向同一处时，容器即为空。

//判空
bool empty() const
{
    return _start == _finish;
}

resize

       如果参数n的值小于当前size，则该函数会将size调整为n值，并且删除超出的元素。


       如果参数n的值大于当前size，则会在末尾插入元素至size等于n值。


//调整大小
void resize(size_t n, const T& val = T())
{
    if (n <= size())
    {
        _finish = _start + n;
    }
    else
    {
        reserve(n);
        while (_finish < _start + n)
        {
            *_finish = val;
            _finish++;
        }
    }
}

reserve

       reserve的实现原理与string相似，当参数n值大于当前容量时，我们才会进行增容操作。这里需要注意：由于容量大小由三个迭代器控制，所以我们重新开辟空间之前需要记录原来的size，便于确定增容之后三个迭代器指向的位置。

//增容
void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();//记录原来的size
        T* tmp = new T[n];
        if (_start)//如果start非空，说明数组不为空，需要拷贝数据
        {
            for (size_t i = 0; i < old_size; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = tmp + n;
    }
}


插入和删除

insert和push_back

       insert和push_back负责插入操作。这里需要注意：insert实现时的迭代器失效问题。


什么是迭代器失效呢？简单的讲，由于vector是使用三个迭代器来维护的，那么如果它们指向的空间被释放，那么就会出现野指针的情况，这三个迭代器的相关操作就是无效的，这就是迭代器失效。迭代器失效的本质就是你管理的内存已经不属于你了。


insert出现迭代器失效的原因：很简单，我们在插入数据时，如果空间已满就会增容，此时分配新的空间，然后把内容拷贝过去并释放旧空间。原本我们传入的参数pos（指定的插入位置）是一个指向旧空间的迭代器，旧空间被释放后，该迭代器就会失效，从而无法插入数据。



解决办法： 记录迭代器pos与start的相对距离，当增容完成之后，根据相对距离更新pos即可。


       为什么string在进行插入的时候不会发生迭代器失效呢？因为参数pos本身是一个整形，代表要插入的下标，只要该下标不越界，就不会出现失效的情况。当然，这只是插入时不会，并不是一定不会。如果你在外部定义了一个迭代器，当字符串空间被释放后，该迭代器也会失效。此时我们对迭代器重新赋值即可。


接下来我们实现insert和push_back的代码：

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= finish);//确保插入位置合法
    if (_finish == _end_of_storage)//空间已满，增容
    {
        size_t len = pos - _start;//记录相对位置
        reserve(capcaity() == 0 ? 4 : 2 * capacity());//增容
        pos = _start + len;//更新pos
    }
    iterator i = _finish - 1;
    while (i >= pos)//pos之后元素全体向后移动一位
    {
        *(i + 1) = *i;
        i--;
    }
    *pos = x;
    _finish++;
    return pos;//返回指向新元素的迭代器
}
void push_back(const T& x)
{
    insert(_finish, x);//直接调用insert
}

erase和pop_back

       erase和pop_back负责删除操作。与insert相同，erase也会发生迭代器失效的问题。但是erase不会造成空间容量的改变，理论上是不会使迭代器失效的。不过，如果有一个迭代器指向末尾元素，删除数据之后，finish前移，该迭代器指向的数据就是非法的，就会造成迭代器失效。所以删除vector的任意元素后，vs编译器就会认为指向该元素的迭代器失效，无法继续使用。


       对于这种问题的解决方法也很简单：如果我们只是删除一次数据，迭代器失效也没关系；如果要连续删除，则需要更新迭代器。对此，我们在erase函数中删除元素后，将该元素下一个元素的迭代器作为返回值，函数外部需要使用该返回值更新迭代器。


erase和pop_back代码实现：

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);//确保删除位置合法
    auto i = pos + 1;
    while (i < _finish)//pos之后元素全体前移一位
    {
        *(i - 1) = *i;
        i--;
    }
    _finish--;
    return pos;//此时下一个元素挪到了删除元素位置，返回该位置迭代器
}
void pop_back()
{
    assert(!empty());//防止空删
    _finish--;
}

3. 程序全部代码

模拟实现vector的全部代码如下：

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
 
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 begin() const
    {
        return _start;
    }
    const_iterator end() const
    {
        return _finish;
    }
 
    //无参构造
    Vector()
    {}
    //初始化器构造
    Vector(initializer_list<T> l)
    {
        reserve(l.size());
        for (auto& e : l)
        {
            push_back(e);
        }
    }
    //迭代器区间构造
    template<class InputIterator>
    Vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first);
            first++;
        }
    }
    //n个val值构造
    Vector(size_t n, const T& val = T())
    {
        reverse(n);
        for (size_t i = 0; i < n; i++)
        {
            push_back(val);
        }
    }
    //拷贝构造
    Vector(const Vector<T>& v)
    {
        reverse(v.capacity());
        for (auto& e : v)
        {
            push_back(e);
        }
    }
    //赋值重载
    Vector<T>& operator=(Vector<T> v)
    {
        swap(v);
        return *this;
    }
    //析构
    ~Vector()
    {
        if (_start)//避免多次释放
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }
    }
 
    //下标引用
    T& operator[](size_t i)
    {
        assert(i < size());//防止越界
        return _start[i];
    }
    const T& operator[](size_t i) const
    {
        assert(i < size());
        return _start[i];
    }
 
    //容量接口
    size_t size() const
    {
        return _finish - _start;
    }
    size_t capacity() const
    {
        return _end_of_storage - _start;
    }
 
    //判空
    bool empty() const
    {
        return _start == _finish;
    }
 
    //交换
    void swap(Vector<T>& tmp)
    {
        std::swap(_start, tmp._start);
        std::swap(_finish, tmp._finish);
        std::swap(_end_of_storage, tmp._end_of_storage);
    }
 
    //调整大小
    void resize(size_t n, const T& val = T())
    {
        if (n <= size())
        {
            _finish = _start + n;
        }
        else
        {
            reserve(n);
            while (_finish < _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
    }
 
    //增容
    void reserve(size_t n)
    {
        if (n > capacity())
        {
            size_t old_size = size();//记录原来的size
            T* tmp = new T[n];
            if (_start)//如果start非空，说明数组不为空，需要拷贝数据
            {
                for (size_t i = 0; i < old_size; i++)
                {
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
            _start = tmp;
            _finish = tmp + old_size;
            _end_of_storage = tmp + n;
        }
    }
 
    //插入和删除
    void push_back(const T& x)
    {
        insert(_finish, x);//直接调用insert
    }
    void pop_back()
    {
        assert(!empty());//防止空删
        _finish--;
    }
    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= _start && pos <= finish);//确保插入位置合法
        if (_finish == _end_of_storage)//空间已满，增容
        {
            size_t len = pos - _start;//记录相对位置
            reserve(capcaity() == 0 ? 4 : 2 * capacity());//增容
            pos = _start + len;//更新pos
        }
        iterator i = _finish - 1;
        while (i >= pos)//pos之后元素全体向后移动一位
        {
            *(i + 1) = *i;
            i--;
        }
        *pos = x;
        _finish++;
        return pos;//返回指向新元素的迭代器
    }
    iterator erase(iterator pos)
    {
        assert(pos >= _start && pos < _finish);//确保删除位置合法
        auto i = pos + 1;
        while (i < _finish)//pos之后元素全体前移一位
        {
            *(i - 1) = *i;
            i--;
        }
        _finish--;
        return pos;//此时下一个元素挪到了删除元素位置，返回该位置迭代器
    }
private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
};


总结

       本篇文章，我们深入了解了vector的底层原理，并成功地模拟实现了它。与传统的动态顺序表不同，它采用了三个迭代器来维护数组，提高了程序灵活性。也正因如此，它的实现难度也有所增大，对于细节把控的要求也很高。之后博主会带领大家学习一个新容器--list。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

文章标签：
C++
容器
存储
编译器
C语言
关键词：
C++ stl
C++ vector
C++ stl vector
ephemerals__
目录
相关文章
ephemerals__
|
24天前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
31 1
ephemerals__
|
1月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
54 7
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
104 4
ephemerals__
|
2月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
105 5
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
79 2
oioihoii
|
1月前
|
存储 对象存储 C++
C++ 中 std::array＜int, array_size＞ 与 std::vector＜int＞ 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`，从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求，而 `std::vector` 则提供了动态调整大小的灵活性，适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
oioihoii
76 0
ephemerals__
|
2月前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库（STL）的基本概念、组成部分及学习方法，强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件：容器、算法、迭代器、仿函数、配接器和空间配置器，并提出了学习STL的三个层次，旨在帮助读者深入理解和掌握STL。
ephemerals__
83 0
Svan.
|
3月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
Svan.
96 5
白子寰
|
3月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
33 1
Svan.
|
3月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
Svan.
90 1

热门文章

最新文章

  • 1
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 2
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 3
    C++ 简介
  • 4
    【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
  • 5
    【硬核】C++11并发：内存模型和原子类型
  • 6
    【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
  • 7
    用 C++ 算法控制员工上网的软件，关键逻辑是啥？来深度解读下
  • 8
    C++学习之继承
  • 9
    探秘：基于 C++ 的局域网电脑控制软件自适应指令分发算法
  • 10
    【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
  • 1
    什么是内存泄漏？C++中如何检测和解决？
    32
  • 2
    探秘：基于 C++ 的局域网电脑控制软件自适应指令分发算法
    45
  • 3
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
    132
  • 4
    【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
    55
  • 5
    【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
    46
  • 6
    【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
    38
  • 7
    【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
    52
  • 8
    【C++面向对象——类与对象】CPU类（头歌实践教学平台习题）【合集】
    39
  • 9
    【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
    38
  • 10
    【C++数据结构——图】最小生成树（头歌实践教学平台习题） 【合集】
    38

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云oss简介和如何对接使用