vector深度剖析及模拟实现
vector.h
#pragma once #include<assert.h> namespace bit { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() {} /*vector(const vector<T>& v) { _start = new T[v.capacity()]; memcpy(_start, v._start, v.size()* sizeof(T)); _finish = _start + v.size(); _endofstorage = _start + v.capacity(); }*/ // v2(v1) vector(const vector<T>& v) { reserve(v.capacity()); for (const 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()) { 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); } // v1 = v3 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, old * sizeof(T)); for (size_t 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()) { 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 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; } void pop_back() { assert(size() > 0); --_finish; } iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); if (_finish == _endofstorage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } //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); assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; ++it; } _finish--; return pos; } 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]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; void print_vector(const vector<int>& v) { for (auto e : v) { cout << e << " "; } cout << endl; } 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(4); v.push_back(4); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : v) { cout << e << " "; } cout << endl; v[0]++; for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; v.insert(v.begin(), 100); print_vector(v); v.insert(v.begin(), 100); print_vector(v); int i = 0; int j = int(); int k = int(10); } 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(4); v.push_back(4); vector<int> v1 = v; for (auto e : v) { cout << e << " "; } cout << endl; for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2; v2.push_back(11); v2.push_back(21); v2.push_back(31); v2.push_back(411); v2.push_back(41); v2.push_back(41); v1 = v2; for (auto e : v1) { cout << e << " "; } cout << endl; for (auto e : v2) { cout << e << " "; } cout << endl; } void test_vector3() { vector<int> v; v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(8); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(15, 1); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(3); for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector4() { vector<string> v; v.reserve(10); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(8); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(15, "yyyy"); for (auto e : v) { cout << e << " "; } cout << endl; 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); for (auto e : v) { cout << e << " "; } cout << endl; v.erase(v.begin()+3); for (auto e : v) { cout << e << " "; } cout << endl; } // 迭代器失效 void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); //v.push_back(7); for (auto e : v) { cout << e << " "; } cout << endl; // 要求删除所有的偶数 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; } void test_vector7() { 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); v.push_back(7); v.push_back(8); v.push_back(9); for (auto e : v) { cout << e << " "; } cout << endl; vector<string> vstr; vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); for (auto e : vstr) { cout << e << " "; } cout << endl; } //指向连续物理空间的指针就是天然的迭代器 void test_vector8() { /*vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); vector<int> v2(v1.begin(), v1.end()); for (auto e : v2) { cout << e << " "; } cout << endl; list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); 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 << " "; } cout << endl;*/ } void test_vector9() { vector<string> v1(5, "1111"); for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2(5, 1); for (auto e : v2) { cout << e << " "; } cout << endl; } }test.cpp
#include<iostream> #include<string> #include<vector> #include<list> #include<algorithm> using namespace std; //string func() //{ // string ret; // //... // // return ret; //} // //int main() //{ // string xx = func(); // // string s1; // cout << sizeof(s1) << endl; // // string s2("1234"); // cout << sizeof(s2) << endl; // // string s3("1111111111111111111111111111111111111111111111"); // cout << sizeof(s3) << endl; // // return 0; //} void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // vector<char> // string // for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; vector<int>::iterator it1 = v.begin(); while (it1 != v.end()) { cout << *it1 << " "; ++it1; } cout << endl; for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector2() { vector<int> v1(10, 1); for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2(v1.begin(), v1.end()); for (auto e : v2) { cout << e << " "; } cout << endl; string s1("12345"); vector<int> v3(s1.begin(), s1.end()); for (auto e : v3) { cout << e << " "; } cout << endl; } void TestVectorExpand() { size_t sz; vector<int> v; v.reserve(100); sz = v.capacity(); cout << "making v grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } } void test_vector3() { TestVectorExpand(); vector<int> v; for (size_t i = 0; i < 100; i++) { v.push_back(i); } cout << v.size() << endl; cout << v.capacity() << endl; v.resize(10); cout << v.size() << endl; cout << v.capacity() << endl; v.shrink_to_fit(); cout << v.size() << endl; cout << v.capacity() << endl; } void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) { cout << e << " "; } cout << endl; v.insert(v.begin(), 0); for (auto e : v) { cout << e << " "; } cout << endl; //vector<int>::iterator it = find(v.begin(), v.end(), 3); auto it = find(v.begin(), v.end(), 3); v.insert(it, 30); for (auto e : v) { cout << e << " "; } cout << endl; list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); auto lit = find(lt.begin(), lt.end(), 3); if (lit != lt.end()) { lt.insert(lit, 300); } for (auto e : lt) { cout << e << " "; } cout << endl; vector<string> vstr; string s1(""); vstr.push_back(s1); vstr.push_back(string("")); vstr.push_back(""); for (const auto& e : vstr) { cout << e << " "; } cout << endl; cout << vstr[0][0] <<'z'<< endl; cout << vstr[0][3] << endl; } #include"vector.h" int main() { //test_vector4(); bit::test_vector9(); return 0; }
