详解C++ STL模拟实现vector

目录

• vector 概述
• 接口总览
• 默认成员函数
• 构造函数
• 析构函数
• 拷贝构造函数
• 复制赋值函数
• vector 的迭代器
• 元素访问
• operator[]
• back
• 容量相关函数
• size
• capacity
• empty
• resize
• reserve
• 修改函数
• insert
• push_back
• erase
• pop_back
• swap

vector 概述

vector 的数据结构安排及操作方式，与原生数组十分相似，两者唯一的差别在于空间运用的灵活性。原生数组是静态空间，一旦配置了就不能改变大小；vector 是动态空间，可以在插入过程中动态调整空间大小。vector 的实现技术，关键在于它对大小的控制及重新配置时的数据移动效率。

在文中，将会挑选 vector 的一些常用接口来模拟实现，但并不和标准库中实现方式相同。标准库中使用了大量内存操作函数来提高效率，代码晦涩难懂，不利用初学者学习。本文实现方式相对简单，但也需要读者有一定的 STL 使用经验。下面就让我们开始吧。

接口总览

namespace qgw {
	template <class T>
	class vector {
		typedef T* iterator;
        typedef const T* const_iterator;
		typedef T& reference;
	public:
		// 默认成员函数
		vector();										// 默认构造函数
		vector(size_t n, const T& val = T());			// 构造 n 个 T 类型对象
		vector(InputIterator first, InputIterator last);// 用一段区间构造
		vector(const vector<T>& v);						// 拷贝构造函数
		vector<T>& operator=(const vector<T>& v);		// 复制赋值函数
		~vector();

		// 迭代器函数
		iterator begin();
        const_iterator begin() const;
		iterator end();
        const_iterator end() const;

		// 元素访问
		reference operator[](size_t pos);
		const reference operator[](size_t pos) const;
		reference back();
		const reference back() const;

		// 容量
		bool empty() const;
		size_t size() const;
		size_t capacity() const;
		void resize(size_t cnt, T val = T());
		void reserve(size_t cap);

		// 修改
		iterator insert(iterator pos, const T& val);
		void push_back(const T& val);
		iterator erase(iterator pos);
		iterator erase(iterator first, iterator last);
		void pop_back();
		void swap(vector<T>& v);

	private:
		iterator _start;			// 表示目前使用空间的头
		iterator _finish;			// 表示目前使用空间的尾
		iterator _end_of_storage;	// 表示已分配空间的尾
	};
}

成员变量介绍

vector 中有三个成员变量，_start 指向使用空间的头，_finish 指向使用空间的尾，_end_of_storage 指向已分配空间的尾。

由上图也可以清晰的看出，_finish - _start 就是 size 的大小，_end_of_storage - _start 就是 capacity 的大小。

默认成员函数

构造函数

默认构造函数

vector 支持一个无参的构造函数，在这个构造函数中我们直接将上文中三个成员变量初始化为空即可。

/// @brief 默认构造函数，将指针初始化为空
vector() {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;
}

构造 n 个 T 类型对象

vector 支持构造 n 个 值为 val 的对象。可以先用 reserve开辟容量，在调用 push_back 插入即可。

注意：reserve 改变的是 capacity 的大小，不改变 size 的大小，先开辟容量为防止需多次扩容降低效率。

/// @brief 构造 n 个值为 val 的对象
/// @param n 容器的大小
/// @param val 用来初始化容器元素的值
vector(size_t n, const T& val = T()) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    reserve(n);
    for (int i = 0; i < n; ++i) {
        push_back(val);
    }
}

一段区间构造

vector 支持使用一段迭代器区间构造，区间范围是 [first, last)，这里的迭代器不一定要是 vector 的迭代器，只有是具有输入功能的迭代器都可以。

/// @brief 用给定的迭代器区间初始化，STL 中的区间均为左闭右开形式，即 [first, last)
/// @tparam InputIterator 所需最低阶的迭代器类型，具有输入功能的迭代器都可以
/// @param first 迭代器起始位置
/// @param last 迭代器终止位置
template< class InputIterator>
    vector(InputIterator first, InputIterator last) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    // 和上一个类似，先开辟空间，尾减头即为要开辟的个数
    reserve(last - first);
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

析构函数

析构函数的实现很简单，首先检查容器是否为空，不为空就释放空间，再把指针置空即可。

注意：因为我们开辟了连续的空间，要使用 delete[] 来释放空间，对应的也要使用 new[] 来开辟空间。即使我们只开辟一个空间也不能使用 new，否则对自定义类型在释放时程序会崩溃。

具体原因请看：new 和 delete 为什么要匹配使用

/// @brief 释放开辟的空间
~vector() {
    if (_start != nullptr) {
        // 释放开辟的空间，从此处可以看出，开辟空间一定要用 new[]
        // 否则对于自定义类型程序将会崩溃
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _end_of_storage = nullptr;
    }
}

拷贝构造函数

下面给出的实现方法比较简单，直接用容器 v 初始化创建一个临时容器 tmp，再交换 tmp 和 this 指针指向就好了。

此时 this 指向的容器是由 v 初始化出来的，tmp 指向了一个全空的容器，tmp 出了作用域就销毁了。

需要注意的是此处一定要先将指针初始化为空，否则交换给 tmp 的指针要是不为空而是随机值的话，tmp 销毁时调用析构函数就会导致程序崩溃。有些 ide（vs 2022） 可能会自动赋空，dev 下就不会，对指针类型编译器本来就不会处理。

/// @brief 用给定容器初始化
/// @param v 用来初始化的容器
vector(const vector<T>& v) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

复制赋值函数

该函数与拷贝构造函数类似，不同的是这里指针不应赋空，否则指针原本指针指向的东西就无法正确释放了。

/// @brief 替换容器内容
/// @param v 用作数据源的另一容器
/// @return *this
vector<T>& operator=(const vector<T>& v) {
    vector<T> tmp(v);
    swap(tmp);
    // 返回值为对象的引用，为的是可以连续赋值
    return *this;
}

vector 的迭代器

vector 维护的是一个连续线性空间，不论元素是什么类型，普通指针都可以作为 vector 的迭代器满足所有的条件，因此元素类型的指针就是 vector 的迭代器。

typedef T* iterator;
typedef const T* const_iterator;

begin 和 end

begin 和 end 获取的是正向迭代器，begin 指向第一个元素，end 指向最后一个元素的下一个位置，begin++ 是向后即 end 方向移动。

对应的还有反向迭代器 rbegin 和 rend，rbegin 指向最后一个元素，rend 指向第一个元素的前一个位置，rbegin++ 是向前即 rend 方向移动。两者对应如下图，因为反向迭代器复杂的多，这里就不实现了。

/// @brief 返回指向 vector 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
    return _start;
}

// const 版本供 const 容器使用
const_iterator begin() const {
    return _start;
}

/// @brief 返回指向 vector 最后元素后一元素的迭代器
/// @return 指向最后元素下一个位置的迭代器
iterator end() {
    return _finish;
}

const_iterator end() const {
    return _finish;
}

元素访问

operator[]

vector 也支持向数组一样的 [] 访问方式，可以随机读取每个位置，返回该位置元素的引用。

需要注意的是，该函数并不做边界检查，需程序员自行检查。

/// @brief 返回位于指定位置 pos 的元素的引用，不进行边界检查
/// @param pos 要返回的元素的位置
/// @return 到所需元素的引用
reference operator[](size_t pos) {
    return _start[pos];
}

// 与上面的唯一不同就是用于 const 容器
const reference operator[](size_t pos) const {
    return _start[pos];
}

back

back 可以获取最后一个元素的引用。

/// @brief 返回到容器中最后一个元素的引用
/// @return 最后元素的引用
reference back() {
    return *(end() - 1);
}

const reference back() const {
    return *(end() - 1);
}

容量相关函数

size

根据图可知 _finish - _start 即为 size。

/// @brief 返回容器中的元素数
/// @return 容器中的元素数量
size_t size() const {
    return _finish - _start;
}

capacity

由图可知 _end_of_storage - _start 即为 capacity。

/// @brief 返回容器当前已为之分配空间的元素数
/// @return 当前分配存储的容量
size_t capacity() const {
    return _end_of_storage - _start;
}

empty

检查是否为空的方法很简单，直接比较 _start 是否 _finish 相等即可，相等就为空，返回 true。

/// @brief 检查容器是否无元素
/// @return 若容器为空则为 true，否则为 false
bool empty() const {
    return _start == _finish;
}

resize

重设容器大小以容纳 cnt 个元素。

如果当前大小大于 cnt，那么减小容器到它的开头 cnt 个元素。

如果当前大小小于 cnt，那么就调用 insert 在最后插入 cnt - size() 个 val。

一定要注意，不能只改变 _finish，呢样会因没调用析构函数从而引发内存泄漏。你可能会想，我们会在最后容器销毁的时候调用它的析构函数，它的析构函数中有 delete[]，这个语句会调用数据的析构函数不会引起内存泄漏。这样想有一定的道理，但有没有可能我们 vector 中一开始有 10 个元素，我们用 resize 将其大小改变为 5，再调用 5 次 insert 将其大小变为 10，最后对象销毁调用析构。

如上图，我们一开始有 10 个 int* 类型的元素，分别指向一块空间，后面 resize 为 5 后又添加了 5 个新的数据（用蓝色标识）。当我们析构的时候我们会析构下图中的元素，释放它们指向的空间，那上图中的 6、7、8、9、10 呢，没办法，因为我们已经找不到它们的指针了，也就没办法释放它们的空间了。

/// @brief 重设容器大小以容纳 cot 个元素
/// @param cnt 容器的大小
/// @param val     用以初始化新元素的值
void resize(size_t cnt, T val = T()) {
    if (cnt < size()) {
        // 新大小小于原来的，需要将多余的部分删除掉
        // 不能只改变 _finish 指向，要使用 erase 来删除，以便调用析构函数
        erase(begin() + cnt, end());
    } else {
        // 新空间更大，直接调用 insert 插入即可
        for (int i = 0; i < cnt - size(); ++i) {
            insert(end(), val);
        }
    }
}

reserve

reserve 用来预留存储空间，如果要 push_back 大量的数据，可能会引起多次空间分配，从而多次转移元素浪费大量时间。可以预先开辟足够的空间，减少空间分配的次数，来提高效率。

注意：

1.若 cap 的值大于当前的 capacity，则分配新存储，否则不做任何事，也就是说 reserve 不会缩小容量

为什么一定要分配新存储，而不是在原空间之后接一部分新空间（因为无法保证原空间之后还有足够的可用空间）

2.同时，capacity 的改变也不会影响 size 的大小

reserve 扩容的思路也比较简单，开辟一段新空间，将原数据拷贝到新空间，释放旧空间即可。

需要注意的是，一定要在开始记录之前元素的个数，因为 _finish 还指向原空间最后一个有效数据的下一个位置，需要将其更新指向新空间。

/// @brief 增加 vector 的容量到大于或等于 cap 的值
/// @param cap vector 的新容量
void reserve(size_t cap) {
    size_t len = size();
    if (cap > capacity()) {
        T* tmp = new T[cap];
        if (_start != nullptr) {
            // 如果容器内之前有数据，将数据拷贝到新位置
            for (int i = 0; i < size(); ++i) {
                tmp[i] = _start[i];
            }
            delete[] _start;    // 释放掉旧的空间
        }
        _start = tmp;
    }
    // 指向新的地址空间
    _finish = _start + len;
    _end_of_storage = _start + cap;
}

修改函数

insert

insert 函数的功能很多，可以在指定位置插入一个或多个值，也可以插入一段区间。这里我们只实现插入一个值的函数，在 pos 前面插入 val。

插入之前首先要检查容量，不够就进行扩容。然后将插入位置之后的数据向后挪动一个位置，插入 val 即可。

需要注意的是，扩容的话需要提前记录 pos 之前的元素个数。因为 pos 指向的是之前空间的某个位置，要将其更新为新空间的地址。

/// @brief 将 val 插入到 pos 迭代器之前
/// @param pos 	将内容插入到它前面的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入 val 的迭代器
iterator insert(iterator pos, const T& val) {
    // 检查参数是否在合法返回，assert 只在 degug 版本下有效
    assert(pos >= _start && pos <= _finish);

    if (_finish == _end_of_storage) {
        // 首先检查容量，空间不够要进行扩容
        // 先记录插入位置之前元素个数
        size_t len = pos - _start;
        // 第一次开辟空间给 10 个，后续扩容为 2 倍
        size_t newCap = capacity() == 0 ? 10 : capacity() * 2;
        reserve(newCap);
        // 更新 pos 在新空间中的位置
        pos = _start + len;
    }

    // 将插入位置之后的所有数据向后挪动一个位置
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end;
        --end;
    }
    *pos = val;
    ++_finish;
    return pos;
}

push_back

push_back 是向容器的最后添加一个元素，直接调用 insert 即可。

/// @brief 添加给定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const T& val) {
    // 直接调用 insert 即可
    insert(end(), val);
}

erase

erase 从容器中删除指定的元素：

1.移除位于 pos 的元素

2.移除范围 [first, last) 中的元素

移除 pos 位置的元素方法很简单，首先调用该位置的析构函数，然后将后面的数据向前移动一个位置，最后的 --_finish 就可以了。

/// @brief 从容器擦除指定位置的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 移除元素之后的迭代器
iterator erase(iterator pos) {
    assert(pos >= _start && pos < _finish);
    // 在 pos 位置调用析构函数，释放资源
    pos->~T();
    // 将 pos 位置之后的的元素都向前移动一个位置
    iterator it = pos + 1;
    while (it != _finish) {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    // 此时的 pos 指向没删除前 pos 位置下一个元素
    return pos;
}

范围删除同样也很简单，首先要计算出要删除的个数，循环调用 erase 删除就可以了。

注：下面这种循环调用的方式效率十分低，库函数并没有使用这种方法，库函数首先对要删除的范围调用析构函数，然后将区间后面的数据移到前面。这样就只会移动一次数据，不向下面需要移动 cnt 次。

/// @brief 移除一段范围的元素
/// @param first 要移除的起始范围
/// @param last 要移除的结束返回
/// @return 移除的最后一个元素之后的迭代器
iterator erase(iterator first, iterator last) {
    int cnt = last - first;
    while (cnt--) {
        first = erase(first);
    }
    return first;
}

pop_back

pop_back 用来删除容器的最后一个元素，直接调用 erase 删除就行。

/// @brief 移除容器最后一个元素
void pop_back() {
    erase(_finish - 1);
}

swap

swap 函数可以用来交换两个容器的内容，不过不用实际交换数据，只需要改变两个容器指针的指向即可。

/// @brief 交换 this 指向的容器和 v 的内容
/// @param v 要交换内容的容器
void swap(vector<T>& v) {
    // 直接交换所有指针即可
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

到此这篇关于详解C++ STL模拟实现vector的文章就介绍到这了,更多相关C++ STL vector内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！