【C++】vector的使用与模拟实现

苏兮

发布于 2026-01-13 17:39:40

1500

vector的使用与模拟实现

✨前言：在C++的STL容器家族中，vector以其高效的随机访问性能和动态扩容特性，成为最受欢迎的序列式容器。本文将带你从基本使用到底层实现，全方位解析vector的奥秘，助你真正掌握这个强大的动态数组工具。 📖专栏：【C++成长之旅】

一、vector的介绍及使用

对于vector的学习，和list的学习基本一样，先会用，再可以自己模拟实现vector就行，那我们就围绕着两个方面来说明吧。 vector学习参考文档【vector的文档介绍】：

可以看到，vector是一个类模版，而并不是像string一样，只能存储字符串，所以也就注定了它的使用很广泛。

我们来看一下常见的接口就可以：

1.1 简单接口

1. vector的定义：

构造函数声明	接口说明
vector()（重点）	无参构造
vector(size_type n, const value_type& val = value_type())	构造并初始化 n 个 val
vector(const vector& x)（重点）	拷贝构造
vector(InputIterator first, InputIterator last)	使用迭代器进行初始化构造

2. vector iterator 的使用：

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

代码示例：

#include<string>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	string str("123456");
	//使用迭代器区间初始化
	vector<int> v(str.begin(), str.end());
	//使用迭代器遍历
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it - '0' << " ";
		++it;
	}
	return 0;
}

对于迭代器，再一次进行说明一下（左闭右开）：

3. vector 空间增长问题：

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve（重点）	改变vector的capacity

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。 reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。 resreve与string中的reserve的还是有所差别的：

这样规定就比较好，没有如何不确定性。

// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}
int main()
{
	TestVectorExpandOP();
	return 0;
}

4. vector 增删查改

vector增删查改	接口说明
push_back（重点）	尾插
pop_back（重点）	尾删
find	查找（算法模块实现，非vector成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[]（重点）	像数组一样访问

都较为简单，自行练习就行。

1.2 迭代器失效问题

先来看以下代码：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4,5 };
	vector<int> v(a, a + 5);
	// 使用find查找4所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 4);
	v.erase(pos);
	cout << *pos << endl;
	return 0;
}

运行结果：

为什么会这样呢？（vs2022测试结果） erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素 时，vs就认为该位置迭代器失效了。 vs的做法比较激进，但也挺好的。

想必大家现在对迭代器有了一点理解了，我们对迭代器进行概念的说明：

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector还有其他操作可能会导致其迭代器失效：

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。空间改变，地址改变，迭代器（指针）未改，就会出现迭代器生效的问题。

#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
	// v.resize(100, 8);

	// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
	// v.reserve(100);

	// 插入元素期间，可能会引起扩容，而导致原空间被释放
	// v.insert(v.begin(), 0);
	// v.push_back(8);

	// 给vector重新赋值，可能会引起底层容量改变
	//v.assign(100, 8);

	/*
	   出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释
   放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块
   已经被释放的空间，而引起代码运行时崩溃。
	   解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给
   it重新赋值即可。
	  */
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

对于vs来说，就迭代器失效，我们刚才也看到，检查比较严格，只要有可能失效，就会报错。 但是，在Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了

int main()
{
    vector<int> v{1,2,3,4,5};
    for(size_t i = 0; i < v.size(); ++i)
         cout << v[i] << " ";
    cout << endl;
    auto it = v.begin();
    cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
   // 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效    
    v.reserve(100);
    cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
    
    // 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会
    // 虽然可能运行，但是输出的结果是不对的
    while(it != v.end())
   {
        cout << *it << " ";
        ++it;
   }
    cout << endl;
    return 0;
}

程序输出： 1 2 3 4 5 扩容之前，vector的容量为: 5 扩容之后，vector的容量为: 100 0 2 3 4 5 409 1 2 3 4 5
2. erase删除任意位置代码后，linux下迭代器并没有失效 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的

#include <vector>
#include <algorithm>
int main()
{
    vector<int> v{1,2,3,4,5};
    vector<int>::iterator it = find(v.begin(), v.end(), 3);
    v.erase(it);
    cout << *it << endl;
    while(it != v.end())
   {
        cout << *it << " ";
        ++it;
   }
    cout << endl;
    return 0;
}

程序可以正常运行，并打印： 4 4 5
3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end 此时迭代器是无效的，++it导致程序崩溃

int main()
{
    vector<int> v{1,2,3,4,5};
   // vector<int> v{1,2,3,4,5,6};
    auto it = v.begin();
    while(it != v.end())
   {
        if(*it % 2 == 0)
            v.erase(it);
        ++it;
   }
    for(auto e : v)
       cout << e << " ";
    cout << endl;
    return 0;
}

使用第一组数据时，程序可以运行 1 3 5 使用第二组数据时，程序最终会崩溃 Segmentation fault

从上述三个例子中可以看到：SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。 也可以说明，在Linux下，g++编译器对迭代器失效的检测并不是非常严格。

对于前面的string中，与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。 所以对于部分函数（insert、earse……）设置有返回值，返回下一个节点的迭代器：

还有erase等等，我就不依次列举了，可以自己看看。

代码示例：

#include<iostream>
#include <string>
using namespace std;
int main()
{
	string s("hello");
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it;
		++it;
	}
	cout << endl;
	it = s.begin();
	while (it != s.end())
	{
		it = s.erase(it);//接受返回值
	}
	while (it != s.end())
	{
		cout << *it;
		++it;
	}
	return 0;
}

我们在自己写代码的时候，有迭代器失效的情况发生，解决办法很简单：在使用前，对迭代器重新赋值即可。

二、vector深度剖析及模拟实现

对于vector的模拟实现来说，底层就是一个动态的顺序表，和string是类似的，那我们该如何定义它的成员变量呢？继续类似与string（下面这种吗）

T* _ptr;
int _size;
int _capacity;

答案是，可以用，但我们不用，换一种：

即用三个指针，在vector中，迭代器就是原生指针，那我们就直接诶用三个迭代器作为成员变量就行了呀。、

    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _end_of_storage = nullptr; // 指向存储容量的尾

那我们就框架就搭好了：

template<class T>
class vector
{
public:
    // vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;

private:
    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _end_of_storage = nullptr; // 指向存储容量的尾
};

对于vector的实现，类似于string的实现，就是比string多了一个模版，少了一个结尾的’\0’处理，模拟实现的代码如下，仅供参考，需要注意的我都备注在代码中了，主要就是深浅拷贝的问题需要注意：

#include<assert.h>
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  // 注意这里的 const
    {
        return _start;
    }
    const_iterator end() const    // 注意这里的 const
    {
        return _finish;
    }

    const_iterator cbegin() const
    {
        return _start;
    }

    const_iterator cend() const
    {
        return _finish;
    }

    //construct and destroy

    vector()
    {
    }

    vector(int n, const T& value = T())
    {
        _start = new T[n];

        for (int i = 0; i < n; i++)
        {
            _start[i] = value;
        }
        _finish = _start + n;
        _end_of_storage = _finish;
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first++);
        }
    }
    vector(const vector<T>& v)
    {
        reserve(v.size());

        for (auto tmp : v)
        {
            push_back(tmp);
        }
    }

    vector<T>& operator= (vector<T> v)
    {
        //深拷贝
        swap(v);
        return *this;
    }

    ~vector()
    {
        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;
    }

    void reserve(size_t n)
    {
        if (_end_of_storage - _start < n)
        {
            iterator tmp = new T[n];
            size_t oldsize = size();
            //深拷贝
            //选择用赋值来深拷贝
            for (int i = 0; i < oldsize; i++)
            {
                tmp[i] = _start[i];
            }

            delete[] _start;
            _start = tmp;

            _finish = _start + oldsize;
            _end_of_storage = _start + n;
        }
    }

    void resize(size_t n, const T& value = T())
    {
        if (n < size())
            _finish = _start + n;
        else
        {
            reserve(n);
            for (int i = size(); i < n; i++)
            {
                _start[i] = value;
                ++_finish;
            }
        }
    }

    //    ///////////////access///////////////////////////////![请添加图片描述](https://i-blog.csdnimg.cn/direct/d01d6b50bbbc4f08b0b31e130a39d840.png)

    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)
        {
            size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(new_capacity);
        }
        *_finish = x;
        ++_finish;
    }

    void pop_back()
    {
        assert(size());
        --_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)
    {
        assert(pos <= _finish);
        assert(pos >= _start);
        int len = pos - _start;
        reserve(size() + 1);
        //更新pos
        pos = _start + len;
        for (int i = size(); i > len; i--)
        {
            _start[i] = _start[i - 1];
        }
        *pos = x;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos)
    {
        assert(pos < _finish);
        assert(pos >= _start);
        int n = pos - _start;
        for (int i = n; i < size() - 1; i++)
        {
            _start[i] = _start[i + 1];
        }
        --_finish;
        return _start + n;
    }

private:
    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _end_of_storage = nullptr; // 指向存储容量的尾
};

注意：对于模版声明和实现不可以像string那样分.c与.h，原因>【模板进阶】