使用allocator实现管理字符串的可变数组

引入移动操作

StrVec的定义与实现

定义

Copy 1#ifndef strVec_hpp
 2#define strVec_hpp
 3
 4#include <stdio.h>
 5#include <memory>
 6#include <string>
 7#include <utility>
 8#include <iostream>
 9
10using std::string;
11using std::allocator;
12using std::pair;
13using std::move;
14using std::ostream;
15
16class StrVec
17{
18    friend ostream &operator<<(ostream &os, const StrVec &sv);
19public:
20    StrVec() : elements(nullptr), first_free(nullptr), cap(nullptr) {}
21    ~StrVec();
22
23    StrVec(const StrVec&);
24    StrVec &operator=(const StrVec&);
25
26    StrVec(StrVec &&) noexcept;
27    StrVec &operator=(StrVec &&) noexcept;
28
29    void push_back(const string&);
30
31    size_t size() const { return first_free - elements; }
32
33    size_t capacity() const { return cap - elements; }
34
35    string *begin() const { return elements; }
36
37    string *end() const { return first_free; }
38
39private:
40
41    static allocator<string> alloc;
42
43    void chk_n_alloc() { if (size() == capacity()) reallocate(); }
44
45    pair<string*, string*> alloc_n_copy(const string *, const string *); // 使用迭代器范围初始化动态内存
46
47    void free();
48    void reallocate();
49
50    string *elements;
51    string *first_free;
52    string *cap;
53};
54#endif

实现

Copy 1#include "strVec.hpp"
 2
 3StrVec::~StrVec() { free(); }
 4
 5StrVec::StrVec(const StrVec &s)
 6{
 7    auto newdata = alloc_n_copy(s.begin(), s.end());
 8
 9    elements = newdata.first;
10    first_free = cap = newdata.second;
11}
12
13StrVec &StrVec::operator=(const StrVec &rhs)
14{
15    auto data = alloc_n_copy(rhs.begin(), rhs.end());
16    free();
17    elements = data.first;
18    first_free = cap = data.second;
19
20    return *this;
21}
22
23StrVec::StrVec(StrVec &&s) noexcept
24  : elements(s.elements), first_free(s.first_free), cap(s.cap)
25{
26    s.elements = s.first_free = s.cap = nullptr;
27}
28
29StrVec &StrVec::operator=(StrVec &&rhs) noexcept
30{
31    if (this != &rhs)
32    {
33        free();
34        elements = rhs.elements;
35        first_free = rhs.first_free;
36        cap = rhs.cap;
37        rhs.elements = rhs.first_free = rhs.cap = nullptr;
38    }
39    return *this;
40}
41
42pair<string*, string*>
43StrVec::alloc_n_copy(const string *b, const string *e)
44{
45    auto data = alloc.allocate(e - b);
46
47    return { data, uninitialized_copy(b, e, data) };
48}
49
50void StrVec::free()
51{
52    if (elements)
53    {
54        for (auto p = first_free; p != elements;)
55            alloc.destroy(--p);
56
57        alloc.deallocate(elements, cap - elements);
58    }
59}
60
61void StrVec::reallocate()
62{
63    auto newcapacity = size() ? 2 * size() : 1;
64    auto newdata = alloc.allocate(newcapacity);
65
66    auto dest = newdata;
67    auto elem = elements;
68
69    for (size_t i = 0; i != size(); ++i)
70        alloc.construct(dest++, std::move(*elem++));
71    free();
72    elements = newdata;
73    first_free = dest;
74    cap = elements + newcapacity;
75}
76
77void StrVec::push_back(const string &s)
78{
79    chk_n_alloc();
80    alloc.construct(first_free++, s);
81}
82
83ostream &operator<<(ostream &os, const StrVec &sv)
84{
85    for (auto b = sv.elements; b != sv.first_free; ++b)
86        os << *b << "\t";
87    return os;
88}

在main函数中使用StrVec

Copy 1#include <iostream>
 2#include "strVec.hpp"
 3
 4using std::cout;
 5using std::endl;
 6
 7allocator<string> StrVec::alloc;
 8
 9int main(int argc, const char * argv[]) {
10    StrVec sv;
11    sv.push_back("one");
12    cout << sv << endl;
13
14    sv.push_back("two"); 
15    cout << sv << endl;          
16
17    sv.push_back("three");
18    cout << sv << endl;           
19
20    sv.push_back("four");
21    cout << sv << endl;           
22
23    sv.push_back("five");
24    cout << sv << endl;           
25
26    return 0;
27}

在reallocate函数中使用std::move函数

string具有类值行为: 拷贝一个string必须为字符串分配内存空间, 销毁一个string必须释放所占的内存空间

reallocate函数每拷贝完一个StrVec的string元素后, 原string对象即将销毁: 如果我们能避免分配和释放string的额外开销, 可以提高StrVec的性能

新标准库引入两种机制, 可以避免string的拷贝:

1. 移动构造函数: 将资源从给定对象移动到正在创建的对象, 而不是拷贝
   
2. 标准库函数move: 表明希望使用string的移动构造函数
   

标准库保证移后 moved-from 源string仍然是一个有效的, 可析构的状态: 不保证其值, 但可以对其调用析构函数

std::move

模板函数

因为极易出现定义与move同名的函数的需求, 我们通常不为move提供using声明, 而是直接使用std::move

我们会定义移动构造函数, 但基本不会为类定义move函数

头文件

Copy1#include <utility>