使用allocator实现字符串容器

注：本文中的实现来自《C++ Primer》。

allocator对象和三个指针

想要实现一个字符串容器，我们需要一个allocator对象和需要三个指针。allocator对象负责管理内存，三个指针分别为elements_、first_free_和cap_。

（1）elements_指向第一个字符串的位置

（2）first_free_指向最后一个字符串的下一个位置

（3）cap_指向容器的最后一个位置的下一个位置

三个指针

class StrVec {
public:
    StrVec() : elements_(nullptr), first_free_(nullptr), cap_(nullptr) {}
private:
    std::allocator<std::string> alloc_;
    std::string* elements_;
    std::string* first_free_;
    std::string* cap_;
}

基本成员函数

除了allocator对象和三个指针，我们还需要几个基本的成员函数：

（1）不管是析构、拷贝赋值、移动赋值，都需要清空当前的容器：

void StrVec::Free() {
    if (elements_) {  // 没有数据的对象不需要释放
            // 析构所有string对象
            for (std::string* p=first_free_; p!=elements_;) {
                alloc_.destroy(--p);
            }
            alloc_.deallocate(elements_, cap_ - elements_);  // 回收内存
    }
}

（2）当往容器内添加数据时，如果恰好当前容量已用完，我们需要重新分配一块较大的内存，将当前数据拷贝到新内存，并释放当前内存：

void StrVec::Reallocate() {
    size_t size = first_free_ - elements_;
    size_t new_capacity = size ? 2 * size : 1;  // 新容量为当前容量的两倍
    std::string* new_data = alloc_.allocate(new_capacity);  // 分配新内存
    // 将当前数据拷贝到新内存
    for (size_t i=0; i!=size; ++i) {
        alloc_.construct(new_data+i, std::move(*(elements_+i)));
    }
    Free();  // 释放当前内存
    elements_ = new_data;
    first_free_ = new_data + size;
    cap_ = new_data + new_capacity;
}

（3）负责判断当前容量是否用完，如果用完则执行Reallocate()

void StrVec::ChkNAlloc() {
    if (first_free_ == cap_) {
        Reallocate();
    }
}

（4）给定两个指针，开辟一块能够恰好容纳这两个指针之间的数据的内存，并且把这些数据拷贝到新开辟的内存

std::pair<std::string*, std::string*> StrVec::AllocNCopy(const std::string* b, const std::string* e) {
    std::string* data = alloc_.allocate(e - b);  // 分配新内存
    return {data, uninitialized_copy(b, e, data)};  // 拷贝
}

高级成员函数

有了上述基本成员函数还不够，想要好用，我们还需要一些高级的成员函数：

（1）大小和容量

size_t StrVec::Size() const {
    return first_free_ - elements_;
}
size_t StrVec::Capacity() const {
    return cap_ - elements_;
}

（2）迭代器

std::string* StrVec::Begin() const {
    return elements_;
}
std::string* StrVec::End() const {
    return first_free_;
}

（3）往容器里添加数据

void StrVec::PushBack(const std::string& s) {
    ChkNAlloc();  // 首先检查已分配的内存是否用完，用完就重新分配
    alloc_.construct(first_free_++, s);  // 在first_free_位置直接构造
}
void StrVec::PushBack(std::string&& s) {
    ChkNAlloc();
    alloc_.construct(first_free_++, std::move(s));
}

（4）列表初始化

StrVec::StrVec(std::initializer_list<std::string> il) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(il.begin(), il.end());
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
}

（5）拷贝构造

StrVec::StrVec(const StrVec& v) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(v.Begin(), v.End());
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
}

（5）拷贝赋值

StrVec& StrVec::operator=(const StrVec& v) {
    if (this != &v) {
        std::pair<std::string*, std::string*> new_data = AllocNCopy(v.Begin(), v.End());
        Free();  // 先释放当前数据
        elements_ = new_data.first;
        cap_ = first_free_ = new_data.second;
    }
    return *this;
}
StrVec& StrVec::operator=(std::initializer_list<std::string> il) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(il.begin(), il.end());
    Free();  // 先释放当前数据
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
    return *this;
}

（6）取下标

std::string& StrVec::operator[](size_t n) {
    return elements_[n];
}
const std::string& StrVec::operator[](size_t n) const {
    return elements_[n];
}

（7）析构

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

完整代码

#include <string>
#include <memory>


class StrVec {
public:
    StrVec();
    size_t Size() const;
    size_t Capacity() const;
    std::string* Begin() const;
    std::string* End() const;
    void PushBack(const std::string&);
    void PushBack(std::string&&);
    StrVec(std::initializer_list<std::string>);
    StrVec(const StrVec&);
    StrVec& operator=(const StrVec&);
    StrVec& operator=(std::initializer_list<std::string>);
    std::string& operator[](size_t n);
    const std::string& operator[](size_t n) const;
    ~StrVec();
private:
    std::allocator<std::string> alloc_;

    std::string* elements_;
    std::string* first_free_;
    std::string* cap_;

    void Free();
    void Reallocate();
    void ChkNAlloc();
    std::pair<std::string*, std::string*> AllocNCopy(const std::string*, const std::string*);
};
StrVec::StrVec() : elements_(nullptr), first_free_(nullptr), cap_(nullptr) {}
void StrVec::Free() {
    if (elements_) {  // 没有数据的对象不需要释放
        // 析构所有string对象
        for (std::string* p=first_free_; p!=elements_;) {
            alloc_.destroy(--p);
        }
        alloc_.deallocate(elements_, cap_ - elements_);  // 回收内存
    }
}
void StrVec::Reallocate() {
    size_t size = first_free_ - elements_;
    size_t new_capacity = size ? 2 * size : 1;  // 新容量为当前容量的两倍
    std::string* new_data = alloc_.allocate(new_capacity);  // 分配新内存
    // 将当前数据拷贝到新内存
    for (size_t i=0; i!=size; ++i) {
        alloc_.construct(new_data+i, std::move(*(elements_+i)));
    }
    Free();  // 释放当前内存
    elements_ = new_data;
    first_free_ = new_data + size;
    cap_ = new_data + new_capacity;
}
void StrVec::ChkNAlloc() {
    if (first_free_ == cap_) {
        Reallocate();
    }
}
std::pair<std::string*, std::string*> StrVec::AllocNCopy(const std::string* b, const std::string* e) {
    std::string* data = alloc_.allocate(e - b);  // 分配新内存
    return {data, uninitialized_copy(b, e, data)};  // 拷贝
}
size_t StrVec::Size() const {
    return first_free_ - elements_;
}
size_t StrVec::Capacity() const {
    return cap_ - elements_;
}
std::string* StrVec::Begin() const {
    return elements_;
}
std::string* StrVec::End() const {
    return first_free_;
}
void StrVec::PushBack(const std::string& s) {
    ChkNAlloc();  // 首先检查已分配的内存是否用完，用完就重新分配
    alloc_.construct(first_free_++, s);  // 在first_free_位置直接构造
}
void StrVec::PushBack(std::string&& s) {
    ChkNAlloc();
    alloc_.construct(first_free_++, std::move(s));
}
StrVec::StrVec(std::initializer_list<std::string> il) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(il.begin(), il.end());
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
}
StrVec::StrVec(const StrVec& v) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(v.Begin(), v.End());
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
}
StrVec& StrVec::operator=(const StrVec& v) {
    if (this != &v) {
        std::pair<std::string*, std::string*> new_data = AllocNCopy(v.Begin(), v.End());
        Free();  // 先释放当前数据
        elements_ = new_data.first;
        cap_ = first_free_ = new_data.second;
    }
    return *this;
}
StrVec& StrVec::operator=(std::initializer_list<std::string> il) {
    std::pair<std::string*, std::string*> new_data = AllocNCopy(il.begin(), il.end());
    Free();  // 先释放当前数据
    elements_ = new_data.first;
    cap_ = first_free_ = new_data.second;
    return *this;
}
std::string& StrVec::operator[](size_t n) {
    return elements_[n];
}
const std::string& StrVec::operator[](size_t n) const {
    return elements_[n];
}
StrVec::~StrVec() {
    Free();
}


#include <iostream>


int main() {
    StrVec v1 = {"foo", "bar"};
    v1.PushBack("baz");
    v1.PushBack("qux");
    v1[3] = "quux";
    StrVec v2;
    v2 = {"foo", "bar"};
    std::cout << v1[3] << std::endl;
    std::cout << v2[1] << std::endl;
    return 0;
}