从零实现 STL vector 容器：深入理解动态内存管理

3. 容量与状态查询

size 函数

返回当前容器中有效元素的个数。

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

capacity 函数

返回当前已分配的总空间大小。

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

4. 拷贝控制规则

拷贝构造函数

必须执行深拷贝。不能使用 memcpy，因为如果元素类型包含动态资源，浅拷贝会导致双重释放问题。我们需要逐个元素调用赋值运算符。

vector(const vector& x) {
    size_t sz = x.size();
    _start = new T[sz];
    for (size_t i = 0; i < sz; ++i) {
        _start[i] = x._start[i];
    }
    _finish = _start + sz;
    _end_of_storage = _start + sz;
}

赋值运算符重载

采用传值语义的参数结合 swap 技术，可以简化代码并保证异常安全。

vector& operator=(vector x) {
    swap(x);
    return *this;
}

交换函数

交换两个 vector 的指针成员，时间复杂度为 O(1)。

void swap(vector& x) {
    std::swap(_start, x._start);
    std::swap(_finish, x._finish);
    std::swap(_end_of_storage, x._end_of_storage);
}

5. 迭代器相关

begin 与 end

提供普通版本和 const 版本的重载，分别返回可读写的迭代器和只读迭代器。

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

6. 下标操作符重载

允许像数组一样访问元素，同时增加边界检查以确保安全。

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

7. 空间管理

reserve 函数

预分配指定大小的空间。如果当前容量不足，则重新分配并拷贝现有数据。

void reserve(size_t n) {
    if (n <= capacity()) return;
    iterator tmp = new T[n];
    if (_start) {
        for (size_t i = 0; i < size(); ++i) {
            tmp[i] = _start[i];
        }
        delete[] _start;
    }
    _start = tmp;
    _finish = _start + size();
    _end_of_storage = _start + n;
}

resize 函数

调整容器大小。若扩大则用默认值或指定值填充，若缩小则截断。

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

8. 插入与删除

insert 函数

在指定迭代器位置插入元素。注意插入可能导致扩容，从而使得原迭代器失效，因此函数返回新位置的迭代器。

iterator insert(iterator pos, const T& val) {
    assert(pos >= _start && pos <= _finish);
    size_t n = pos - _start;
    if (capacity() == size()) {
        reserve(size() + 1);
        // 扩容后需要修正 pos 索引
        pos = _start + n;
    }
    // 移动元素
    for (size_t i = size(); i > n; --i) {
        *(pos + i - 1) = *(pos + i - 2);
    }
    *pos = val;
    _finish++;
    return pos;
}

push_back 函数

在尾部追加元素，内部复用 insert 逻辑。

void push_back(const T& val) {
    if (_finish == _end_of_storage) {
        reserve(size() + 1);
    }
    *_finish++ = val;
}

erase 函数

删除指定位置的元素，返回该位置之后的迭代器。

iterator erase(iterator pos) {
    assert(pos < _finish);
    iterator next = pos + 1;
    while (next < _finish) {
        *pos++ = *next++;
    }
    _finish--;
    return pos;
}

pop_back 函数

删除尾部元素。

void pop_back() {
    assert(_finish > _start);
    _finish--;
}

9. 析构函数

清理动态分配的内存，并将指针置空以防悬垂指针。

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

完整代码示例

以下是整合后的 vector 类实现：

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

template<class T>
class vector {
    typedef T* iterator;
    typedef const T* const_iterator;
public:
    // 空构造
    vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

    // 用 n 个元素对象进行初始化
    vector(size_t n, const T& val = T()) {
        _start = new T[n];
        for (size_t i = 0; i < n; ++i) {
            _start[i] = val;
        }
        _finish = _start + n;
        _end_of_storage = _start + n;
    }

    // 使用一个迭代器区间进行初始化
    template<class InputIterator>
    vector(InputIterator first, InputIterator last) {
        size_t n = last - first;
        _start = new T[n];
        InputIterator it = first;
        for (size_t i = 0; i < n; ++i) {
            _start[i] = *it++;
        }
        _finish = _start + n;
        _end_of_storage = _start + n;
    }

    // 拷贝构造函数
    vector(const vector& x) {
        size_t sz = x.size();
        _start = new T[sz];
        for (size_t i = 0; i < sz; ++i) {
            _start[i] = x._start[i];
        }
        _finish = _start + sz;
        _end_of_storage = _start + sz;
    }

    // 析构函数
    ~vector() {
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _end_of_storage = nullptr;
    }

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

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

    // 下标操作
    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 swap(vector& x) {
        std::swap(_start, x._start);
        std::swap(_finish, x._finish);
        std::swap(_end_of_storage, x._end_of_storage);
    }

    // 赋值
    vector& operator=(vector x) {
        swap(x);
        return *this;
    }

    // 空间管理
    void reserve(size_t n) {
        if (n <= capacity()) return;
        iterator tmp = new T[n];
        if (_start) {
            for (size_t i = 0; i < size(); ++i) {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + size();
        _end_of_storage = _start + n;
    }

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

    // 插入
    iterator insert(iterator pos, const T& val) {
        assert(pos >= _start && pos <= _finish);
        size_t n = pos - _start;
        if (capacity() == size()) {
            reserve(size() + 1);
            pos = _start + n;
        }
        for (size_t i = size(); i > n; --i) {
            *(pos + i - 1) = *(pos + i - 2);
        }
        *pos = val;
        _finish++;
        return pos;
    }

    void push_back(const T& val) {
        if (_finish == _end_of_storage) {
            reserve(size() + 1);
        }
        *_finish++ = val;
    }

    // 删除
    iterator erase(iterator pos) {
        assert(pos < _finish);
        iterator next = pos + 1;
        while (next < _finish) {
            *pos++ = *next++;
        }
        _finish--;
        return pos;
    }

    void pop_back() {
        assert(_finish > _start);
        _finish--;
    }

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

结语

通过以上步骤，我们完成了 vector 容器的基本实现。这个过程不仅涵盖了动态内存管理、模板元编程的基础，还涉及了 RAII 和资源管理的重要原则。希望读者能通过这段代码，对 STL 容器的底层运作机制有更深刻的理解。

将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online