统计

  • 随笔 - 50
  • 文章 - 42
  • 评论 - 147
  • 引用 - 0

留言簿(6)

随笔分类

文章分类

Link

搜索

  •  

积分与排名

  • 积分 - 162594
  • 排名 - 161

最新评论

阅读排行榜

评论排行榜

简版 容器vector 实现

vector为我们提供了可伸缩的顺序存储容器，在顺序和随机存储方面效率很高

实现vector的关键在于实现内存分配和对象构造的分离，一般来讲我们直接用new来构造对象就经历了这两个过程，而实现vector就需要我们先申请请到一片连续的内存区域，然后在需要时在改内存上构造对象。这里用到allocator模板类
该类内部封装了如下方法：
template<typename elm>
class allocator
{
elm *allocate(size_t n)      //分配n个对象存储空间
void construct(elm* p,size_t n) //在以p为开始的内存上构造n个对象
void destroy(elm* p) //销毁对象
void deallocate(elm*p,size_t n) //释放从p开始的n个对象内存

}
有了这些就足够了，一下就是简版Vector实现LyVector
 1#include "stdafx.h"
 2#include "memory"
 3template <typename elmType>
 4class LyVector
 5{
 6private:
 7    elmType* _first;
 8    elmType* _last;
 9    elmType* _end;
10    allocator<elmType> _alc;
11public:
12    typedef typename elmType valueType;
13    LyVector():
14      _first(0),_last(0),_end(0){};
15    bool push_back(const elmType &t)
16    {
17        if (_last==_end)
18        {
19            size_t size=_last-_first;
20
21            size_t capacity=2*size;
22            if (capacity==0)
23            {
24                capacity=2;
25            }
26            //创建新的存储区域并赋值
27            elmType* newElm=_alc.allocate(capacity);
28            if (newElm==NULL)
29            {
30                return false;
31            }
32            uninitialized_copy(_first,_last,newElm);
33            //删除就有存储区
34            for(;_first!=_last;)
35                _alc.destroy(--_last);
36            _alc.deallocate(_first,size);
37            _first=newElm;
38            _last=newElm+size;
39            _end=newElm+capacity;
40        }
41        _alc.construct(_last++,t);
42        return true;
43    }
44    void popBack()
45    {
46        if (size()==0)
47        {
48            _DEBUG_ERROR("No element fount");
49            return;
50        }
51        _alc.destroy(--_last);
52    }
53    
54    size_t size()
55    {
56        return _last-_first;
57    }
58    size_t capacity()
59    {
60        return _end-_first;
61    }
62    
63    elmType* operator[](size_t pos)
64    {
65        if (pos>=size())
66        {
67            _DEBUG_ERROR("out of range");
68            return NULL;
69        }
70        return _first+pos;
71    }
72
73
74    friend ostream& operator<<(ostream &o,const LyVector &im)
75    {
76        for (LyVector::valueType * first=im._first;first!=im._last;first++)
77        {
78            o<<*first<<endl;
79        }
80        return o;
81    }
82};

从实现看来，我觉得在使用vector，有以下几点注意：
1. 最好为所存储对象实现拷贝构造函数，不然在重新分配存储空间时可能会产生内存访问违规问题，原因是对象在存入vector和在vecotr重新构造是都会调用拷贝构造函数
2. 对象存入是会在制定位置产生新的对象，不必担心原对象生存期

posted on 2009-08-12 15:46 pear_li 阅读(2475) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理