C++中vector的实现

注意几点：分配内存不要使用new和delete，因为new的同时就把对象构造了，而我们需要的是原始内存。所以应该使用标准库提供的allocator类来实现内存的控制。当然也可以重载operator new操作符，因为二者都是使用malloc作为底层实现，所以直接采用malloc也可以。对象的复制必须使用系统提供的uninitialized_fill和uninitialized_copy，因为我们无法手工调用构造函数。对于C++中的对象，除了POD之外，使用memcpy系列的函数是绝对错误的。myvector.h#ifndef _VECTOR_H_
#define _VECTOR_H_
#include <stddef.h>
#include <algorithm>
#include <memory>template <typename T>
class Vector
{
public:
typedef T *iterator;
typedef const T *const_iterator;
typedef size_t size_type;
typedef T value_type; class reverse_iterator
{
public:
reverse_iterator（iterator it = NULL）:current_（it） {}
iterator base（） const { return current_; } reverse_iterator &operator++（）//前置
{
--current_;
return *this;
} reverse_iterator operator++（int）//后置
{
reverse_iterator temp（*this）;
--current_;
return temp;
} reverse_iterator &operator--（）
{
++current_;
return *this;
} reverse_iterator operator--（int）
{
reverse_iterator temp（*this）;
++current_;
return temp;
} T &operator*（）
{
iterator temp = current_;
return *--temp;
} T *operator->（）
{
iterator temp = current_;
return --temp;
} friend bool operator==（const reverse_iterator &lhs,
const reverse_iterator &rhs）
{
return lhs.current_ == rhs.current_;
}
friend bool operator！=（const reverse_iterator &lhs,
const reverse_iterator &rhs）
{
return lhs.current_ ！= rhs.current_;
}
private:
iterator current_;
}; Vector（） { create（）; }//无参构造函数
explicit Vector（size_type n, const T &t = T（）） { create（n, t）; }
Vector（const Vector &v） { create（v.begin（）, v.end（））;}// 拷贝构造函数
~Vector（） { uncreate（）;} Vector &operator=（const Vector &other）;
T &operator[] （size_type i） { return data_[i]; }
const T &operator[] （size_type i） const {return data_[i]; } void push_back（const T &t）; size_type size（） const { return avail_ - data_;}
size_type capacity（）const { return limit_ - data_;} iterator begin（） { return data_; }
const_iterator begin（） const {return data_;}
iterator end（） {return avail_;}
const_iterator end（） const { return avail_; } reverse_iterator rbegin（）{return reverse_iterator（end（））;}
reverse_iterator rend（） {return reverse_iterator（begin（））;} void swap（Vector &rhs）
{
std::swap（data_, rhs.data_）;
std::swap（avail_, rhs.avail_）;
std::swap（limit_, rhs.limit_）;
}
private:
iterator data_;//首元素
iterator avail_;//末尾元素的下一个
iterator limit_; std::allocator<T> alloc_;//内存分配器 void create（）;
void create（size_type, const T &）;
void create（const_iterator, const_iterator）; void uncreate（）; void grow（）;
void uncheckAppend（const T &）;
}; template <typename T>
inline Vector<T> &Vector<T>::operator=（const Vector &rhs）
{
if（this ！= rhs）
{
uncreate（）;//释放原来的内存
create（rhs.begin（）, rhs.end（））;
}
return *this;
} template <typename T>
inline void Vector<T>::push_back（const T &t）
{
if（avail_ == limit_）
{
grow（）;
}
uncheckAppend（t）;
} template <typename T>
inline void Vector<T>::create（）
{
//分配空的数组
data_ = avail_ = limit_ = 0;
} template <typename T>
inline void Vector<T>::create（size_type n, const T &val）
{
//分配原始内存
data_ = alloc_.allocate（n）;
limit_ = avail_ = data_ + n;
//向原始内存填充元素
std::uninitialized_fill（data_, limit_, val）;
} template <typename T>
inline void Vector<T>::create（const_iterator i, const_iterator j）
{
data_ = alloc_.allocate（j-i）;
limit_ = avail_ = std::uninitialized_copy（i, j, data_）;
} template <typename T>
inline void Vector<T>::uncreate（）
{
if（data_）//逐个析构
{
iterator it = avail_;
while（it ！= data_）
{
alloc_.destroy（--it）;
}
alloc_.deallocate（data_, limit_ - data_ ）;//真正释放内存
}
data_ = limit_ = avail_ = 0;//重置指针
} template <typename T>
inline void Vector<T>::grow（）
{
//内存变为2倍
size_type new_size = std::max（2 * （limit_ - data_）, std::ptrdiff_t（1））;
//分配原始内存
iterator new_data = alloc_.allocate（new_size）;
//复制元素
iterator new_avail = std::uninitialized_copy（data_, avail_, new_data）; uncreate（）;//释放以前内存 data_ = new_data;
avail_ = new_avail;
limit_ = data_ + new_size;
} template <typename T>
inline void Vector<T>::uncheckAppend（const T &val）
{
alloc_.construct（avail_++, val）;
}#endif /*VECTOR_H*/test_main.cpp#include "myvector.h"
#include <iostream>
#include <string>
using namespace std;void print_reverse（Vector<string> &vec）
{
cout << "reverse_iterator: " << endl;
for（Vector<string>::reverse_iterator it = vec.rbegin（）;
it ！= vec.rend（）;
++it）
{
cout << *it << endl;
}
cout << endl;
}void print（Vector<string> &vec）
{
cout << "iterator: " << endl;
for（Vector<string>::iterator it = vec.begin（）;
it ！= vec.end（）;
++it）
{
cout << *it << endl;
}
cout << endl;
}int main（int argc, const char *argv[]）
{
Vector<string> vec（3, "hello"）; for（Vector<string>::const_iterator it = vec.begin（）;
it ！= vec.end（）;
++it）
{
cout << *it << endl;
}
cout << endl;

cout << "size=" << vec.size（） << endl;
cout << "capacity:" << vec.capacity（） << endl;
vec.push_back（"foo"）;
vec.push_back（"bar"）; cout << "size:=" << vec.size（） << endl;
cout << "capacity=" << vec.capacity（） << endl;

print_reverse（vec）;
print（vec）;
return 0;
}《C++ 设计新思维》下载见 http://www.linuxidc.com/Linux/2014-07/104850.htmC++ Primer Plus 第6版中文版清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm读C++ Primer 之构造函数陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm读C++ Primer 之智能指针 http://www.linuxidc.com/Linux/2011-08/40177.htm读C++ Primer 之句柄类 http://www.linuxidc.com/Linux/2011-08/40175.htm将C语言梳理一下，分布在以下10个章节中：

Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-10/107633.htm