曾经在论坛上看到面试时候被问到STL中Vector的实现,想想如果真的要实现Vector的源码,仅仅是一个Allocator就非常麻烦,一二时分钟内是搞不定的,面试官出这道题也就是想知道你对STL的实现理解程度。
template<class Object>
class Vector
{
public:
explicit Vector(int initsize=0)
:theSize(initsize),theCapacity(initsize+SPACE_CAPACITY)
{
datas=new Object[theCapacity];
}
Vector(const Vector & rhs):datas(NULL)
{
operator=(rhs);
}
~Vector()
{
delete []datas;
}
const Vector & operator=(const Vector& rhs)
{
if(&rhs!=this)
{
delete []datas;
theSize=rhs.size();
theCapacity=rhs.capacity();
datas=new Object[theCapacity];
for(int k=0;k<theSize;++k)
datas[k]=rhs.datas[k];
}
return *this;
}
void resize(int newSize)
{
if(newSize>theCapacity)
reserve(newSize*2+1);
theSize=newSize;
}
void reserve(int newCapacity)
{
if(newCapacity<theSize) return;
Object* olddatas=datas;
datas=new Object[newCapacity];
for(int k=0;k<theSize;++k)
datas[k]=olddatas[k];
theCapacity=newCapacity;
delete []olddatas;
}
Object& operator[](int index)
{
return datas[index];
}
const Object& operator[](int index) const
{
return datas[index];
}
bool empty() const
{
return theSize==0;
}
int size() const
{
return theSize;
}
int capacity() const
{
return theCapacity;
}
void push_back(const Object & x)
{
if(theSize==theCapacity)
reserve(2*theCapacity+1);
datas[theSize++]=x;
}
void pop_back()
{
theSize--;
}
const Object& back() const
{
return datas[theSize-1];
}
typedef Object* iterator;
typedef const Object* const_iterator;
iterator begin()
{
return &datas[0];
}
const_iterator begin() const
{
return &datas[0];
}
iterator end()
{
return &datas[size()];
}
const_iterator end() const
{
return &datas[size()];
}
enum {SPACE_CAPACITY=16};
private:
int theSize;
int theCapacity;
Object * datas;
};
下面一个是CSDN上看到的:
#include <iostream>
#include <new>
using namespace std;
template <class T>
class Iterator
{
public:
Iterator(): m_pData(NULL),m_nSize(0), m_nLen(0)
{
}
virtual ~Iterator()
{
if (NULL != m_pData)
{
delete[] m_pData;
m_pData = NULL;
}
}
public:
virtual T* begin() = 0;
virtual T* end() = 0;
protected:
int m_nSize;
int m_nLen;
T *m_pData;
};
template <class T>
class CMyVector : public Iterator<T>
{
public:
typedef T* iterator;
public:
CMyVector(int nSize = 10)
{
if (nSize <= 0)
{
nSize = 10;
}
m_nSize = nSize;
m_pData = new T[m_nSize];
}
~CMyVector()
{
}
public:
int Length() const
{
return m_nLen;
}
bool push_back(T obj)
{
if (m_nLen >= m_nSize)
{
int nSize = m_nSize * 2 + 1;
T *pTemp = new(nothrow) T[nSize];
if (!pTemp)
{
return false;
}
memcpy(pTemp, m_pData, sizeof(T) * m_nLen);
delete []m_pData;
m_pData = pTemp;
m_nSize = nSize;
}
memcpy(m_pData + m_nLen, &obj, sizeof(obj));
m_nLen++;
return true;
}
public:
virtual T* end()
{
return m_pData + m_nLen;
}
virtual T* begin()
{
return m_pData;
}
};
int main(int argc, char* argv[])
{
CMyVector<int> vtData;
CMyVector<int>::iterator it;
for (int i = 0; i < 30; i++)
{
vtData.push_back(i);
}
cout << "vector data: " << endl;
for (it = vtData.begin(); it != vtData.end(); it++)
{
cout << *it << "\t";
}
cout << endl;
return 0;
}
联系客服