PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C++语言基础(17-1)_STL容器vector的简易自己实现

前面学习了C++的STL中容器的一些内容,今天尝试自己写一个有部分vector功能的类模板,熟悉模板的使用。

 

Vector实际上是个动态数组,主要就是要解决内存的动态分配问题。

这里定义了这些成员变量:

using iterator = T*; //typedef T* iterator;

iterator m_start; //起始位置指针 相当于 T* m_start

iterator m_finish; //有数据的结束位置指针

iterator m_end_of_storage; //存储空间的结束位置指针

每次在增加元素进vector的时候,都要去检查是不是有多的内存空间可以存储,假如没有,那么就需要扩充内存,扩充的标准是当前内存的1.5倍(为了提高效率)。因为vector是连续内存,所以扩充内存的时候是分几个步骤做的:

第1步,重新new内存,大小按照扩充后的需求;

第2步,把原先内存的数据全部复制到新内存空间;

第3步,删除原先的内存空间。

具体实现的功能,可以看下面的代码,对于定点插入,定点删除,因为时间关系没有去实现,但其实和顺序表的插入删除是一样的。

//ppcvector.h
//xvector 类模板

#pragma once
#ifndef _PPCVECTOR_H
#define _PPCVECTOR_H
#include <assert.h>

template<class T>
class xvector {
public:
 using iterator = T*; //typedef T* iterator;
private:
 iterator _newMemory(size_t len); //创建新内存
 void _deleteMemory(iterator it); //删除内存
 void _copy(iterator itSrc, iterator itDst, size_t len); //复制内存
 void _Reserve(size_t _Count); //增加_Count个内存
public:
 xvector() { m_start = m_finish = m_end_of_storage = NULL;} //无参构造,不分配内存
 xvector(size_t n, const T& other); //构造n个相同的other
 xvector(const T& other) :xvector(1, other) {}; //拷贝构造
 ~xvector() { if (m_start) _deleteMemory(m_start); } //析构
public:
 int size() const { return m_finish - m_start; } //求有值的大小
 int capacity() const { return m_end_of_storage - m_start; } //求内存的大小
 bool empty() { return size() == 0 ? true : false; }
 T& operator[](int pos) const { return *(m_start + pos); } //[]重载
 T& at(int pos) const { assert(pos >= 0 && pos < size()); return *(m_start + pos);}
 iterator begin() const { return m_start; }
 iterator end() const { return m_finish; }
 T& front() const { return *m_start; }
 T& back() const { return *(m_finish - 1); }
 T& pop_back(); //删除最后1个元素
 void clear(); //清空
public:
 void reserve(size_t n); //分配内存
 void push_back(const T& other); //尾部插入数据
 void assign(size_t _Count, const T& _Val); //添加_Count个_Val进去
 xvector<T>& operator=(const xvector<T>& other); //赋值重载
private:
 iterator m_start; //起始位置指针
 iterator m_finish; //有数据的结束位置指针
 iterator m_end_of_storage; //存储空间的结束位置指针
};

template<class T> //注意: 这里其实是 T* 但是不能直接写iterator,必须按照下面的写 typename ...
typename xvector<T>::iterator xvector<T>::_newMemory(size_t len) { //创建新内存
 iterator itTmp = new T[len];
 assert(itTmp != NULL);
 return itTmp;
}

template<class T>
void xvector<T>::_deleteMemory(iterator it) { //删除内存
 if (it != NULL)
 delete[] it;
}

template<class T>
void xvector<T>::_copy(iterator itSrc, iterator itDst, size_t len) { //复制内存
 memcpy_s(itDst, sizeof(T)*len, itSrc, sizeof(T)*len);
}
template <class T>
void xvector<T>::_Reserve(size_t _Count) { //增加_Count个内存
 if (_Count == 0) return;
 size_t newlen = capacity() + _Count;
 iterator itTmp = new T[newlen]; //新分配内存
 assert(itTmp != NULL);
 _copy(m_start, itTmp, capacity());
 m_finish = itTmp + size();
 if (m_start)
 _deleteMemory(m_start); //删除原来的内存
 m_start = itTmp;
 m_end_of_storage = m_start + newlen;
}
template<class T>
xvector<T>::xvector(size_t _Count, const T& other) { //构造n个相同的other
 m_start = m_finish = m_end_of_storage = NULL;
 _Reserve(_Count);
 for (size_t i = 0; i < _Count; ++i)
 m_start[i] = other;
 m_finish = m_start + _Count;
 m_end_of_storage = m_finish; 
}
template<class T>
void xvector<T>::reserve(size_t _Count) { //分配内存,假如当前内存比这个大,不操作
 if (_Count <= (m_end_of_storage - m_start))
 return;
 _Reserve(_Count - (m_end_of_storage - m_start));
}

template<class T>
void xvector<T>::push_back(const T& other) { //尾部插入数据
 if (m_end_of_storage - m_finish == 0) { //需要重新分配新内存
 int newlen = (m_end_of_storage - m_start) * 1.5;
 newlen = newlen > (m_end_of_storage - m_start) ? newlen : newlen + 1; //确保有1的增加
 _Reserve(newlen - (m_end_of_storage - m_start)); //增加内存
 }
 *m_finish++ = other;
}

template<class T>
void xvector<T>::assign(size_t _Count, const T& _Val) { //添加_Count个_Val进去
 if (_Count == 0) return;
 _Reserve(_Count);
 for (size_t i = 0; i < _Count; ++i) 
 push_back(_Val);
}
template <class T>
xvector<T>& xvector<T>::operator=(const xvector<T>& other) { //赋值重载 注意返回值是 &
 if (capacity() < other.size()) //内存不够,增加
 _Reserve(other.size() - capacity());
 _copy(other.begin(), m_start, other.size());
 m_finish = m_start + other.size();
 return *this;
}
template<class T>
void xvector<T>::clear() {
 _deleteMemory(m_start);
 m_start = m_finish = m_end_of_storage = NULL;
}

template<class T>
T& xvector<T>::pop_back() { //删除最后1个元素
 assert(!empty());
 return *(--m_finish);
}

#endif

 

(2017-04-16 www.vsppc.com)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C++语言基础(17-1)_STL容器vector的简易自己实现

分享到:更多 ()

评论 74

评论前必须登录!