《STL系列》之vector原理及实现 |
您所在的位置：网站首页 › vector的原理 › 《STL系列》之vector原理及实现 |
《STL系列》之vector原理及实现
|
最近忙得蛋疼，但还是想写点属于自己的东西。也不知道写点啥，最后决定试着自己实现STL中常用的几个集合，一来加深自己对STL的理解，二来看看自己是否有这个能力实现。实现目标就是：1能和STL兼容；2最大化的实现STL中的接口并保持一致。即将STL中的集合换成我写的也能用。这篇博客介绍的是vector的原理及实现。 先把vector的大致实现说一下，后面会给出完整的源码。 新增元素：Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。插入新的数据分在最后插入push_back和通过迭代器在任何位置插入，这里说一下通过迭代器插入，通过迭代器与第一个元素的距离知道要插入的位置，即int index=iter-begin()。这个元素后面的所有元素都向后移动一个位置，在空出来的位置上存入新增的元素。 void insert(const_iterator iter,const T& t ) { int index=iter-begin(); if (index等, 通过这些方法可以找到当前元素或是别的元素. vector是STL集合中比较特殊的一个,因为vector中的每个元素都是连续的,所以在自己实现vector的时候可以用指针代替,如typedef T* iterator;typedef const T* const_iterator，如果STL中的函数能方便的操作自己写的集合，实现的迭代器最好继承std::iterator。我实现vector的迭代器大概是这个样子： template class viterator:public std::iterator{} 后面会给出完整的代码，std::iterator的源码如下： template struct iterator { // base type for all iterator classes typedef _Category iterator_category; typedef _Ty value_type; typedef _Diff difference_type; typedef _Diff distance_type; // retained typedef _Pointer pointer; typedef _Reference reference; };
Iterator其中没有任何成员，只是定义了一组类型，所以继承它并不会让你的struct变大，这组类型是STL的内部契约，STL中的函数假设每个迭代器都定义了这些类型，所以只要你的迭代器定义了这些类型，就可以和STL函数集合一起使用。 我的vector实现源码如下：  
#ifndef _CVECTOR_H_
#define _CVECTOR_H_
namespace cth
{
class NoCopy
{
public:
inline NoCopy(){}
NoCopy(const NoCopy&);
NoCopy& operator=(const NoCopy&);
};
template
class viterator:public std::iterator
{
public:
viterator()
{
t=NULL;
}
viterator(T* t_)
{
t=t_;
}
viterator(const viterator& other)
{
t=other.t;
}
viterator& operator=(const viterator& other)
{
t=other.t;
return *this;
}
viterator& operator++()
{
t++;
return *this;
}
viterator operator++(int)
{
viterator iter=*this;
t++;
return iter;
}
viterator operator+(int count)
{
viterator iter=*this;
iter.t+=count;
return iter;
}
viterator& operator--()
{
t--;
return *this;
}
viterator operator--(int)
{
viterator iter=*this;
t--;
return iter;
}
viterator operator-(int count)
{
viterator iter=*this;
iter.t-=count;
return iter;
}
int operator-(const viterator& other)
{
return t-other.t;
}
int operator-(const viterator& other)const
{
return t-other.t;
}
T& operator*()
{
return *t;
}
const T& operator*() const
{
return *t;
}
T* operator->()
{
return t;
}
const T* operator->() const
{
return t;
}
inline bool operator!=(const viterator& other)
{
return t!=other.t;
}
inline bool operator!=(const viterator& other)const
{
return t!=other.t;
}
inline bool operator==(const viterator& other)
{
return t==other.t;
}
inline bool operator==(const viterator& other)const
{
return t==other.t;
}
inline bool operator=other.t;
}
private:
T* t;
};
template
class cvector:public NoCopy
{
public:
typedef viterator iterator;//viterator就是对一个指针的包装，所以完全可以用T*代替viterator
typedef const viterator const_iterator;
//typedef T* iterator;
//typedef const T* const_iterator;
cvector()
{
initData(0);
}
cvector(int capa,const T& val=T())
{
initData(capa);
newCapacity(capacity_);
for (int i=0;i0);
return buf[index];
}
T& operator[](int index)
{
assert(size_>0 && index>=0 && index0?capa:0;
}
int size_;
int capacity_ ;
T* buf;
};
struct Point
{
Point(int x_=0,int y_=0):x(x_),y(y_){}
int x,y;
};
bool operator |
【本文地址】
今日新闻 |
推荐新闻 |