1.vector类的实现
重要构造定义：
template<class T>class myVector{public: typedef T value_type;//元素类型 起别名 typedef value_type* pointer;// typedef value_type* iterator;//迭代器 typedef value_type& reference;//援用 typedef const value_type* const_pointer;//常量指针 typedef const value_type& const_reference;//常量援用 typedef size_t size_type;//数据类型根本尺寸大小private: iterator start; iterator finish; iterator end_of_storage;供类外部以及派生类应用：
protected://调配空间并填充初始值, 不返回任何值void __allocate_add_fill(size_type n, const T& value){ iterator result = (iterator)malloc(n*sizeof(T)); if (result){//result!=0 申请内存胜利，在失去的内存上创建对象 start = result; end_of_storage = start + n; finish = end_of_storage; while (n--){ //指针偏移，进行赋值 construct(result, value);//在内存上，一个个的进行结构对象 ++result; } } else{ cout << "内存不足，程序终止！" << endl; exit(0); } }//调配空间 从first开始复制n个值到新空间中, 并返回新开拓的空间的首地址 iterator __allocate_and_copy(iterator first, size_type n){ //内存申请 iterator result = (iterator)malloc(n*sizeof(T)); iterator _start = result; if (0 != result){ while(n--){ construct(result, *first); ++result; ++first; } cout << endl; } else{ cout << "内存不足，程序终止！" << endl; exit(0); } return _start; }//将first到last迭代器之间(first,last)的元素拷贝到_start开始的内存中, 并返回 指向 拷贝完所有数据之后最初一个数据的下一个地位的指针 iterator __copy(iterator first, iterator last, iterator _start){ while (first < last){ *_start++ = *first++; } return _start; }//将first到last迭代器之间(first,last)的元素从新赋值iterator __fill(iterator first, iterator last, const T& value){ while (first < last){ *first++ = value; } return first;}//本人写的 从迭代器first开始填充n个值为value的元素iterator __fill_n(iterator first, size_type n, const T& value){ while (n--){ *first++ = value; } return first;}//本人写的 将从 [first,last)所有元素 一一顺次后移， 最初的一个元素移到end的地位void __backCopy(iterator first, iterator last, iterator end){ while (last >= first){ // *end-- = *last--; }}供内部应用的接口：
public: //返回首元素指针 iterator begin(){ return start; } const iterator begin() const { return start; } //返回尾元素下一个地位的指针 iterator end(){ return finish; } const iterator end() const{ return finish; } //------------------ //取元素 本人写 T front(){ return *begin(); }//取vector中第一个元素 T back(){ return *(end() - 1); }//取vector中最初一个元素 //容器大小 size_type size() const{ return (size_type)(end() - begin()); } //容器的理论大小 size_type capacity() const{ return (end_of_storage - begin()); } //判断容器是否为空 bool empty(){ return begin() == end(); }//默认构造函数 myVector() :start(NULL), finish(NULL), end_of_storage(NULL){ cout << "默认构造函数，不调配空间" << endl; }//构造函数重载 myVector(size_type n, const T& value){ __allocate_add_fill(n, value); } myVector(int n, const T&value){ __allocate_add_fill(n, value); } myVector(long n, const T&value){ __allocate_add_fill(n, value); } myVector(size_type n){ __allocate_add_fill(n, T()); }//??? T()?? myVector(int n){ __allocate_add_fill(n, T()); } myVector(long n){ __allocate_add_fill(n, T()); }//元素操作 //删除最初一个元素 void pop_back(){ if (!empty()){ --finish; destroy(finish); } } //删除指定地位上的元素，并返回指向删除元素的迭代器 iterator erase(iterator position){ if (position > begin() && position < end()){ __copy(position + 1, finish, position); } destroy(finish); --finish; return position; }//删除指定范畴的元素 并返回 迭代器返回的元素 iterator erase(iterator first, iterator last){ if (first > begin() && first < last && last < end()){ iterator iter = __copy(last, finish, first); destroy(iter, finish); finish -= (last - first); return first; } } //革除全副元素 void clear(){ erase(begin(), end()); }push_back函数：
//在vector容器的前面增加一个元素，值为value void push_back(const T& value){ if (finish != end_of_storage){//如果新退出元素后，空间够用的话 construct(finish, value); ++finish; } else{//如果新退出元素之后 空间不够用的话 //重新分配空间 const size_type old_size = size(); const size_type new_size = (old_size == 0) ? 1 : 2 * old_size;//如果原空间为0，则配置1的大小，如果原空间不为0，则配置原空间二倍大小的新空间到新的地址 iterator new_start = (iterator)malloc(new_size*sizeof(T)); iterator new_finish = new_start;//开始时，未拷贝前，完结地位等于起始地位 iterator new_capacity = new_start + new_size; //内存调配要具备原子性，即： 要么全副胜利，要么全副失败 try{//1:将原空间的全副元素拷贝到新空间 2:为新的元素设定初始值 3:调整 new_finish for (iterator it = begin(); it < end(); ++it){//1:将原空间的全副元素拷贝到新空间 construct(new_finish, *it); } construct(new_finish, value);//2:为新的元素设定初始值 ++new_finish;//3:调整 new_finish } catch (...){//如果内存调配失败了 destroy(new_start, new_finish); free(new_start);//删除申请到的内存 new_start = NULL; new_finish = NULL; throw("从新分配内存失败！"); } destroy(begin(), end());//析构，并开释原vector free(start);//删除原vector的内存 start = new_start;//更改迭代器，指向新的vector finish = new_finish; end_of_storage = new_start + new_size; } }insert函数：
//插入 在值为value的一个元素到position的地位上 void insert(iterator position, const T& value){ insert(position, 1, value); } //在position地位之后，插入n的值为value的元素 void insert(iterator position, size_type n, const T& value){ if (n == 0)return; if ((end_of_storage - finish) >= n){//备用空间够插入n个新元素 T x_copy = value; const size_type size_from_position_to_end = finish - position; iterator old_finish = finish; if (size_from_position_to_end > n){ //先从pos到oldfinish拿出后n个数，放到前面 //再将pos到剩下的几个数向后挪动到oldfinish //插入n个value到pos->pos+n __copy(finish - n, finish, finish); finish += n; __backCopy(position, old_finish - n, old_finish); __fill(position, position + n, x_copy); } else{ //在前面先插入多的value，而后再将pos到oldfinish的拿进去插到前面 //而后将剩下的value放到pos到oldfinsh __fill_n(finish, n - size_from_position_to_end, x_copy); finish += n - size_from_position_to_end; __copy(position, old_finish, finish); finish += size_from_position_to_end; __fill(position, old_finish, x_copy);//在 } } else{ //从新申请空间 const size_type old_size = size(); size_type _max = 0; if (old_size > n) _max = old_size; else _max = n; const size_type len = old_size + _max; iterator new_start = (iterator)malloc(len * sizeof(T)); iterator new_finish = new_start; //内存的调配要有原子性，即:要么全副胜利，要么全副失败。 try{ new_finish = __copy(begin(), position, new_start);//1.将原内容 至position的所有元素(不蕴含position) 拷贝到新的vector new_finish = __fill_n(new_finish, n, value);//2.将position地位到前面的n个元素都填充为value new_finish = __copy(position, end(), new_finish);//3.拷贝从 position地位到end()地位的原vector的所有残余元素 } catch (...)//如果失败了 { destroy(new_start, new_finish); free(new_start);//删除申请到的内存 new_start = new_finish = NULL; throw; //抛出异样 } //析构并开释原vector destroy(begin(), end()); //删除内存 free(start); //调整迭代器，指向新的vector start = new_start; finish = new_finish; end_of_storage = new_start + len; } }//重载操作符 reference operator[](size_type n){ return *(begin() + n); }//取 第n个元素 const_reference operator[](size_type n) const{ return *(begin() + n); } //两个容器是否相等（每个元素） bool operator==(const myVector&v){ if (v.size() != size())return false; iterator it; for (it = v.begin(); it < v.end(); ++it){ if (*it != *(begin() + (it - v.begin()))) break; } //比拟到了最初就齐全相等 if (it == v.end()) return true; else return false; } bool operator!=(const myVector&v){ return !(operator==(v)); }};2.自定义函数
#pragma oncetemplate<class T1, class T2>inline void construct(T1 *p, const T2 &value){ new (p)T1(value); //用placement new在所指对象上创立一个对象，value是初始化对象的值}template<class T>inline void destroy(T* pointer){//只做了一层包装，将指针所指的对象析构--通过间接调用类的析构函数 pointer->~T();}template<class ForwardIterator>inline void destroy(ForwardIterator first, ForwardIterator last){//destroy的泛化版 承受两个迭代器为参数 for (; first < last; ++first){ destroy(&*first);//得 了解一下 &* }}inline void destroy(char*, char*){};//针对 char* 的特化版inline void destroy(wchar_t*, wchar_t*){};//针对 wchar_t* 的特化版3.测试代码
void display(const myVector<int> &v){ for (myVector<int>::iterator it = v.begin(); it != v.end(); ++it){ cout << *it << " "; } cout << endl;}void test(){ cout << "test--------" << endl; myVector<int> v(100); v.push_back(10); v.push_back(9); v.push_back(8); v.push_back(7); v.push_back(6); v.push_back(5); for (int i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; myVector<int>::iterator it; for (it = v.begin(); it != v.end(); ++it){ cout << *it << " "; } cout << endl; cout << "size: " << v.size() << endl;}void test1(){ cout << "test1--------" << endl; myVector<int> v(100); v.push_back(10); v.push_back(9); v.push_back(8); v.push_back(7); v.push_back(6); v.push_back(5); myVector<int>::iterator it = v.begin() + 3; v.insert(it, 3, 300); display(v); v.insert(it, 4, 500); display(v); v.insert(it, 2, 200); display(v); v.insert(it, 2, 20); display(v); v.insert(it, 3, 30); display(v); v.insert(it, 4, 40); display(v);}void test2(){ cout << "test2--------" << endl; myVector<int> v(100); v.push_back(10); v.push_back(9); v.push_back(8); v.push_back(7); v.push_back(6); v.push_back(5); myVector<int>::iterator it = v.begin(); v.insert(it, 300); display(v); v.insert(it, 500); display(v); v.insert(it, 200); display(v); v.insert(it, 20); display(v); v.insert(it, 30); display(v); v.insert(it, 40); display(v);}运行后果：
/*test--------10 9 8 7 6 5 10 9 8 7 6 5 size: 6test1--------10 9 8 300 300 300 7 6 5 10 9 8 500 500 500 500 300 300 300 7 6 5 10 9 8 200 200 500 500 500 500 300 300 300 7 6 5 10 9 8 20 20 200 200 500 500 500 500 300 300 300 7 6 5 10 9 8 30 30 30 20 20 200 200 500 500 500 500 300 300 300 7 6 5 10 9 8 40 40 40 40 30 30 30 20 20 200 200 500 500 500 500 300 300 300 7 6 5 test2--------300 10 9 8 7 6 5 500 300 10 9 8 7 6 5 200 500 300 10 9 8 7 6 5 20 200 500 300 10 9 8 7 6 5 30 20 200 500 300 10 9 8 7 6 5 40 30 20 200 500 300 10 9 8 7 6 5 Program ended with exit code: 0*/援用:https://github.com/MissStrick...