自定义一个arrray类,模拟实现vector类的全部功能,array类的实现用动态内存分配或链表实现

发布网友发布时间：2022-04-24 12:37

共1个回答

热心网友时间：2023-10-13 01:32

#include <cassert>

template<class T>
class vector
{
private:
typedef T& reference;
typedef const T& const_ref;

public:
typedef T* iterator;
typedef const T* const_it;

enum{ INITCAPACITY = 20};

vector()
{
m_capacity = INITCAPACITY;
m_pb = new T[m_capacity];
m_pe = m_pb;
}

vector(size_t s)
{
m_capacity = s>INITCAPACITY ? s:INITCAPACITY;
m_pb = new T[m_capacity];
m_pe = m_pb;
}

~vector()
{
if (m_pb)
{
delete[] m_pb;
m_pb = 0;
}

m_pe = 0;
m_capacity = 0;

}

inline const_ref operator[] (size_t t) const
{
assert( t < (size_t)(m_pe - m_pb));
return m_pb[t];
}

inline iterator begin()
{
return m_pb;
}

inline iterator end()
{
return m_pe;
}

inline const_it begin()const
{
return m_pb;
}

inline const_it end() const
{
return m_pe;
}

inline size_t size() const
{
return m_pe-m_pb;
}

inline size_t capacity()const
{
return m_capacity;
}

inline bool empty() const
{
return m_pe == m_pb;
}

inline const_ref back() const
{
return *(m_pe-1);
}

void push_back(T t)
{
if ( (size_t)(m_pe-m_pb+1) > m_capacity )
{
reserve(m_capacity<<1);
}

*m_pe++ = t;
}

void pop_back()
{
if(m_pe > m_pb)
{
--m_pe;
}
}

void clear()
{
m_pe = m_pb;
}

///////////////////////////////////////////////////////////////////////
//Desc: 倒置容器的元素
///////////////////////////////////////////////////////////////////////
void reverse()
{
iterator b = m_pb;
iterator e = m_pe;

for ( ; --e > b ; ++b )
{
ite_swap(e,b);
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 倒置b e区间的元素
///////////////////////////////////////////////////////////////////////
static void reverse( iterator b, iterator e )
{
for ( ; --e > b ; ++b )
{
ite_swap(e,b);
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 重新分配容器的容量
///////////////////////////////////////////////////////////////////////
void reserve(size_t s)
{
if (s > m_capacity )
{
iterator p = new T[s];

for (iterator it = m_pb; it!= m_pe;)
{
*p++ = *it++;
}

delete[] m_pb;

//*****这里需要保证m_pb释放后仍然指向原来的地址*****//
m_pb = p-(m_pe-m_pb);
m_pe = p;
m_capacity =s;
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 删除容器内b e区间的所有元素，
///////////////////////////////////////////////////////////////////////
void erase(iterator b, iterator e )
{
assert(b >= m_pb && b < m_pe);
assert(e > m_pb && e <= m_pe);

while( e != m_pe)
{
*b++ = *e++;
}

m_pe -= (e-b);
}

///////////////////////////////////////////////////////////////////////
//Desc: 删除容器内的一个元素，
///////////////////////////////////////////////////////////////////////
void erase(iterator it)
{
assert(it >= m_pb && it < m_pe);

while( it !=m_pe )
{
*it++ = *(it+1);
}

--m_pe;
}

///////////////////////////////////////////////////////////////////////
//Desc: 将b e区间的元素复制到容器尾部
///////////////////////////////////////////////////////////////////////
void copyback(const_it b, const_it e )
{
assert( b < e );

for( ; b != e; ++b )
{
if ( (size_t)(m_pe-m_pb+1) > m_capacity )
{
reserve(m_capacity<<1);
}

*m_pe++ = *b;
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 将b e区间符合条件的元素复制到容器尾部
///////////////////////////////////////////////////////////////////////
void copyback(const_it b, const_it e, bool(*f)(const_ref))
{
assert( b < e );

for ( ; b != e; ++b )
{
if ( f(*b))
{
if ((size_t)(m_pe-m_pb+1) > m_capacity )
{
reserve(m_capacity<<1);
}

*m_pe++ = *b;
}
}
}

iterator find_if( bool(*f)(const_ref) )
{
iterator it;

for ( it = m_pb; it != m_pe; ++it)
{
if ( f(*it) )
{
break;
}
}

return it;
}

///////////////////////////////////////////////////////////////////////
//Desc: 在容器内查找第一个元素，如果找到返回指针，否则返回超尾
///////////////////////////////////////////////////////////////////////
iterator find( const_ref t, bool(*f)(const_ref, const_ref) )
{
iterator it;

for ( it = m_pb; it != m_pe; ++it)
{
if ( f(*it,t) )
{
break;
}
}

return it;
}

///////////////////////////////////////////////////////////////////////
//Desc: 在b e区间查找第一个元素，如果找到返回指针，否则返回超尾
///////////////////////////////////////////////////////////////////////
static iterator find_if( iterator b, iterator e, bool(*f)(const_ref) )
{
assert( b < e );

iterator it;

for ( it = b; it != e; ++it)
{
if ( f(*it) )
{
break;
}
}

return it;
}

///////////////////////////////////////////////////////////////////////
//Desc: 查找与最后一个元素，如果找到返回指针，否则返回超尾
///////////////////////////////////////////////////////////////////////
iterator find_end( const_ref val, bool(*f)(const_ref, const_ref) )
{
for (iterator it = m_pe-1; it != m_pb-1; --it)
{
if ( f(*it , val) )
{
return it;
}
}

return m_pe;
}

iterator find_end( bool(*f)(const_ref) )
{
for (iterator it = m_pe-1; it != m_pb-1; --it)
{
if ( f(*it) )
{
return it;
}
}

return m_pe;
}

///////////////////////////////////////////////////////////////////////
//Desc: 查找符合条件的元素数量
///////////////////////////////////////////////////////////////////////
size_t count_if( bool(*f)(const_ref) )
{
size_t count =0;

for (iterator it = m_pb; it != m_pe; ++it)
{
if ( f(*it))
{
++count;
}
}

return count;
}

///////////////////////////////////////////////////////////////////////
//Desc: 查找符合条件的元素数量,可以比较相等或者不相等
///////////////////////////////////////////////////////////////////////
size_t count_if( const_ref val, bool(*f)(const_ref, const_ref) )
{
size_t count =0;

for (iterator it = m_pb; it != m_pe; ++it)
{
if ( f(*it, val))
{
++count;
}
}

return count;
}

///////////////////////////////////////////////////////////////////////
//Desc: 在容器内查找元素，将其删除，并移动超尾
///////////////////////////////////////////////////////////////////////
void remove_if(bool(*f)(const_ref) )
{
for (iterator it = m_pb; it != m_pe; )
{
if ( f(*it))
{
for (iterator it1 = it; it1!= m_pe; ++it1)
{
*it1= *(it1+1) ;
}

--m_pe;
}
else
{
++it;
}
}
}

static void ite_swap( iterator x, iterator y )
{
T t = *x;
*x = *y, *y = t;
}

///////////////////////////////////////////////////////////////////////
//Desc: 依照条件排序b'e区间的元素
///////////////////////////////////////////////////////////////////////
static void sort(iterator b, iterator e, bool(*f)(const_ref,const_ref))
{
assert( b <= e );

for ( ; b != e; ++b )
{
for (iterator it = b+1; it!= e; ++it)
{
if ( f(*it,*b) )
ite_swap(it, b);
}
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 依照条件排序b'e区间的元素
///////////////////////////////////////////////////////////////////////
void sort( bool(*f)(const_ref,const_ref) )
{
iterator b = m_pb;

for ( ; b != m_pe; ++b )
{
for (iterator it = b+1; it!= m_pe; ++it)
{
if ( f(*it,*b) )
ite_swap(it, b);
}
}
}

template< class F >
static void for_each(iterator b, iterator e, F(*f)(reference))
{
assert( b <= e);

while( b != e)
{
f(*b++);
}
}

template< class F >
void for_each( F(*f)(reference) )
{
iterator b = m_pb;

while( b != m_pe)
{
f(*b++);
}
}

///////////////////////////////////////////////////////////////////////
//Desc: 随机打乱b'e区间的元素
///////////////////////////////////////////////////////////////////////
static void random_shuffle(iterator b, iterator e)
{
assert( b < e);

iterator it = b;

for (size_t u = 1; ++it != e; ++u)
{
size_t m = 0x7FFF;
size_t n = rand() & 0x7FFF;

for (; m < u && m != ~0L; m = (m<<0xF) | 0x7FFF )
{
n = (n<<0xF) | 0x7FFF;
}

ite_swap( it, b+(n%u) );
}
}

private:
iterator m_pb;
iterator m_pe;
size_t m_capacity;
};