七、vector
2. vecotr的使用
上节我们以二维数组结束，这一节我们以二维数组开始。
// 二维数组 vector<vector<int>> vv;
二维数组在底层是连续的一维数组。vv[i][j] 是怎样访问的？是 * ( *(a + i) + j) 。
3. vector的模拟实现
细细的学习了 string 之后， vector 上手就非常简单，所以我们现在就来实现一下 vector 。注意，部分内容和 STL 里的 vector 保持一致，需要理解。
我们先开一个头文件：vector.h。把框架补上：
#pragma once namespace my { template<class T> class vector { public: typedef T* iterator; private: // 数据起始地址 iterator _start = nullptr; // 数据末尾地址 iterator _finish = nullptr; // 容量末尾地址 iterator _endofstorage = nullptr; }; }
简单实现一下插入数据：
// vector.h #pragma once #include<assert.h> namespace my { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() {} ~vector() { delete[] _start; _start = _finish = _endofstorage = nullptr; } size_t size() const { // 数据个数 return _finish - _start; } size_t capacity() const { // 容量大小 return _endofstorage - _start; } // 下标 + [] 访问 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } void push_back(const T& val) { // 判断扩容 if (_finish == _endofstorage) { // 保留 size size_t old_size = size(); // 2倍扩容 size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); // 开空间 T* tmp = new T[newcapacity]; // 拷贝内容, 注意字节数 memcpy(tmp, _start, size() * sizeof(T)); // 释放旧空间 delete[] _start; // 更改地址 _start = tmp; _finish = _start + old_size; _endofstorage = _start + newcapacity; } // 插入数据 *_finish = val; ++_finish; } private: // 数据起始地址 iterator _start = nullptr; // 数据末尾的下一个地址 iterator _finish = nullptr; // 容量末尾的下一个地址 iterator _endofstorage = nullptr; }; void test01() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (int i = 0; i < v.size(); ++i) { std::cout << v[i] << " "; } std::cout << std::endl; } }
注意细节：在 push_back 函数里面，扩容的时候需要保存旧的 size 的值，当发生扩容时，_finish 已经发生改变，会出严重错误！！。
我们将测试函数放在 my命名空间内，vector 类外 。
然后是源文件：test.cpp
// test.cpp #include<iostream> #include"vector.h" using namespace std; int main() { // 命名空间域内的测试函数 my::test01(); return 0; }
嗯，不错，接下来实现迭代器，还是那句话，迭代器是行为像指针的东西，不一定是指针，但是我们简单的模拟实现就将其当作指针实现：
// 类内 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
// 测试区 void test02() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::iterator it = v.begin(); while (it != v.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; }
// test.cpp #include<iostream> #include"vector.h" using namespace std; int main() { my::test02(); return 0; }
我们需要一个通用的扩容函数 reserve 。
void reserve(size_t n) { // 比当前容量大才允许扩容 if (n > capacity()) { size_t old_size = size(); // 开空间 T* tmp = new T[n]; // 拷贝内容, 注意字节数 memcpy(tmp, _start, size() * sizeof(T)); // 释放旧空间 delete[] _start; // 更改地址 _start = tmp; _finish = _start + old_size; _endofstorage = _start + n; } }
于是，我们的 push_back 函数可以复用 reserve 了。
void push_back(const T& val) { // 判断扩容 if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } // 插入数据 *_finish = val; ++_finish; }
接下来实现尾删 pop_back 和判空函数 empty 。
// 尾删 void pop_back() { assert(!empty()); --_finish; } // 判断容器是否为空 bool empty() { return _start == _finish; }
还有 insert 插入函数：
void insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _finish); // 记录相对位置 size_t len = pos - _start; if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } // 如果发生异地扩容，需要更新 迭代器 ，否则将会发生迭代器失效 pos = _start + len; iterator it = _finish - 1; while (it >= pos) { *(it + 1) = *it; --it; } *pos = val; ++_finish; }
测试一下：
// 测试区 void test03() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); // 头部插入一个0 v.insert(v.begin(), 0); // 尾删 v.pop_back(); for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; }
// test.cpp #include<iostream> #include"vector.h" using namespace std; int main() { my::test03(); return 0; }
既然 insert 没有问题，那么。。push_back 又可以复用了。
void push_back(const T& val) { 判断扩容 //if (_finish == _endofstorage) //{ // reserve(capacity() == 0 ? 4 : 2 * capacity()); //} 插入数据 //*_finish = val; //++_finish; insert(end(), val); }
非常nice啊，继续实现 erase 。
void erase(iterator pos) { assert(pos >= _start); // 不要等于 _finish assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; ++it; } --_finish; }
有了 erase ，pop_back 就可以复用了。
// 尾删 void pop_back() { //assert(!empty()); // //--_finish; erase(end() - 1); --_finish; }
再实现 resize 。我们先给个框架。很多人对后面的第二个参数有疑问，那是什么？
void resize(size_t n, const T& val = T()) { }
我们的 vector 使用的是模板，不能锁死任意一个类型，所以不能冒然的 等于0 啊之类的，万一是个类不久出大问题了吗？所以这里是 调用无参的匿名对象的构造函数 ，看是看懂了，但是，这不本末倒置了吗？，这让内置类型怎么办？内置类型难道有构造函数？嘿，你还真别说，内置类型还真有构造函数等等 。祖师爷就是为了解决这种问题，他将内置类型给升级成了，有点厉害啊。所以，内置类型也能这样玩：
int i = 1; int i = int(); int i = int(2);
内置类型的默认值：int就是0，double就是0.0，指针类型就是nullptr 这样。这么看来，上面的第二个参数就能理解了吧。resize 的实现其实非常简单：
void resize(size_t n, const T& val = T()) { // 插入数据 if (n > size()) { reserve(n); while (_finish < _start + n) { *_finish = val; ++_finish; } } // 删除数据 else { _finish = _start + n; } }
ok，我们来测试一下：
// 测试区 void test04() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.resize(10); for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; v.resize(30, 7); for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; v.resize(3); for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; }
// test.cpp #include<iostream> #include"vector.h" using namespace std; int main() { my::test04(); return 0; }
最后，再写一个 拷贝构造函数 ，这个拷贝构造函数将会非常 玄幻。直接上菜：
vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } }
没错，就是用 auto，自动匹配类型，创建出一个 vector< T >。
测试一下：
// 测试区 void test05() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; vector<int> v1(v); for (auto e : v1) { std::cout << e << " "; } std::cout << std::endl; }
// tset.cpp #include<iostream> #include"vector.h" using namespace std; int main() { my::test05(); return 0; }
非常 nice 啊。
