首页 > 代码库 > 自己动手实现简单的Vector
自己动手实现简单的Vector
看到今天，终于自己动手写了一个自己的vector，我这个版本的vector只有vector主要的一些操作，包括原版vector的所有构造函数，begin(),end(),size(),capacity(),empty(),erase(),clear(),pop_back,push_back(),重载了[],==,!=操作符等.其中有个比较重要的insert()，我暂时没写。其实和push_back差不多，只不过考虑的条件更多，代码更复杂，逻辑并不难。废话不多说，现将我的vector代码贴出来：
/*
自己动手实现vector，不用alloc配置器，就用一般的 malloc/free
*/
1 #ifndef __MY_VECTOR_H 2 #define __MY_VECTOR_H 3 #include<cstddef> 4 #include "construct.h" 5 template<class T> 6 class My_vector 7 { 8 public: 9 typedef T value_type; 10 typedef value_type* pointer; 11 typedef value_type* iterator; 12 typedef value_type& reference; 13 typedef const value_type* const_pointer; 14 typedef const value_type* const_iterator; 15 typedef const value_type& const_reference; 16 typedef size_t size_type; 17 protected: 18 void __allocate_and_fill(size_type n, const T& value) //分配空间，并填充初始值 19 { 20 iterator result = (iterator)malloc(n*sizeof(T)); 21 if(0 != result) 22 { 23 //申请内存成功，在得到的内存上创建对象！ 24 start = result; 25 end_of_storage = start + n; 26 finish = end_of_storage; 27 while(n--) 28 { 29 construct(result,value); //在内存上，一个个的进行构造对象 30 ++result; 31 } 32 } 33 else 34 { 35 cout << "内存不足，程序终止！" << endl; 36 exit(0); 37 } 38 } 39 iterator __allocate_and_copy(iterator first,iterator last,size_type n) //分配空间，并复制值到空间中 40 { 41 iterator result = (iterator)malloc(n*sizeof(T)); 42 iterator _start = result; 43 if( 0 != result) 44 { 45 while(n--) 46 { 47 construct(result,*first); 48 ++result; 49 ++first; 50 } 51 cout << endl; 52 } 53 else 54 { 55 cout << "内存不足，程序终止！" << endl; 56 exit(0); 57 } 58 return _start; 59 } 60 //将first到last迭代器之间[first,last)的元素拷贝到_start开始的内存中 61 iterator __copy(iterator first,iterator last,iterator _start) 62 { 63 while(first < last) 64 { 65 *_start++ = *first++; 66 } 67 return _start; 68 } 69 public: 70 //返回首元素指针 71 iterator begin() { return start; } 72 const iterator begin() const { return start;} 73 //返回尾元素下一个位置的指针 74 iterator end() { return finish; } 75 const iterator end() const { return finish;} 76 //容器的大小 77 size_type size() const { return (size_type)(end() - begin()); } 78 //容器的实际大小 79 size_type capacity() const { return (size_type)(end_of_storage - begin()); } 80 //判断容器是否为空 81 bool empty() { return begin() == end(); } 82 //typedef ptrdiff_t difference_type; 83 //默认构造函数 84 My_vector():start(0),finish(0),end_of_storage(0){ cout << "默认构造函数，不分配空间" << endl;} 85 //构造函数重载 C c(n,t): 86 My_vector(size_type n, const T& value) { __allocate_and_fill(n, value);} 87 My_vector(int n, const T& value) { __allocate_and_fill(n, value); } 88 My_vector(long n, const T& value) { __allocate_and_fill(n, value); } 89 //构造函数重载 C c(n): 90 My_vector(size_type n) { __allocate_and_fill(n, T()); } 91 My_vector(int n) { __allocate_and_fill(n, T()); } 92 My_vector(long n) { __allocate_and_fill(n, T()); } 93 //构造函数重载 C c2(c1) 94 My_vector(const My_vector<T>& mv) 95 { 96 start = __allocate_and_copy(mv.begin(), mv.end(),mv.end() - mv.begin()); 97 finish = start + (mv.end() - mv.begin()); 98 end_of_storage = finish; 99 } 100 //构造函数重载 C c2(b,e) 101 My_vector(const iterator& b,const iterator& e) 102 { 103 start = __allocate_and_copy(b,e,size_type(e - b + 1)); 104 finish = start + (e - b + 1); 105 end_of_storage = finish; 106 } 107 //元素操作 108 //删除最后一个元素 109 void pop_back() 110 { 111 if(!empty()) 112 { 113 --finish; 114 destroy(finish); 115 } 116 } 117 //删除指定位置上的元素,返回指向删除元素的迭代器 118 iterator erase(iterator position) 119 { 120 if(position > begin() && position < end()) 121 { 122 __copy(position + 1,finish,position); 123 } 124 --finish; 125 destroy(finish); 126 return position; 127 } 128 //重载erase,根据迭代器范围删除 129 iterator erase(iterator first,iterator last) 130 { 131 iterator i = __copy(last,finish,first); 132 destroy(i,finish); 133 finish -= (last - first); 134 return first; 135 } 136 //清除全部元素 137 void clear() 138 { 139 erase(begin(),end()); 140 } 141 //在vector 容器后面增加一个元素 142 void push_back(const T& value) 143 { 144 if(finish != end_of_storage) //如果还有备用空间 145 { 146 construct(finish,value); 147 ++finish; 148 } 149 else 150 { 151 //重新申请空间 152 const size_type old_size = size(); 153 const size_type new_size = (old_size == 0)?1:2*old_size; 154 iterator new_start = (iterator)malloc(new_size * sizeof(T)); 155 iterator new_finish = new_start; 156 //内存的分配要有原子性，即:要么全部成功，要么全部失败。 157 try{ 158 //1.将原内容拷贝到新的vector 159 //2.为新的元素设定初值x 160 //3.调整new_finish 161 for(iterator it = begin();it < end(); ++it) 162 { 163 //cout << "it:" << *it << " "; 164 construct(new_finish++,*it); 165 } 166 construct(new_finish,value); 167 ++new_finish; 168 } 169 catch(...) 170 { 171 //如果失败了 172 destroy(new_start,new_finish); 173 //删除申请到的内存 174 free(new_start); 175 new_start = finish = NULL; 176 throw; //抛出异常 177 } 178 179 //析构并释放原vector 180 destroy(begin(),end()); 181 //删除内存 182 free(start); 183 //调整迭代器，指向新的vector 184 start = new_start; 185 finish = new_finish; 186 end_of_storage = new_start + new_size; 187 } 188 } 189 //insert--这个好多代码，不想写 190 void insert(iterator position,size_type n,const T& value) 191 { 192 } 193 void insert(iterator position,const T& value) 194 { 195 insert(position,1,value); 196 } 197 //重载操作符 198 reference operator[](size_type n){ return *(begin() + n); } 199 const_reference operator[](size_type n) const{ return *(begin() + n); } 200 bool operator==(const My_vector& mv) 201 { 202 if(mv.size() != size()) 203 return false; 204 for(iterator it = mv.begin();it < mv.end(); ++it) 205 { 206 if(*it != *(begin() + (it - mv.begin()))) 207 break; 208 } 209 if(it == mv.end()) 210 return true; 211 else 212 return false; 213 } 214 bool operator!=(const My_vector& mv) 215 { 216 return !(operator==(mv)); 217 } 218 private: 219 iterator start; 220 iterator finish; 221 iterator end_of_storage; 222 }; 223 #endif
其中包含的 "construct.h" 文件代码如下：
1 template <class T> 2 inline void destroy(T* pointer) { 3 pointer->~T(); //只是做了一层包装，将指针所指的对象析构---通过直接调用类的析构函数 4 } 5 6 template <class T1, class T2> 7 inline void construct(T1* p, const T2& value) { 8 new (p) T1(value); //用placement new在 p 所指的对象上创建一个对象，value是初始化对象的值。 9 } 10 11 template <class ForwardIterator> //destroy的泛化版，接受两个迭代器为参数 12 inline void destroy(ForwardIterator first, ForwardIterator last) { 13 for ( ; first < last; ++first) 14 destroy(&*first); 15 } 16 17 18 inline void destroy(char*, char*) {} //针对 char * 的特化版 19 inline void destroy(wchar_t*, wchar_t*) {} //针对 wchar_t*的特化版
现将测试My_vector的代码也贴出来：
1 #include<iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 My_vector<int>::iterator it; 8 9 //默认构造函数 10 My_vector<int> mvec; 11 cout << mvec.begin() << " " << mvec.end() << endl; 12 cout << "size=" << mvec.size() << endl; 13 cout << "capacity=" << mvec.capacity() << endl; 14 for(it = mvec.begin();it < mvec.end(); ++it) 15 { 16 cout << *it << " "; 17 } 18 cout << endl; 19 //根据元素个数和一个初始值的构造函数 20 My_vector<int> mvecnt(2,9); 21 cout << mvecnt.begin() << " " << mvecnt.end() - 1 << endl; 22 cout << "size=" << mvecnt.size() << endl; 23 cout << "capacity=" << mvecnt.capacity() << endl; 24 for(it = mvecnt.begin();it < mvecnt.end(); ++it) 25 { 26 cout << *it << " "; 27 } 28 cout << endl; 29 30 My_vector<int> mvecnt1(2,9); 31 cout << mvecnt1.begin() << " " << mvecnt1.end() - 1 << endl; 32 cout << "size=" << mvecnt1.size() << endl; 33 cout << "capacity=" << mvecnt1.capacity() << endl; 34 for(it = mvecnt1.begin();it < mvecnt1.end(); ++it) 35 { 36 cout << *it << " "; 37 } 38 cout << endl; 39 mvecnt1.pop_back(); 40 cout << "size=" << mvecnt1.size() << endl; 41 //测试 != 和 == 42 if(mvecnt != mvecnt1) 43 cout << "mvecnt != mvecnt1" << endl; 44 else if(mvecnt == mvecnt1) 45 cout << "mvecnt == mvecnt1" << endl; 46 //根据元素个数的构造函数 47 My_vector<int> mvecn(4); 48 cout << mvecn.begin() << " " << mvecn.end() - 1 << endl; 49 cout << "size=" << mvecn.size() << endl; 50 cout << "capacity=" << mvecn.capacity() << endl; 51 for(it = mvecn.begin();it < mvecn.end(); ++it) 52 { 53 cout << *it << " "; 54 } 55 cout << endl; 56 //复制构造函数 57 My_vector<int> mvecc(mvec); 58 cout << mvecc.begin() << " " << mvecc.end() - 1 << endl; 59 cout << "size=" << mvecc.size() << endl; 60 cout << "capacity=" << mvecc.capacity() << endl; 61 for(it = mvecc.begin();it < mvecc.end(); ++it) 62 { 63 cout << *it << " "; 64 } 65 cout << endl; 66 //根据两个迭代器构造函数 67 int arr[6] = {1,2,3,4,5,6}; 68 My_vector<int> mvecbe(&arr[0],&arr[5]); 69 cout << mvecbe.begin() << " " << mvecbe.end() - 1 << endl; 70 cout << "size=" << mvecbe.size() << endl; 71 cout << "capacity=" << mvecbe.capacity() << endl; 72 for(it = mvecbe.begin();it < mvecbe.end(); ++it) 73 { 74 cout << *it << " "; 75 } 76 cout << endl; 77 //以上5个构造函数测试完毕 78 //测试 pop_back() 79 mvecbe.pop_back(); 80 cout << "size=" << mvecbe.size() << endl; 81 cout << "capacity=" << mvecbe.capacity() << endl; 82 for(it = mvecbe.begin();it < mvecbe.end(); ++it) 83 { 84 cout << *it << " "; 85 } 86 cout << endl; 87 //测试 erase(); 88 mvecbe.erase(mvecbe.begin() + 1,mvecbe.begin() + 3); 89 cout << "size=" << mvecbe.size() << endl; 90 cout << "capacity=" << mvecbe.capacity() << endl; 91 for(it = mvecbe.begin();it < mvecbe.end(); ++it) 92 { 93 cout << *it << " "; 94 } 95 cout << endl; 96 //测试clear() 97 mvecbe.clear(); 98 cout << "size=" << mvecbe.size() << endl; 99 cout << "capacity=" << mvecbe.capacity() << endl; 100 for(it = mvecbe.begin();it < mvecbe.end(); ++it) 101 { 102 cout << *it << " "; 103 } 104 cout << endl; 105 cout << mvecbe[0] << endl; 106 //以下测试push_back() 107 mvec.push_back(7); 108 cout << mvec.begin() << " " << mvec.end() << endl; 109 cout << "size=" << mvec.size() << endl; 110 cout << "capacity=" << mvec.capacity() << endl; 111 for(it = mvec.begin();it < mvec.end(); ++it) 112 { 113 cout << *it << " "; 114 } 115 cout << endl; 116 mvec.push_back(3); 117 cout << "size=" << mvec.size() << endl; 118 cout << "capacity=" << mvec.capacity() << endl; 119 for(it = mvec.begin();it < mvec.end(); ++it) 120 { 121 cout << *it << " "; 122 } 123 cout << endl; 124 mvec.push_back(4); 125 cout << "size=" << mvec.size() << endl; 126 cout << "capacity=" << mvec.capacity() << endl; 127 for(it = mvec.begin();it < mvec.end(); ++it) 128 { 129 cout << *it << " "; 130 } 131 cout << endl; 132 mvec.push_back(9); 133 cout << "size=" << mvec.size() << endl; 134 cout << "capacity=" << mvec.capacity() << endl; 135 for(it = mvec.begin();it < mvec.end(); ++it) 136 { 137 cout << *it << " "; 138 } 139 cout << endl; 140 mvec.push_back(0); 141 cout << "size=" << mvec.size() << endl; 142 cout << "capacity=" << mvec.capacity() << endl; 143 for(it = mvec.begin();it < mvec.end(); ++it) 144 { 145 cout << *it << " "; 146 } 147 cout << endl; 148 return 0; 149 }
代码可能比较长，也比较乱。初始尝试写vector，以后会将vector的功能补全，并将其写成一个可以直接调用的头文件！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。