STL源码学习

本文记录自己阅读STL源码（自己实现部分STL功能）的过程中收获的一些理解和感悟，记录STL标准库设计的一些精妙之处。

STL组成部分：容器、算法、迭代器、函数对象、适配器、空间配置器

项目初衷

1. 算法题中用到很多STL标准库中的容器和算法，一直都知道他们是非常高效的，对象的耦合性低、复用性高，但是却不知道是怎么样实现了高效。因此很想了解他们的底层实现。也一直知道内存管理是C++的精髓，但是只从语法上学习并没有很直接的感受，因此希望通过阅读STL源码中对内存的管理方法，对智能指针的实现来对内存管理有更好的认识。
2. 实现一份类似STL的标准库也能学习到很多巧妙的设计方法，也是我从单单从C++primer上学习语法和做算法题到真正实现设计和开发一些东西的跨越。
3. SGI版本中源码中未实现的：move相关的操作，另外智能指针实现的只有auto_ptr。
4. 我们版本的TinySTL：灵活使用了auto关键字，因为很多很长也很复杂的类型名。另外static_cast的使用也很多，增加了move的相关操作。

设计经验

1. 用 #pragma once来防止重复定义
2. 声明与定义分离，类中尽量只放声明。尽可能多用const和引用。
3. 类型偏特化的使用：不同类型的数据使用相同的算法也有可能具有不一样的效率。对于某些只有一个字节大小的类型（如char、const unsigned char（原生指针））我们会设计针对特定类型的特化版本的函数来增进效率（通过使用C标准库函数如memmove、memcmp）。
4. 模板出错比较难检查，因为必须运行时才能发现错误，编译阶段无法发现。一般模板中既包含声明又包含定义
5. 做一个类似这样的库的项目最先要实现的是底层的内存分配，保证不发生内存泄露。然后要设计一系列基础的算法例如copy、fill等，并且尽可能做到最高效（通过尽可能地调用C库中的函数来写）。因为我们需要设计一系列容器，而对于容器进行整体的拷贝和赋值等操作需要大量应用copy等算法，因此需要事先设计好并且保证高效。同时由于容器的操作涉及到一系列对象的拷贝、移动等，因此要保证异常的安全，需要更多的思考。

内存相关

《STL源码剖析》中阐述的内存池实现机制：

allocate 包装 malloc，deallocate包装free

一般是一次20*2个的申请，先用一半，留着一半，为什么也没个说法，侯捷在STL那边书里说好像是C++委员会成员认为20是个比较好的数字，既不大也不小。

1. 首先客户端会调用malloc()配置一定数量的区块（固定大小的内存块，通常为8的倍数），假设40个32bytes的区块，其中20个区块（一半）给程序实际使用，1个区块交出，另外19个处于维护状态。剩余20个（一半）留给内存池，此时一共有（20*32byte）
2. 客户端之后有有内存需求，想申请（20*64bytes）的空间，这时内存池只有（20*32bytes），就先将（10*64bytes)个区块返回，1个区块交出，另外9个处于维护状态，此时内存池空空如也.
3. 接下来如果客户端还有内存需求，就必须再调用malloc()配置空间，此时新申请的区块数量会增加一个随着配置次数越来越大的附加量，同样一半提供程序使用，另一半留给内存池。申请内存的时候用永远是先看内存池有无剩余，有的话就用上，然后挂在0-15号某一条链表上，要不然就重新申请。
4. 如果整个堆的空间都不够了，就会在原先已经分配区块中寻找能满足当前需求的区块数量，能满足就返回，不能满足就向客户端报bad_alloc异常

allocator就是用来分配内存的，最重要的两个函数是allocate和deallocate，就是用来申请内存和回收内存的，外部（一般指容器）调用的时候只需要知道这些就够了。

内部实现，目前的所有编译器都是直接调用的::operator new()和::operator delete()，说白了就是和直接使用new运算符的效果是一样的，所以老师说它们都没做任何特殊处理。

萃取机制

Traits，又被叫做特性萃取技术，说得简单点就是提取“被传进的对象”对应的返回类型，让同一个接口实现对应的功能。

因为STL的算法和容器是分离的，两者通过迭代器链接。算法的实现并不知道自己被传进来什么。萃取器相当于在接口和实现之间加一层封装，来隐藏一些细节并协助调用合适的方法，这需要一些技巧（例如，偏特化）。总的来说，Traits 的作用主要是用来为使用者提供类型信息。

traits 技术需要用到的技术有：模板特化及 typename 关键字等。

个人体悟：这个机制有点类似于Java中的反射机制！精妙！（当然是编译期的，无法实现运行期间的反射）

模板的特化

模板特化分为模板全特化和模板偏特化。

类模板全特化：

有时为了需要，针对特定的类型,需要对模板进行特化，也就是特殊处理。例如 stack 类模板针对 bool类型。因为实际上 bool 类型只需要一个二进制位，就可以对其进行存储,使用一个字或者一个字节都是浪费存储空间的。

template <typename T>
class stack
{
    //...
};

template <>
class stack<bool>
{
    //...
};

类模板的偏特化：

模板的偏特化是指需要根据模板的某些但不是全部的参数进行特化。例如 C++ 标准库中的类 vector 的定义：

template <class T, class Allocator>
class vector
{
    //...
};

template <class Allocator>
class vector<bool, Allocator>
{
    //...
};

这个偏特化的例子中，一个参数被绑定到 bool 类型，而另一个参数仍未绑定需要由用户指定。

typename 关键字

先看一个问题，以下模板的声明中， class 和 typename 有什么不同？

template<class T> class Test;
template<typename T> class Test;

答案：没有不同。

然而，C++ 并不总是把 class 和 typename 视为等价。有时候我们一定得使用 typename。

默认情况下，C++ 语言假定通过作用域运算符访问的名字不是类型。因此，如果我们希望使用一个模板类型参数的类型成员，就必须显式告诉编译器该名字是一个类型。我们通过使用关键字 typename 来实现这一点：

template<typename T>
typename T::value_type top(const T &c)
{
    if (!c.empty())
        return c.back();
    else
        return typename T::value_type();
}

top 函数期待一个容器类型的实参，它使用 typename 指明其返回类型，并在 c 中没有元素时生成一个初始值的默认元素，并返回给调用者。

在这里我们只需要记住一点，当我们希望通知编译器一个名字表示类型时，必须使用关键字 typename，而不能使用 class。

实现 Traits Classes

正式进入 traits 的关键地带。

我们知道，在 STL 中，容器与算法是分开的，彼此独立设计，容器与算法之间通过迭代器联系在一起。那么，算法是如何从迭代器类中萃取出容器元素的类型的？没错，这正是我们要说的 traits classes 的功能。

迭代器所指对象的类型，称为该迭代器的 value_type。我们来简单模拟一个迭代器 traits classes 的实现。

template <class IterT>
struct my_iterator_traits
{
    typedef typename IterT::value_type value_type;
};

my_iterator_traits 其实就是个类模板，其中包含一个类型的声明。

typedef typename IterT::value_type value_type; 的含义：将迭代器的 value_type 通过 typedef 为 value_type。

对于 my_iterator_traits，我们还有一个一个偏特化版本

template <class IterT>
struct my_iterator_traits<IterT *>
{
    typedef IterT value_type;
};

即如果 my_iterator_traits 的实参为指针类型时，直接使用指针所指元素类型作为 value_type。

为了测试 my_iterator_traits 能否正确萃取迭代器元素的类型，我们编写以下的测试函数。通过函数重载的方式，来测试元素的类型。

#include <iostream>
#include <vector>

using namespace::std;

template <class IterT>
    struct my_iterator_traits
    {
        typedef typename IterT::value_type value_type;
    };

template <class IterT>
    struct my_iterator_traits<IterT *>
    {
        typedef IterT value_type;
    };

void fun(int a) {
    cout << "fun(int) is called" << endl;
}

void fun(double a) {
    cout << "fun(double) is called" << endl;
}

void fun(char a) {
    cout << "fun(char) is called" << endl;
}
int main(){
    my_iterator_traits<vector<int>::iterator>::value_type a;
    fun(a); // 输出 fun(int) is called

    my_iterator_traits<vector<double>::iterator>::value_type b;
    fun(b); // 输出 fun(double) is called

    my_iterator_traits<char *>::value_type c;
    fun(c); // 输出 fun(char) is called

    return 0;
}

编译并运行

$ ./testTraits 
fun(int) is called
fun(double) is called
fun(char) is called

我们来解释 my_iterator_traits<vector<int>::iterator>::value_type a; 语句的含义。

vector<int>::iterator 为 vector<int> 的迭代器，该迭代器包含了 value_type 的声明，由 vector 的代码可以知道该迭代器的value_type 即为 int 类型。

接着，my_iterator_traits<vector<int>::iterator> 会采用 my_iterator_traits 的通用版本，即my_iterator_traits<vector<int>::iterator>::value_type 使用 typename IterT::value_type 这一类型声明，这里 IterT 为 vector<int>::iterator，故整个语句萃取出来的类型为 int 类型。

对 double 类型的 vector 迭代器的萃取也是类似的过程。

而 my_iterator_traits<char*>::value_type 则使用 my_iterator_traits 的偏特化版本，直接返回 char 类型。

由此看来，通过 my_iterator_traits ，我们正确萃取出了迭代器所指元素的类型。

总结一下我们设计并实现一个 traits class 的过程：

• 确认若干我们希望将来可取得的类型相关信息。例如，对于上面的迭代器，我们希望取得迭代器所指元素的类型。
• 为该信息选择一个名称。例如，上面我们起名为 value_type。
• 提供一个 template 和一组特化版本（例如，我们上面的 my_iterator_traits），内容包含我们希望支持的类型相关信息。

iterator的设计

源码：

#ifndef MYTINYSTL_ITERATOR_H_
#define MYTINYSTL_ITERATOR_H_

//这个头文件用于迭代器设计，包含了一些模板结构体与全局函数

#include <cstddef>

#include "type_traits.h"

namespace mystl {

    //五种迭代器类型
    struct input_iterator_tag {};		//只读迭代器
    struct output_iterator_tag {};		//只写
    struct forward_iterator_tag :public input_iterator_tag{};	//允许写入型算法进行读写操作
    struct bidirectional_iterator_tag : public forward_iterator_tag {};		//双向
    struct random_access_iterator_tag : public bidirectional_iterator_tag{};//随机访问迭代器，涵盖指针所有能力

    //iterator 模板
    template <typename Category, typename T, typename Distance = ptrdiff_t,
    typename Pointer = T*, typename Reference = T&>
        struct iterator {
            typedef Category	iterator_category;
            typedef T			value_type;
            typedef Pointer		pointer;
            typedef Reference	reference;
            typedef Distance	difference_type;
        };

    //iterator traits
    template <class T>
        struct has_iterator_cat{
            private:
            struct two { char a; char b; };		//大小为2
            template <class U> static two test(...);
            template <class U> static char test(typename U::iterator_category* = 0);
            public:
            static const bool value = sizeof(test<T>(0)) == sizeof(char);	//判断是否有iterator_category
        };

    template <typename Iterator, bool>
    struct iterator_traits_impl {};

    template <typename Iterator>
    struct iterator_traits_impl<Iterator, true> {
        typedef typename Iterator::iterator_category	iterator_category;
        typedef typename Iterator::value_type			value_type;
        typedef typename Iterator::pointer				pointer;
        typedef typename Iterator::reference			reference;
        typedef typename Iterator::difference_type		difference_type;
    };

    template<typename Iterator, bool>
    struct iterator_traits_helper{};

    /*is_converible模板用于检查是否可以将任何数据类型A转换为任何数据类型B*/
    template <typename Iterator>
    struct iterator_traits_helper<Iterator,true>
        : public iterator_traits_impl<Iterator,
    std::is_convertible<typename Iterator::iterator_category,input_iterator_tag>::value ||
        std::is_convertible<typename Iterator::iterator_category,output_iterator_tag>::value>
        {};

    //萃取迭代器的特性
    template <typename Iterator>
    struct iterator_traits
        : public iterator_traits_helper<Iterator,has_iterator_cat<Iterator>::value>{};

    //针对原生指针的偏特化版本
    template <typename T>
    struct iterator_traits<T*> {	//非常量指针
        typedef random_access_iterator_tag		iterator_category;
        typedef T								value_type;
        typedef T*								pointer;
        typedef T&								reference;
        typedef ptrdiff_t						difference_type;
    };

    template <typename T>
    struct iterator_traits<const T*>	//常量指针
    {
        typedef random_access_iterator_tag      iterator_category;
        typedef T								value_type;
        typedef const T*                        pointer;
        typedef const T&                        reference;
        typedef ptrdiff_t                       difference_type;
    };

    template <typename T, typename U, bool = has_iterator_cat<iterator_traits<T>>::value>
        struct has_iterator_cat_of
            : public m_bool_constant<std::is_convertible<
                typename iterator_traits<T>::iterator_category, U>::value>
                {
                };

    //萃取某种迭代器
    template <typename T,typename U>
    struct has_iterator_cat_of<T,U,false>:public m_false_type {};

    template <typename Iter>
    struct is_input_iterator : public has_iterator_cat_of<Iter,input_iterator_tag> {};

    template <typename Iter>
    struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag> {};

    template <typename Iter>
    struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag> {};

    template <typename Iter>
    struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag> {};

    template <typename Iter>
    struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag> {};

    template <typename Iterator>
    struct is_iterator:
    public m_bool_constant<is_input_iterator<Iterator>::value||
        is_output_iterator<Iterator>::value>{};

    //萃取某个迭代器的category
    template <typename Iterator>
    typename iterator_traits<Iterator>::iterator_category
        iterator_category(const Iterator&) {
        typedef typename iterator_traits<Iterator>::iterator_category Category;
        return Category();
    }

    //萃取某个Iterator的difference_type
    template <typename Iterator>
    inline typename iterator_traits<Iterator>::difference_type*	//该行表示函数的返回类型
        distance_type(const Iterator&) {
        return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
    }

    template <typename Iterator>
    inline typename iterator_traits<Iterator>::value_type*
        value_type(const Iterator&) {
        return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
    }

    //下面函数用于计算迭代器间的距离

    //distance的input_iterator_tag版本 复杂度O(n)
    template<typename InputIterator>
    inline typename iterator_traits<InputIterator>::difference_type
        distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag) {
        typename iterator_traits<InputIterator>::difference_type n = 0;
        while (first != last) {
            ++first;
            ++n;
        }
        return n;
    }

    //distance的random_acces_iterator_tag的版本 复杂度O(1)
    template<typename RandomIterator>
    inline typename iterator_traits<RandomIterator>::difference_type
        distance_dispatch(RandomIterator first, RandomIterator last, random_access_iterator_tag) {
        return last - first;
    }

    template<typename InputIterator>
    inline typename iterator_traits<InputIterator>::difference_type
        distance(InputIterator first, InputIterator last) {
        return distance_dispatch(first, last, iterator_category(first));
    }

    //以下函数用于让迭代器前进n个距离

    // advance 的input_iterator_tag的版本
    template<typename InputIterator, typename Distance>
    inline void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
        while (n--) ++i;
    }

    // advance 的bidirectional_iterator_tag的版本
    template <typename BidirectionalIterator, typename Distance>
    inline void advance_dispatch(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
        if (n >= 0)
            while (n--) ++i;
        else
            while (n++) --i;
    }

    // advance 的random_access_iterator_tag的版本
    template<typename RandomIterator, typename Distance>
    inline void advance_dispatch(RandomIterator& i, Distance n, random_access_iterator_tag) {
        i += n;
    }

    template<typename InputIterator, typename Distance>
    inline void advance(InputIterator& i, Distance n) {
        advance_dispatch(i, n, iterator_category(i));
    }

    /**********************************************************************************************/

    // 模板类 : reverse_iterator
    //代表反向迭代器，使前进变为后退，后退为前进
    template <class Iterator>
        class reverse_iterator
        {
            private:
            Iterator current;	//记录对应的正向迭代器

            public:
            //单向迭代器的五种相应类别
            typedef typename iterator_traits<Iterator>::iterator_category	iterator_category;
            typedef typename iterator_traits<Iterator>::value_type			value_type;
            typedef typename iterator_traits<Iterator>::difference_type		difference_type;
            typedef typename iterator_traits<Iterator>::pointer				pointer;
            typedef typename iterator_traits<Iterator>::reference			reference;

            typedef Iterator												iterator_type;
            typedef reverse_iterator<Iterator>								self;

            public:
            //构造函数
            reverse_iterator() { }
            //下面这个构造函数将reverse_iterator与某个迭代器i系结起来
            explicit reverse_iterator(iterator_type i) : current(i) { }
            reverse_iterator(const self& rhs) : current(rhs.current) { }

            public:
            // 取出对应的正向迭代器
            iterator_type base() const{
                return current;
            }
            //重载操作符
            reference operator*() const { //实际应该对应正向迭代器的前一个位置
                Iterator tmp = current;
                return *--tmp;
            }
            pointer operator->() const { return &(operator*()); }

            //前进(++)变为后退(--)
            self& operator++() {	//前置
                --current;
                return *this;
            }
            self operator++(int) {	//后置
                self tmp = *this;
                --current;
                return tmp;
            }
            //后退(--)变为前进(++)
            self& operator--() {	//前置
                ++current;
                return *this;
            }
            self operator--(int) {	//后置
                self tmp = *this;
                ++current;
                return;
            }
            self& operator+=(difference_type n) {
                current -= n;
                return *this;
            }
            self operator+(difference_type n) const {
                return self(current - n);
            }
            self& operator-=(difference_type n) {
                current += n;
                return *this;
            }
            self operator-(difference_type n) const {
                return self(current + n);
            }
            //注意，下面第一个*和唯一一个+都会调用本类的对应重载函数，第二个*则不会
            reference operator[](difference_type n) const {
                return *(*this + n);
            }
        };

    //重载 operator - 
    template<typename Iterator>
    typename reverse_iterator<Iterator>::difference_type
        operator-(const reverse_iterator<Iterator>& lhs,
                  const reverse_iterator<Iterator>& rhs){
        return rhs.base() - lhs.base();
    }

    //重载比较操作符
    template <typename Iterator>
    bool operator==(const reverse_iterator<Iterator>& lhs,
                    const reverse_iterator<Iterator>&rhs) {
        return lhs.base() == rhs.base();
    }

    template <class Iterator>
        bool operator!=(const reverse_iterator<Iterator>& lhs,
                        const reverse_iterator<Iterator>& rhs){
        return !(lhs == rhs);
    }

    //注意大小比较是与正向迭代器相反的
    template <class Iterator>
        bool operator>(const reverse_iterator<Iterator>& lhs,
                       const reverse_iterator<Iterator>& rhs){
        return rhs < lhs;
    }

    template <class Iterator>
        bool operator<=(const reverse_iterator<Iterator>& lhs,
                        const reverse_iterator<Iterator>& rhs){
        return !(rhs < lhs);
    }

    template <class Iterator>
        bool operator>=(const reverse_iterator<Iterator>& lhs,
                        const reverse_iterator<Iterator>& rhs)
    {
        return !(lhs > rhs);
    }

}//namespace mystl
#endif // !MYTINYSTL_ITERATOR_H_

1. Input_iterator计算distance (difference_type)是O(n)复杂度，需要顺序查找。
2. random_access_iterator则是O(1)复杂度，直接相减就行。同样的想法也在advance函数（用于让迭代器前进n个位置）上体现。两种类型的iterator应该分开来处理保证最高的效率
3. 反向迭代器并不另外实现，而是全部在正向迭代器中操作，注意反向迭代器的begin为正向迭代器的end的前一个（并不相同），反向迭代器的last也为正向迭代器begin的前一个。另外大小的比较也是相反的。

注意重载前置后置运算符写法的区分：

（1）前置++重载时没有参数，而后置++重载时有参数。不会使用其参数，仅仅是区分用

（2）前置++需要返回引用，因为重载自加运算符后可以返回对象的引用， 以方便在表达式中连续使用。而后置++返回的不是引用，所以不能进行连续使用。

//前进(++)变为后退(--)
self& operator++() {	//前置
    --current;
    return *this;
}
self operator++(int) {	//后置
    self tmp = *this;
    --current;
    return tmp;
}
//后退(--)变为前进(++)
self& operator--() {	//前置
    ++current;
    return *this;
}
self operator--(int) {	//后置
    self tmp = *this;
    ++current;
    return;
}

allocator的设计

allocator.h源码

#ifndef MYTINYSTL_ALLOCATOR_H_
#define MYTINYSTL_ALLOCATOR_H_

//空间配置器，空间不一定是内存，也可以是磁盘或其它辅助存储介质
//该头文件包含一个模板类allocator，用于管理内存的分配。释放，对象的构造、析构

#include "construct.h"
#include "util.h"

namespace mystl 
{
    //模板类allocator 空间配置器
    //模板函数代表数据类型
    template <typename T>
    class allocator {
        public:
        typedef T			value_type;
        typedef T*			pointer;
        typedef const T*	const_pointer;
        typedef T&			reference;
        typedef const T&	const_reference;
        typedef size_t		size_type;
        typedef ptrdiff_t	difference_type;

        public:
        static T*	allocate();
        static T*	allocate(size_type n);	//分配一段原始的、未构造的内存，保存n个类型T的对象

        static void deallocate(T* ptr);		//释放从T*指针p中地址开始的内存
        //指明了这块内存保存了n个类型为T的对象，注意ptr必须是一个先前由allocate返回的指针，且n必须是ptr创建时要求的大小
        //在调用deallocate之前，用户必须对每个在这块内存中创建的对象调用destroy
        static void deallocate(T* ptr, size_type n);	

        //ptr必须是一个类型为T*的指针，指向一块原始内存；arg被传递给类型为T的构造函数，用来在p指向的内存中构造一个对象
        static void construct(T* ptr);
        static void construct(T* ptr, const T& value);
        static void construct(T* ptr, T&& value);

        template <typename...Args>
        static void construct(T* ptr, Args&&... args);

        static void destroy(T* ptr);		//对p指向的内存执行析构函数
        static void destroy(T* first, T* last);
    };

    template <typename T>
    inline T* allocator<T>::allocate() {		//开辟存储一个对象的空间
        return static_cast<T*>(::operator new(sizeof(T)));
    }

    template <typename T>
    inline T* allocator<T>::allocate(size_type n) {	//开辟存储n个对象的空间
        return n == 0 ? nullptr : static_cast<T*>(::operator new(n * sizeof(T)));
    }

    template <typename T>
    inline void allocator<T>::deallocate(T* ptr) {
        if (ptr == nullptr)
            return;
        ::operator delete(ptr);
    }

    template <class T>
        inline void allocator<T>::deallocate(T* ptr, size_type /*size*/)
        {
            if (ptr == nullptr)
                return;
            ::operator delete(ptr);
        }

    template <typename T>
    inline void allocator<T>::construct(T* ptr) {
        mystl::construct(ptr);
    }

    template <typename T>
    inline void allocator<T>::construct(T* ptr, const T& value){
        mystl::construct(ptr, value);
    }

    template <typename T>
    inline void allocator<T>::construct(T* ptr, T&& value){
        mystl::construct(ptr, mystl::move(value));
    }

    template <typename T>
    template <typename ...Args>
    inline void allocator<T>::construct(T* ptr, Args&& ...args){
        mystl::construct(ptr, mystl::forward<Args>(args)...);
    }

    template <typename T>
    inline void allocator<T>::destroy(T* ptr){
        mystl::destroy(ptr);
    }

    template <class T>
        void allocator<T>::destroy(T* first, T* last){
            mystl::destroy(first, last);
        }

}// namespace mystl

#endif // !MYTINYSTL_ALLOCATOR_H_

construct.h源码：

#ifndef MYTINYSTL_CONSTRUCT_H_
#define MYTINYSTL_CONSTRUCT_H_

//这个头文件包含两个函数 construct,destroy
//construct 负责对象的构造， destroy负责对象的析构

#include <new>		//使用placement new
#include "type_traits.h"
#include "iterator.h"

#ifdef _MSC_VER
#pragma warning(push)			//保存当前的编译器警告状态
#pragma warning(disable:4100)	//unused parameter
#endif //_MSC_VER

namespace mystl {

    //构造对象

    template <typename Ty>
    inline void construct(Ty* ptr) {
        ::new ((void*)ptr) Ty();		//使用placement new来进行构造;这是operator new的一个重载版本、允许你在一个已经分配好的内存中（栈或堆中）构造一个新的对象，其中的void*p实际上就是指向一个已经分配好的内存缓冲区的的首地址。(void*)ptr实际上指向已经分配好的内存缓冲区的首地址
    }

    template <typename Ty1,typename Ty2>
    inline void construct(Ty1* ptr, const Ty2& value) {
        ::new ((void*)ptr) Ty1(value);	//placement new; 调用T1::T1(value)
    }

    template <typename Ty,typename... Args>
    inline void construct(Ty* ptr, Args&&... args) {
        ::new((void*)ptr) Ty(mystl::forward<Args>(args)...);
    }

    //destroy将对象析构

    //以下为destroy的第一版本，接受一个指针，泛化版本
    template <typename Ty>
    inline void destroy_one(Ty*, std::true_type){}

    //特化版本
    template<typename Ty>
    inline void destroy_one(Ty* pointer, std::false_type) {
        if (pointer != nullptr) {
            pointer->~Ty();
        }
    }

    //以下为destroy的第二版本，接受两个迭代器，泛化版本
    template <typename ForwardIterator>
    inline void destroy_two(ForwardIterator first,ForwardIterator last,std::true_type){}

    //特化版本
    template <typename ForwardIterator>
    inline void destroy_two(ForwardIterator first, ForwardIterator last, std::false_type) {
        for (; first != last; ++first) {
            destroy(&*first);
        }
    }

    template <typename Ty>
    inline void destroy(Ty* pointer) {
        destroy_one(pointer, std::is_trivially_destructible<Ty>{});
    }

    template<typename ForwardIterator>
    inline void destroy(ForwardIterator first, ForwardIterator last) {
        destroy_two(first, last, std::is_trivially_destructible<
                    typename iterator_traits<ForwardIterator>::value_type>{});
    }

}	//namespace mystl



#ifdef _MSC_VER
#pragma warning(pop)			//恢复原先的警告状态
#endif //_MSC_VER

#endif // !MYTINYSTL_CONSTRUCT_H_

首先对于C++中的delete和new函数进行一些解释：

• 在我们使用new来建造一个对象的时候，一般是分为两个步骤的：
  • 调用**::operator new()**来构建空间；注：::operator new内部由malloc实现、省略指针转换这步。
  • 调用对象的构造函数
• 同理，当我们使用delete函数的时候：
  • 调用对象的析构函数
  • 调用**::operator delete()**释放空间。注：::operator delete内部由free实现

在STL的实现中，我们为了实现精细化分工将上述步骤的两个阶段分开来操作。

• 内存的配置和释放分别由allocate()和deallocate()负责

• 对象构建和析构的操作分别由construct()和destroy()负责

这里我们实现的allocator的内存配置和释放操作只对::operator new 和::operator delete作了一层简单的封装，因此效率比较差，如果要提高效率要实现内存池的技术

简单阐述一下SGI STL中实现的具备次配置力的空间配置器alloc

https://www.daimajiaoliu.com/daima/9eb85665d156c00

设计目的：要求考虑多线程状态，要考虑内存不足时的应变措施，要考虑过多“小型区块”可能造成的内存碎片的问题

简单总结功能：

SGI版本的STL中使用的空间配置器有多级：

• 如果分配的内存区块够大，超过128bytes时，就移交第一级配置器处理（直接使用malloc，free）。
• 如果分配的内存区块比较小（过多的小额区块会造成内存碎片，并且注意需要考虑每次配置都需要的额外负担）。当小于128bytes时，以内存池进行管理（称为次层配置）：每次配置一大块内存，并维护对应的自由链表，下次若再由相同大小的内存需求，就直接从自由链表free-list中拨出。如果释放小型区块，则回收到free-list中。
• 为了方便管理，二级配置器会主动将任何小额区块的内存需求量上调至8的倍数。

uninitialized.h

1. 这个头文件用于对未初始化的空间构造元素（使用construct和destroy），并要对一些情况保证异常安全
2. 定义了uninitialized_copy, uninitialized_copy_n, uninitialized_fill, uninitialized_fill_n, uninitialized_move, uninitialized_move_n.
3. 另外加上我们定义在别的头文件上的construct()和destroy()。这些全局函数都作用于未初始化空间上，对于容器的实现很有帮助（使我们将内存配置与对象的构造行为分离开来）。互相之间的代码实现上相差不大。

例如uninitialized_copy函数，如果我们的对象提供了显式的赋值运算，则不能通过直接copy来实现，而需要通过迭代器一个对象一个对象构造，为了保证异常安全，我们还需要记录一个指向目标区间开头的指针，假如在构造的中途出现了异常，需要把之前构造的所有对象都销毁，保证不出现内存泄漏。

但是如果我们的对象是POD（源码解析中的称呼，Plain Old Data），也就是标量类型的或是传统的C struct类型，则必然拥有trival ctor/dtor/copy/assignment 函数，因此可以使用最有效率的初值填写手法（直接调用上层copy等函数，传入的参数会调用使用C库函数实现的版本）。而对非POD类型的对象采取保险安全的做法。

copy（理念就是尽可能使用C标准函数memmove，直接复制内存，来加强效率。另外区分随机访问迭代器也会有所不同（利用萃取的机制提取迭代器的类型tag）。要设计一些列泛化及特化的版本）

源码：

#ifndef MYTINYSTL_UNINITIALIZED_H_
#define MYTINYSTL_UNINITIALIZED_H_

//这个头文件用于对未初始化的空间构造元素
#include "algobase.h"
#include "construct.h"
#include "iterator.h"
#include "type_traits.h"
#include "util.h"

namespace mystl {

    /*****************************************************************************************/
    // uninitialized_copy
    // 把 [first, last) 上的内容复制到以 result 为起始处的空间，返回复制结束的位置
    // 对于隐式提供赋值运算符的类，可以简单使用mystl::copy，否则，要保证异常安全
    /*****************************************************************************************/
    template <typename InputIter, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_copy(InputIter first, InputIter last, ForwardIter result, std::true_type) {
        return mystl::copy(first, last, result);
    }

    template <typename InputIter, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_copy(InputIter first, InputIter last, ForwardIter result, std::false_type) {
        auto cur = result;
        try {
            for (; first != last; ++first, ++cur) {
                mystl::construct(&*cur, *first);
            }
        }
        catch (...) {
            for (; result != cur; --cur) {
                mystl::destroy(&*cur);
            }
        }
        return cur;
    }

    template <typename InputIter, typename ForwardIter>
    inline ForwardIter uninitialized_copy(InputIter first, InputIter last, ForwardIter result) {
        return mystl::unchecked_uninit_copy(first, last, result,
                                            std::is_trivially_copy_assignable<		//如果类的赋值运算符是隐式提供的，则为真
                                            typename iterator_traits<ForwardIter>::
                                            value_type>{});
    }

    /*****************************************************************************************/
    // uninitialized_copy_n
    // 把 [first, first + n) 上的内容复制到以 result 为起始处的空间，返回复制结束的位置
    /*****************************************************************************************/
    template <typename InputIter, typename Size, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_copy_n(InputIter first, Size n, ForwardIter result, std::true_type){
        return mystl::copy_n(first, n, result).second;
    }

    template <typename InputIter, typename Size, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_copy_n(InputIter first, Size n, ForwardIter result, std::false_type){
        auto cur = result;
        try{
            for (; n > 0; --n, ++cur, ++first){
                mystl::construct(&*cur, *first);
            }
        }
        catch (...){
            for (; result != cur; --cur)
                mystl::destroy(&*cur);
        }
        return cur;
    }

    template <typename InputIter, typename Size, typename ForwardIter>
    inline ForwardIter uninitialized_copy_n(InputIter first, Size n, ForwardIter result){
        return mystl::unchecked_uninit_copy_n(first, n, result,
                                              std::is_trivially_copy_assignable<
                                              typename iterator_traits<InputIter>::
                                              value_type>{});
    }

    /*****************************************************************************************/
    // uninitialized_fill
    // 在 [first, last) 区间内填充元素值
    /*****************************************************************************************/
    template <typename ForwardIter, typename T>
    inline void
    unchecked_uninit_fill(ForwardIter first, ForwardIter last, const T& value, std::true_type){
        mystl::fill(first, last, value);
    }

    template <typename ForwardIter, typename T>
    inline void
    unchecked_uninit_fill(ForwardIter first, ForwardIter last, const T& value, std::false_type)
    {
        auto cur = first;
        try{
            for (; cur != last; ++cur){
                mystl::construct(&*cur, value);
            }
        }
        catch (...){
            for (; first != cur; ++first)
                mystl::destroy(&*first);
        }
    }

    template <typename ForwardIter, typename T>
    inline void  uninitialized_fill(ForwardIter first, ForwardIter last, const T& value){
        mystl::unchecked_uninit_fill(first, last, value,
                                     std::is_trivially_copy_assignable<
                                     typename iterator_traits<ForwardIter>::
                                     value_type>{});
    }

    /*****************************************************************************************/
    // uninitialized_fill_n
    // 从 first 位置开始，填充 n 个元素值，返回填充结束的位置
    /*****************************************************************************************/
    template <typename ForwardIter, typename Size, typename T>
    inline ForwardIter
    unchecked_uninit_fill_n(ForwardIter first, Size n, const T& value, std::true_type){
        return mystl::fill_n(first, n, value);
    }

    template <typename ForwardIter, typename Size, typename T>
    inline ForwardIter
    unchecked_uninit_fill_n(ForwardIter first, Size n, const T& value, std::false_type){
        auto cur = first;
        try{
            for (; n > 0; --n, ++cur){
                mystl::construct(&*cur, value);
            }
        }
        catch (...){
            for (; first != cur; ++first)
                mystl::destroy(&*first);
        }
        return cur;
    }

    template <typename ForwardIter, typename Size, typename T>
    inline ForwardIter uninitialized_fill_n(ForwardIter first, Size n, const T& value){
        return mystl::unchecked_uninit_fill_n(first, n, value,
                                              std::is_trivially_copy_assignable<
                                              typename iterator_traits<ForwardIter>::
                                              value_type>{});
    }

    /*****************************************************************************************/
    // uninitialized_move
    // 把[first, last)上的内容移动到以 result 为起始处的空间，返回移动结束的位置
    /*****************************************************************************************/
    template <typename InputIter, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_move(InputIter first, InputIter last, ForwardIter result, std::true_type){
        return mystl::move(first, last, result);
    }

    template <typename InputIter, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_move(InputIter first, InputIter last, ForwardIter result, std::false_type){
        ForwardIter cur = result;
        try{
            for (; first != last; ++first, ++cur){
                mystl::construct(&*cur, mystl::move(*first));
            }
        }
        catch (...){
            mystl::destroy(result, cur);	//销毁范围内的所有元素
        }
        return cur;
    }

    template <typename InputIter, typename ForwardIter>
    inline ForwardIter uninitialized_move(InputIter first, InputIter last, ForwardIter result){
        return mystl::unchecked_uninit_move(first, last, result,
                                            std::is_trivially_move_assignable<
                                            typename iterator_traits<InputIter>::
                                            value_type>{});
    }

    /*****************************************************************************************/
    // uninitialized_move_n
    // 把[first, first + n)上的内容移动到以 result 为起始处的空间，返回移动结束的位置
    /*****************************************************************************************/
    template <typename InputIter, typename Size, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_move_n(InputIter first, Size n, ForwardIter result, std::true_type){
        return mystl::move(first, first + n, result);
    }

    template <typename InputIter, typename Size, typename ForwardIter>
    inline ForwardIter
    unchecked_uninit_move_n(InputIter first, Size n, ForwardIter result, std::false_type){
        auto cur = result;
        try{
            for (; n > 0; --n, ++first, ++cur){
                mystl::construct(&*cur, mystl::move(*first));
            }
        }
        catch (...){
            for (; result != cur; ++result)
                mystl::destroy(&*result);
            throw;
        }
        return cur;
    }

    template <class InputIter, class Size, class ForwardIter>
        ForwardIter uninitialized_move_n(InputIter first, Size n, ForwardIter result){
        return mystl::unchecked_uninit_move_n(first, n, result,
                                              std::is_trivially_move_assignable<
                                              typename iterator_traits<InputIter>::
                                              value_type>{});
    }
}
#endif // !MYTINYSTL_UNINITIALIZED_H_

注意在uninitialized_move中，如果移动了一部分元素后发生了异常，则会销毁已经移动过去的部分，原始部分的对象也不会恢复，因此容易出错，要尽量保证移动的安全性。

memory.h

设计内存管理关于未初始化的空间的一些操作。包含了智能指针的实现

源码：

#ifndef MYTINYSTL_MEMORY_H_
#define MYTINYSTL_MEMORY_H_

//这个头文件负责更高级的动态内存管理
//包含一些基本函数、空间配置器、未初始化的储存空间管理，以及一个模板类auto_ptr

#include <cstddef>
#include <cstdlib>
#include <climits>

#include "algobase.h"
#include "allocator.h"
#include "construct.h"
#include "uninitialized.h"

namespace mystl{

    //获取对象地址
    template <typename Tp>
    constexpr Tp* address_of(Tp& value) noexcept {
        return &value;
    }

    //获取、释放 临时缓冲区
    template <typename T>
    pair<T*, ptrdiff_t> get_buffer_helper(ptrdiff_t len, T*) {
        if (len > static_cast<ptrdiff_t>(INT_MAX / sizeof(T)))
            len = INT_MAX / sizeof(T);
        while (len > 0) {
            T* tmp = static_cast<T*>(malloc(static_cast<size_t>(len) * sizeof(T)));
            if (tmp!=nullptr)		//如果分配成功
                return pair<T*, ptrdiff_t>(tmp, len);
            len /= 2;		//如果分配失败则减少len的大小
        }
        return pair<T*, ptrdiff_t>(nullptr, 0);
    }

    template<typename T>
    pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t len) {
        return get_buffer_helper(len, static_cast<T*>(0));
    }

    template<typename T>
    pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t len, T*) {
        return get_buffer_helper(len, static_cast<T*>(0));
    }

    template<typename T>
    void release_temporary_buffer(T* ptr) {
        free(ptr);
    }
    /*************************************************************************************/
    // 类模板 : temporary_buffer
    // 进行临时缓冲区的申请与释放
    /*************************************************************************************/
    template <typename ForwardIter, typename T>
    class temporary_buffer {
        private:
        ptrdiff_t original_len;	//缓冲区申请的大小
        ptrdiff_t len;			//缓冲区实际的大小
        T*		  buffer;		//指向缓冲区的指针

        public:
        //构造、析构函数
        temporary_buffer(ForwardIter first, ForwardIter last);
        ~temporary_buffer() {
            mystl::destroy(buffer, buffer + len);
            free(buffer);
        }
        public:
        ptrdiff_t size()           const noexcept { return len; }
        ptrdiff_t requested_size() const noexcept { return original_len; }
        T*        begin()                noexcept { return buffer; }
        T*        end()                  noexcept { return buffer + len; }

        private:
        void allocate_buffer();
        void initialize_buffer(const T&, std::true_type) { }
        void initialize_buffer(const T& value, std::false_type) {
            mystl::uninitialized_fill_n(buffer, len, value);
        }

        private:
        temporary_buffer(const temporary_buffer&);
        void operator=(const temporary_buffer&);
    };

    //构造函数
    template <typename ForwardIter, typename T>
    temporary_buffer<ForwardIter,T>::
    temporary_buffer(ForwardIter first, ForwardIter last) {
        try {
            len = mystl::distance(first, last);
            allocate_buffer();
            if (len > 0) {
                initialize_buffer(*first, std::is_trivially_default_constructible<T>());
            }
        }
        catch (...) {
            free(buffer);
            buffer = nullptr;
            len = 0;
        }
    }

    //allocate_buffer函数
    template <typename ForwardIter, typename T>
    void temporary_buffer<ForwardIter, T>::allocate_buffer() {
        original_len = len;
        if (len > static_cast<ptrdiff_t>(INT_MAX / sizeof(T)))
            len = INT_MAX / sizeof(T);
        while (len > 0) {
            buffer = static_cast<ptrdiff_t>(malloc(len * sizeof(T)));
            if (buffer != nullptr)
                break;
            len /= 2;	//申请失败时减小申请空间大小
        }
    }

    /*************************************************************************************/
    // 模板类: auto_ptr
    // 一个具有严格对象所有权的小型智能指针
    /*************************************************************************************/
    template <typename T>
    class auto_ptr {
    public:
        typedef T		elem_type;

    private:
        T* m_ptr;	//实际指针

    public:
        //构造、拷贝、析构函数
        explicit auto_ptr(T* p = nullptr) :m_ptr(p) { }
        auto_ptr(auto_ptr& rhs) :m_ptr(rhs.release()) { }
        template<typename U>
        auto_ptr(auto_ptr<U>& rhs) : m_ptr(rhs.release()) { }

        auto_ptr& operator=(auto_ptr& rhs) {
            if (this != &rhs) {		//只处理非自赋值情况，另外保证智能指针的独占性
                delete m_ptr;
                m_ptr = rhs.release();
            }
            return *this;
        }

        template<typename U>
        auto_ptr& operator=(auto_ptr<U>& rhs) {
            if (this->get() != rhs.get()) {
                delete m_ptr;
                m_ptr = rhs.release();
            }
            return *this;
        }

        ~auto_ptr() { delete m_ptr; m_ptr = nullptr; }

        public:
        //重载operator* 和 operator->
        T& operator*() const { return *m_ptr; }
        T* operator->() const { return m_ptr; }

        //获得指针
        T* get() const { return m_ptr; }

        //释放指针,将原智能指针的控制权取消
        T* release() {
            T* tmp = m_ptr;
            m_ptr = nullptr;
            return tmp;
        }

        //重置指针，取消auto_ptr对原对象的控制权，并选择性提供一个新的对象控制权
        void reset(T* p = nullptr) {
            if (m_ptr != p) {
                delete m_ptr;
                m_ptr = p;
            }
        }

    };
    /*************************************************************************************/
    // 模板类: shared_ptr
    // C++11新标准的智能指针
    /*************************************************************************************/
    template <typename T>
    class shared_ptr {
    private:
        int* count;//共享一个计数器
        T* m_ptr;
    public:
        shared_ptr(T* p=nullptr):count(new int(1)),m_ptr(p){ }
        shared_ptr(shared_ptr<T>& other): count(&(++*other.count)),m_ptr(other.m_ptr){ }
        T* operator->() { return m_ptr; }	//调用
        T& operator*() { return *m_ptr; }	//解引用

        shared_ptr<T>& operator=(shared_ptr<T>& other) {
            if (this != &other) {
                ++*other.count;	//	计数器加一
                if (this->m_ptr && 0 == --*this->count) {
                    delete count;
                    delete m_ptr;
                }
                this->m_ptr = other.m_ptr;
                this->count = other.count;
            }
            return *this;
        }

        ~shared_ptr() {
            if (--*count == 0) {
                delete count;
                count = nullptr;
                delete m_ptr;
                m_ptr = nullptr;
            }
        }
        int getRef() { return *count; }
    };

    /*************************************************************************************/
    // 模板类: unique_ptr
    // C++11新标准的智能指针,类似auto_ptr，但功能更强大
    /*************************************************************************************/
    template <typename T>
    class Delete { //默认删除器
        public:
        template<typename T>
        void operator()(T* p) {
            if (p) {
                delete p;
                p = nullptr;
            }
        }
    };
    template <typename T,typename D=Delete<T>>
    class unique_ptr {
        private:
        T* m_ptr = nullptr;
        D del;
        public:
        explicit unique_ptr(T* pp = nullptr, const D& dd=D()):
        m_ptr(pp),del(dd){ }
        ~unique_ptr() { del(m_ptr); }

        /*注意unique_ptr不支持普通的拷贝和赋值，因此要将相应的拷贝控制成员定义成delete*/ 
        unique_ptr(const unique_ptr&) = delete;
        unique_ptr& operator=(const unique_ptr&) = delete;

        /*但是可以拷贝或赋值一个将要被销毁的unique_ptr (右值引用)*/
        unique_ptr(unique_ptr&& rvalue) :
        m_ptr(rvalue.m_ptr), del(mystl::move(rvalue.del)) {
            rvalue.m_ptr = nullptr;
        }
        unique_ptr& operator=(unique_ptr&& rvalue) noexcept {
            if (this != &rvalue) {
                del(*this);
                m_ptr = rvalue.m_ptr;
                del = mystl::move(rvalue.del);
                rvalue.m_ptr = nullptr;
            }
            return *this;
        }

        T* release(){
            T* tmp = m_ptr;
            m_ptr = nullptr;
            return tmp;
        }
        /*
	u.reset()   释放u指向的对象
	u.reset(q)  如果提供了内置指针q，就令u指向这个对象
	u.reset(nullptr)  将u置为空
	*/
        void reset() { del(m_ptr); }
        void reset(T* q) {
            if (m_ptr) {
                del(m_ptr);
                m_ptr = q;
            }
            else
                m_ptr = nullptr;
        }
        void swap(unique_ptr &other) noexcept {
            using mystl::swap;
            swap(m_ptr, other.m_ptr);
            swap(del, other.del);
        }
        T* get() { return m_ptr; }
        D& get_deleter() { return del; }
        T& operator*() { return *m_ptr; }
        T* operator->() { return m_ptr; }
    };

}; //namespace mystl


#endif // !MYTINYSTL_MEMORY_H_

vector.h

1. vector与array非常相似，唯一的差别在与空间运用的灵活性。array使用的是静态空间，一旦配置了就不能改变；vector是动态空间，随着元素的加入，内部机制会自行扩充空间以容纳新元素。
2. 注意扩充空间的实质是“配置新空间->数据移动->释放旧空间”的过程，时间成本很高，因此不应该每新增一个元素就只扩充一个元素的空间。

注意vector中size()和capacity()是不同的：

• capacity()，返回对象缓冲区（vector维护的内存空间）实际申请的空间大小
• size()，返回当前对象缓冲区存储数据的个数。
• 对于vector来说，capacity是永远大于等于size的，当capacity和size相等时，当再新增元素时，vector就会扩容，capacity变大。扩容的方式不同的编译器不同，一般是成一定的倍数增长。（我们的代码中采用0.5倍增长）

另外注意当我们调用erase()和clear()时，实际上只是减小了size并没有减小capacity。

vector中定义的主要成员：

1. 迭代器相关：begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
2. 容量相关：empty(), size(), max_size(), capacity(), reserve(size_type n), shrink_to_fit()
3. 访问元素相关：operator[], at(), front(), back(),
4. 修改容器相关：assign(), emplace()/emplace_back(), push_back()/pop_back(), insert(), erase(), clear(),resize(), reverse(), swap()

内存分配方式：

• 初始开辟的内存空间最小为16个对象的大小（默认构造函数分配16个对象大小的空间），不管构造函数是否填充元素。

• 如果构造函数需要分配n个对象的空间（n大于16），则只开辟n个对象大小。

• 扩容内存空间方式：

  • 当我们需要增加capacity时，需要构建一个临时对象开辟一块新的空间，然后利用swap函数进行成员的交换。由于是临时对象，因此离开作用域时会被自动销毁。算是一个trick。

    //swap定义在utils.h中，使用移动语义来避免拷贝
    template <typename Tp>
    void swap(Tp& lhs, Tp& rhs) {
    	Tp tmp(mystl::move(lhs));
    	lhs = mystl::move(rhs);
    	rhs = mystl::move(tmp);
    }
    
    //参考了cpp reference中的swap_ranges源码
    template <typename ForwardIt1, typename ForwardIt2>
    constexpr ForwardIt2 swap_ranges(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2) {
    	while (first1 != last1) {
    		mystl::swap(first1++, first2++);
    	}
    	return first2;
    }

• erase和clear：注意其中调用的是destroy(iterator)，因此如果数组中存放的是对象的指针，并不会调用对象的析构函数，因此在erase和clear之前要将对应的对象的指针delete（调用析构函数）

• insert函数需要考虑插入元素的个数是否大于容器内剩余的备用空间，如果备用空间充足又要考虑是否在目前的size()范围内。书中的uninitialized_copy全部被uninitialized_move代替，更高效

源码：

#ifndef MYTINYSTL_VECTOR_H_
#define MYTINYSTL_VECTOR_H_

/*
	这个头文件包含一个模板类vector

	异常保证：
	mystl::vector<T>满足基本异常保证，部分函数无异常保证，并对以下函数做强异常安全保证：
		emplace
		emplace_back
		push_back
	当std::is_nothrow_move_assignable<T>::value == true 时，以下函数也满足强异常保证：
		reserve
		resize
		insert

*/

#include <initializer_list>

#include "iterator.h"
#include "memory.h"
#include "util.h"
#include "exceptdef.h"

namespace mystl {

#ifdef max
#pragma message("#undefining marco max")
#undef max
#endif

#ifdef min
#pragma message("#undefining marco min")
#undef min
#endif

//模板类vector
//模板参数T代表类型

template<typename T>
class vector {
	static_assert(!std::is_same<bool, T>::value, "vector<bool> is abandoned in mystl");
public:
	//vector的嵌套型别定义
	typedef mystl::allocator<T>                      allocator_type;
	typedef mystl::allocator<T>                      data_allocator;

	typedef typename allocator_type::value_type      value_type;
	typedef typename allocator_type::pointer         pointer;
	typedef typename allocator_type::const_pointer   const_pointer;
	typedef typename allocator_type::reference       reference;
	typedef typename allocator_type::const_reference const_reference;
	typedef typename allocator_type::size_type       size_type;
	typedef typename allocator_type::difference_type difference_type;

	typedef value_type*                              iterator;
	typedef const value_type*                        const_iterator;
	typedef mystl::reverse_iterator<iterator>        reverse_iterator;
	typedef mystl::reverse_iterator<const_iterator>  const_reverse_iterator;

	allocator_type get_allocator() { return data_allocator(); }

private:
	iterator begin_;  // 表示目前使用空间的头部
	iterator end_;    // 表示目前使用空间的尾部
	iterator cap_;    // 表示目前储存空间的尾部

public:
	//构造、赋值、移动、析构函数
	vector() noexcept{
		try_init();
	}

	explicit vector(size_type n){
		fill_init(n, value_type());
	}

	vector(size_type n, const value_type& value){
		fill_init(n, value);
	}
	template <class Iter, typename std::enable_if<
		mystl::is_input_iterator<Iter>::value, int>::type = 0>
		vector(Iter first, Iter last){
		MYSTL_DEBUG(!(last < first));
		range_init(first, last);
	}

	vector(const vector& rhs){
		range_init(rhs.begin_, rhs.end_);
	}

	vector(vector&& rhs) noexcept
		:begin_(rhs.begin_),
		end_(rhs.end_),
		cap_(rhs.cap_){
		rhs.begin_ = nullptr;
		rhs.end_ = nullptr;
		rhs.cap_ = nullptr;
	}

	vector(std::initializer_list<value_type> ilist){
		range_init(ilist.begin(), ilist.end());
	}

	vector& operator=(const vector& rhs);
	vector& operator=(vector&& rhs) noexcept;

	vector& operator=(std::initializer_list<value_type> ilist){
		vector tmp(ilist.begin(), ilist.end());
		swap(tmp);
		return *this;
	}

	~vector(){
		destroy_and_recover(begin_, end_, cap_ - begin_);
		begin_ = end_ = cap_ = nullptr;
	}

public:

	// 迭代器相关操作
	iterator               begin()         noexcept{
		return begin_;
	}
	const_iterator         begin()   const noexcept{
		return begin_;
	}
	iterator               end()           noexcept{
		return end_;
	}
	const_iterator         end()     const noexcept{
		return end_;
	}

	reverse_iterator       rbegin()        noexcept{
		return reverse_iterator(end());
	}
	const_reverse_iterator rbegin()  const noexcept{
		return const_reverse_iterator(end());
	}
	reverse_iterator       rend()          noexcept{
		return reverse_iterator(begin());
	}
	const_reverse_iterator rend()    const noexcept{
		return const_reverse_iterator(begin());
	}

	const_iterator         cbegin()  const noexcept{
		return begin();
	}
	const_iterator         cend()    const noexcept{
		return end();
	}
	const_reverse_iterator crbegin() const noexcept{
		return rbegin();
	}
	const_reverse_iterator crend()   const noexcept{
		return rend();
	}

	// 容量相关操作
	bool      empty()    const noexcept{
		return begin_ == end_;
	}
	size_type size()     const noexcept{
		return static_cast<size_type>(end_ - begin_);
	}
	size_type max_size() const noexcept{
		return static_cast<size_type>(-1) / sizeof(T); 
	}
	size_type capacity() const noexcept{
		return static_cast<size_type>(cap_ - begin_);
	}
	void      reserve(size_type n);
	void      shrink_to_fit();

	// 访问元素相关操作
	reference operator[](size_type n){
		MYSTL_DEBUG(n < size());
		return *(begin_ + n);
	}
	const_reference operator[](size_type n) const{
		MYSTL_DEBUG(n < size());
		return *(begin_ + n);
	}
	reference at(size_type n){
		THROW_OUT_OF_RANGE_IF(!(n < size()), "vector<T>::at() subscript out of range");
		return (*this)[n];
	}
	const_reference at(size_type n) const{
		THROW_OUT_OF_RANGE_IF(!(n < size()), "vector<T>::at() subscript out of range");
		return (*this)[n];
	}

	reference front(){
		MYSTL_DEBUG(!empty());
		return *begin_;
	}
	const_reference front() const{
		MYSTL_DEBUG(!empty());
		return *begin_;
	}
	reference back(){
		MYSTL_DEBUG(!empty());
		return *(end_ - 1);
	}
	const_reference back() const{
		MYSTL_DEBUG(!empty());
		return *(end_ - 1);
	}

	pointer       data()       noexcept { return begin_; }
	const_pointer data() const noexcept { return begin_; }

	// 修改容器相关操作

	// assign

	void assign(size_type n, const value_type& value){
		fill_assign(n, value);
	}

	template <class Iter, typename std::enable_if<
		mystl::is_input_iterator<Iter>::value, int>::type = 0>
		void assign(Iter first, Iter last){
		MYSTL_DEBUG(!(last < first));
		copy_assign(first, last, iterator_category(first));
	}

	void assign(std::initializer_list<value_type> il){
		copy_assign(il.begin(), il.end(), mystl::forward_iterator_tag{});
	}

	// emplace / emplace_back

	template <class... Args>
	iterator emplace(const_iterator pos, Args&& ...args);

	template <class... Args>
	void emplace_back(Args&& ...args);

	// push_back / pop_back

	void push_back(const value_type& value);
	void push_back(value_type&& value){
		emplace_back(mystl::move(value));
	}

	void pop_back();

	// insert

	iterator insert(const_iterator pos, const value_type& value);
	iterator insert(const_iterator pos, value_type&& value){
		return emplace(pos, mystl::move(value));
	}

	iterator insert(const_iterator pos, size_type n, const value_type& value){
		MYSTL_DEBUG(pos >= begin() && pos <= end());
		return fill_insert(const_cast<iterator>(pos), n, value);
	}

	template <class Iter, typename std::enable_if<
		mystl::is_input_iterator<Iter>::value, int>::type = 0>
		void     insert(const_iterator pos, Iter first, Iter last){
		MYSTL_DEBUG(pos >= begin() && pos <= end() && !(last < first));
		copy_insert(const_cast<iterator>(pos), first, last);
	}

	// erase / clear
	iterator erase(const_iterator pos);
	iterator erase(const_iterator first, const_iterator last);
	void     clear() { erase(begin(), end()); }

	// resize / reverse
	void     resize(size_type new_size) { return resize(new_size, value_type()); }
	void     resize(size_type new_size, const value_type& value);

	void     reverse() { mystl::reverse(begin(), end()); }

	// swap
	void     swap(vector& rhs) noexcept;

private:
	// helper functions

	// initialize / destroy
	void      try_init() noexcept;

	void      init_space(size_type size, size_type cap);

	void      fill_init(size_type n, const value_type& value);
	template <class Iter>
	void      range_init(Iter first, Iter last);

	void      destroy_and_recover(iterator first, iterator last, size_type n);

	// calculate the growth size
	size_type get_new_cap(size_type add_size);

	// assign

	void      fill_assign(size_type n, const value_type& value);

	template <class IIter>
	void      copy_assign(IIter first, IIter last, input_iterator_tag);

	template <class FIter>
	void      copy_assign(FIter first, FIter last, forward_iterator_tag);

	// reallocate

	template <class... Args>
	void      reallocate_emplace(iterator pos, Args&& ...args);
	void      reallocate_insert(iterator pos, const value_type& value);

	// insert

	iterator  fill_insert(iterator pos, size_type n, const value_type& value);
	template <class IIter>
	void      copy_insert(iterator pos, IIter first, IIter last);

	// shrink_to_fit

	void      reinsert(size_type size);
};

/*****************************************************************************************/

// 拷贝赋值操作符
template <class T>
vector<T>& vector<T>::operator=(const vector& rhs)
{
	if (this != &rhs)
	{
		const auto len = rhs.size();
		if (len > capacity())
		{
			vector tmp(rhs.begin(), rhs.end());
			swap(tmp);
		}
		else if (size() >= len)
		{
			auto i = mystl::copy(rhs.begin(), rhs.end(), begin());
			data_allocator::destroy(i, end_);
			end_ = begin_ + len;
		}
		else
		{
			mystl::copy(rhs.begin(), rhs.begin() + size(), begin_);
			mystl::uninitialized_copy(rhs.begin() + size(), rhs.end(), end_);
			cap_ = end_ = begin_ + len;
		}
	}
	return *this;
}

// 移动赋值操作符
template <class T>
vector<T>& vector<T>::operator=(vector&& rhs) noexcept
{
	destroy_and_recover(begin_, end_, cap_ - begin_);
	begin_ = rhs.begin_;
	end_ = rhs.end_;
	cap_ = rhs.cap_;
	rhs.begin_ = nullptr;
	rhs.end_ = nullptr;
	rhs.cap_ = nullptr;
	return *this;
}

// 预留空间大小，当原容量小于要求大小时，才会重新分配
template <class T>
void vector<T>::reserve(size_type n){
	if (capacity() < n)
	{
		THROW_LENGTH_ERROR_IF(n > max_size(),
			"n can not larger than max_size() in vector<T>::reserve(n)");
		const auto old_size = size();
		auto tmp = data_allocator::allocate(n);
		mystl::uninitialized_move(begin_, end_, tmp);
		data_allocator::deallocate(begin_, cap_ - begin_);
		begin_ = tmp;
		end_ = tmp + old_size;
		cap_ = begin_ + n;
	}
}

// 放弃多余的容量
template <class T>
void vector<T>::shrink_to_fit()
{
	if (end_ < cap_)
	{
		reinsert(size());
	}
}

// 在 pos 位置就地构造元素，避免额外的复制或移动开销
template <class T>
template <class ...Args>
typename vector<T>::iterator
vector<T>::emplace(const_iterator pos, Args&& ...args)
{
	MYSTL_DEBUG(pos >= begin() && pos <= end());
	iterator xpos = const_cast<iterator>(pos);
	const size_type n = xpos - begin_;
	if (end_ != cap_ && xpos == end_)
	{
		data_allocator::construct(mystl::address_of(*end_), mystl::forward<Args>(args)...);
		++end_;
	}
	else if (end_ != cap_)
	{
		auto new_end = end_;
		data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
		++new_end;
		mystl::copy_backward(xpos, end_ - 1, end_);
		*xpos = value_type(mystl::forward<Args>(args)...);
	}
	else
	{
		reallocate_emplace(xpos, mystl::forward<Args>(args)...);
	}
	return begin() + n;
}

// 在尾部就地构造元素，避免额外的复制或移动开销
template <class T>
template <class ...Args>
void vector<T>::emplace_back(Args&& ...args)
{
	if (end_ < cap_)
	{
		data_allocator::construct(mystl::address_of(*end_), mystl::forward<Args>(args)...);
		++end_;
	}
	else
	{
		reallocate_emplace(end_, mystl::forward<Args>(args)...);
	}
}

// 在尾部插入元素
template <class T>
void vector<T>::push_back(const value_type& value)
{
	if (end_ != cap_)
	{
		data_allocator::construct(mystl::address_of(*end_), value);
		++end_;
	}
	else
	{
		reallocate_insert(end_, value);
	}
}

// 弹出尾部元素
template <class T>
void vector<T>::pop_back()
{
	MYSTL_DEBUG(!empty());
	data_allocator::destroy(end_ - 1);
	--end_;
}

// 在 pos 处插入元素
template <class T>
typename vector<T>::iterator
vector<T>::insert(const_iterator pos, const value_type& value)
{
	MYSTL_DEBUG(pos >= begin() && pos <= end());
	iterator xpos = const_cast<iterator>(pos);
	const size_type n = pos - begin_;
	if (end_ != cap_ && xpos == end_)
	{
		data_allocator::construct(mystl::address_of(*end_), value);
		++end_;
	}
	else if (end_ != cap_)
	{
		auto new_end = end_;
		data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
		++new_end;
		auto value_copy = value;  // 避免元素因以下复制操作而被改变
		mystl::copy_backward(xpos, end_ - 1, end_);
		*xpos = mystl::move(value_copy);
		end_ = new_end;
	}
	else
	{
		reallocate_insert(xpos, value);
	}
	return begin_ + n;
}

// 删除 pos 位置上的元素
template <class T>
typename vector<T>::iterator
vector<T>::erase(const_iterator pos)
{
	MYSTL_DEBUG(pos >= begin() && pos < end());
	iterator xpos = begin_ + (pos - begin());
	mystl::move(xpos + 1, end_, xpos);
	data_allocator::destroy(end_ - 1);
	--end_;
	return xpos;
}

// 删除[first, last)上的元素
template <class T>
typename vector<T>::iterator
vector<T>::erase(const_iterator first, const_iterator last)
{
	MYSTL_DEBUG(first >= begin() && last <= end() && !(last < first));
	const auto n = first - begin();
	iterator r = begin_ + (first - begin());
	data_allocator::destroy(mystl::move(r + (last - first), end_, r), end_);
	end_ = end_ - (last - first);
	return begin_ + n;
}

// 重置容器大小
template <class T>
void vector<T>::resize(size_type new_size, const value_type& value)
{
	if (new_size < size())
	{
		erase(begin() + new_size, end());
	}
	else
	{
		insert(end(), new_size - size(), value);
	}
}

// 与另一个 vector 交换
template <class T>
void vector<T>::swap(vector<T>& rhs) noexcept
{
	if (this != &rhs)
	{
		mystl::swap(begin_, rhs.begin_);
		mystl::swap(end_, rhs.end_);
		mystl::swap(cap_, rhs.cap_);
	}
}

/*****************************************************************************************/
// helper function

// try_init 函数，若分配失败则忽略，不抛出异常
template <class T>
void vector<T>::try_init() noexcept
{
	try
	{
		begin_ = data_allocator::allocate(16);
		end_ = begin_;
		cap_ = begin_ + 16;
	}
	catch (...)
	{
		begin_ = nullptr;
		end_ = nullptr;
		cap_ = nullptr;
	}
}

// init_space 函数
template <class T>
void vector<T>::init_space(size_type size, size_type cap)
{
	try
	{
		begin_ = data_allocator::allocate(cap);
		end_ = begin_ + size;
		cap_ = begin_ + cap;
	}
	catch (...)
	{
		begin_ = nullptr;
		end_ = nullptr;
		cap_ = nullptr;
		throw;
	}
}

// fill_init 函数
template <class T>
void vector<T>::
fill_init(size_type n, const value_type& value)
{
	const size_type init_size = mystl::max(static_cast<size_type>(16), n);
	init_space(n, init_size);
	mystl::uninitialized_fill_n(begin_, n, value);
}

// range_init 函数
template <class T>
template <class Iter>
void vector<T>::
range_init(Iter first, Iter last)
{
	const size_type init_size = mystl::max(static_cast<size_type>(last - first),
		static_cast<size_type>(16));
	init_space(static_cast<size_type>(last - first), init_size);
	mystl::uninitialized_copy(first, last, begin_);
}

// destroy_and_recover 函数
template <class T>
void vector<T>::
destroy_and_recover(iterator first, iterator last, size_type n)
{
	data_allocator::destroy(first, last);//先销毁对象
	data_allocator::deallocate(first, n);//再释放空间
}

// get_new_cap 函数
template <class T>
typename vector<T>::size_type
vector<T>::
get_new_cap(size_type add_size)
{
	const auto old_size = capacity();
	THROW_LENGTH_ERROR_IF(old_size > max_size() - add_size,
		"vector<T>'s size too big");
	if (old_size > max_size() - old_size / 2)	//如果继续0.5倍增长会超过总内存容量
	{
		return old_size + add_size > max_size() - 16
			? old_size + add_size : old_size + add_size + 16;
	}
	const size_type new_size = old_size == 0
		? mystl::max(add_size, static_cast<size_type>(16))	//如果原本大小为0
		: mystl::max(old_size + old_size / 2, old_size + add_size);//至少0.5倍容量增长，或新增大小
	return new_size;
}

// fill_assign 函数
template <class T>
void vector<T>::
fill_assign(size_type n, const value_type& value)
{
	if (n > capacity())
	{
		vector tmp(n, value);
		swap(tmp);
	}
	else if (n > size())
	{
		mystl::fill(begin(), end(), value);
		end_ = mystl::uninitialized_fill_n(end_, n - size(), value);
	}
	else
	{
		erase(mystl::fill_n(begin_, n, value), end_);
	}
}

// copy_assign 函数
template <class T>
template <class IIter>
void vector<T>::
copy_assign(IIter first, IIter last, input_iterator_tag)
{
	auto cur = begin_;
	for (; first != last && cur != end_; ++first, ++cur)
	{
		*cur = *first;
	}
	if (first == last)
	{
		erase(cur, end_);
	}
	else
	{
		insert(end_, first, last);
	}
}

// 用 [first, last) 为容器赋值
template <class T>
template <class FIter>
void vector<T>::
copy_assign(FIter first, FIter last, forward_iterator_tag)
{
	const size_type len = mystl::distance(first, last);
	if (len > capacity())
	{
		vector tmp(first, last);
		swap(tmp);
	}
	else if (size() >= len)
	{
		auto new_end = mystl::copy(first, last, begin_);
		data_allocator::destroy(new_end, end_);
		end_ = new_end;
	}
	else
	{
		auto mid = first;
		mystl::advance(mid, size());
		mystl::copy(first, mid, begin_);
		auto new_end = mystl::uninitialized_copy(mid, last, end_);
		end_ = new_end;
	}
}

// 重新分配空间并在 pos 处就地构造元素
template <class T>
template <class ...Args>
void vector<T>::
reallocate_emplace(iterator pos, Args&& ...args)
{
	const auto new_size = get_new_cap(1);
	auto new_begin = data_allocator::allocate(new_size);
	auto new_end = new_begin;
	try
	{
		new_end = mystl::uninitialized_move(begin_, pos, new_begin);
		data_allocator::construct(mystl::address_of(*new_end), mystl::forward<Args>(args)...);
		++new_end;
		new_end = mystl::uninitialized_move(pos, end_, new_end);
	}
	catch (...)
	{
		data_allocator::deallocate(new_begin, new_size);
		throw;
	}
	destroy_and_recover(begin_, end_, cap_ - begin_);
	begin_ = new_begin;
	end_ = new_end;
	cap_ = new_begin + new_size;
}

// 重新分配空间并在 pos 处插入元素
template <class T>
void vector<T>::reallocate_insert(iterator pos, const value_type& value)
{
	const auto new_size = get_new_cap(1);
	auto new_begin = data_allocator::allocate(new_size);
	auto new_end = new_begin;
	const value_type& value_copy = value;
	try
	{
		new_end = mystl::uninitialized_move(begin_, pos, new_begin);
		data_allocator::construct(mystl::address_of(*new_end), value_copy);
		++new_end;
		new_end = mystl::uninitialized_move(pos, end_, new_end);
	}
	catch (...)
	{
		data_allocator::deallocate(new_begin, new_size);
		throw;
	}
	destroy_and_recover(begin_, end_, cap_ - begin_);
	begin_ = new_begin;
	end_ = new_end;
	cap_ = new_begin + new_size;
}

// fill_insert 函数
template <class T>
typename vector<T>::iterator
vector<T>::
fill_insert(iterator pos, size_type n, const value_type& value)
{
	if (n == 0)
		return pos;
	const size_type xpos = pos - begin_;
	const value_type value_copy = value;  // 避免被覆盖
	if (static_cast<size_type>(cap_ - end_) >= n)
	{ // 如果备用空间大于等于新增元素的个数
		const size_type after_elems = end_ - pos;	//计算插入点之后的现有元素的个数
		auto old_end = end_;
		if (after_elems > n)
		{//插入点之后的现有元素个数 大于 新增元素个数
			mystl::uninitialized_copy(end_ - n, end_, end_);
			end_ += n;	//将vector尾端标记向后移
			mystl::move_backward(pos, old_end - n, old_end);
			mystl::uninitialized_fill_n(pos, n, value_copy);//从插入点之后填入新值
		}
		else
		{//插入点之后的现有元素个数 小于 新增元素个数
			end_ = mystl::uninitialized_fill_n(end_, n - after_elems, value_copy);
			end_ = mystl::uninitialized_move(pos, old_end, end_);
			mystl::uninitialized_fill_n(pos, after_elems, value_copy);
		}
	}
	else
	{ // 如果备用空间不足(需要配置额外的内存，调用get_new_cap实现)
		const auto new_size = get_new_cap(n);
		auto new_begin = data_allocator::allocate(new_size);
		auto new_end = new_begin;
		try
		{
			//先将旧vector的插入点之前的元素复制到新空间
			new_end = mystl::uninitialized_move(begin_, pos, new_begin);
			//再将新增元素（皆为n）填入新空间
			new_end = mystl::uninitialized_fill_n(new_end, n, value);
			//再将旧vector插入点之后的元素复制到新空间
			new_end = mystl::uninitialized_move(pos, end_, new_end);
		}
		catch (...)
		{//先销毁对象，再释放内存空间
			destroy_and_recover(new_begin, new_end, new_size);
			throw;
		}
		data_allocator::deallocate(begin_, cap_ - begin_);
		begin_ = new_begin;
		end_ = new_end;
		cap_ = begin_ + new_size;
	}
	return begin_ + xpos;
}

// copy_insert 函数
template <class T>
template <class IIter>
void vector<T>::
copy_insert(iterator pos, IIter first, IIter last)
{
	if (first == last)
		return;
	const auto n = mystl::distance(first, last);
	if ((cap_ - end_) >= n)
	{ // 如果备用空间大小足够
		const auto after_elems = end_ - pos;
		auto old_end = end_;
		if (after_elems > n)
		{
			end_ = mystl::uninitialized_copy(end_ - n, end_, end_);
			mystl::move_backward(pos, old_end - n, old_end);
			mystl::uninitialized_copy(first, last, pos);
		}
		else
		{
			auto mid = first;
			mystl::advance(mid, after_elems);
			end_ = mystl::uninitialized_copy(mid, last, end_);
			end_ = mystl::uninitialized_move(pos, old_end, end_);
			mystl::uninitialized_copy(first, mid, pos);
		}
	}
	else
	{ // 备用空间不足
		const auto new_size = get_new_cap(n);
		auto new_begin = data_allocator::allocate(new_size);
		auto new_end = new_begin;
		try
		{
			new_end = mystl::uninitialized_move(begin_, pos, new_begin);
			new_end = mystl::uninitialized_copy(first, last, new_end);
			new_end = mystl::uninitialized_move(pos, end_, new_end);
		}
		catch (...)
		{
			destroy_and_recover(new_begin, new_end, new_size);
			throw;
		}
		data_allocator::deallocate(begin_, cap_ - begin_);
		begin_ = new_begin;
		end_ = new_end;
		cap_ = begin_ + new_size;
	}
}

// reinsert 函数
template <class T>
void vector<T>::reinsert(size_type size)
{
	auto new_begin = data_allocator::allocate(size);
	try
	{
		mystl::uninitialized_move(begin_, end_, new_begin);
	}
	catch (...)
	{
		data_allocator::deallocate(new_begin, size);
		throw;
	}
	data_allocator::deallocate(begin_, cap_ - begin_);
	begin_ = new_begin;
	end_ = begin_ + size;
	cap_ = begin_ + size;
}

/*****************************************************************************************/
// 重载比较操作符

template <class T>
bool operator==(const vector<T>& lhs, const vector<T>& rhs)
{
	return lhs.size() == rhs.size() &&
		mystl::equal(lhs.begin(), lhs.end(), rhs.begin(),rhs.end());
}

template <class T>
bool operator<(const vector<T>& lhs, const vector<T>& rhs)
{
	return mystl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), lhs.end());
}

template <class T>
bool operator!=(const vector<T>& lhs, const vector<T>& rhs)
{
	return !(lhs == rhs);
}

template <class T>
bool operator>(const vector<T>& lhs, const vector<T>& rhs)
{
	return rhs < lhs;
}

template <class T>
bool operator<=(const vector<T>& lhs, const vector<T>& rhs)
{
	return !(rhs < lhs);
}

template <class T>
bool operator>=(const vector<T>& lhs, const vector<T>& rhs)
{
	return !(lhs < rhs);
}

// 重载 mystl 的 swap
template <class T>
void swap(vector<T>& lhs, vector<T>& rhs)
{
	lhs.swap(rhs);
}
};  //namespace mystl

#endif  // !MYTINYSTL_VECTOR_H_

list.h

1. 对于双向链表list来说，每次插入或删除一个元素，就配置或释放一个元素空间。因此对于空间的利用是绝对的精准不存在浪费的。并且对于任何位置的元素插入或元素移除，list永远是常数时间。
2. 书中的源代码没有保存size成员，因此每次调用size()都需要重新计算一次，由于迭代器不支持随机访问，为O(n)复杂度。我们的代码另外保存了一个size成员存储链表的大小，缺点是所有涉及到成员修改的成员函数都需要额外增加对size的修改。
3. list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。list迭代器必须有能力指向list节点，并有能力进行正确的递增、递减、取值、成员存取等操作。

由于list是一个双向链表，迭代器必须具备前移、后移的能力，所以list提供的是bidirectional iterators。

另外注意list有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的。list的元素删除操作（erase）也只有“指向被删除元素的那个迭代器”

注意我们继承了iterator基类，其中包含5个迭代器基本类型（iterator_category, value_type, pointer, reference, difference_type）

deque.h

1. deque是双向开口的连续线性空间，可以在头尾两端分别做（常数时间内）元素的插入和删除。deque没有容量（capacity）的观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。因此不会发生像vector那样因空间不足而重新配置一块更大的空间并拷贝元素释放旧空间的过程。也因此，deque没有必要提供空间保留（reserve）的功能。
2. deque也提供random access iterator，但是它的迭代器不是普通指针，复杂度很高，因此除非必要，尽量选择vector。要对deque进行排序，应该先将deque复制到一个vector上，排序完再复制回deque
3. deque采用一块map（不是STL中的map容器）作为主控，map是一小块连续空间（我们的代码设置默认大小为8），其中每个元素（称为节点 node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区是deque的储存空间主体。
   • map是一个T**，它是一个指针，指向另一个指针，那个指针指向类型为T的一块空间
4. 迭代器中保存4个指针（因此一个迭代器大小为16字节），其中三个指向缓冲区中的位置（头、尾、当前），剩下一个指向缓冲区所在的位置。

迭代器设计

// deque 的迭代器设计
template <class T, class Ref, class Ptr>
struct deque_iterator : public iterator<random_access_iterator_tag, T>
{
  typedef deque_iterator<T, T&, T*>             iterator;
  typedef deque_iterator<T, const T&, const T*> const_iterator;
  typedef deque_iterator                        self;

  typedef T            value_type;
  typedef Ptr          pointer;
  typedef Ref          reference;
  typedef size_t       size_type;
  typedef ptrdiff_t    difference_type;
  typedef T*           value_pointer;
  typedef T**          map_pointer;

  static const size_type buffer_size = deque_buf_size<T>::value;

  // 迭代器所含成员数据
  value_pointer cur;    // 指向所在缓冲区的当前元素
  value_pointer first;  // 指向所在缓冲区的头部
  value_pointer last;   // 指向所在缓冲区的尾部
  map_pointer   node;   // 缓冲区所在节点

  // 构造、拷贝、移动函数
  deque_iterator() noexcept
    :cur(nullptr), first(nullptr), last(nullptr), node(nullptr) {}

  deque_iterator(value_pointer v, map_pointer n)
    :cur(v), first(*n), last(*n + buffer_size), node(n) {}

  deque_iterator(const iterator& rhs)
    :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node){ }
  deque_iterator(iterator&& rhs) noexcept
    :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node){
    rhs.cur = nullptr;
    rhs.first = nullptr;
    rhs.last = nullptr;
    rhs.node = nullptr;
  }

  deque_iterator(const const_iterator& rhs)
    :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node){ }

  self& operator=(const iterator& rhs){
    if (this != &rhs){
      cur = rhs.cur;
      first = rhs.first;
      last = rhs.last;
      node = rhs.node;
    }
    return *this;
  }

  // 转到另一个缓冲区
  void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + buffer_size;
  }

  // 重载运算符
  reference operator*()  const { return *cur; }
  pointer   operator->() const { return cur; }

  difference_type operator-(const self& x) const{
    return static_cast<difference_type>(buffer_size) * (node - x.node)
      + (cur - first) - (x.cur - x.first);
  }

  self& operator++(){
    ++cur;
    if (cur == last)
    { // 如果到达缓冲区的尾
      set_node(node + 1);
      cur = first;
    }
    return *this;
  }
  self operator++(int){
    self tmp = *this;
    ++*this;
    return tmp;
  }

  self& operator--(){
    if (cur == first)
    { // 如果到达缓冲区的头
      set_node(node - 1);
      cur = last;
    }
    --cur;
    return *this;
  }
  self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
  }

  self& operator+=(difference_type n)
  {
    const auto offset = n + (cur - first);
    if (offset >= 0 && offset < static_cast<difference_type>(buffer_size))
    { // 仍在当前缓冲区
      cur += n;
    }
    else
    { // 要跳到其他的缓冲区
      const auto node_offset = offset > 0
        ? offset / static_cast<difference_type>(buffer_size)
        : -static_cast<difference_type>((-offset - 1) / buffer_size) - 1;
      set_node(node + node_offset);
      cur = first + (offset - node_offset * static_cast<difference_type>(buffer_size));
    }
    return *this;
  }
  self operator+(difference_type n) const
  {
    self tmp = *this;
    return tmp += n;
  }
  self& operator-=(difference_type n)
  {
    return *this += -n;
  }
  self operator-(difference_type n) const
  {
    self tmp = *this;
    return tmp -= n;
  }

  reference operator[](difference_type n) const { return *(*this + n); }

  // 重载比较操作符
  bool operator==(const self& rhs) const { return cur == rhs.cur; }
  bool operator< (const self& rhs) const
  { return node == rhs.node ? (cur < rhs.cur) : (node < rhs.node); }
  bool operator!=(const self& rhs) const { return !(*this == rhs); }
  bool operator> (const self& rhs) const { return rhs < *this; }
  bool operator<=(const self& rhs) const { return !(rhs < *this); }
  bool operator>=(const self& rhs) const { return !(*this < rhs); }
};

缓冲区大小设置：

• 如果对象T的大小小于256字节，那么每块缓冲区分配可以存储4096/sizeof(T) 个对象的空间

• 如果大于等于256字节，那么分配16个对象的空间