6 string实现

- - 一．string的三种实现方式
  - 二．面向对象之继承
  - 三．关联式容器
  - - 1.set的基本使用
    - 2.map的基本使用

一．string的三种实现方式

深拷贝（对比浅拷贝）
写时复制思想：只有当需要对字符串执行写操作的时候才进行深拷贝，如果是读操作的时候，就执行浅拷贝。实现技术：浅拷贝 + 引用计数，ubuntu1404使用写时复制

pointer这边是在栈空间，数据、引用计数相关存放在堆空间，ubuntu1404使用的是第二种形式，因此在ubuntu1404上面sizeof(string对象)时的结果都是8，图解如下：

有两种写时复制的形式：
1. 图解：
```
class string {
private: 
    Allocator _allocator; 
    size_t size; 
    size_t capacity; 
    char * pointer; 
};
```
2. 图解：
```
class string {
private: 
    char * _pointer; 
};
```
短字符串优化：当字符串的长度小于16字节的时候，就申请在栈上；当字符串的长度大于等于16字节的时候，就申请在堆上。 ubuntu1804上使用的短字符串优化。每个string对象都占32个字节。

形式为：

故std::string的数据成员为：
```
class string { 
    union Buffer { 
        char * _pointer; 
        char _local[16]; 
    };
    Buffer _buffer; 
    size_t _size; 
    size_t _capacity; 
};
```
最佳策略：facebook开源的folly库实现的fbstring的做法：
1. 很短的（0~22）字符串用SSO，23字节表示字符串（包括’’）,1字节表示长度.
2. 中等长度的（23~255）字符串用eager copy，8字节字符串指针，8字节size，8字节capacity.
3. 很长的(大于255)字符串用COW, 8字节指针（字符串和引用计数），8字节size，8字节capacity.

尝试自己实现cow形式的string类的实现，引用计数放在栈跟静态全局位置都不能完成需求：

放在栈上时，拷贝构造函数时传入的是const对象，不能改变refcount；
静态全局变量时，refcount所有string对象共享，字符串不同的时候refcount一样；
鉴于此，所以string类只保留指针及相关信息，把字符串跟引用计数及相关信息都放在堆上；

写cow形式的string类时，下标运算符[ ]重载时有个问题，无法确定下标访问时是否有修改该位置的值，从而无法判断是否要进行复制。

解决思路：定义一个内部类，数据成员包含字符串的首地址和下标访问的idx，当重载下标运算符时，直接定义该内部类的对象并返回。该内部类进行赋值运算符重载和类型转换运算符【operator char()】重载，赋值运算符保证当修改该字符串内容时进行写时复制，类型转换保证正确的返回要读的值。（也就是代理模式）

#include 
#include 
using std::cout;
using std::endl;
class String
{
public:
    String()
    : _pstr(new char[5]() + 4)
    {
        cout << "String()" << endl;
        initRefcount();
    }
    
    String(const char *pstr)
    : _pstr(new char[strlen(pstr) + 5]() + 4)
    {
        cout << "String(const char *)" << endl;
        strcpy(_pstr, pstr);
        initRefcount();
    }

    String(const String &rhs)
    : _pstr(rhs._pstr)//浅拷贝
    {
        cout << "String(const String &)" << endl;
        increaseRefcount();
    }

    String &operator=(const String &rhs)
    {
        cout << "String &operator=(const String &)" << endl;
        if(this != &rhs)
        {
            release();//2、释放左操作数
            _pstr = rhs._pstr;//3、浅拷贝
            increaseRefcount();
        }
        return  *this;
    }
    ~String()
    {
        cout << "~String()" << endl;
        release();
    }
private:
    //设计模式之代理模式
    class CharProxy
    {
    public:
        CharProxy(String &self, size_t idx)
        : _self(self)
        , _idx(idx)
        {}
        char &operator=(const char &ch);
        
        operator char()
        {
            return _self._pstr[_idx];
        }

    private:
        String  &_self;
        size_t _idx;
    };
public:
    CharProxy operator[](size_t idx)
    {
        return CharProxy(*this, idx);
    }
private:
    void release()
    {
        decreaseRefcount();
        if(0 == getRefcount())
        {
            delete [] (_pstr - 4);
        }
    }
    void initRefcount()
    {
        *(int *)(_pstr - 4) = 1;
    }
    void increaseRefcount()
    {
        ++*(int *)(_pstr - 4);
    }
    void decreaseRefcount()
    {
        --*(int *)(_pstr - 4);
    }
public:
    size_t size()
    {
        return strlen(_pstr);
    }

    const char *c_str()
    {
        return _pstr;
    }

    int getRefcount()
    {
        return *(int *)(_pstr - 4);
    }

    friend std::ostream &operator<<(std::ostream &os, const String &rhs);
    

private:
    char *_pstr;
};

std::ostream &operator<<(std::ostream &os, const String &rhs)
{
    if(rhs._pstr)
    {
        os << rhs._pstr;
    }
    return os;
}

char &String::CharProxy::operator=(const char &ch)
{
    if(_idx < _self.size())
    {
        if(_self.getRefcount() > 1)//是不是共享的
        {
            char *ptmp = new char[_self.size() + 5]() + 4;
            strcpy(ptmp, _self._pstr);
            _self.decreaseRefcount();

            _self._pstr = ptmp;
            _self.initRefcount();
        }
        _self._pstr[_idx] = ch;//真正赋值的位置
        return _self._pstr[_idx];
    }
    else
    {
        static char charnull = '';
        return charnull;
    }
}

#if 0
std::ostream &operator<<(std::ostream &os, const String::CharProxy &rhs)
{
    os << rhs._self._pstr[rhs._idx];
    return os;
}
#endif

二．面向对象之继承

派生类生成的三大步骤

吸收基类的成员

改造基类的成员

添加自己的成员
继承的局限，以下不能继承：

构造函数

析构函数

用户重载的operator new/delete运算符

用户重载的operator=运算符

友元关系
派生类对象对基类成员的访问权限

protected成员是保护成员，只能在本类和派生类中访问，是一种区分血缘关系内外有别的成员。

总结：派生类的访问权限规则如下：
1. 不管以什么继承方式，派生类内部都不能访问基类的私有成员；
2. 不管以什么继承方式，派生类内部除了基类的私有成员不可以访问外，其他的都可以访问；
3. 不管以什么继承方式，派生类对象除了公有继承基类中的公有成员可以访问外，其他的一律不能访问。
派生类对象的构造
1. 如果派生类有显式定义构造函数，而基类没有显示定义构造函数，则创建派生类的对象时，派生类相应的构造函数会被自动调用，此时都自动调用了基类缺省的无参构造函数。
2. 如果派生类没有显式定义构造函数而基类有显示定义构造函数，则基类必须拥有默认构造函数。
3. 如果派生类有构造函数，基类有默认构造函数，则创建派生类的对象时，基类的默认构造函数会自动调用，如果你想调用基类的有参构造函数，必须要在派生类构造函数的初始化列表中显示调用基类的有参构造函数。
4. 如果派生类和基类都有构造函数，但基类没有默认的无参构造函数，即基类的构造函数均带有参数，则派生类的每一个构造函数必须在其初始化列表中显示的去调用基类的某个带参的构造函数。如果派生类的初始化列表中没有显示调用则会出错，因为基类中没有默认的构造函数。
派生类构造函数的调用顺序：
1. 完成对象所占整块内存的开辟，由系统在调用构造函数时自动完成。
2. 调用基类的构造函数完成基类成员的初始化。
3. 若派生类中含对象成员、const成员或引用成员，则必须在初始化表中完成其初始化。
4. 派生类构造函数体执行。
  
  注意：这里的一个说法，错误说法，创建派生对象的时候，先调用基类构造函数，然后调用派生类构造函数。
  
  正确说法：创建派生类对象的时候，会调用派生类的构造函数，为了完成对从基类继承的数据成员的初始化，需要利用基类的构造函数，所以可以看到基类构造函数的一个调用，然后再调用派生的构造函数的函数体。
派生类对象的销毁。

在执行派生类析构函数时，基类析构函数会被自动调用。执行顺序是先执行派生类的析构函数，再执行基类的析构函数，这和执行构造函数时的顺序正好相反。当考虑对象成员时，继承机制下析构函数的调用顺序：
1. 先调用派生类的析构函数；
2. 再调用派生类中成员对象的析构函数；
3. 最后调用普通基类的析构函数。
多重/基继承
1. 多基继承
  
  构造与销毁：首先要执行所有基类的构造函数，再执行派生类构造函数中初始化表达式的其他内容和构造函数体。各基类构造函数的执行顺序与其在初始化表中的顺序无关，而是由定义派生类时指定的基类顺序决定的。析构函数的执行顺序同样是与构造函数的执行顺序相反。
  
  对于每一个基类，在派生类进行继承的时候，都要写继承方式，否则就是私有继承。
2. 成员名冲突的二义性：
  
  在调用时，指明要调用的是某个基类的成员函数即可，即使用作用域限定符就可以解决该问题。
3. 菱形继承的二义性：
  
  使用虚基类，虚拟继承。若有类B、C虚拟继承类A，类D继承B、C，那么B、C中会多一个虚基指针，指向虚基类，类D也会继承B、C的虚基指针。

基类与派生类间的相互转换

“类型适应”是指两种类型之间的关系，说A类适应B类是指A类的对象能直接用于B类对象所能应用的场合。派生类适用于基类，故：

向上转型

可以把派生类的对象赋值给基类的对象

可以把基类的引用绑定到派生类的对象

可以声明基类的指针指向派生类的对象 (向上转型)

cout << endl << "从派生类对象向基类对象进行转换"  << endl;
Base base = derived;//ok, 1、派生类对象可以赋值给基类对象
base.operator=(derived);
//Base &operator=(const Base &rhs) == > const Base &rhs = derived

Base &ref = derived;//ok,2、基类的引用可以绑定到派生类对象

Base *pbase = &derived;//ok,3、基类的指针可以指向派生类对象

向下转型

直接转型时是不可以的。（从内存的角度来考虑，向下转型，比如派生类指针指向基类对象时，若转型成功，则它访问的内存大于基类对象所占用的内存，造成内存越界，不安全）

cout << endl << "从基类对象向派生类对象进行转换" << endl;
Base base1(100);
Derived derived1(200, 300);
derived1 = base1; //error,1、基类对象不能向派生类对象进行转换
derived1.operator=(base1);
//Derived &operator(const Derived &rhs) ====> const Derived &rhs = base1;

Derived &ref2 = base1;//error, 2、派生类的引用不能绑定基类对象上

Derived *pderived1 = &base1;//error, 3、派生类的指针不能指向基类对象(向下转型)

可采用强制类型转换，但还有安全和不安全两种情况：

Base base2(100);
Derived derived2(200, 300);

Derived *pderived2 = static_cast(&base2); //ok,不安全的向下转型

Base *pbase3 = &derived2;
Derived *pderived3 = static_cast(pbase3);//ok, 安全的向下转型

派生类对象之间的转换。

没有定义派生类的拷贝构造或没有重载派生类的赋值运算符：
1. 派生类对象拷贝构造时，如果用户定义了基类的拷贝构造函数，而没有定义派生类的拷贝构造函数，那么在用一个派生类对象初始化新的派生类对象时，两对象间的派生类部分执行缺省的行为，而两对象间的基类部分执行用户定义的基类拷贝构造函数。
2. 派生类对象赋值操作时，如果用户重载了基类的赋值运算符函数，而没有重载派生类的赋值运算符函数，那么在用一个派生类对象给另一个已经存在的派生类对象赋值时，两对象间的派生类部分执行缺省的赋值行为，而两对象间的基类部分执行用户定义的重载赋值函数。
定义了派生类的拷贝构造函数或者重载了派生类对象的赋值运算符
1. 在用已有派生类对象初始化新的派生类对象时，或者在派生类对象间赋值时，将会执行用户定义的派生类的拷贝构造函数或者重载赋值函数，而不会再自动调用基类的拷贝构造函数和基类的重载对象赋值运算符，这时，通常需要用户在派生类的拷贝构造函数或者派生类的赋值函数中显式调用基类的拷贝构造或赋值运算符函数。
```
//example：
Derived(const Derived &rhs)
: Base(rhs)                    //显示调用基类的构造函数，传派生类对象，妙！
, _pderived(new char[strlen(rhs._pderived) + 1]())
{
    cout << "Derived(const Derived &)" << endl;
    strcpy(_pderived, rhs._pderived);
}

Derived &operator=(const Derived &rhs)
{
    cout << "Derived &operator=(const Derived &)" << endl;
    if(this != &rhs)
    {
        Base::operator=(rhs);  //显示调用基类的赋值运算符函数，传派生类对象，妙！

        delete [] _pderived;
        _pderived = nullptr;

        _pderived = new char[strlen(rhs._pderived) + 1]();
        strcpy(_pderived, rhs._pderived);
    }
    return *this;
}
```

三．关联式容器 1.set的基本使用

特征：

关键字是唯一的，不能重复；

默认情况下，会按照关键字进行升序排列；

底层实现使用的是红黑树。

构造函数来初始化

可以创建一个空对象(无参)

使用迭代器范围(begin,end)进行初始化

使用大括号进行初始化

//初始化
// int arr[10] = {1, 2, 4, 6, 8, 9, 12, 3, 5, 6}; 
// set number(arr, arr + 10);//左闭右开的区间
set number = {1, 2, 4, 6, 8, 9, 12, 3, 5, 6};

遍历
1. for(auto &elem,number);
2. 迭代器 set::iterator it;
3. 输出流迭代器ostream_iterator + copy算法来遍历输出
```
ostream_iterator osi(cout," ");
copy(number.begin(),number.end(),osi);
cout << endl;
```

查找

count函数：返回元素的个数
```
size_type count(const Key& key) const;
```

find函数：返回指向元素的迭代器

iterator find(const Key& key);
const_iterator find(const Key& key) const;

auto  it2 = number.find(18);
if(it2 == number.end())
{
    cout << "该元素不存在set中" << endl;
}
else
{
    cout << *it2 << endl;
}

插入: insert()函数:

std::pair insert( const value_type& value );

template< class InputIt >
void insert( InputIt first, InputIt last );

若插入成功，则返回值ret的second成员为true，否则为false。

cout << endl << "set的插入操作" << endl;
pair::iterator, bool> ret =  number.insert(7);
if(ret.second)
{
    cout << "插入成功 : " << *ret.first << endl;
}
else
{
    cout << "该元素插入失败" << endl;
}

int arr2[5] = {2, 30, 20, 10, 8};
number.insert(arr2, arr2 + 5);

对于std::pair类型，其实就是一个模板类：

std::pair
Defined in header 
template struct pair;

Member name	Type
first	     T1
second	     T2

std::pair number(1, "hello,world");
cout << number.first << "   " << number.second << endl

下标访问

set不支持下标访问
不支持修改【为了保证它底层实现的数据结构的红黑树的稳定性】

2.map的基本使用

特征同set

初始化

可以创建一个空对象

使用迭代器返回(begin,end)进行初始化

使用大括号进行初始化

//map的特征：
//1、key值是唯一的（关键字是唯一的），不能重复
//2、默认情况下，会按照key值进行升序排列
map number = {
    {"010","北京"},
    {"020","天津"},
    pair("0755", "深圳"),
    pair("027", "武汉"),
    {"020","南京"},
    {"030","天津"},
};

count()、find()函数均同set，insert也同set，只是插入的内容为pair类型(写成大括号也可以)。

cout << endl << "map的插入" << endl;

auto ret2 = number.insert({"0987", "新疆"});
if(ret2.second)
{
    cout << "插入成功 " << ret2.first->first << "  " << ret2.first->second << endl;
}
else
{
    cout << "插入失败" << endl;
}

map的下标访问，具有查找、插入、修改功能。[原理是重载了该下标访问运算符]

6 string实现

C/C++/C#相关栏目本月热门文章