本文共 9324 字，大约阅读时间需要 31 分钟。
StrVec类的设计
vector类将其元素保存在连续的内存中。为了获得可接受的性能，vector预先分配足够的内存来保存可能需要的更多元素。vector的每个添加元素的成员函数会检查是否有空间容纳更多的元素。如果有，成员函数会在下一个可用位置构造一个对象。如果没有可用空间，vector就会重新分配空间：它获得新的空间，将已有元素移动到新空间中，释放旧空间，并添加元素。
在StrVec类中采用类似的策略，
用allocator来获得原始内存。由于allocator分配的内存是未构造的，我们将需要添加新元素时用allocator的construct成员在原始内存中创建对象，当需要删除元素时，用destory成员来销毁。 每个StrVec有三个指针成员指向其元素所使用的内存： 1、elements，指向分配的内存中的首元素
2、first_free，指向最后一个实际元素之后的位置
3、cap，指向分配的内存末尾之后的位置
StrVrc还有一个名为alloc的静态成员，其类型为allocator<string>。alloc成员会分配StrVec使用的内存，我们的类还有4个工具函数：
1、alloc_n_copy会分配内存，并拷贝一个给定范围中的元素
2、free会销毁构造的元素并释放内存
3、chk_n_alloc保证StrVec至少有容纳一个新元素的空间。如果没有空间添加新元素，chk_n_alloc会调用reallocate来分配更多内存
4、reallocate在内存用完时为StrVec分配新内存
StrVec类定义 //类vector类内存分配策略的简化实现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;} size_t capacity() const { return cap - elements;} std::string *begin() const { return elements;} std::string *end() const { return first_free;} private: static std::allocator alloc; //分配元素 //被添加元素的函数使用 void chk_n_alloc(){ if(size() == capacity()) reallocate();} //工具函数，被拷贝构造函数、赋值运算符和析构函数所使用 std::pair alloc_n_copy(const string*, const string*); void free(); //销毁元素并释放内训 void reallocate(); //获得更多内存并拷贝已有元素 string *elements; string *first_free; string *cap;} 使用construct
函数push_back调用chk_n_alloc确保有空间容纳新元素。当改函数返回时，push_back知道必有空间容纳新元素。它要求allocator成员来construct新的尾元素：
void StrVec::push_back(const string &s){ chk_n_alloc(); alloc.construct(first_free++, s);} 当我们用allocator分配内存时，必须记住内存是未构造的。为了使用改内存，必须使用construct，在该内存中构造一个对象。传递给construct的第一个参数必须是一个指针。指向allocate所分配的未构造的内存空间。剩余参数确定用哪个构造函数来构造对象。在本例中，只有一个额外参数，类型为string，因此会使用string的拷贝构造函数。
调用construct会在first_free当前指定的地址构造一个对象，并递增first_free指向下一个未构造的元素。
alloc_n_copy成员 alloc_n_copy成员会分配足够多的内存来保存给定范围的元素，并将这些元素拷贝到新分配的内存中。此函数返回一个指针的pair，两个指针分别指向新空间的开始位置和尾后位置：
std::pair 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)};}
它是在返回语句中完成拷贝工作的，返回语句中对返回值进行了列表初始化。返回pair的first成员指向分配的内存的开始位置；second成员则是uninitialized_copy的返回值，此值是一个指针，指向最后一个构造元素之后的位置。
free()成员 free()成员有两个责任，首先destory元素，然后释放StrVec自己分配的内存空间。for循环调用allocator的destory成员，从构造的尾元素开始，到首元素为止，逆序销毁所有元素：
void StrVec::free(){ if (elements){ for (auto p = first_free; p != elements; p--) alloc.destroy(p); alloc.deallocate(elements, cap - elements); //释放分配的内存空间 }} 传递给deallocate的指针必须是之前某次allocate调用所返回的指针。因此，在调用deallocate之前我们首先检查elements是否为空。
拷贝控制成员 拷贝构造函数调用alloc_n_copy: 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;} alloc_n_copy的返回值是一个指针的pair。其first成员指向第一个构造的元素，second成员指向最后一个构造的元素之后的位置。由于alloc_n_copy分配的空间恰好容纳给定的元素，cap也指向最后一个构造元素之后的位置。
析构函数调用free: StrVec::~StrVec(){ free();} 拷贝赋值运算符在释放之前调用alloc_n_copy，这样就可以正确处理自赋值了：
StrVec& StrVec::operator=(const StrVec &rhs){ auto data = alloc_n_copy(s.begin(), s.end()); free(); //free掉自身 elements = data.first; first_free = cap = data.second; return *this;} 类似拷贝构造函数，拷贝赋值运算符使用alloc_n_copy的返回值来初始化它的指针
在重新分配内存的过程中移动而不是拷贝元素
reallocate成员函数应该实现的功能：
1、为一个新的更大的string数组分配内存
2、在内存空间的前一部分构造对象，保存现有元素
3、销毁原内存空间中的元素，并释放这块内存
string具有类值行为，当拷贝一个string时，必须为这些字符分配内存空间，而销毁一个string必须释放所占有的内存。
reallocate成员函数拷贝StrVec中的string，则拷贝之后，每个string只有唯一的用户。一旦将旧元素拷贝到新空间，我们就会立即销毁原string。
因此，拷贝这些string中的数据是多余的。在重新分配内存空间时，如果我们能避免分配和释放string的额外开销，StrVec的性能会好很多。
移动构造函数和std::move
移动构造函数通常将资源“移动”而不是拷贝到正在创建的对象。而且标准库保证移后原string仍然保持一个有效的、可析构的状态。对于string，我们可以想象每个string都有一个指向char数组的指针。可以假定string的移动构造函数进行了指针拷贝，而不是为字符分配内存然后拷贝字符。
move的标准库函数定义在utility头文件中。
1、当reallocate在新内存中构造string时，它必须调用move来表示希望使用string的移动构造函数。如果漏掉了move调用，将会使用string的拷贝构造函数
2、当使用move时，直接调用std::move而不是move
reallocate成员
首先调用allocate分配新内存空间。我们每次重新分配内存时都会将StrVec的容量加倍。如果StrVec为空，我们将分配容纳一个元素的空间：
void StrVec::reallocate() { //我们将分配当前大小两倍的内存空间 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;} a.construct(p, args): p必须是类型T*的指针，指向一块原始内存，arg被传递给类型为T的构造函数，用来在p指向的内存中构造一个对象。
练习13.39：编写自己版本的StrVec，包括自己版本的reserve、capacity、和resize
//capacitysize_t capacity() const { return cap - elements; }//reserve预留一部分空间，需要reallocate()成员函数void reserve(size_t n) { if (n > capacity()) reallocate(n); }//resize有两个版本，区别是不带/带初值void StrVec::resize(size_t n) { if (n > size()) { while (size() < n) push_back(""); } else if (n < size()) { while (size() > n) alloc.destroy(--first_free); }}//添加对象inline void StrVec::resize(size_t n, const std::string& s) { if (n > size()) { while (size() < n) push_back(s); }} 练习13.40：为StrVec类添加一个构造函数，它接受一个initializer_list<string>参数
StrVec::StrVec(initializer_list il) { //调用alloc_n_copy分配与列表il中元素数组一样多的空间 auto newdata = alloc_n_copy(il.begin(), il.end()); elements = newdata.first; first_free = cap = newdata.second;}
完整的StrVec类的代码如下：
#include #include #include #include using namespace std;//类vector类内存分配策略的简化实现class StrVec { public: StrVec() :elements(nullptr), first_free(nullptr), cap(nullptr) { } //默认初始化 StrVec(const StrVec&); //拷贝构造函数 StrVec(initializer_list il); StrVec& operator=(const StrVec&); //拷贝赋值运算符 ~StrVec(); void push_back(const std::string&); //拷贝元素 size_t size() const { return first_free - elements; } size_t capacity() const { return cap - elements; } // reserve预留一部分空间，需要reallocate()成员函数 void reserve(size_t n) { if (n > capacity()) reallocate(n); } // reserve预留一部分空间，需要reallocate()成员函数 std::string* begin() const { return elements; } std::string* end() const { return first_free; }private: static allocator alloc; //分配元素 //被添加元素的函数使用 void chk_n_alloc() { if (size() == capacity()) reallocate(); } //工具函数，被拷贝构造函数、赋值运算符和析构函数所使用 pair alloc_n_copy(const string*, const string*); void free(); //销毁元素并释放内训 void reallocate(); //获得更多内存并拷贝已有元素 void reallocate(size_t n); void resize(size_t n); void resize(size_t n, const std::string& s); string* elements; string* first_free; string* cap;};inline void StrVec::push_back(const string& s) { chk_n_alloc(); alloc.construct(first_free++, s);}inline pair 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() { if (elements) { for (auto p = first_free; p != elements; p--) 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(initializer_list il) { //调用alloc_n_copy分配与列表il中元素数组一样多的空间 auto newdata = alloc_n_copy(il.begin(), il.end()); elements = newdata.first; first_free = cap = newdata.second;}inline StrVec::~StrVec() { free(); }inline StrVec& StrVec::operator=(const StrVec& rhs) { auto data = alloc_n_copy(rhs.begin(), rhs.end()); free(); //free掉自身 elements = data.first; first_free = cap = data.second; return *this;}inline void StrVec::reallocate() { //我们将分配当前大小两倍的内存空间 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;}inline void StrVec::reallocate(size_t newcapacity) { //分配新内存 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;}//reserve预留一部分空间，需要reallocate()成员函数//void reserve(size_t n) { if (n > capacity()) reallocate(n); }//resize有两个版本，区别是不带/带初值inline void StrVec::resize(size_t n) { if (n > size()) { while (size() < n) push_back(""); } else if (n < size()) { while (size() > n) alloc.destroy(--first_free); }}//添加对象inline void StrVec::resize(size_t n, const std::string& s) { if (n > size()) { while (size() < n) push_back(s); }}
练习13.41：在push_back中，我们为什么在construct调用中后置递增运算，如果前置递增运算会发生什么？
因为first_free指向第一个空闲的位置，也就是最后一个string的尾后元素，所以应使用后置递增运算符若使用前置递增运算，first_free就指向了最后一个string，和first_free的设定不符合
练习13.43：重写free成员，用for_each()和lambda来代替for循环destroy元素，你更倾向于哪种实现？
for_each(elements, first_free, [](std::string &s){ alloc.destroy(&s);});//在lambda中应该取s的地址，用来调用destory 转载地址：http://ztxmb.baihongyu.com/