C++STL详解（四）—— vector的模拟实现

阅读量：798 次

发布时间：2023-04-03

本文共 4262 字，大约阅读时间需要 14 分钟。

模拟实现C++标准库vector类代码解析与总结

在C++编程中，vector 是标准库中最常用的动态数组实现之一。通过阅读和分析其官方文档，可以深入了解 vector 的各个成员函数及其实现原理。本文将从构造函数、成员变量、拷贝与赋值操作、析构函数以及其他相关函数等方面详细解析 vector 的实现逻辑。

1. 模拟实现背景

为了避免与标准库中的 vector 类产生命名冲突，建议将模拟实现放在自己的命名空间中。这样可以确保代码的唯一性并避免潜在的问题。

namespace cl {    // 模拟实现vector template    template
   
        class vector {    public:        // 其他成员函数定义    };}

2. 模拟实现成员变量

vector 类的实现中维护三个关键成员变量：

_start：指向容器的头。

_finish：指向容器中有效数据的尾。

_endofstorage：指向整个容器的尾。

通过这些指针，可以轻松获取容器的大小和容量：

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

3. 构造函数

3.1 默认构造函数

无参构造函数用于初始化空容器：

vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}

3.2 拷贝构造函数

支持从其他 vector 或输入迭代器中初始化容器。传统实现方式为：

vector(const vector
   
    & v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {    _start = new T[v.size()];    for (size_t i = 0; i < v.size(); ++i) {        _start[i] = v[i];    }    _finish = _start + v.size();    _endofstorage = _start + v.capacity();}

现代写法推荐使用范围遍历：

vector(const vector
   
    & v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {    reserve(v.capacity());    for (auto e : v) {        push_back(e);    }}

3.3 拷贝构造函数注意事项

使用 reserve 函数预分配空间以提高效率。

对于内置类型或浅拷贝类型（如 int），直接使用 memcpy 是可行的。

对于深拷贝类型（如 string），必须通过 push_back 或其他拷贝机制确保深拷贝。

3.4 拷贝构造与赋值函数的区别

拷贝构造用于初始化容器，赋值函数用于将现有容器赋值给另一个对象。

4. 赋值运算符重载

4.1 传统写法

vector
   
    & operator=(const vector
    
     & v) {    if (this != &v) {        delete[] _start;        _start = new T[v.capacity()];        for (size_t i = 0; i < v.size(); ++i) {            _start[i] = v[i];        }        _finish = _start + v.size();        _endofstorage = _start + v.capacity();    }    return *this;}

4.2 现代写法

vector
   
    & operator=(const vector
    
     & v) {    swap(*this, v);    return *this;}

现代写法通过交换两个对象的成员变量来实现赋值操作。

5. 拷贝与赋值注意事项

拷贝操作通常会引发深拷贝，而赋值操作通常会调用拷贝构造函数。

memcpy 函数不能用于深拷贝类型（如 string），因为会导致多个对象共享同一数据。

6. 析构函数

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

7. 迭代器相关函数

7.1 迭代器定义

typedef T* iterator;typedef const T* const_iterator;

7.2 begin() 和 end() 函数

iterator begin() { return _start; }iterator end() { return _finish; }const_iterator begin()const { return _start; }const_iterator end()const { return _finish; }

7.3 范围遍历

for (auto e : v) {    // 遍历每个元素}

8. 容量和大小管理

8.1 reserve 函数

void reserve(size_t n) {    if (n > capacity()) {        size_t sz = size();        T* tmp = new T[n];        if (_start) {            for (size_t i = 0; i < sz; ++i) {                tmp[i] = _start[i];            }            delete[] _start;        }        _start = tmp;        _finish = _start + sz;        _endofstorage = _start + n;    }}

8.2 resize 函数

void resize(size_t n, const T& val = T()) {    if (n < size()) {        _finish = _start + n;    } else {        if (n > capacity()) {            reserve(n);        }        while (_finish < _start + n) {            *_finish = val;            _finish++;        }    }}

9. 修改容器内容

9.1 push_back 函数

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

9.2 pop_back 函数

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

9.3 insert 和 erase 函数

void insert(iterator pos, const T& x) {    if (_finish == _endofstorage) {        size_t len = pos - _start;        size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();        reserve(newcapacity);        pos = _start + len;    }    while (pos + 1 <= _finish) {        _finish--;        _finish++;    }    *pos = x;    _finish++;}iterator erase(iterator pos) {    assert(!empty());    iterator it = pos + 1;    while (it != _finish) {        _finish--;        it++;    }    _finish--;    return pos;}

10. swap 函数

void swap(vector
   
    & v) {    swap(_start, v._start);    swap(_finish, v._finish);    swap(_endofstorage, v._endofstorage);}

11. 访问容器相关函数

11.1 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];}