vector介绍
vector 是 C++ 标准库中的一个容器类模板，提供了动态数组的功能。它能够在运行时根据需要自动调整大小，并且支持快速的随机访问。
vector 的特点包括：
- 动态大小： vector 能够自动调整大小以容纳存储的元素。当元素数量增加时，vector 会自动分配更多的内存空间来容纳新的元素。
- 连续存储： vector 使用连续的内存块存储元素，因此可以通过指针算术运算来实现快速的随机访问。
- 快速插入和删除： 在 vector 的末尾插入或删除元素的操作具有较低的时间复杂度。然而，在中间位置插入或删除元素需要移动后续元素的成本较高。
- 随机访问： 可以通过索引来直接访问 vector 中的元素，而不需要遍历整个容器。
- 迭代器支持： vector 提供了迭代器来遍历容器中的元素，包括正向迭代器和反向迭代器。
- 内存管理： vector 负责管理存储元素的内存，可以自动分配和释放内存。
- 使用 vector 可以方便地存储和操作一组元素，它提供了许多成员函数和操作符重载来实现元素的插入、删除、访问和修改等操作。由于 vector 是一个模板类，可以存储任意类型的对象，包括内置类型和自定义类型。
思路
为了实现了一个简化版的动态数组类 vector，我们需要进行以下操作：
- 首先，定义一个 vector 类，并声明了一些成员函数和类型别名。其中 iterator 表示迭代器类型，begin() 和 end() 函数分别返回指向容器起始和结束位置的迭代器。
- 然后，类中的私有成员变量包括 _start、_finish 和 _endofstorage，它们分别表示指向容器起始位置、结束位置和分配的内存结束位置的迭代器。
- 接下来，实现构造函数、拷贝构造函数和范围构造函数，用于创建 vector 对象。构造函数可以接受不同的参数形式，包括空构造、拷贝构造和范围构造。
- 然后，还需要实现一些其他的成员函数：
如 swap() 函数用于交换两个 vector 对象的内容，
operator= 重载函数用于实现赋值操作，
push_back() 函数用于在容器末尾添加元素，
capacity() 函数用于获取容器的容量，
size() 函数用于获取容器的大小，
reserve() 函数用于调整容器的容量，
resize() 函数用于调整容器的大小，并可以指定默认值，
insert() 函数用于在指定位置插入元素，
erase() 函数用于删除指定位置的元素，
operator[] 重载函数用于通过索引访问容器中的元素。
代码
#pragma once #include <assert.h> //模拟实现 namespace hsl { template <class T> class vector { public: typedef T* iterator; iterator begin() { return _start; } iterator end() { return _finish; } vector() {} vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } } template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } } vector(size_t n,const T& val=T()) { for (size_t i = 0; i < n; i++) { push_back(val); } } vector(int n, const T& val = T()) { for (int i = 0; i < n; i++) { push_back(val); } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish,v._finish ); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator =(vector<T>& v) { swap(v); return *this; } ~vector() { delete[] _start; _start = _finish = _endofstorage = nullptr; } void push_back(const T& x) { if (_finish == _endofstorage) { size_t cp; reserve(cp = capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } size_t capacity() const { return _endofstorage - _start; } size_t size() const { return _finish - _start; } void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; size_t sz = size(); if (_start) { // memcpy(tmp, _start, sizeof(T) * n); for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start+sz; _endofstorage = _start + n; } } void resize(size_t n,T val = T()) { if (n <= size()) { _finish = _start + n; } else { reserve(n); /*int begin = size(); while (begin < n) { push_back(val); begin++; }*/ while (_finish < _start + n) { *(_finish) = val; ++_finish; } } } void insert(iterator pos,const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _endofstorage) { 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; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); auto it = pos; while (it < _finish) { *it = *(it + 1); it++; } --_finish; return pos; } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } private: iterator _start=nullptr; iterator _finish=nullptr; iterator _endofstorage=nullptr; }; //测试函数 void test_vector1() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(4); v1.push_back(4); v1.push_back(5); v1.push_back(6); for (auto e : v1) { cout << e << " "; } cout << endl; auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { it=v1.erase(it); } else { it++; } } for (auto e : v1) { cout << e<<" "; } cout << endl; } void test_vector2() { vector<string> v1; v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector3() { vector<int> v1(10,1); vector<int> v2; v2 = v1; for (auto e : v2) { cout << e << " "; } cout << endl; } }
代码（有注释版）
#pragma once #include <assert.h> namespace hsl { template <class T> class vector { public: typedef T* iterator; // 迭代器类型定义为指向 T 类型的指针 iterator begin() // 返回指向容器起始位置的迭代器 { return _start; } iterator end() // 返回指向容器结束位置的迭代器 { return _finish; } vector() // 默认构造函数 {} vector(const vector<T>& v) // 拷贝构造函数 { reserve(v.capacity()); // 根据 v 的容量分配内存 for (auto& e : v) // 遍历 v 中的元素 { push_back(e); // 将元素添加到当前 vector 中 } } template <class InputIterator> vector(InputIterator first, InputIterator last) // 范围构造函数 { while (first != last) // 遍历指定范围内的元素 { push_back(*first); // 将元素添加到当前 vector 中 first++; // 移动迭代器 } } // 构造函数：创建一个指定大小的 vector，并用指定的值进行初始化 vector(size_t n, const T& val = T()) { for (size_t i = 0; i < n; i++) { push_back(val); // 将指定值 val 添加到 vector 中 } } // 构造函数：创建一个指定大小的 vector，并用指定的值进行初始化 vector(int n, const T& val = T()) { for (int i = 0; i < n; i++) { push_back(val); // 将指定值 val 添加到 vector 中 } } // 交换两个 vector 对象的内容 void swap(vector<T>& v) { std::swap(_start, v._start); // 交换容器的起始位置 std::swap(_finish, v._finish); // 交换容器的结束位置 std::swap(_endofstorage, v._endofstorage); // 交换容器的内存结束位置 } // 赋值运算符重载 vector<T>& operator =(vector<T>& v) { swap(v); // 交换当前 vector 和 v 的内容 return *this; // 返回当前 vector 对象 } // 析构函数：释放 vector 对象所占用的内存 ~vector() { delete[] _start; // 释放内存 _start = _finish = _endofstorage = nullptr; // 将迭代器置空 } // 在 vector 的末尾添加一个元素 void push_back(const T& x) { if (_finish == _endofstorage) // 如果内存空间不足 { size_t cp; reserve(cp = capacity() == 0 ? 4 : capacity() * 2); // 扩容 } *_finish = x; // 将元素 x 添加到末尾 ++_finish; // 更新结束位置的迭代器 } // 返回 vector 的容量大小 size_t capacity() const { return _endofstorage - _start; // 返回分配的内存大小 } // 返回 vector 的元素个数 size_t size() const { return _finish - _start; // 返回当前元素个数 } // 调整 vector 的容量 void reserve(size_t n) { if (n > capacity()) // 如果需要的容量大于当前分配的内存大小 { T* tmp = new T[n]; // 申请新的内存空间 size_t sz = size(); if (_start) // 如果原始 vector 不为空 { for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; // 更新起始位置的迭代器 _finish = _start + sz; // 更新结束位置的迭代器 _endofstorage = _start + n; // 更新内存结束位置的迭代器 } } // 调整 vector 的大小，并用指定的值填充新元素 void resize(size_t n, T val = T()) { if (n <= size()) // 如果指定大小小于等于当前元素个数 { _finish = _start + n; // 更新结束位置的迭代器 } else { reserve(n); // 调整容器的容量 while (_finish < _start + n) // 如果结束位置的迭代器还未到达指定大小 { *(_finish) = val; // 添加指定值 val 到结束位置 ++_finish; // 更新结束位置的迭代器 } } } // 在指定位置插入一个元素 void insert(iterator pos, const T& x) { assert(pos >= _start); // 断言：插入位置在合法范围内 assert(pos <= _finish); if (_finish == _endofstorage) // 如果内存空间不足 { 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; // 更新结束位置的迭代器 } // 删除指定位置的元素 iterator erase(iterator pos) { assert(pos >= _start); // 断言：删除位置在合法范围内 assert(pos < _finish); iterator begin = pos + 1; // 获取删除位置的下一个位置的迭代器 while (begin != _finish) // 将元素前移一位 { *(begin - 1) = *begin; ++begin; } --_finish; // 更新结束位置的迭代器 return pos; // 返回删除位置的迭代器 } // 重载 [] 运算符，通过索引访问容器中的元素 T& operator [](size_t index) { assert(index >= 0 && index < size()); // 断言：索引在合法范围内 return _start[index]; // 返回对应索引位置的元素引用 } private: iterator _start; // 指向容器起始位置的迭代器 iterator _finish; // 指向容器结束位置的迭代器 iterator _endofstorage; // 指向容器分配的内存结束位置的迭代器 }; void test_vector1() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(4); v1.push_back(4); v1.push_back(5); v1.push_back(6); for (auto e : v1) { cout << e << " "; } cout << endl; auto it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { it=v1.erase(it); } else { it++; } } for (auto e : v1) { cout << e<<" "; } cout << endl; } void test_vector2() { vector<string> v1; v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); v1.push_back("xxxxxxxxxxxxxxxxxxxxxxxxxxxx"); for (auto e : v1) { cout << e << " "; } cout << endl; } void test_vector3() { vector<int> v1(10,1); vector<int> v2; v2 = v1; for (auto e : v2) { cout << e << " "; } cout << endl; } }
（本章完）
