用allocator实现的标准库vector类模版

1. 1. ★**关于本模版**
   1. 1.1. ◇实现了《C++ primer》顺序容器一章中列出的所有vector支持的操作：
   2. 1.2. ◇Iterator和ReIterator类
   3. 1.3. ◇补充说明
2. 2. ★reallocate()的改动
3. 3. ★**关于const成员函数的使用**
   1. 3.1. ◇下标操作符
   2. 3.2. ◇const是个好东西
4. 4. define PI 3.14可以写成const double PI= 3.14;
5. 5. ★代码

《C++ primer》在一书收官之处介绍了allocator，并给出了reallocate()函数管理容器的内存分配，心脏有了，一番折腾，我大Vector成矣。

★**关于本模版**

◇实现了《C++ primer》顺序容器一章中列出的所有vector支持的操作：

• 容器定义的类型别名（p272）：size_type、iterator、const_iterator、reverse_iterator、const_reverse_iterator、difference_type、value_type、reference、const_reference
• 容器构造函数（p265）：C<T> c、C c(n, t)、C c(b, e)、C c(n)、C c(c2)
• begin和end成员（p273）：返回const和非const迭代器
• 在顺序容器中添加元素（p274）：push_back、push_front
• 容器大小的操作（p278）：size、max_size、empty、resize
• 访问元素（p279）：back、front、operator[]、at
• 删除元素（p280）：erase、clear、pop_back、pop_front
• 赋值操作（p283）：operator=、swap、assign
• capacity和reserve成员（p285）：capacity、reserve

◇Iterator和ReIterator类

开始时使用指针直接模拟迭代器，但是反向迭代器没法实现，于是分别写了正向和反向迭代器类，供Vector使用。

类中重载了的操作符：*、->、==、!=、++（前自增和后自增两个版本）、—（前自减和后自减两个版本）

◇补充说明

标准库vector比我的这个版本复杂很多，我只是模拟实现了基础操作。

大部分功能进过测试，但是代码中还是难免有错，或者实现得不合理或代码啰嗦的地方，有发现的还望指出。

★reallocate()的改动

按我实现成员函数的方式，书上的reallocate()需要进行改动。

原函数是根据容器堆大小（size）来计算新空间，但是在一个Vector上申请空间时，增大的是capcacity，size不会改变，就使得没有办法重复申请更多内存，这样，把一个size很大的Vectoc复制到size很小的Vector中的操作就没办法完成，因为只能申请一次空间。

将原函数的size改为capacity后，内存可重复申请，直至足够大。

`std::ptrdiff_t newcapacity = 2 * std::max(size, 1);  // 原
std::ptrdiff_t newcapacity = 2 * std::max(capacity, 1);  // 现`对程序应该也没有影响，毕竟内存分配多少只是决策问题。

★**关于const成员函数的使用**

◇下标操作符

定义了const和非const版本：

`T& operator[](const size_type) { return elements[index]; };
const T& operator[](const size_type) const { return elements[index]; };`

const版本中，返回值的const和常成员的const声明缺一不可。

假如缺失常成员const声明，如果定义一个const实例并用下标操作法访问：

const Vector<char> cvec(5, 'a'); char c = cvec[2]; // 错误！ vs2010提示： error C2678: 二进制“[”: 没有找到接受“const Vector<T>”类型的左操作数的运算符(或没有可接受的转换)

显然，我们应该提供一个const版本的成员来供const实例使用。但是

`T& operator[](const size_type) const { return elements[index]; };`

是否就行了呢？

`const Vector<char> cvec(5, 'a');
cvec[0] = 'A';`

会发现声明为const的cvec[0]变成了’A’！

原因在于，cvec[0]返回的是该元素的非const引用，赋值可以进行。

所以，返回值和函数都必须为const。

◇const是个好东西

写这个模版的一个大收获，就是基本高清了const的应用。

C++中的const关键字的用法非常灵活，而使用const将大大改善程序的健壮性。写这个模版的过程中，我了解到一些东西。

1.代替宏常量

define PI 3.14可以写成const double PI= 3.14;

一方面，const常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查，而对后者只进行字符替换。

另一方面，const定义的常量在程序运行过程中只有一份拷贝，而#define定义的常量在内存中有若干个拷贝，使用const常量可以节省空间，避免不必要的内存分配。

2.大大改善程序的健壮性

primer一书的代码一直是各种const，以前一师兄就问道你杂写这么多const，当时俺还只能说书上就这么些的，现在这方面的认识算是比较清楚了。

一句话：任何不会修改数据成员的函数都应该声明为const 类型。

而对于参数、返回值的const声明，基本同此，但是要看实际情况具体分析。

3.new返回的指针必须是const类型的

我在写程序过程中记得吃了它不少亏，现在也不是很清楚，不妨记下，以后遇上再来研究。

★代码

Vector.h

#ifndef MY_VECTOR
#define MY_VECTOR

#include <iostream>
#include <memory>
#include <algorithm>

#include "Iterator.h"

template <typename T> class Vector {
public:

true// 容器定义的类型别名 p272
truetypedef std::size_t size_type;
truetypedef Iterator<T> iterator;
truetypedef const Iterator<T> const_iterator;
truetypedef ReIterator<T> reverse_iterator;
truetypedef const ReIterator<T> const_reverse_iterator;
truetypedef signed int difference_type;
truetypedef T value_type;
truetypedef T& reference;
truetypedef const T& const_reference;

true// 容器构造函数 p265
trueVector(): elements(0), first_free(0), last(0) { } // C<T> c;
trueVector(size_type, const T&);  // C c(n, t);
truetemplate <typename Iter> Vector(Iter*, Iter*); // C c(b, e);  复合数据类型，不要用模板直接表示
trueexplicit Vector(size_type); // C c(n);
trueVector(const Vector&); // C c(c2);

true// begin和end成员 p273
trueiterator begin() { return elements; }
trueiterator end() { return first_free; }
truereverse_iterator rbegin() { return first_free - 1; }
truereverse_iterator rend() { return elements - 1; }
trueconst_iterator begin() const { return elements; }
trueconst_iterator end() const { return first_free; }
trueconst_reverse_iterator rbegin() const { return first_free - 1; }
trueconst_reverse_iterator rend() const { return elements - 1; }

true// 在顺序容器中添加元素 p274
truevoid push_back(const T&);
truevoid push_front(const T&);

true// 容器大小的操作 p278
truesize_type size() const { return first_free - elements; }
truesize_type max_size() const { return last - elements; }
truebool empty() const { if (elements) return 0; return 1; }
truevoid resize(const size_type);
truevoid resize(const size_type, const T&);

true// 访问元素 p279
trueT& back() const { return *(first_free - 1); }
trueT& front() const { return *elements; }
trueT& operator[](const size_type) { return elements[index]; };
trueconst T& operator[](const size_type) const { return elements[index]; };
trueT& at(const size_type index) { return elements[index]; }
trueconst T& at(const size_type index) const { return elements[index]; }

true// 删除元素 p280
trueiterator erase(iterator);
trueiterator erase(iterator, iterator);
truevoid clear();
truevoid pop_back();
truevoid pop_front();

true// 赋值操作 p283
trueVector& operator=(const Vector&);
truevoid swap(Vector&);
truetemplate <typename Iter> void assign(Iter*, Iter*);
truevoid assign(size_type, const T&);

true// capacity和reserve成员 p285
truesize_type capacity() const { return last - elements; }
truevoid reserve(const size_t);

true~Vector() { destory(); }

true// 方便测试用，标准库没有
truevoid display();

private:
truestatic std::allocator<T> alloc;  // 静态成员，所有Vector <T>对象可以公用，调用相应的成员函数分配不同的空间
truevoid reallocate();    // get more space and copy existing elements
trueT* elements;         // pointer to first element in the array
trueT* first_free;         // pointer to first free element in the array
trueT* last;                // pointer to one past the end of the array

truevoid destory(); // 销毁元素及释放内存

truetemplate <typename Iter> void copy_elem(Iter*, Iter*);
};

// public:
template <typename T> Vector<T>::Vector(typename Vector<T>::size_type n, const T &t)
{
trueelements = alloc.allocate(n * 3 / 2);
truefirst_free = elements + n;
truelast = elements + n * 3 / 2;

truefor (size_type i = 0; i != n; i++)
truetruealloc.construct(elements + i, t);
}
template <typename T> template <typename Iter> Vector<T>::Vector(Iter *b, Iter *e)
{
trueelements = alloc.allocate((e - b) * 3 / 2);
truefirst_free = elements + (e - b);
truelast = elements + (e - b) * 3 / 2;

truecopy_elem(b, e);
}
template <typename T> Vector<T>::Vector(typename Vector<T>::size_type n)
{
trueelements = alloc.allocate(n * 3 / 2);
truefirst_free = elements + n;
truelast = elements + n * 3 / 2;

truefor (size_type i = 0; i != n; i++)
truetruealloc.construct(elements + i, T());
}
template <typename T> Vector<T>::Vector(const Vector<T> &vec)
{
true// 初始化新Vector对象
trueelements = alloc.allocate(vec.capacity());
truefirst_free = elements + (vec.size());
truelast = elements + (vec.capacity());

true// 复制元素到新Vector
truecopy_elem(vec.elements, vec.first_free);
}

template <typename T> void Vector<T>::push_back(const T &t)
{
trueif (first_free == last)
truetruereallocate();
truealloc.construct(first_free, t);
true++first_free;
}
template <typename T> void Vector<T>::push_front(const T &t)
{
trueif (first_free == last)
truetruereallocate();
truealloc.construct(first_free, t);

    T tmp =  *first_free;
true*first_free = *elements;
true*elements = tmp;

true++first_free;
}

template <typename T> void Vector<T>::resize(const size_type n)
{
truesize_type size = first_free - elements;

trueif (n > last - elements) {
truetrue// 重复申请内存直至足够
truetruewhile (n > last - elements)
truetruetruereallocate();
truetruestd::uninitialized_fill(elements + size, elements + n, T());
true} else if (n > size)
truetruestd::uninitialized_fill(elements + size, elements + n, T());
trueelse {
truetruefor (T *p = first_free; p != elements + n; )
truetruetruealloc.destroy(--p);
true}

truefirst_free = elements + n;
}
template <typename T> void Vector<T>::resize(const size_type n, const T &t)
{
truesize_t size = first_free - elements;
truesize_t capacity = last - elements;

trueif (n > capacity) {
truetrue// 重复申请内存直至足够
truetruewhile (n > last - elements)
truetruetruereallocate();
truetruestd::uninitialized_fill(elements + size, elements + n, t);
true} else if (n > size)
truetruestd::uninitialized_fill(elements + size, elements + n, t);
trueelse {
truetruefor (T *p = first_free; p != elements + n; )
truetruetruealloc.destroy(--p);
true}

truefirst_free = elements + n;
}

template <typename T> typename Vector<T>::iterator Vector<T>::erase(iterator iter)
{
trueVector<T>::iterator back_iter = iter;
truefor ( ; iter != first_free - 1; ++iter)
truetrue*iter = *(iter + 1);
truealloc.destroy(--first_free); // 撤销最后一个元素并重置first_free
truereturn back_iter;
}
template <typename T> typename Vector<T>::iterator Vector<T>::erase(iterator b, iterator e)
{
trueVector<T>::iterator back_iter = b;
trueVector<T>::iterator old_first_free = first_free;
truefor ( ; e != first_free - 1; ++b, ++e)
truetrue*b = *(e + 1);
truefirst_free = b;
truewhile (b != old_first_free)
truetruealloc.destroy(b++);
truereturn back_iter;
}
template <typename T> void Vector<T>::clear()
{
truefor (T *p = first_free; p != elements; )
truetruealloc.destroy(--p);
truefirst_free = elements;
}
template <typename T> void Vector<T>::pop_back()
{
truealloc.destroy(--first_free);
}
template <typename T> void Vector<T>::pop_front()
{
truefor (T *p = elements; p != first_free - 1; ++p)
truetrue*p = *(p + 1);
true--first_free;
}

template <typename T> void Vector<T>::swap(Vector<T> &vec)
{
trueVector::iterator tmp_elements = elements;
trueVector::iterator tmp_first_free = first_free;
trueVector::iterator tmp_last = last;
trueelements = vec.elements;
truefirst_free = vec.first_free;
truelast = vec.last;
truevec.elements = tmp_elements;
truevec.first_free = tmp_first_free;
truevec.last = tmp_last;
}
template <typename T> template <typename Iter> void Vector<T>::assign(Iter* b, Iter* e)
{
truetypename Vector<T>::size_type n = e - b;
truewhile (last - elements < e - b)
truetruereallocate();
trueclear();
truefor (T *p = elements; b != e; ++p, ++b)
truetrue*p = *b;
truefirst_free = elements + n;
}
template <typename T> void Vector<T>::assign(typename Vector<T>::size_type n, const T& t)
{
truewhile (last - elements < n)
truetruereallocate();
trueclear();
truestd::uninitialized_fill(elements, elements + n, t);
truefirst_free = elements + n;
}

template <typename T> void Vector<T>::reserve(const std::size_t capa)
{
truestd::ptrdiff_t size = first_free - elements;
trueT* newelements = alloc.allocate(capa);

trueif (size < capa)
truetruestd::uninitialized_copy(elements, first_free, newelements);
trueelse
truetruestd::uninitialized_copy(elements, elements + capa, newelements);
truefor (T *p = first_free; p != elements; )
truetruealloc.destory(--p);

trueif (elements)
truetruealloc.deallocate(elements, last - elements);
trueelements = newelements;
truefirst_free = elements + std::min((int)size, (int)capa); // 这里转下类型
truelast = first + capa;
}

template <typename T> void Vector<T>::display()
{
truefor (Vector<T>::iterator iter = begin(); iter != end(); ++iter)
truetruestd::cout << *iter << " ";
truestd::cout << std::endl;
}

template <typename T> Vector<T>& Vector<T>::operator=(const Vector<T> &vec)
{
trueif (this != &vec) {
truetruedestory();

truetrueelements = alloc.allocate(vec.capacity());
truetruefirst_free = elements + vec.size();
truetruelast = elements + vec.capacity();

truetruecopy_elem(vec.elements, vec.first_free);
true}
truereturn *this;
}

// private:
template <typename T> std::allocator<T> Vector<T>::alloc;
template <typename T> void Vector<T>::reallocate()
{
truestd::ptrdiff_t capacity = last - elements;
truestd::ptrdiff_t size = last - elements;
true// 此处将书上的szie改为了capacity，否者会导致resize等操作等无法申请到足够内存
truestd::ptrdiff_t newcapacity = 2 * std::max(capacity, 1);
trueT* newelements = alloc.allocate(newcapacity);

true// construct copies of the existing elements in the new space
truestd::uninitialized_copy(elements, first_free, newelements);
truefor (T *p = first_free; p != elements; )
truetruealloc.destroy(--p);

trueif (elements)
truetruealloc.deallocate(elements, last - elements);
trueelements = newelements;
truefirst_free = elements + size;
truelast = elements + newcapacity;
}
template <typename T> void Vector<T>::destory()
{
truefor (T *p = first_free; p != elements; )
truetruealloc.destroy(--p);
trueif (elements)
truetruealloc.deallocate(elements, last - elements);
}
template <typename T> template <typename Iter> void Vector<T>::copy_elem(Iter *b, Iter *e)
{
truefor (typename Vector<T>::size_type i = 0; i != e - b; ++i)
truetruealloc.construct(elements + i, *(b + i));
}

#endif

Iterator.h

#ifndef MY_ITERATOR
#define MY_ITERATOR

template <typename T> class Iterator {
public:
trueIterator(T* it = 0): current(it) { }

trueT& operator*() const { return *current; }
trueT* operator->() const { return current; }
truebool operator==(const Iterator &iter) const
true{
truetruereturn current == iter.current;
true}
truebool operator!=(const Iterator &iter) const
true{
truetruereturn current != iter.current;
true}

trueIterator* operator++()
true{
truetrue++current;
truetruereturn this;
true}
trueIterator* operator--()
true{
truetrue--current;
truetruereturn this;
true}
true// 后缀式操作符接受一个额外的int型形参，以区分前缀式
trueIterator* operator++(int)
true{
truetrueIterator* ret(this);
truetrue++current;
truetruereturn ret;
true}
trueIterator* operator--(int)
true{
truetrueIterator* ret(this);
truetrue--current;
truetruereturn ret;
true}
private:
trueT* current;
};
template <typename T> class ReIterator {
public:
trueReIterator(T* it = 0): current(it) { }

trueT& operator*() const { return *current; }
trueT* operator->() const { return current; }
truebool operator==(const ReIterator &iter) const
true{
truetruereturn current == iter.current;
true}
truebool operator!=(const ReIterator &iter) const
true{
truetruereturn current != iter.current;
true}

trueReIterator* operator++()
true{
truetrue--current;
truetruereturn this;
true}
trueReIterator* operator--()
true{
truetrue++current;
truetruereturn this;
true}
trueReIterator* operator++(int)
true{
truetrueReIterator* ret(this);
truetrue--current;
truetruereturn ret;
true}
trueReIterator* operator--(int)
true{
truetrueReIterator* ret(this);
truetrue++current;
truetruereturn ret;
true}
private:
trueT* current;
};

#endif