C++ vector 容器使用与模拟实现

这里我们可以补充一下：当然对象会在出函数作用域时自动调用析构函数的。

3. 迭代器的使用

迭代器有两种：一种是正向的迭代器，一种是反向的迭代器。正向的迭代器通过迭代器移动可以从前往后遍历 vector 对象。反向的迭代器通过迭代器移动可以从后往前遍历 vector 对象。

在 vector 中，迭代器其实就是指针。

所以迭代器都是前开后闭的区间。即：加入 v 是 vector 对象，则 [v.begin(), v.end()) 或 [v.rbegin(), v.rend())

使用示例：

#include<iostream>
#include<vector>
using namespace std;
void test2() {
    vector<int> v1; // push_back 是逐步向 v1 中尾插入数据的函数
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    // 正向输出
    vector<int>::iterator it = v1.begin();
    while (it != v1.end()) {
        cout << *it << ' ';
        it++;
    }
    cout << endl;
    // 反向输出
    vector<int>::reverse_iterator rit = v1.rbegin();
    while (rit != v1.rend()) {
        cout << *rit << ' ';
        rit++;
    }
    cout << endl;
}

所以我们 vector 的遍历方法也就有三种，如下所示：

#include<iostream>
#include<vector>
using namespace std;
void test3() {
    vector<int> v1; // push_back 是逐步向 v1 中尾插入数据的函数
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    // 遍历方法 1:for 循环
    for (int i = 0; i < v1.size(); i++) {
        cout << v1[i] << ' ';
    }
    cout << endl;
    // 遍历方法 2:迭代器输出
    vector<int>::iterator it = v1.begin(); //auto it = v1.begin(); //常常是这样写的，因为比较简单
    while (it != v1.end()) {
        cout << *it << ' ';
        it++;
    }
    cout << endl;
    // 遍历方法 3:范围 for
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
}

4. 与空间相关的使用

vector 中有几个与空间相关的比较常用的函数：

前面的 size、capacity、empty 都比较简单，只是获取数据即可。后面的 resize、reserve 需要重点了解。 需要注意的有以下几点：

vector 的扩容策略因编译器 STL 实现而异，如 VS 中 capacity 通常按 1.5 倍增长，而 G++ 则按 2 倍增长，故不应固化扩容倍数认知。reserve(n) 可预先分配至少容纳 n 个元素的内存，可以避免频繁扩容带来的性能损耗，适用于我们预先知道元素数量的场景。resize(n) 则会调整 vector 的 size 为 n，新增元素会被初始化，多余元素会被销毁，其操作比 reserve 更复杂。

使用示例：

void test4() {
    vector<int> v1;
    cout << "empty:" << v1.empty() << endl;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    cout << "empty:" << v1.empty() << endl;
    cout << "size:" << v1.size() << endl;
    cout << "capacity:" << v1.capacity() << endl;
    v1.resize(20);
    cout << "size:" << v1.size() << endl;
    cout << "capacity:" << v1.capacity() << endl;
    v1.reserve(100);
    cout << "size:" << v1.size() << endl;
    cout << "capacity:" << v1.capacity() << endl;
}

5. 增删查改

关于增删改查的常用函数有以下几种：

vector 的尾插使用比较简单，

void test5() {
    vector<int> v1;
    v1.push_back(1); // 尾插 1
    v1.push_back(2); // 尾插 2
    v1.push_back(3); // 尾插 3
    v1.push_back(4); // 尾插 4
    v1.push_back(5); // 尾插 5
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
}

我们需要注意在 vector 中是没有头插的。但我们可以通过 insert 实现，但通过 insert 进行插入有多个函数重载需要注意。

第一个是在 position 位置插入 val，第二个是在 position 位置插入 n 个 val，第三个是在 position 位置插入一个由迭代器范围 [ first, last ) 定义的元素序列。要注意上面的参数都是迭代器参数。

void test6() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    vector<int>::iterator it=v1.begin();
    v1.insert(v1.begin()+2, 6); //在第 2 个位置之前插入 6
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    v1.insert(v1.begin()+2, 6, 10); //在第 2 个位置之前插入 6 个 10
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    int arr[] = { 11,12,13,14 };
    v1.insert(v1.begin()+2, arr, arr+3); //在第 2 个位置之前插入 arr 的 [arr,arr+3) 的数据
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
}

进行删除操作时，尾删比较好使用，就不做解释了。

对于 erase 有两个函数重载，它们都是传的迭代器参数：

使用示例：

void test7() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    v1.erase(v1.begin()); //删除第一个元素
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    v1.erase(v1.begin(),v1.begin()+2); //删除当前的 [v1.begin(),v1.begin()) 的两个元素
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
}

因为 vector 是使用数组实现的，，所以通过运算符重载 operator[ ] 可以实现对 vector 对象的访问及修改。这里就不多说了。

对于两个 vector 对象，使用 swap 就可以高效交换两个 vector 对象的内容。

void test8() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    vector<int> v2(3,6);
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    for (auto e : v2) {
        cout << e << ' ';
    }
    cout << endl;
    v1.swap(v2); // 交换 v1 和 v2
    for (auto e : v1) {
        cout << e << ' ';
    }
    cout << endl;
    for (auto e : v2) {
        cout << e << ' ';
    }
    cout << endl;
}

对于查找，vector 里面没有提供，所以我们可以使用算法模块 find 实现。使用算法模块需要包含头文件：

三、vector 的模拟实现

1. 成员变量的解释

在 STL 源码底层里面，实现 vector 主要是靠使用三个迭代器实现的，也可以是称为指针（因为 vector 的迭代器就是指针）。即：

• start：指向第一个元素，标记数据起始。
• finish：指向最后一个元素的下一个位置，标记数据结束。
• end_of_storage：指向动态分配内存的末尾的下一个位置（即内存块的尾后位置），标记容量上限。

图示如下：

要注意我们模拟时需要我们自己来定义一个命名空间域，并且由于 vector 是可以存储多种类型的，所以我们需要使用模板实现，所以成员变量定义就可以如下所示：

namespace MyTest {
    template<class T> class vector {
    public:
        //重定义可以和库里的保持一致，便于理解
        typedef T* iterator;
        typedef const T* const_iterator;
    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}

2. 模拟实现 vector 的总代码

namespace MyTest {
    template<class T> class my_vector {
    public:
        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; }
        //构造
        my_vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { }
        my_vector(size_t n, const T& val = T()) //如果没有传 val，则 val 会去调用它的默认构造
        {
            resize(n, val);
        }
        my_vector(int n, const T& val = T())
        {
            resize(n, val);
        }
        template<class InputIterator>
        my_vector(InputIterator first, InputIterator last)
        {
            while (first != last) {
                push_back(*first);
                ++first;
            }
        }
        //拷贝构造 - 深拷贝
        my_vector(const my_vector<T>& v)
        {
            _start = new T[v.capacity()];
            for (size_t i = 0; i < v.size(); i++) {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
        }
        void swap(my_vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }
        my_vector<T>& operator=(my_vector<T> v)//传值，会调用拷贝构造
        {
            swap(v);
            return *this;
        }
        //析构
        ~my_vector()
        {
            //清除空间资源
            if (_start) {
                delete[] _start;
                _start = _finish = _end_of_storage = nullptr;
            }
        }
        //空间相关操作
        //获取数据个数
        size_t size() const { return _finish - _start; }
        //获取容量
        size_t capacity() const { return _end_of_storage - _start; }
        //[]运算符重载
        T& operator[](size_t pos)
        {
            assert(pos < size()); //断言位置合理性
            return _start[pos];
        }
        const T& operator[](size_t pos) const
        {
            assert(pos < size()); //断言位置合理性
            return _start[pos];
        }
        //扩容 (重要)
        void reserve(size_t n)
        {
            if (n > capacity()) {
                size_t sz = size();//这里需要保存一下原数据的个数
                T* tmp = new T[n];
                if (_start) {
                    //如果 vector 不为空，则要拷贝数据
                    for (int i = 0; i < size(); i++) {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;//释放原空间
                }
                //对该对象进行赋值
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }//扩容完成
        }
        //改变 size
        void resize(size_t n, const T val = T())
        {
            if (n < size()) {
                //如果 n 比当前 size 小，只需要移动 finish 即可
                _finish = _start + n;
            } else {
                //如果比 size 大，则需要先扩容，再补充元素
                reserve(n);
                while (_finish != _start + n) {
                    *_finish = val;
                    _finish++;
                }
            }
        }
        //在 pos 位置插入 x
        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start && pos <= _finish); //判满
            if (_finish == _end_of_storage) {
                size_t len = pos - _start;
                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapacity);
                pos = _start + len;//防止迭代器失效 (因为扩容后空间地址会改变)
            }
            //移动数据
            iterator end = _finish - 1;
            while (end >= pos) {
                *(end + 1) = *end;
                end--;
            }
            //插入
            *pos = x;
            _finish++;
            return pos;
        }
        //尾插
        void push_back(const T& x) { insert(end(), x); }
        //删除 pos 位置的数据
        iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos + 1;
            while (it != _finish) {
                *(it - 1) = *it;
                ++it;
            }
            _finish--;
            return pos;
        }
    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}

四、关于 vector 的常见问题

1. 迭代器失效的问题

迭代器失效是指迭代器指向的对象不再有效，继续使用该迭代器会导致未定义行为。对于 vector 而言，迭代器失效主要发生在以下两种情况：

1. 容量变化导致的失效：当 vector 的容量 (capacity) 发生变化时，所有现有迭代器、指针和引用都会失效。
2. 元素删除导致的失效：当删除某个元素时，指向该元素及其之后所有元素的迭代器都会失效。

（1）容量变化导致

原因

我们在进行插入数据时往往会执行扩容操作。由于 vector 在内存中是连续存储的，所以当空间不足时，它会分配一块更大的内存 (通常是当前容量的 2 倍)，将原有元素复制过去，然后释放旧内存。这个过程之后，如果之前使用了迭代器，则所有迭代器都会指向旧的内存地址，因此就会失效。

比如：在 VS 下的迭代器失效

#include<vector>
#include<iostream>
using namespace std;
int main() {
    vector<int> v = { 1, 2, 3 };
    auto it = v.begin(); // 指向第一个元素
    v.push_back(4); // 可能触发扩容
    // 此时 it 可能已经失效
    cout << *it << endl; //此时迭代器就失效了，在 VS 下就是报错
    return 0;
}

运行后：

避免方法

预留空间：使用 reserve() 预先分配足够空间。谨慎使用需要扩容的操作：在需要保持迭代器有效的操作中，避免使用可能导致扩容的操作。

（2）元素删除导致

原因

当使用 erase() 删除 vector 中的元素时，会导致后续元素向前移动，被删除元素之后的所有元素的迭代器都会失效，因为元素移动后，迭代器指向的位置可能被覆盖，从而失效，继续使用这些失效的迭代器会导致不可预测的程序行为，即未定义行为。

比如：

#include<vector>
#include<iostream>
using namespace std;
int main() {
    vector<int> v = { 1, 2, 3 };
    auto it = v.begin(); // 指向第一个元素
    v.erase(it); // 删除操作后，就元素移动了
    cout << *it << endl; // 此时迭代器就失效了，这是未定义行为，在 VS 下会报错
    return 0;
}

运行后：

解决方法

每次删除时都返回新的迭代器。

总结一下

在 vector 中，通过插入或删除迭代器对象后，就不能再访问这个迭代器了。因为我们认为此时迭代器是失效的，访问时结果是未定义的，我们不能这么使用。

同时我们需要知道，不同编译器对迭代器失效的处理也是不同的，比如 VS 是强制检查，比较严格；g++ 的处理就比较宽松。

2. 关于 memcpy 的拷贝问题（深浅拷贝）

使用 memcpy 而出现的问题常常出现在我们来模拟实现 vector 时出现。比如我们在模拟实现 vector 的拷贝构造函数时，如果使用 memcpy 来进行拷贝，即：

my_vector(const my_vector<T>& v) {
    _start = new T[v.capacity()];
    memcpy(_start, v._start, sizeof(T) * v.size()); // 注意这样写是有问题的
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}

这样写会出现的问题是：深浅拷贝的问题。可以说这样写的效果就是浅拷贝的效果。所以当我们写一个自定义的类型的 vector 时，就会出现问题，比如 string。

那么我们再执行以下代码：

int main() {
    MyTest::my_vector<string> v;
    v.push_back("11111");
    v.push_back("22222");
    v.push_back("33333");
    v.push_back("44444");
    MyTest::my_vector<string> v2(v);
    return 0;
}

这段代码的执行效果如下：

其中 v 和 v2 是指向同一个空间的。

原因分析

memcpy 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。如果拷贝的是内置类型的元素，memcpy 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为 memcpy 的拷贝实际是浅拷贝。

所以如果对象中涉及到资源管理时，千万不能使用 memcpy 进行对象之间的拷贝，因为 memcpy 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。那么我们对于上面的代码，要使自定义类型也可以使用的话就可以这样写：

my_vector(const my_vector<T>& v) {
    _start = new T[v.capacity()];
    for (size_t i = 0; i < v.size(); i++) {
        _start[i] = v._start[i];
    }
    /*memcpy(_start, v._start, sizeof(T) * v.size());*/
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}

这样就是深拷贝：

3. 模拟 vector 的构造函数重载的问题

我们在模拟实现构造函数时有三个函数的实现：

//构造
my_vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { }
//第二个
my_vector(size_t n, const T& val = T()) //如果没有传 val，则 val 会去调用它的默认构造
{
    resize(n, val);
}
//第三个
template<class InputIterator>
my_vector(InputIterator first, InputIterator last)
{
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

其中的第二个和第三个的构造函数实现是有问题的。因为它们是很像的。当我们定义 vector 的对象时，编译器会调用最合适它的一个函数，比如这段代码：

MyTest::my_vector<int> v(4, 6); // 调用的是第三个构造函数

这里会优先调用的是第三个构造函数，但第三个函数是必须要用迭代器才能正常使用的，否则就不会正常运行：

所以在我们模拟实现 vector 的构造函数时，就需要注意这个情况。

在 vector 的库里面解决这个问题的方法就是将第二个函数进行了改进，就是将第二个函数进行重载一下，即以下代码：

my_vector(size_t n, const T& val = T()) //如果没有传 val，则 val 会去调用它的默认构造
{
    resize(n, val);
}
my_vector(int n, const T& val = T())
{
    resize(n, val);
}
template<class InputIterator>
my_vector(InputIterator first, InputIterator last)
{
    while (first != last) {
        push_back(*first);
        ++first;
    }
}