C++ vector 类常用接口及模拟实现

vector 的遍历有三种方法：下标 + []、迭代器、范围 for。

（1）下标 + []

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    for (size_t i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

（2）迭代器

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    vector<int>::iterator it = v.begin();
    while (it != v.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

（3）范围 for

范围 for 的底层是迭代器。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    for (auto e : v) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

3. vector 类对象的容量操作

（1）resize

改变 vector 的 size，同时对新增数据初始化（未指定就调用默认构造）。resize 一般不会缩容，但会改变 size：小于 size 时删除数据，大于 size 时插入数据，空间不够时会扩容。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    cout << v.size() << endl;
    cout << v.capacity() << endl;

    v.reserve(20);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    cout << v.size() << endl;
    cout << v.capacity() << endl;

    v.resize(15, 2);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    cout << v.size() << endl;
    cout << v.capacity() << endl;

    v.resize(5);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    return 0;
}

（2）capacity

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    v.reserve(20);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    v.reserve(15);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    v.reserve(5);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    return 0;
}

从运行结果可以看出，把 capacity 改成 20 后，再使用 reserve 不会减小 vector 的 capacity。

4. vector 增删查改

（1）push_back 和 insert

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    // 使用 push_back 尾插元素
    v.push_back(2);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    // 在起始位置插入元素
    v.insert(v.begin(), 3);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    // 在下标为 3 的位置插入元素
    v.insert(v.begin() + 3, 4);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

（2）erase

erase 可以删除一个位置，也可以删除一段迭代器区间。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 1);
    // 删除起始位置
    v.erase(v.begin());
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    // 删除下标为 3 的位置
    v.erase(v.begin() + 3);
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

5. vector 的使用

vector 不仅可以存储内置类型，还可以存储自定义类型甚至存储 vector。

使用 vector 存储 vector

使用 vector 存储 vector 可以看作二维数组，也可以像访问二维数组一样使用 [][] 访问（实际上是两次函数调用）。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 0);
    // 使用 vector 存储 vector，相当于 5 行 10 列的二维数组
    vector<vector<int>> vv(5, v);
    // 使用下标 + [] 访问 vector
    for (int i = 0; i < vv.size(); i++) {
        for (int j = 0; j < vv[i].size(); j++) {
            cout << vv[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

三、vector 迭代器失效问题

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

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

1. 会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、assign、push_back 等

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5};
    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;
}

2. 指定位置元素的删除操作

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {1, 2, 3, 4};
    vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
    // 使用 find 查找 3 所在位置的 iterator
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    // 删除 pos 位置的数据，导致 pos 迭代器失效
    v.erase(pos);
    cout << *pos << endl; // 此处会导致非法访问
    return 0;
}

erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上迭代器不会失效，但是如果 pos 刚好是最后一个元素，删除之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素时，vs 就认为该位置迭代器失效了。

3. 注意：在 Linux 下，g++ 编译器对迭代器失效的检测并不是非常严格，处理也没有 vs 极端。在 Linux 下迭代器失效后，代码不一定会崩溃，但运行结果肯定不对，如果 it 不再 begin 到 end 范围内，程序一定会崩溃。

4. 与 vector 类似，string 在插入 + 扩容操作 + erase 之后，迭代器也会失效。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s("hello");
    auto it = s.begin();
    // 放开之后程序会崩溃，因为 resize 到 20 string 会进行扩容
    // 扩容之后，it 指向之前的旧空间已经被释放了，该迭代器就会失效
    // 后序打印时，再访问 it 指向的空间，程序就会崩溃
    // s.resize(20, '!');
    while (it != s.end()) {
        cout << *it;
        ++it;
    }
    cout << endl;
    it = s.begin();
    while (it != s.end()) {
        it = s.erase(it); // 按照下面方式写，运行时程序会崩溃，因为在 erase(it) 之后，it 位置的迭代器就失效了
        // s.erase(it);
        // ++it;
    }
    return 0;
}

迭代器失效的解决办法：在使用前对迭代器重新赋值即可。

四、vector 模拟实现

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace zsy {
template<class T>
class vector {
public:
    typedef T* iterator;
    typedef const T* const_iterator;

    // 默认构造
    // vector() {}
    // c++11:强制生成默认构造
    vector() = default;

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

    // 类模板的成员函数可以是函数模板
    // 迭代器区间构造（可以使用任意容器的迭代器初始化 vector，但要求类型是匹配的）
    template<class InputIterator>
    vector(InputIterator first, InputIterator last) {
        while (first != last) {
            push_back(*first);
            ++first;
        }
    }

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

    void clear() {
        _finish = _start;
    }

    // v1 = v3
    // 赋值重载
    // 传统写法
    // const vector<T>& operator=(const vector<T>& v) {
    //     if (this != &v) {
    //         clear();
    //         reserve(v.size());
    //         for (auto e : v) {
    //             push_back(e);
    //         }
    //     }
    //     return *this;
    // }

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

    // 现代写法
    const vector<T>& operator=(vector<T> v) {
        swap(v);
        return *this;
    }

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

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

    // 扩容
    void reserve(size_t n) {
        if (n > capacity()) {
            size_t old_size = size();
            T* tmp = new T[n];
            // 使用 memcpy 会产生深拷贝问题
            // memcpy(tmp, _start, old_size * sizeof(T));
            // 遍历并一个个赋值可以解决深拷贝问题
            for (size_t i = 0; i < old_size; i++) {
                tmp[i] = _start[i];
            }
            delete[] _start;
            _start = tmp;
            _finish = tmp + old_size;
            _end_of_storage = _start + 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;
            }
        }
    }

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

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

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

    // 尾插
    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;
    }

    // 这种比较长的函数可以在类里面声明、类外面定义，但不能分成两个文件，否则会链接错误
    iterator insert(iterator pos, const T& x) {
        assert(pos >= _start);
        assert(pos <= _finish);
        // 如果满了就先扩容
        if (_finish == _end_of_storage) {
            // 计算相对位置，扩容后对迭代器重新赋值可以解决迭代器失效问题
            size_t len = pos - _start;
            reserve(capacity() == 0 ? 4 : capacity() * 2);
            pos = _start + len;
        }
        iterator end = _finish - 1;
        while (end >= pos) {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;
        _finish++;
        // insert 之后迭代器会失效，要访问就要更新这个失效的迭代器
        // 返回新插入元素，可以解决迭代器失效问题
        return pos;
    }

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

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

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

private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
};

template<class T>
void print_vector(const vector<T>& v) {
    // 规定：从未实例化的类模板中取东西，编译器不能区分这里的 const_iterator 是类型还是静态成员变量，需要加上 typename
    // typename vector<T>::const_iterator it = v.begin();
    // 也可以直接将类型名写成 auto
    auto it = v.begin();
    while (it != v.end()) {
        cout << *it << " ";
        ++it;
    }
}
}