实现模板
#include<assert.h> #include<string.h> #include<iostream> #include<list> using namespace std; namespace fnc { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; //构造函数 vector() { } //复制拷贝 vector(const vector<T>& v) { reserve(v.capacity()); for (const auto& a : v) { push_back(a); } } //迭代器区间构造 template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } } vector(size_t n, const T& val = T()) { resize(n, val); } vector(int n, const T& val = T()) { resize(n, 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() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } //返回对应的位置 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } void reserve(size_t n) { if (n > capacity()) { size_t old = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * old);//不建议 for (int i = 0; i < old; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + old; _endofstorage = _start + n; } } void resize(size_t n, T val = T()) { if (n > size()) { if (n > capacity()) { reserve(n); } //先记住之前的位置 while (_finish < _start + n) { *_finish = val; _finish++; } } else { _finish = _start + n; } } void push_back(const T& x) { //满扩容 if (_finish == _endofstorage) { size_t newcapacity =capacity() == 0 ? 1 : capacity() * 2; reserve(newcapacity); } *_finish = x; _finish++; } void pop_back() { assert(size() > 0); --_finish; } iterator insert(iterator pos,const T& x) { //确保pos是正确的范围内 assert(pos >= _start && pos < _finish); if (_finish == _endofstorage) { size_t distance = pos - _start; size_t newcapacity = capacity() == 0 ? 1 : capacity() * 2; reserve(newcapacity); pos = _start + distance; } //插入腾出空间 //memmove(pos + 1, pos, sizeof(T) * (_finish - pos));//不建议 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } *pos = x; _finish++; return pos; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); //将对应位置挤掉 //memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));//不建议 iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; it++; } --_finish; return pos; } size_t capacity() { return _endofstorage - _start; } size_t size() { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; } size_t size() const { return _finish - _start; } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } private: iterator _start=nullptr; iterator _finish=nullptr; iterator _endofstorage=nullptr; };
首先我们看vector的成员函数，都是通过迭代器来确定具体位置的，
_start表示vector的起始位置，
_finish表示vector有效存储的结束位置，
_endodstorage表示当前开辟的空间指向最后的地址位置
下面通过实例来讲解一些需要注意的地方。
vector和const_vector
对于vector来说，实际上就是C语言的数组，这也就表明vector存储的元素的地址空间是连续的，所以这里的迭代器实际上表示的就是原始指针，但为了区别是否有const修饰，需要对他们进行简单的封装。
被const修饰的迭代器，只具有可读性，对于一些只读的函数，要多加const重载函数。
例子：
void print_vector(const vector<int>& v) { for (auto a : v) { cout << a << " "; } cout << endl; } void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; for (auto a : v) { cout << a << " "; } cout << endl; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; v.insert(v.begin(), 111); print_vector(v); v.insert(v.begin(), 110); print_vector(v); v.erase(v.begin() + 4); print_vector(v); v.erase(v.begin()); print_vector(v); }
如果这里没有添加const修饰的begin和end函数，那么将会报错，因为涉及到权限放大的问题。
resize()和reserve()
reserve()也就是对vector的容量进行扩容，
这里需要对原先的存储进行，方便后面进行对成员变量迭代器的定位。
这里要注意，_finish和_endofstorge都是相对于_start来取相对位置的，因为创建了一个新的空间。
resize()就是改变vector()的有效容量
T是泛型类型，T()表示取对应的默认构造参数，内置类型会取到0，或者nullptr；
自定义类型会根据构造参数进行初始化，取到对应的值；
void test_vector2() { vector<int> myvector; // set some initial content: for (int i = 1; i < 10; i++) myvector.push_back(i); myvector.resize(5); myvector.resize(8, 100); myvector.resize(12); cout << "myvector contains:"; for (int i = 0; i < myvector.size(); i++) cout << ' ' << myvector[i]; std::cout << endl; }
拷贝构造和赋值
这里会发现，我是在成员变量进行了声明，构造函数没有进行初始化；
一开始，我只是在构造函数进行了初始化，而在拷贝构造中没有进行初始化，那么由于这两个函数是构成重载的，所以像一些有指针的，由于没有进行初始化，会变成野指针，这样就会报错。
所以在这里总结：
void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int> v1 = v; cout << "原来的v1 "; for (auto a : v1) { cout << a << " "; } cout << endl; vector<int> v2; v2.push_back(22); v2.push_back(33); v2.push_back(44); v2.push_back(55); v1=v2; cout << "赋值后的v1 "; for (auto a : v1) { cout << a << " "; } cout << endl; }
深浅拷贝的问题
先看例子
void test_vector4() { vector<string> v; v.reserve(10); v.push_back("xxx"); v.push_back("xxx"); v.push_back("xxx"); v.push_back("xxx"); v.push_back("xxx"); v.push_back("xxx"); for (auto a : v) { cout << a << " "; } cout << endl; //n>size v.resize(8); for (auto a : v) { cout << a << " "; } cout << endl; //n>capacity v.resize(15, "yyyy"); for (auto e : v) { cout << e << " "; } cout << endl; //n<size v.resize(3); for (auto e : v) { cout << e << " "; } cout << endl; }
迭代器失效问题
void test_vector5() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); //要求删除所有偶数 vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it=v.erase(it); } else { it++; } } for (auto e : v) { cout << e << " "; } cout << endl; }
vector的其他构造
void test_vector6() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int> v2(v1.begin(), v1.end()); for (auto e : v2) { cout << e << " "; } cout << endl; list<int> lt; lt.push_back(11); lt.push_back(22); lt.push_back(33); lt.push_back(44); vector<int> v3(lt.begin(), lt.end()); for (auto e : v3) { cout << e << " "; } cout << endl; int a[] = { 100,200,300 }; vector<int> v4(a, a + 3); for (auto e : v4) { cout << e << " "; } }
void test_vector7() { vector<string> v1(5, "1234"); for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2(5, 1); for (auto e : v2) { cout << e << " "; } cout << endl; } }
运行： 
