allocator class

当分配一大块内存时，我们通常计划在这块内存上按需构造对象，这样的我们希望将内存分配和对象构造分离。但是通常的new关键字的分配的动态空间，有时候会造成一些浪费，更致命的是“如果一个类没有默认构造函数，那么这个类就不能动态分配数组了”。

这时我们需要一个能将内存分配和对象构造分离的机制，allocator很好地帮助我们解决了这个问题。

#include 《memory》，allocator提供了一种类型感知的内存分配方法，它分配的内存是原始的，未构造的。我们可以利用allocator提供的操作对这些内存进行操作，

allocator<T> a	定义了一个名为a的allocator对象，它可以为类型为T的对象分配内存
a.allocator(n)	先定义，后分配。这分配一段原始的，未构造的，保存n个类型为T的对象；----》可以看出alllocator方法分配内存，也是先定义类型，在分配类型的数量
a.deallocat(p,n)	note，在此操作之前，必须堆每个在这个内存中创建的对象调用destory方法。 释放从T*,这块内存保存了n类型为T的对象,p必须是一个先前由allocator返回的指针.且n必须是p创建时所要求大小,在调用deallocator之前,用于必须堆每个在这块内存中创建的对象调用destroy方法
a.construct(p,args)	p必须是一个T*的指针,指向一个块原始内存,args被传递给类型为T的构造函数,用在在p指向的内存中构造一个对象
a.destroy(p)	p为类型为T*的指针,此方法堆p所指对象执行析构函数

allocator<string> alloc;
auto const p = alloc.allcoate(n);

auto q = p;
alloc.construct(q++);//*q is a null string
alloc.construct(q++,10,'c')// *q is cccccccccc
alloc.construct(q++,"hi")//*q is hi

在未构造对象的情况下,就使用原始内存是错误的
例如
cout<<*p<<endl;
cout<<*q<<endl;//这个是非法的

记住,为了使用allcocate返回的内存,我们必须用construct构造对象,使用未构造的函数,其行为是未定义的.
党我们使用完对象后,必须堆每个构造函数调用destroy来销毁
while(q!=p){
  alloc.destroy(--q);  
}//我们只能堆真正构造了的元素进行destroy操作

//一旦元素被销毁后,我们重新使用这部分内存来保存其他string,
//也可以将内存归还给os,释放内存是通过deallocate(p,n)来完成的

alloc.deallocate(p,n);

拷贝/填充未初始化的算法,STL还定义了两个伴随算法,可以在未初始化内存中创建对象

uninitialized_copy(b,e,b2)	从迭代器b和e指出的输入范围拷贝元素到迭代器b2指定的未构造的原始原始内存中,b2指向的内存必须足够大,能容纳输入序列中元素的拷贝
uninitiated_copy(b,n,b2)
uninitiated_fill(b,e,t)	在迭代器b和e指定的原始内存范围中创建对象,对象的值均为t的拷贝
uninitiated_fill(b,n,t)

/*
假定有一个例子,希望将其内容拷贝到动态内存中,我们将分配一块比vector中元素空间大一倍的动态内存,然后将原vector中的元素拷贝到前一半空间,后一半空间利用一个给定值进行填充
*/

auto p = alloc.allocate(vi.size()*2);

auto q = uninitiated_copy(vi.begin(),vi.end(),p);

uninitiated_fill(q,vi.size(),42);

 test case

#ifndef STRVEC_H_INCLUDED
#define STRVEC_H_INCLUDED
#include<vector>
#include<string>
#include<memory>
#include<utility>
#include<iostream>
/**
这里要实现的是一个STLvector的简化版,只能运用于string,由于没有template.
设计思路:
1,预先分配足够大的内存来保存可能需要的更多的元素,
2,当StrVec添加每个元素时,成员函数chk_n_alloc()会检查是否有足够空间容纳更多的元素
  2.1 如果有,alloc.construct()会在下一个可用位置构造一个对象
  2.2 如果没有,StrVec会充分分配空间alloc_n_copy(),并且拷贝一个给定范围中的元素,然后释放掉旧的空间free()
        并添加新的元素


        ---------------------------------------------
        |   |   |   |   |                           |
        ---------------------------------------------
        ^                 ^                           ^
        elements          first_free                  cap
        --
每个StrVec有三个指针指向其元素所使用的内存:
elements,指向分配中的首元素
frist_free,指向最后一个实际元素位置之后的位置
cap,指向分配的内存末尾之后的位置
------------------

StrVec除了指出位置的指针外,还有名为alloc的静态成员,类型为allocator<string>,它分配我们所需要的内存
---
另外还有4个工具函数,
alloc_n_copy(),分配内存并拷贝一个给定范围中的元素
free()//销毁构造的元素病释放内存
chk_n_alloc()//保证StrVec至少能容纳一个新元素的空间,如果没有空间添加新元素,chk_n_alloc会调用reallocate()来分配更多的空间按
reallocate()//在内存使用完后,reallocate()重新分配元素

*/



using namespace std;
class StrVec{
public:
    StrVec():elements(nullptr),first_free(nullptr),cap(nullptr){}///构造函数,对成员进行初始化
    StrVec(const StrVec&);///拷贝构造函数,从无到有
    StrVec &operator=(const StrVec &);///拷贝赋值运算符=,对存在的元素赋予新值
    ~StrVec();///析构函数

    void push_back(const std::string&);///拷贝元素

    size_t size() const {return first_free - elements;}///返回StrVec中的元素个数
    size_t capacity() const {return cap - elements;}///返回StrVec中实际分配的(可以容纳类型元素的)内存大小
    string *begin() const {return elements;}///返回首元素
    string *end() const {return first_free;}///返回StrVec末尾元素的后一个位置


private:
    static allocator<string> alloc;///分配元素,注意是静态成员
    void chk_n_alloc(){///被添加元素的函数使用
        if(size() == capacity())
            reallocate();
    }///
    ///工具函数，被拷贝构造函数，赋值运算符和析构函数使用
    pair<string*,string*> alloc_n_copy(const string*,const string*);///什么时候没有空间容纳新元素呢? first_free==cap的时候.
    void free();///撤销元素病释放内存
    void reallocate();///获得更多内存并且拷贝已有元素

    string *elements;///指向数组首元素的指针
    string *first_free;///指向数组第一个空闲元素的指针
    string *cap;///指向数组尾后位置的指针
};

void show();

#endif // STRVEC_H_INCLUDED

----

#include "StrVec.h"
using namespace std;

allocator<string> StrVec::alloc;

void show(){
    std::cout<<"from StrVec.cpp"<<std::endl;
}

void StrVec::push_back(const string& s){
    chk_n_alloc();///

    alloc.construct(first_free++,s);
}


///函数返回一个pair,两个指针分别指向新空间的开始位置和拷贝的尾后位置,即data是新空间开始的位置,uninitiated_copy()返回新空间拷贝的尾后位置
pair<string*, string*>
StrVec::alloc_n_copy(const string *b,const string *e){
    auto data = alloc.allocate(e-b);
    return make_pair(data,uninitialized_copy(b,e,data));
    //return {data,unintialized_copy(b,e,data)};
}

void StrVec::free(){
    ///can not pass a nullptr to deallocate(),if elements is 0,then free() do nothing
    if(elements){
        for(auto p = first_free;p != elements;/* */){
            StrVec::alloc.destroy(--p);
        }
        StrVec::alloc.deallocate(elements,cap-elements);
    }
}

StrVec::StrVec(const StrVec &s){
    auto newdata = alloc_n_copy(s.begin(),s.end());
    elements = newdata.first;
    first_free = newdata.second;
    cap = newdata.second;
}

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

StrVec &StrVec::operator=(const StrVec &rhs){
    ///
    auto data = alloc_n_copy(rhs.begin(),rhs.end());
    free();///释放掉已有元素之前,调用alloc_n_copy缓存rhs的元素,这可以处理自我赋值
    elements = data.first;
    first_free = data.second;
    cap = data.second;

    return *this;///
}

/**
在重新分配内存的过程中移动而不是拷贝元素
我们reallocate()应该做些什么呢?
1,为一个新的,更大的string数组分配元素
2,在内存空间的前一部分构造,保存现有元素
3,销毁原来内存空间中的元素,并释放这块内存
*/

void StrVec::reallocate(){
    auto newcapacity = size() ? 2*size():1;

    auto newdata = StrVec::alloc.allocate(newcapacity);

    auto dest = newdata;
    auto elem = elements;

    for(size_t i = 0;i != size();i++){
        StrVec::alloc.construct(dest++,std::move(*elem++));
    }

    free();

    elements = newdata;
    first_free = dest;
    cap = elements + newcapacity;
}

-----main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include "StrVec.h"
using namespace std;



int main()
{
    show();
    StrVec sv;
    sv.push_back("aaa");
    sv.push_back("bbb");

    int length = sv.size();
    string *ptr = sv.begin();
    for(int i = 0;i<length;i++){
        cout<<*ptr++<<endl;
    }

    StrVec svb(sv);
    string *ptrb = svb.begin();
    for(int i = 0;i<svb.size();i++){
        cout<<*ptrb++<<endl;
    }

    StrVec svc = sv;
    string *ptrc = svb.begin();
    for(int i = 0;i<svc.size();i++){
        cout<<*ptrc++<<endl;
    }
    return 0;
}

================