C++初阶——简单实现vector

目录

1、前言

2、Vector.h

3、Test.cpp

---

1、前言

简单实现std::vector类模板。

相较于前面的string，vector要注意：

深拷贝，因为vector的元素可能是类类型，类类型元素可以通过赋值重载，自己实现深拷贝。

迭代器失效，其实无非是两种(现在认为)：

1. 迭代器更新了，但是认为用的是之前的迭代器，可以先保存值。

2. 迭代器没有更新，但是认为是用更新后的迭代器，那就更新迭代器。

2、Vector.h #pragma once #include <iostream> #include <vector> #include <assert.h> using namespace std; namespace Lzc { template <class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() // 有了拷贝构造，就不会生成默认构造，但是需要默认构造 {} vector(size_t n, const T& val = T())// int有默认构造int(),为了兼容模板 { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } } template <class InputIterator> // 使用别的容器的迭代器初始化 vector(InputIterator first, InputIterator last) { // reserve(last - first); // last - first 有迭代器不支持减 while (first != last) { push_back(*first); ++first; } } vector(const vector<T>& v) { reserve(v.size()); for (int i = 0; i < v.size(); i++) { push_back(v[i]); } } void swap(vector<T>& tmp) { std::swap(_start, tmp._start); std::swap(_finish, tmp._finish); std::swap(_end_of_storage, tmp._end_of_storage); } vector& operator=(const vector<T>& v) { vector tmp(v); swap(tmp); 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; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void clear() { _finish = _start; } bool empty() const { return _finish == _start; } 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 resize(size_t n, const T& val = T()); // resize一般用于扩容+初始化 void reserve(size_t n); void push_back(const T& val) { if (size() == capacity()) reserve(capacity() == 0 ? 4 : 2 * capacity()); *_finish = val; ++_finish; } void pop_back() { assert(size() > 0); --_finish; } iterator insert(iterator pos, const T& val); iterator erase(iterator pos); private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; template<class T> void vector<T>::resize(size_t n, const T& val) // resize一般用于扩容+初始化 { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish < _start + n) { *_finish = val; ++_finish; } } } template<class T> void vector<T>::reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); T* tmp = new T[n]; for (size_t i = 0; i < old_size; i++) { tmp[i] = _start[i]; // 若为类类型，会赋值重载，先释放，再深拷贝 } delete[] _start; _start = tmp; _finish = tmp + old_size; // 不能调用size(),因为_start已更新，所以先保存size() _end_of_storage = tmp + n; } } // vector<T>::iterator编译器认为是类中的静态变量，typename告诉编译器是类型 template<class T> typename vector<T>::iterator vector<T>::insert(iterator pos, const T& val) { assert(pos <= _finish); assert(pos >= _start); if (size() == capacity()) { size_t old_pos = pos - _start; // 扩容后pos没有指向新空间 reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + old_pos; } iterator it = _finish; while (it != pos) { *it = *(it - 1); // 若为类类型，会赋值重载，先释放，再深拷贝 --it; } *pos = val; ++_finish; return pos; } template<class T> typename vector<T>::iterator vector<T>::erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it != end()) { *(it - 1) = *it; // 若为类类型，会赋值重载，先释放，再深拷贝 ++it; } --_finish; return pos; } template<class Container> // 什么容器都能打印 void print_Container(const Container& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; } } 3、Test.cpp #include "Vector.h" #include <list> #include <string> namespace Lzc { void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; //vector<int>::iterator it = v.begin(); auto it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : v) { cout << e << " "; } cout << endl; vector<double> vd; vd.push_back(1.1); vd.push_back(1.2); vd.push_back(1.3); vd.push_back(1.4); vd.push_back(1.5); print_Container(vd); } void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); print_Container(v); // 若iterator insert(iterator& pos, const T& val) // 下面的临时变量(具有常性)，不能传引用 /*v.insert(v.begin() + 2, 30); print_vector(v);*/ int x; cin >> x; auto p = find(v.begin(), v.end(), x); if (p != v.end()) { // insert以后p就是失效，不要直接访问，要访问就要更新这个失效的迭代器的值 /*v.insert(p, 20); (*p) *= 10;*/ p = v.insert(p, 40); (*(p + 1)) *= 10; } print_Container(v); } void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //v.push_back(5); print_Container(v); // 删除所有的偶数 auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); // 删除了，相当于++了 } else { ++it; } } print_Container(v); } void test_vector4() { int i = int(); // int有默认构造int(),为了兼容模板 int j = int(1); int k(2); vector<int> v; v.resize(10, 1); v.reserve(20); print_Container(v); cout << v.size() << endl; cout << v.capacity() << endl; v.resize(15, 2); print_Container(v); v.resize(25, 3); print_Container(v); v.resize(5); print_Container(v); } void test_vector5() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); print_Container(v1); vector<int> v2 = v1; print_Container(v2); vector<int> v3; v3.push_back(10); v3.push_back(20); v3.push_back(30); v1 = v3; print_Container(v1); print_Container(v3); } void test_vector6() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); v1.push_back(4); vector<int> v2(v1.begin(), v1.begin() + 3); print_Container(v1); print_Container(v2); // 1 2 3 list<int> lt; lt.push_back(10); lt.push_back(10); lt.push_back(10); lt.push_back(10); vector<int> v3(lt.begin(), lt.end()); print_Container(lt); print_Container(v3);// 10 10 10 10 vector<string> v4(10, "1111111"); print_Container(v4); vector<int> v5(10); print_Container(v5); vector<int> v6(10u, 1); // 指定构造函数，不然编译器会使用模板函数。 print_Container(v6); // vector(size_t n, const T& val = T()) //vector<int> v7(10, 1); // 编译器会使用模板函数，报错 //print_Container(v7); // 可以再重载一个vector(int n, const T& val = T()) } void test_vector7() // 扩容后需深拷贝 { vector<string> v; v.push_back("11111111111111111111"); v.push_back("11111111111111111111"); v.push_back("11111111111111111111"); v.push_back("11111111111111111111"); print_Container(v); v.push_back("11111111111111111111"); print_Container(v); } } int main() { Lzc::test_vector7(); return 0; }