13-39.md

#include <iostream>
using std::cin; using std::cout; using std::endl; using std::cerr;
#include <string>
using std::string;
#include <memory>
using std::allocator; using std::uninitialized_copy;
#include <utility>
using std::pair;

//类vector类内存分配策略的简化实现
class StrVec {
public:
    StrVec() :    //allocator成员进行默认初始化
        elements(nullptr), first_free(nullptr), cap(nullptr) {};
    StrVec(const StrVec &);             //拷贝构造函数
    StrVec &operator=(const StrVec &);  //拷贝赋值运算符
    ~StrVec();                          //析构函数
    void push_back(const string &);     //拷贝元素
    size_t size() const { return first_free - elements;}
    size_t capacity() const { return cap - elements;}
    string *begin() const { return elements;}
    string *end() const { return first_free;}
    void reserve(const size_t &);
    void resize(const size_t &);   //新元素默认值初始化
    void resize(const size_t &, const string &);   //新元素使用指定值初始化
private:
    static allocator<string> alloc; //分配元素
    //被添加元素的函数所使用
    void chk_n_alloc() {if (size() == capacity()) reallocate();}
    //工具函数，被拷贝构造函数、拷贝赋值运算符和析构函数所使用
    pair<string *, string *> alloc_n_copy (const string *, const string *);
    void free();            //销毁元素并释放内存
    void reallocate();      //获得更多内存并拷贝已有元素
    string *elements;       //指向数组首元素的指针
    string *first_free;     //指向数组第一个空闲元素的指针
    string *cap;            //指向数组尾后位置的指针
};

allocator<string> StrVec::alloc;

inline
void StrVec::push_back(const string &s) {
    chk_n_alloc();  //确保有空间容纳新元素
    //在first_free指向的元素中构造s的副本
    alloc.construct(++first_free, s);
}

inline
pair<string *, string *>
StrVec::alloc_n_copy(const string *b, const string *e) {
    //分配空间保存给定范围的元素
    auto data = alloc.allocate(e - b);
    //初始化并返回一个pair，该pair由data和uninitialized_copy的返回值构成
    return {data, uninitialized_copy(b, e, data)};
}

inline
void StrVec::free() {
    //不能传递给deallocate一个空指针，如果elements为空指针，函数什么也不做
    if (elements){
        //逆序销毁旧元素
        for (auto p = first_free; p != elements;)
            alloc.destroy(--p);
        alloc.deallocate(elements, cap - elements);
    }
}

inline
StrVec::StrVec(const StrVec &s) {
    //调用alloc_n_copy分配空间以容纳与s中一样多的元素
    auto newdata = alloc_n_copy(s.begin(), s.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
}

inline
StrVec::~StrVec() { free(); }

inline
StrVec &
StrVec::operator=(const StrVec &rhs){
    //调用alloc_n_copy分配内存，大小与rhs中元素占用空间一样多
    auto data = alloc_n_copy(rhs.begin(), rhs.end());
    free();
    elements = data.first;
    first_free = cap = data.second;
    return *this;
}

inline
void StrVec::reallocate() {
    //将分配当前大小两倍的内存空间，若为0则分配1
    auto newcapacity = size() ? 2 *size() : 1;
    //分配新内存
    auto newdata = alloc.allocate(newcapacity);
    //将数据从旧内存移动到新内存
    auto dest = newdata;    //指向新数组中下一个空闲位置
    auto elem = elements;   //指向旧数组中下一个元素
    for (size_t i = 0; i != size(); ++i)
        alloc.construct(dest++, std::move(*elem++));
    free(); //一旦我们移动完元素就释放旧内存空间
    //更新我们的数据结构，执行新元素
    elements = newdata;
    first_free = dest;
    cap = elements + newcapacity;
}

void StrVec::reserve(const size_t &i) {
    //只有当需要的内存空间大于当前容量时才改变容量
    if (i > capacity()){
        auto newcapacity = i;
        auto newdata = alloc.allocate(newcapacity);
        auto dest = newdata;
        auto elem = elements;
        for (size_t j = 0; j != size(); ++j)
            alloc.construct(dest++, std::move(*elem++));
        free();
        elements = newdata;
        first_free = dest;
        cap = elements + newcapacity;
    } else {
        return;
    }
}

void StrVec::resize(const size_t &n) {
    if (n > capacity()){    //大于当前容量时，扩容并值初始化
        auto newcapacity = n;
        auto newdata = alloc.allocate(newcapacity);
        auto dest = newdata;
        auto elem = elements;
        for (size_t i = 0; i != size(); ++i)
            alloc.construct(dest++, std::move(*elem++));
        free();
        //使用值初始化构造剩余空间的每一个元素
        while (dest != newdata + newcapacity)
            alloc.construct(dest++,string());
        elements = newdata;
        first_free = dest;
        cap = elements + newcapacity;
    } else if (n == capacity() || n <= 0){
        return;
    } else {    //小于当前容量时，缩小容量并删除元素
        auto newcapacity = n;
        auto newdata = alloc.allocate(newcapacity);
        auto dest = newdata;
        auto elem = elements;
        for (size_t i = 0; i != size(); ++i)
            alloc.construct(dest++, std::move(*elem++));
        free();
        elements = newdata;
        first_free = dest;
        cap = elements + newcapacity;
    }
}

int main(){
    StrVec sv1;
    sv1.push_back("sv1");
    sv1.resize(10);
}