目录

一、vs和g++下string结构说明

1.1 vs下string的结构

1.2 g++下string的结构

二、vector和list对比

2.1 vector优缺点

2.2 list优缺点

三、迭代器失效问题

四、list模拟实现 -> 操作符重载问题

一、vs和g++下string结构说明

注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节

1.1 vs下string的结构

测试代码

#include <iostream>#include <string>usingnamespacestd;
intmain()
{
strings1("11111");
strings2(s1);
cout<<"s1: "<<sizeof(s1) <<endl;
cout<<"s2: "<<sizeof(s2) <<endl;
printf("s1: %p\n", s1.c_str());
printf("s2: %p\n", s2.c_str());
return0;
}

运行结果

       结果打印地址是不同的两份地址，是因为进行了深拷贝，给 s2 开辟了独立的空间，我们能理解，但是 s1 和 s2 的大小为什么是 28 呢？？

       string 总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义 string 中字符串的存储空间：

1. 当字符串长度小于16时，使用内部固定的字符数组来存放
2. 当字符串长度大于等于16时，从堆上开辟空间

union_Bxty{ // storage for small buffer or pointer to larger onevalue_type_Buf[_BUF_SIZE];
pointer_Ptr;
char_Alias[_BUF_SIZE]; // to permit aliasing} _Bx

       这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，string 对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高（实际上只有 capacity 只有15 ，因为第16个空间用于储存 ‘\0’）

在调试模式下查看：

       此时看到的结果并不是 string 真正的结构，VS编译器为了方便大家容易理解，在监视窗口显示进行了优化，点击下面的原始视图查看才是string 本来的面目

此时，我们看到的才是 string 的结构，从图中看出：

1. _Buf 大小是16字节，每一个都是 char 类型
2. 还有一个指针 _Ptr 占用4字节，char* 类型；
3. _Mysize 就是 _size，unsigned int 类型，占用4字节
4. _Myres 就是 _capacity，unsigned int 类型，占用4字节

所以，最后加起来一共是 16+4+4+4=28

注：VS测试编译器版本：VS2019

1.2 g++下string的结构

把刚才的代码拷贝到Linux的 g++ 下运行

#include <iostream>#include <stdio.h>#include <string>usingnamespacestd;
intmain()
{
strings1("11111");
strings2(s1);
cout<<"s1: "<<sizeof(s1) <<endl;
cout<<"s2: "<<sizeof(s2) <<endl;
printf("s1: %p\n", s1.c_str());
printf("s2: %p\n", s2.c_str());
return0;
}

运行结果

       结果也很奇怪奇怪，s1 和 s2 的大小居然是 8， s1 和 s2 的地址更加奇怪，地址居然是相同的？？两个对象共用一块空间？？

       g++下，string 是通过写时拷贝实现的，string 对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段:

1. 空间总大小
2. 字符串有效长度
3. 引用计数

struct_Rep_base{
size_type_M_length;
size_type_M_capacity;
_Atomic_word_M_refcount;
};

• 4.指向堆空间的指针，用来存储字符串

       准确来说，s1、s2 大小应该是 4，因为 s1、s2 里面只有一个指针，上面结果为什么是 8 可能与 g++ 编译器版本有问题

       g++ 下，string 是通过写时拷贝实现的，string 拷贝默认是浅拷贝，使用引用计数指向这块空间，假设 s1 和 s2 不修改指向这个空间的内容，编译器就赚了，不用开额外的空间给s2，赌徒思维；假设 s2 发生对内容的修改操作，s2 就会发生写时拷贝，就会另外开空间给 s2

下面进行验证，修改 s2 的内容：

#include <iostream>#include <stdio.h>#include <string>usingnamespacestd;
intmain()
{
strings1("11111");
strings2(s1);
cout<<"s1: "<<sizeof(s1) <<endl;
cout<<"s2: "<<sizeof(s2) <<endl;
printf("s1: %p\n", s1.c_str());
printf("s2: %p\n", s2.c_str());
cout<<endl;
s2+="2";
printf("s1: %p\n", s1.c_str());
printf("s2: %p\n", s2.c_str());
return0;
}

运行结果，地址确实发生了变化

二、vector和list对比

2.1 vector优缺点

vector优点：

1. 支持下标随机访问
2. 尾删尾插效率高（但不明显）
3. CPU高速缓存命中率高：因为物理空间连续

vector缺点：

1. 前面部分插入删除效率低，O(n)

1. 扩容有消耗，还存在一定的空间浪费，扩容开多了浪费，开少了浪费空间

2.2 list优缺点

ist优点：

1. 按需申请释放，无需扩容
2. 任意位置插入删除是O(1)

list缺点：

1. 不支持下标的随机访问
2. CPU高速缓存命中率低

总之，vector 和 list 之间是互补的

补充 C++ 的一个坑

注：上面的图片是随便截的，并不止这几处，只是拿来举例

为什么库里面的l类名不用加类型？

       上面框出来的地方这其实是 C++ 的一个坑，在类里面可以直接用类名代表类型，比如  list& operator= (const list& x)，它也可以写成这样： list& operator= (const list& x)，这两种都可以运行，但是不建议使用类名代表类型这种方式

但是在类外部，就必须指定类型，比如 list 、vector，类外面不指明类型直接报错

普通类类名等价于类型类模板类名不等价于类型// 如：list模板 类名list  类型list<T> // 类模板里面可以用类名代表类型，但是建议不要那么用

三、迭代器失效问题

      迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)

• vector 迭代器失效：insert 和 erase
• list 迭代器失效：erase
• string 有没有迭代器失效的问题？ 有，insert 和 erase 失效跟vector类似，但是一般不关注 string 迭代器的失效问题，因为 string 的 insert和erase常用接口函数都是下标支持的，迭代器基本不用

四、list模拟实现 -> 操作符重载问题

list模拟实现在上一篇，链接 ，代码如下：（上篇忘记了...）

Ptroperator->()
{
return&_pnode->_data;
}

在迭代器类里面实现

在某种场景下要使用 -> 这个操作符，比如

#include "list.h"structPos{
int_row;
int_col;
Pos(introw=0, intcol=0)
        :_row(row)
        , _col(col)
    {}
};
voidTest_operator()
{
fy::list<Pos>lt;
Posp1(1, 1);
lt.push_back(p1);
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
// int* p  -> *p// Pos* p  -> p->fy::list<Pos>::iteratorit=lt.begin();
while (it!=lt.end())
    {
it->_row++;
cout<<it->_row<<":"<<it->_col<<endl;
//cout << it.operator->()->_row << ":" << it->_col << endl;//cout << (&(*it))->_row << ":" << (*it)._col << endl;++it;
    }
cout<<endl;
}
intmain()
{
Test_operator();
return0;
}

        用 Pos 类来构造 list，要访问 Pos里面的成员就要使用 -> ，这也是要返回数据的地址的原因

return &_pnode->_data;

上面代码运行结果

       实际上，it -> 的本来面貌是 it->->，编译器为了可读性，做了特殊处理，省略了一个 ->  

       it-> 会调用 operator->() 这个函数，这个函数返回的是数据的地址，即 Pos*，Pos* 再用 -> 就会访问里面的元素

这句打印的代码也可以写成下面两句：

cout<<it->_row<<":"<<it->_col<<endl;
//cout << it.operator->()->_row << ":" << it->_col << endl;//cout << (&(*it))->_row << ":" << (*it)._col << endl;

但是依旧是第一种简便，后面有实现 operator->() 的情况，解释跟这里一样

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新