C++ Primer 13.5练习：实现StrVec和String

StrVec(13.5)

该练习设计了一个vector的特化版本 - 一个专门用于存储string的vector，其内存分配通过一个allocator类alloc来管理，用三个指针element, first_free, end_of_storage分别表示内存区开头，已构造内存的末尾以及整个内存区的末尾。

我花了5-6小时设计整个类，但个人认为最重要，最必不可少的组成部分当属默认构造函数，push_back()，构析push_back()将元素加入的容器的操作涉及alloc的分配构造，加入元素前类会先检查容器是否已满，若是就需要通过调用reallocate()函数分配比原内存2倍大的新内存并将旧有元素移动（这里为什么用移动而不是拷贝我并不明白，反正效率更高）到新内存，然后销毁旧内存，更新三个元素指针。

void StrVec::push_back(const string& val){    
    if(size() == capacity()){
        reallocate();
        push_back(val);
    }
    else{
        alloc.construct(first_free++,val);
    }
}

reallocate()会调用其下的一个工具函数alloc_n_move(n)去新构造一片大小为n的内存并将元素移动到那上面去，至于为什么用工具函数是考虑到了设计reserve和resize的情况，不过由于时间关系我目前并未设计这两个函数。

//scaling vector to two times of its original size
void StrVec::reallocate(){
    size_t new_capacity = size() * 2;
    alloc_n_move(new_capacity);
}


//move all element to new memory with a size of n;
void StrVec::alloc_n_move(size_t _n){
    size_t new_capacity = (size() == 0) ? 1 : _n;
    string* new_elem = alloc.allocate(new_capacity);
    string *dest = new_elem;
    string *old_elem = element;

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

    free();

    element = new_elem;
    first_free = dest;
    end_of_storage = new_elem + new_capacity;
}

构析和reallocate()都需要调用free()函数将旧内存销毁，之后的拷贝赋值函数也会调用到free()，当然需要注意先拷贝再复制以防止自赋值的情况。设计free()时一定注意三个指针是否在自己预料的位置…自己之前因此debug了半天。。。。。。。

void StrVec::free(){
    //the element must exist
    if(element){
        for(string* it = first_free; it != element; ){
            alloc.destroy(--it);
        }
        alloc.deallocate(element,end_of_storage - element);
    }
}

上面的就都是核心功能了，后面的从初始化列表构造，拷贝构造，拷贝赋值，pop_back, reserve, resize等等就基本是点缀，不过前面的三个函数都要调用到一个alloc_n_copy(b,e)的函数，这个函数会从[b,e）的区别拷贝内存到新内存并返回新内存的区间[newb, newe)

pair<string*,string*> StrVec::alloc_n_copy(const string* b,const string* e){
    auto data = alloc.allocate(e - b);
    return {data, uninitialized_copy(b,e,data)};
}

StrVec.h

#pragma once
#include<iostream>
#include<string>
#include<memory>
#include<initializer_list>
using namespace std;
class StrVec{
public:
    StrVec():element(nullptr),first_free(nullptr),end_of_storage(nullptr){}
    StrVec(initializer_list<string> lst);
    StrVec(const StrVec&);
    StrVec& operator=(const StrVec&);
    void push_back(const string& val);
    void pop_back();
    const string* begin() const { return element; }	//必须在后面加const，否则有qualifer错误
    const string* end() const { return first_free; }
    size_t size() const { return size_t(first_free - element); }
    size_t capacity() { return size_t(end_of_storage - element); }
    bool empty() {return element == first_free;}
    void print();
    ~StrVec();
private:
    void reallocate();
    pair<string*,string*> alloc_n_copy(const string*,const string*);
    void alloc_n_move(size_t);
    void free();
private:
    string* element;
    string* first_free;
    string* end_of_storage;
    allocator<string> alloc;
};

StrVec.cpp

#include"StrVec.h"
StrVec::StrVec(initializer_list<string> lst){
    auto range = alloc_n_copy(lst.begin(), lst.end());
    element = range.first;
    first_free = range.second;
    end_of_storage = element + lst.size();
}

StrVec::StrVec(const StrVec& rhs){
    auto range = alloc_n_copy(rhs.begin(), rhs.end());
    element = range.first;
    first_free = range.second;
    end_of_storage = element + rhs.size();
}

StrVec& StrVec::operator=(const StrVec& rhs){
    auto range = alloc_n_copy(rhs.begin(), rhs.end());
    //确保先copy再free - 防范自赋值的情况
    free();
    element = range.first;
    first_free = range.second;
    end_of_storage = element + rhs.size();
    return *this;
}

void StrVec::push_back(const string& val){    
    if(size() == capacity()){
        reallocate();
        push_back(val);
    }
    else{
        alloc.construct(first_free++,val);
    }
}

void StrVec::pop_back(){
    if(empty() == true)
        return;
    --first_free;
    alloc.destroy(first_free);
}

//scaling vector to two times of its original size
void StrVec::reallocate(){
    size_t new_capacity = size() * 2;
    alloc_n_move(new_capacity);
}

pair<string*,string*> StrVec::alloc_n_copy(const string* b,const string* e){
    auto data = alloc.allocate(e - b);
    return {data, uninitialized_copy(b,e,data)};
}

//move all element to new memory with a size of n;
void StrVec::alloc_n_move(size_t _n){
    size_t new_capacity = (size() == 0) ? 1 : _n;
    string* new_elem = alloc.allocate(new_capacity);
    string *dest = new_elem;
    string *old_elem = element;

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

    free();

    element = new_elem;
    first_free = dest;
    end_of_storage = new_elem + new_capacity;
}


void StrVec::free(){
    //the element must exist
    if(element){
        for(string* it = first_free; it != element; ){
            alloc.destroy(--it);
        }
        alloc.deallocate(element,end_of_storage - element);
    }
}

void StrVec::print(){
    for(string* it = element; it != first_free; it++){
        cout << *it << " ";
    }
    cout << endl;
}

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

12.12 ADD:

将reserve和resize实现了一下，并拿去和vector测试对比，基本和当时背的八股差不多了，不过这次还惊讶的发现原来vector用resize是可能调用push_back的：参数n > capacity的情况下vector的capacity出现了两倍扩容。

源码一写，这下对于这两个函数基本没有疑问了。

void reserve(size_t);
void resize(size_t, const string& val = string());
....
/*  change capacity to demanded _n,
    if _n <= cap, do nothing, otherwise
    make memory of capacity n and move old elements, 
    then destroy old memory.
 */
void StrVec::reserve(size_t _n){
    if(_n < 0)
        throw std::length_error("Strvec::reserve");
    //实际上这里还应该检测max_size,这里就不设计了
    if(_n <= capacity())
        return;
    else{
        alloc_n_move(_n);
    }
}

/* 
    change size to demanded _n,
    if _n < size, change size to _n.
 */
void StrVec::resize(size_t _n, const string& val){
    if(_n < 0)
        throw std::length_error("Strvec::resize");
    //实际上这里还应该检测max_size,这里就不设计了
    while(size() != _n){
        if(_n < size())
            pop_back();
        else{
            //如果发生了扩容，让push_back背后的alloc_n_move承担
            push_back(val);
        }
    }  
}

测试程序（对于vector改个类型就行）

#include<vector>
#include"StrVec.h"
void print(StrVec &vec){
    for(string str : vec){
        cout << str << " ";
    }
    cout << endl;
}
int main(){
    StrVec vec1({"H","G","B","N","E","G"});    
    cout << vec1.size() << " " << vec1.capacity() << endl;

    vec1.resize(8);
    cout << vec1.size() << " " << vec1.capacity() << endl;
    print(vec1);

    vec1.resize(12);
    cout << vec1.size() << " " << vec1.capacity() << endl;
    print(vec1);

    vec1.resize(17,"B");
    cout << vec1.size() << " " << vec1.capacity() << endl;
    print(vec1);


}

String(13.5)

其实String的很多行为都和vector相似，上面的StrVec稍加改进就是一个String了， 但实际的String需要处理的细节更多，包括重载ostream输出，定义加减比较运算符等，这里只把c_str和const char*构造实现了，有趣的是不同于vector，string源码size()和capacity()其实是用的变量记录而不是指针计算，size()和capacity都是O(1）返回，底层管理的其实也是个char数组而不是用alloc（EffectiveSTL提到可能还有其他实现方式，比如引用计数指向同一块字符串内存），另外不同于vector，string不管用哪种方式构造都会预留15大小的空间，直到用完了后再两倍扩容。

另外在实现的时候遇到了一个坑，我空参构造String设置的是将三个指针都置为Nullptr，但是这样程序会出现一个莫名其妙的bug，就是调用了某个空参构造的String的c_str后，剩下的String不管有参无参都打印不出属性，起初我还以为是逻辑错误导致指针赋错值的问题，结果我gdb了半天，不断改测试代码，发现指针都是赋的正常值，始终没怪到自己的String类上，最后问了下chatGPT, 一下子就道破了我String类的问题。。。。AI牛逼啊，虽然我不知道为什么一个对象c_str返回空指针会导致其他对象输出异常。

const char* String::c_str() const{
    if(element)
        return element;
    //这里不能直接返回空指针，不然后面对象输出会异常
    return ""; 
}

String.h

#pragma once
#pragma once
#include<iostream>
#include<string>
#include<memory>
#include<initializer_list>
#include<algorithm>
using namespace std;
class String{
public:
    String():element(nullptr),first_free(nullptr),end_of_storage(nullptr){}
    String(initializer_list<char> lst);
+    String(const char*);
    String(const String&);
    String& operator=(const String&);
    void push_back(const char& val);
    void pop_back();
+    const char* c_str() const;
    const char* begin() const { return element; }
    const char* end() const { return first_free; }
    size_t size() const { return size_t(first_free - element); }
    size_t capacity() { return size_t(end_of_storage - element); }
    void reserve(size_t);
    void resize(size_t, const char& val = char());
    bool empty() {return element == first_free;}
    void print();
    ~String();
private:
    void reallocate();
    pair<char*,char*> alloc_n_copy(const char*,const char*);
    void alloc_n_move(size_t);
    void free();
private:
    char* element;
    char* first_free;
    char* end_of_storage;
    allocator<char> alloc;
};

String.cpp

#include"String.h"
#include <cstring>

String::String(initializer_list<char> lst){
    auto range = alloc_n_copy(lst.begin(), lst.end());
    element = range.first;
    first_free = range.second;
    end_of_storage = element + lst.size();
}

+String::String(const char* c_str) {
    size_t len = strlen(c_str);
    char *beg = const_cast<char*>(c_str);
    char *end = beg + len;

    auto range = alloc_n_copy(beg, end);
    element = range.first;
    first_free = range.second;
    end_of_storage = element + len;
}

String::String(const String& rhs){
    auto range = alloc_n_copy(rhs.begin(), rhs.end());
    element = range.first;
    first_free = range.second;
    end_of_storage = element + rhs.size();
}

String& String::operator=(const String& rhs){
    auto range = alloc_n_copy(rhs.begin(), rhs.end());
    //确保先copy再free - 防范自赋值的情况
    free();
    element = range.first;
    first_free = range.second;
    end_of_storage = element + rhs.size();
    return *this;
}

void String::push_back(const char& val){    
    if(size() == capacity()){
        reallocate();
        push_back(val);
    }
    else{
        alloc.construct(first_free++,val);
    }
}

void String::pop_back(){
    if(empty() == true)
        return;
    --first_free;
    alloc.destroy(first_free);
}

+const char* String::c_str() const{
    if(element)
        return element;
    return ""; // return an empty string instead of a null pointer
}

/*  change capacity to demanded _n,
    if _n <= cap, do nothing, otherwise
    make memory of capacity n and move old elements, 
    then destroy old memory.
 */
void String::reserve(size_t _n){
    if(_n < 0)
        throw std::length_error("Strvec::reserve");
    //实际上这里还应该检测max_size,这里就不设计了
    if(_n <= capacity())
        return;
    else{
        alloc_n_move(_n);
    }
}

/* 
    change size to demanded _n,
    if _n < size, change size to _n.
 */
void String::resize(size_t _n, const char& val){
    if(_n < 0)
        throw std::length_error("Strvec::resize");
    //实际上这里还应该检测max_size,这里就不设计了
    while(size() != _n){
        if(_n < size())
            pop_back();
        else{
            //如果发生了扩容，让push_back背后的alloc_n_move承担
            push_back(val);
        }
    }
   
}


//scaling vector to two times of its original size
void String::reallocate(){
    size_t new_capacity = size() * 2;
    alloc_n_move(new_capacity);
}

pair<char*,char*> String::alloc_n_copy(const char* b,const char* e){
    auto data = alloc.allocate(e - b);
    return {data, uninitialized_copy(b,e,data)};
}

/* move all element to new memory with a capacity of n;
    size remain unchange.
*/
void String::alloc_n_move(size_t _n){
    size_t new_capacity = (size() == 0) ? 1 : _n;
    char* new_elem = alloc.allocate(new_capacity);
    char *dest = new_elem;
    char *old_elem = element;

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

    free();

    element = new_elem;
    first_free = dest;
    end_of_storage = new_elem + new_capacity;
}


void String::free(){
    //the element must exist
    if(element){
        for(char* it = first_free; it != element; ){
            alloc.destroy(--it);
        }
        alloc.deallocate(element,end_of_storage - element);
    }
}

void String::print(){
    for(char* it = element; it != first_free; it++){
        cout << *it << " ";
    }
    cout << endl;
}

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

测试代码：

#include<iostream>
#include<vector>
#include"String.h"
using namespace std;
int main(){
    String cpp;
    cpp.push_back('A');
    cout << cpp.c_str() <<  cpp.size() << cpp.capacity() << endl;
    String cpp2 = "bbbb";
    for(auto it = cpp2.begin(); it != cpp2.end(); it++){
        cout << *it << " ";
    }
    String cpp3(cpp);
    cout << cpp3.c_str() << " " << cpp3.size() << " " << cpp3.capacity() << endl;

    String cpp4 = "happy";
    cout << cpp4.c_str() << " " << cpp4.size() << " " << cpp4.capacity() << endl;


}

string源码部分：

...
pointer _M_p; // The actual data.
};

_Alloc_hider	_M_dataplus;
size_type		_M_string_length;

enum { _S_local_capacity = 15 / sizeof(_CharT) };

union
{
    _CharT           _M_local_buf[_S_local_capacity + 1];
    size_type        _M_allocated_capacity;
};
...
size_type
size() const _GLIBCXX_NOEXCEPT
{ return _M_string_length; }
 
    
 /**
     *  Returns the total number of characters that the %string can hold
     *  before needing to allocate more memory.
 */
    size_type
    capacity() const _GLIBCXX_NOEXCEPT
{
    return _M_is_local() ? size_type(_S_local_capacity)
        : _M_allocated_capacity;
}