push: stack、priority_queue insert: unordered_map、unorder_set 均有：vector、string

queue: front stack: top

string转化为int string2int = atoi(string1.c_str()) int转化string int2string = to_string(number)

STL算法总结

迭代器 begin() end() rbegin() rend()

sort()方法：vector

vector

vector vec;

容量 vec.size() vec.empty() vec.resize() vec.reverse()

元素访问 vec[] vec.front()：返回第一个元素 vec.back()：返回最后一个元素 vec.data()：返回第一个元素的指针

修改

push_back() pop_back() insert() erase() clear() swap() assign() emplace() emplace_back()

unordered_map

unordered_map<int,int> res;

容量 res.empty() res.size()

元素访问 res.find() 如果找到返回迭代器，否则返回end() res.count() [] at() ->second

修改 res.insert() res.erase() res.clear()

hash相关

string

string s1;

容量 s1.length() s1.size() s1.resize() s1.reserve()

元素访问 s1.front() s1.back() s1.find() s1.substr() s1.empty()

修改 s1.assign(str1); += s1.swap() s1.push_back() s1.pop_back() s1.clear() s1.insert() s1.append() s1.erase() s1.replace() s1.copy() s1.tranfrom()

stack

stack st;

st.push() st.top() st.pop() st.empty() st.size()

priority_queue

priority_queue<int, vector, less> queue1; 大堆根 priority_queue<int, vector, greater> queue2; 小堆根

queue1.push() queue1.top() queue1.empty() queue1.pop() queue1.emplace()

自定义比较函数

unorder_set

unorder_set sets;

sets.empty() sets.size() sets.find() sets.count() sets.insert() sets.erase() sets.clear()

pair

std::pair <int, float> pair1;

pair1.first

⼿写字符串函数 strcat，strcpy，strncpy，memset，memcpy实现

strcpy

//把 src 所指向的字符串复制到 dest，注意：dest定义的空间应该⽐src⼤。
char* strcpy(char *dest,const char *src) {
 char *ret = dest;
 assert(dest!=NULL);//优化点1：检查输⼊参数
 assert(src!=NULL);
 while(*src!='\0')
 *(dest++)=*(src++);
 *dest='\0';//优化点2：⼿动地将最后的'\0'补上
 return ret;

//考虑内存᯿叠的字符串拷⻉函数 优化的点
char* strcpy(char *dest,char *src) {
 char *ret = dest;
 assert(dest!=NULL);
 assert(src!=NULL);
 memmove(dest,src,strlen(src)+1);
 return ret;
}

}

strcat

char* strcat(char *dest,const char *src) {
 //1. 将⽬的字符串的起始位置先保存，最后要返回它的头指针
 //2. 先找到dest的结束位置,再把src拷⻉到dest中，记得在最后要加上'\0'
 char *ret = dest;
 assert(dest!=NULL);
 assert(src!=NULL);
 while(*dest!='\0')
 dest++;
 while(*src!='\0')
 *(dest++)=*(src++);
 *dest='\0';
 return ret;
}

strcmp

int strcmp(const char *s1,const char *s2) {
 assert(s1!=NULL);
 assert(s2!=NULL);
 while(*s1!='\0' && *s2!='\0') {
 if(*s1>*s2)
 return 1;
 else if(*s1<*s2)
 return -1;
 else {
 s1++,s2++;
 }
 }
 //当有⼀个字符串已经⾛到结尾
 if(*s1>*s2)
 return 1;
 else if(*s1<*s2)
 return -1;
 else
 return 0;
}

strstr

char* strstr(char *str1,char *str2) {
 char* s = str1;
 assert(str1!='\0');
 assert(str2!='\0');
 if(*str2=='\0')
 return NULL;//若str2为空，则直接返回空
 while(*s!='\0') {//若不为空，则进⾏查询
 char* s1 = s;
 char* s2 = str2;
 while(*s1!='\0'&&*s2!='\0' && *s1==*s2)
 s1++,s2++;
 if(*s2=='\0')
 return s;//若s2先结束
 if(*s2!='\0' && *s1=='\0')
 return NULL;//若s1先结束⽽s2还没结束，则返回空
 s++;
 }
 return NULL;
}

memcpy

void* memcpy(void* dest, void* src, size_t num) {
 void* ret = dest ;
 size_t i = 0 ;
 assert(dest != NULL ) ;
 assert(src != NULL) ;
 for(i = 0; i<num; i++) {
 //因为void* 不能直接解引⽤，所以需要强转成char*再解引⽤
 //此处的void*实现了泛型编程
 *(char*) dest = *(char*) src ;
 dest = (char*)dest + 1 ;
 src = (char*) src + 1 ;
 }
 return ret ;
}

memmove

//考虑内存᯿叠的memcpy函数 优化的点
void* memmove(void* dest, void* src, size_t num) {
 char* p1 = (char*)dest;
 char* p2 = (char*)src;
 if(p1<p2) {//p1低地址p2⾼地址
 for(size_t i=0; i!=num; ++i)
 *(p1++) = *(p2++);
 }
 else {
 //从后往前赋值
 p1+=num-1;
 p2+=num-1;
 for(size_t i=0; i!=num; ++i)
 *(p1--) = *(p2--);
 }
 return dest;
}

STL

容器、算法、迭代器、仿函数、配接器、配置器 容器通过配置器获得空间、算法通过迭代器获得容器内容、仿函数完成策略变化、配接器用于算法、仿函数和迭代器

容器

各种数据结构，vector、list、deque、set、map，用来存放数据

算法

各种常用算法，sort（插入、快排、堆排序）、search（二分查找）

迭代器

将operator* operator-> operator++ operator–等指针操作重载

仿函数

重载operator()的类或类模板

配置器

实现动态空间配置、空间管理和释放的类模板

内存管理allocator

双层配置器

• 第⼀级配置器直接使⽤ malloc()和 free()完成内存的分配和回收
• 第⼆级配置器则根据需求的⼤⼩选择不同的策略执⾏
  • 如果需求块⼤⼩⼤于 128bytes，则直接转⽽调⽤第⼀级配置器，使⽤malloc()分配内存。
  • 如果需求块⼤⼩⼩于 128bytes，第⼆级配置器中维护了 16 个⾃由链表，负责 16 种⼩型区块的次配置能⼒。
  • ⾸先查看所需需求块⼤⼩所对应的链表中是否有空闲空间，如果有则直接返回，如果没有，则向内存池中申请所需需求块⼤⼩的内存空间，如果申请成功，则将其加⼊到⾃由链表中。如果内存池中没有空间，则使⽤ malloc() 从堆中进⾏申请，且申请到的⼤⼩是需求的⼆倍（或⼆倍＋n 附加），⼀倍放在⾃由空间中，⼀倍（或⼀倍＋n）放⼊内存池中。
  • 如果 malloc()也失败，则会遍历⾃由空间链表，四处寻找“尚有未⽤区块，且区块够⼤”的freelist，找到⼀块就挖出⼀块交出。如果还是没有，仍交由 malloc()处理，因为 malloc() 有out-of-memory 处理机制或许有机会释放其他的内存拿来⽤，如果可以就成功，如果不⾏就报bad_alloc 异常。

vector

特点：连续空间、三个迭代器、扩充空间

是动态空间，随着元素的加⼊，它的内部机制会自行扩充空间以容纳新元素。vector 维护的是⼀个连续的线性空间，⽽且普通指针就可以满⾜要求作为 vector 的迭代器

有三个迭代器

• ⼀个指向⽬前使⽤空间头的 iterator
• ⼀个指向⽬前使⽤空间尾的 iterator
• ⼀个指向⽬前可⽤空间尾的 iterator

当有新的元素插⼊时，如果⽬前够⽤则直接插⼊，如果不够，则扩充⾄两倍，如果两倍不⾜，就扩张⾄⾜够⼤的容量。是申请⼀块连续空间，将原有的数据拷⻉到新空间中，再释放原有空间，完成⼀次扩充。需要注意的是，每次扩充是重新开辟的空间，所以扩充后，原有的迭代器将会失效

list

特点：非连续空间、双向 每次插⼊或删除⼀个元素，就配置或释放⼀个空间，⽽且原有的迭代器也不会失效。 双向链表。普通指针已经不能满⾜ list 迭代器的需求，因为 list 的存储空间是不连续的。 list 的迭代器必需具备前移和后退功能，所以 list 提供的是 BidirectionalIterator。list 的数据结构中只要⼀个指向 node 节点的指针就可以了。

deque

deque 双向开⼝的连续线性空间。⽀持从头尾两端进⾏元素的插⼊和删除操作。 deque 更贴切实现了动态空间的概念。deque 没有容量的概念，因为它是动态地以分段连续空间组合⽽成，随时可以增加⼀段新的空间并连接起来。 要维护这种整体连续的假象，并提供随机存取的接⼝（即也提供RandomAccessIterator），避开了“重新配置，复制，释放”的轮回，代价是复杂的迭代器结构。也就是说除⾮必要，我们应该尽可能使⽤ vector，⽽不是 deque。 迭代器：缓冲区现行元素、缓冲区头、缓冲区尾、指向map deque 采⽤⼀块所谓的map作为主控，这⾥的 map 实际上就是⼀块⼤⼩连续的空间，其中每⼀个元素，我们称之为节点 node，都指向了另⼀段连续线性空间称为缓冲区，缓冲区才是 deque 的真正存储空间主体。默认大小512bytes，当满载时候，会申请一块更大的空间

stack

是⼀种先进后出的数据结构，只有⼀个出⼝，stack 允许从最顶端新增元素，移除最顶端元素，取得最顶端元素。deque 是双向开⼝的数据结构，所以使⽤ deque 作为底部结构并封闭其头端开⼝，就形成了⼀个 stack。

queue

是⼀种先进先出的数据结构，有两个出⼝，允许从最底端加⼊元素，取得最顶端元素，从最底端新增元素，从最顶端移除元素。deque 是双向开⼝的数据结构，若以deque 为底部结构并封闭其底端的出⼝，和头端的⼊⼝，就形成了⼀个 queue。（其实 list 也可以实现 deque

heap

堆并不属于 STL 容器组件，它是个幕后英雄，扮演 priority_queue 的助⼿，priority_queue 允许⽤户以任何次序将任何元素推⼊容器内，但取出时⼀定是从优先权最⾼（数值最⾼）的元素开始取。⼤根堆作为 priority_queue 的底层机制。

⼤根堆，是⼀个满足每个节点的键值都⼤于或等于其⼦节点键值的⼆叉树（具体实现是⼀个vector，⼀块连续空间，通过维护某种顺序来实现这个⼆叉树），新加⼊元素时，新加⼊的元素要放在最下⼀层为叶节点，即具体实现是填补在由左⾄右的第⼀个空格（即把新元素插⼊在底层 vector 的 end()），然后执⾏⼀个所谓上溯的程序：将新节点拿来与 ⽗节点（i»1）⽐较，如果其键值⽐⽗节点⼤，就⽗⼦对换位置，如此⼀直上溯，直到不需要对换或直到根节点为⽌。当取出⼀个元素时，最⼤值在根节点，取⾛根节点，要割舍最下层最右边的右节点，并将其值重新安插⾄最⼤堆，最末节点放⼊根节点后(nums[1] = nums[len -1];)，进⾏⼀个下溯程序：将空间节点和其较⼤的节点对调，并持续下⽅，直到叶节点为⽌。

priority_queue

底层时⼀个vector，使⽤heap形成的算法，插⼊，获取 heap 中元素的算法，维护这个vector，以达到允许⽤户以任何次序将任何元素插⼊容器内，但取出时⼀定是从优先权最⾼（数值最⾼）的元素开始取的⽬的。

slist

slist 是⼀个单向链表。

vector注意事项

• 注意插⼊和删除元素后迭代器失效的问题
• 清空 vector 数据时，如果保存的数据项是指针类型，需要逐项 delete，否则会造成内存泄

频繁调⽤ push_back()影响

• 向 vector 的尾部添加元素，很有可能引起整个对象 存储空间的᯿新分配，᯿新分配更⼤的内存，再将原数据拷⻉到新空间中，再释 放原有内存，这个过程是耗时耗⼒的，频繁调push_back()会导致性能的下降
• C++11 之后， vector 容器中添加了新的⽅法： emplace_back() ，和 push_back()⼀样的是都是在容器末尾添加⼀个新的元素进去，不同的是 emplace_back() 在效率上相较于 push_back() 有了⼀定的提升。
• 内存优化主要体现在使⽤了就地构造（直接在容器内构造对象，不⽤拷⻉⼀个复制品再使⽤）+强制类型转换的⽅法来实现，在运⾏效率⽅⾯，由于省去了拷⻉构造过程，因此也有⼀定的提升。

map 和 set

• map 和 set 都是 C++ 的关联容器，其底层实现都是红⿊树（RB-Tree）⼏乎所有的 map 和 set的操作⾏为，都只是转调 RB-tree 的操作⾏为。
• map 中的元素是 key-value（关键字—值）对：关键字起到索引的作⽤，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set 中每个元素只包含⼀个关键字。
• set 的迭代器是 const 的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么⾸先需要删除该键，然后调节平衡，再插⼊修改后的键值，调节平衡，如此⼀来，破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；⽽map的迭代器则不允许修改key值，允许修改value值。
• map⽀持下标操作，set不⽀持下标操作。map可以⽤key做下标，map的下标运算符[ ]将关键码作为下标去执⾏查找，如果关键码不存在，则插⼊⼀个具有该关键码和mapped_type类型默认值的元素⾄map中，因此下标运算符[ ]在map应⽤中需要慎⽤，const_map不能⽤，只希望确定某⼀个关键值是否存在⽽不希望插⼊元素时也不应该使⽤，mapped_type类型没有默认值也不应该使⽤。如果find能解决需要，尽可能⽤find。

stl迭代器删除元素

• 序列容器 vector，deque来说，使⽤ erase(itertor) 后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动⼀个位置，但是 erase 会返回下⼀个有效的迭代器；

错误做法：

for(vector<int>::iterator iter = vecInt.begin(); iter != vecInt.end(); iter++){
		if(*iter == 444){
			vecInt.erase(iter); // iter 移除后，成为野指针，无法在得到下一个地址
		}
	}

正确做法:

for(vector<int>::iterator iter = vecInt.begin(); iter != vecInt.end(); iter++){
		if(*iter == 444){
			iter = vecInt.erase(iter);  // 移除后，将指针返回（返回指针为下一个iterator的值）
			iter--;
		}
	}

• 对于关联容器 map set 来说，使⽤了 erase(iterator) 后，当前元素的迭代器失效，但是其结构是红⿊树，删除当前元素的，不会影响到下⼀个元素的迭代器，所以在调⽤ erase 之前，记录下⼀个元素的迭代器即可。

if (it != myMap.end()) {
        auto next = std::next(it);  // 记录下一个元素的迭代器
        // 操作next iterator

        myMap.erase(it);
}

• 对于 list 来说，它使⽤了不连续分配的内存，并且它的 erase ⽅法也会返回下⼀个有效的iterator，因此上⾯两种正确的⽅法都可以使⽤。

迭代器和指针

• 迭代器
  • 提供⼀种方法顺序访问⼀个聚合对象中各个元素, ⽽⼜不需暴露该对象的内部表示。过运⽤该模式，使得我们可以在不知道对象内部表示的情况下，按照⼀定顺序（由iterator提供的⽅法）访问聚合对象中的各个元素。
  • 是封装了原⽣指针，根据不同类型的数据结构来实现不同的++，–等操作

STL ⾥ resize 和 reserve 的区别

• resize()：改变当前容器内含有元素的数目(size())，值为默认为0.当v.push_back(3);之后，则是3是放在了v的末尾，即下标为len，此时容器是size为len+1；
• reserve()：改变当前容器的最⼤容量（capacity）,它不会⽣成元素，只是确定这个容器允许放⼊多少对象，如果reserve(len)的值⼤于当前的capacity()，那么重新新分配⼀块能存len个的空间，然后把之前v.size()个对象通过 copy construtor 复制过来，销毁之前的内存；

二叉树

⼀个⼆叉树如果不为空，便是由⼀个根节点和左右两个⼦树构成，左右⼦树都可能为空。

二叉搜索树

⼆叉搜索树：⼆叉搜索树可以提供对数时间的元素插⼊和访问。 节点的放置规则是：任何节点的键值⼀定⼤于其左⼦树的每⼀个节点的键值，并⼩于其右⼦树中的每⼀个节点的键值。 插⼊：从根节点开始，遇键值较⼤则向左，遇键值较⼩则向右，直到尾端，即插⼊点。 删除：如果删除点只有⼀个⼦节点，则直接将其⼦节点连⾄⽗节点。如果删除点有两个⼦节点，以右⼦树中的最⼩值代替要删除的位置。

平衡二叉树

“平衡”的⼤致意思是：没有任何⼀个节点过深，不同的平衡条件会造就出不同的效率表现。以及不同的实现复杂度。有数种特殊结构例如 AVL-tree, RB-tree, AA-tree，均可以实现平衡⼆叉树。

严格的平衡二叉树（AVL）

AVL-tree 是要求任何节点的左右⼦树⾼度相差最多为 1 的平衡⼆叉树。 当插⼊新的节点破坏平衡性的时候，从下往上找到第⼀个不平衡点，需要进⾏单旋转，或者双旋转进⾏调整。

红黑树（RB-Tree）

要求： 性质1：每个节点要么是⿊⾊，要么是红⾊。 性质2：根节点是⿊⾊。 性质3：每个叶⼦节点（NIL）是⿊⾊。 性质4：每个红⾊结点的两个⼦结点⼀定都是⿊⾊。 性质5：任意⼀结点到每个叶⼦结点的路径都包含数目相同的⿊结点。

memcpy

• 完成内存的拷贝
  • 如果内存有重叠（对小端），则从高位到低位复制
  • 如果内存无重叠，则从低位到高位传递

  void* my_memcpy(void *dst, void *src, size_t count){
    if(dst == nullptr || src == nullptr){
      return nullptr;
    }
    char* temp_dst = (char*) dst;
    char* temp_src = (char*) src;
    if(temp_dst > temp_src && temp_dst < temp_src+ count){
      // 内存重叠
      temp_dst = temp_dst + count -1;
      temp_src = temp_src + count -1;
      while(count--){
        *temp_dst-- = *temp_src--;
      }
    }
    else {
      while(count--){
        *temp_dst++ = *temp_src++;
      }
    }
    return (void * )dst;
  }

工厂模式

目的

• 程序更规范有条理
  • 当我们创建实例对象时,如果不仅仅做赋值这样简单的事情,而是有一大段逻辑,那这个时候我们要将所有的初始化逻辑都写在构造函数中吗? 显然，这样使得代码很难看
• 降低耦合度，提高可阅读性
  • 将长的代码进行”切割”，再将每一个小逻辑都”封装”起来，这样可以降低耦合度,修改的时候也可以直奔错误段落

实现方式

区别

• 懒汉式指系统运行中，实例并不存在，只有当需要使用该实例时，才会去创建并使用实例
• 饿汉式指系统一运行，就初始化创建实例，当需要时，直接调用即可

c++模板底层

• 编译器并不是把函数模板处理成能够处理任意类的函数；编译器从函数模板通过具体类型产⽣不同的函数
• 编译器会对函数模板进⾏两次编译：在声明的地⽅对模板代码本身进⾏编译，在 调⽤的地⽅对参数替换后的代码进⾏编译。
• 这是因为函数模板要被实例化后才能成为真正的函数，在使⽤函数模板的源⽂件中包含函数模 板的头⽂件，如果该头⽂件中只有声明，没有定义，那编译器⽆法实例化该模板，最终导致链 接错误。

模板元编程

• 函数名相同，参数类型不同要重新写函数。模板出现就是提高了程序的复用性，提高效率
• 当刚上手的时候肯定是根据具体的数据类型来组织代码。随着越来越熟，用一种广泛的表达去取代具体数据类型，在c++中就叫做模板编程。

类型

• 函数模板
• 类模板

格式 template <template T>或template <class T>

底层实现

• 编译器将函数模板通过具体类型产生不同的函数
  • 对模板代码声明处进行编译
  • 在调用地方对替换后代码编译

模板和继承

• 使用目的
  • 模板用于生成一组类或函数，这些类和函数的实现是一样的
  • 继承是事物之间的联系，从父类到子类是从普遍到特殊，从共性到特性
• 多态的不同
  • 模板是编译时多态
  • 继承是运行时多态
• 复制内容
  • 模板是对代码的复制，编译完成后，会生成对应的函数或类
  • 继承是对数据的复制，复制虚表、数据

函数模板

运行时的堆与栈上的对象

堆对象与栈对象的区别

• 对象生命周期区别
  • 栈对象生命周期只能在作用域内，堆生命周期可以在动态地分配和释放内存的过程中随时变化。
• 对象的性能
  • 栈性能更快，栈有专门的寄存器，压栈出栈指令效率更高，堆是由OS动态调度，堆内存可能被OS调度在非物理内存中，或是申请内存不连续，造成碎片过多等问题；
  • 堆都是动态分配的，栈是编译器完成的。栈的分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现
• 某些情况如果是在栈上创建，但数据仍然在堆上，如std::vector v，对象v创建在栈，但其数据在堆上，只是指针指向堆，堆上的数据由std负责维护

只在堆上生成对象的类

class A {
    // A a; 创建对象是利用编译器确定，需要public的构造和析构，因此使用private或protected构造和析构可以取消静态创建，但针对需要继承的类型有进一步限制为protected
protected:
    A() {} 
    ~A() {}
public:
    static A* create() {
        return new A();
    }
    // 在析构中因为无法调用，使用单独的delete()函数
    void destroy() {
        delete this;
    }

};

int main() {
    A* object = A::create();

    object->destroy();
    object = nullptr;

    return 0;
}

只在栈上生成对象的类

class A {
private:
    void operator delete(void* ptr) {}
    void* operator new (size_t t) {}
public:
    A() {}
    ~A() {}
};

int main() {
    A a;
    return 0;
}

栈上分配内存

alloca

• 不需要手动释放，超出作用域自动释放

问题

• 会爆栈

野指针和悬空指针

• 野指针：没有初始化的指针
• 悬空指针：指向内存已经被释放了

内存泄漏

申请了一块内存，使用完毕后没有释放。程序运⾏时间越⻓，占⽤内存越多，最终⽤尽全部内存，整个系统崩溃。

由程序申请的⼀块内存，且没有任何⼀个指针指向它，那么这块内存就泄漏了。

原因

• malloc/new和delete/free没有匹配
• new[] 和 delete[]没有匹配
• 没有将父类的析构函数定义为虚函数

监测手段

• 把new封装在构造函数中，将delete封装到析构函数中
• 智能指针
• valgrind ，这个可以打印出发生内存泄露的部分代码
• linux使用swap命令观察还有多少可以用的交换空间，两分钟内执行三四次，肉眼看看交换区是不是变小了
• 使用/usr/bin/stat工具如netstat、vmstat等。如果发现有内存被分配且没有释放，有可能进程出现了内存泄漏。

智能指针种类

• unique_ptr（独占式）、shared_ptr（共享式、强引用）、weak_ptr（弱引用，只提供访问，但不管理）

 T* get();  // 获得原生指针
 T& operator*();  // 重写*
 T* operator->(); // 重写->
 T& operator=(const T& val);  // 重写=
 T* release();  // 释放智能指针，返回原生指针
 void reset (T* ptr = nullptr); // 释放原先的对象，将智能指针管理新指针的对象

智能指针 shared_ptr

• 是RAII类模型，用来动态分配内存
  • 将指针用类封装，然后实例化为对象，当对象过期，让析构函数删除指向的内存

shared_ptr

• 多个指针可以指向一个相同的对象，当最后一个shared_ptr离开作用域的时候才会释放掉内存。

实现原理

• 在shared_ptr内部有一个共享引用计数器来自动管理，计数器实际上就是指向该资源指针的个数
• 每当复制一个 shared_ptr引用计数会 + 1
  • shared_ptr<A> sp2(sp1);
  • shared_ptr <A> sp3; sp3 = sp2;
• 当一个 shared_ptr 离开作用域时，引用计数会 - 1
  • sp3.reset(new A(3));
• 当引用计数为 0 的时候，则delete 内存。
• 这样相比auto来说就好很多，当计数器为0的时候指针才会彻底释放掉这个资源。
• 注意不能将两个shared_ptr托管同一个指针
  • shared_ptr <A> sp1(p), sp2(p); //error!!!

线程安全

• 同一个shared_ptr，多个线程读是安全的
• 同一个shared_ptr，多个线程写是不安全的
  • 线程在指向修改到计数器变化两个过程中并非原子操作，中间可能被打断
  • 方法：加锁
• 不同的shared_ptr，多个线程写是安全的
• shared_ptr管理数据的安全性不明

线程不安全例子

  shared_ptr<foo> o1;
  shared_ptr<foo> p2(new foo);
  shared_ptr<foo> p3(new foo);
  p1 = p2;
  p2 = p3; // 可能出现p1悬空指针

方法

• 构造函数

    std::shared_ptr<int> p1;  // p1.use_count() = 0
    std::shared_ptr<int> p2(nullptr);  // p1.use_count() = 0
    std::shared_ptr<int> p3(new int);
    std::shared_ptr<int> p4(new int, std::default_delete<int>());
  

• reset
  • reset()会释放并摧毁原生指针
  • reset(param)会管理这个新指针
• make_shared()
  • 缺点
    • 构造函数为protected或private时，无法使用make_shared
    • 对象的内存可能无法及时回收
• swap方法
  • 交换两个shared_ptr所拥有的对象，即指向的对象交换
• shared_from_this
  • 如果当前对象需要交给某个对象来管理，则当前对象生命周期需要晚于某个对象，为实现上述目标，类继承std::enable_sharded_from_this<T>

    class Widget: public std::enable_shared_from_this<Widget>{
      public:
        void do_something(A& a){
          a.widget = shared_from_this();
        }
    }

shared_ptr和make_shared区别

性能

• shared_ptr初始化需要分配两次内存
• make_shared初始化只需要分配一次内存

内存泄漏问题

• shared_ptr可能会产生异常问题，而maked_shared可以避免问题

    processWidget(std::shared_ptr<Widget>(new Widget), computePriority());
  

• 上述代码可能会有资源泄露，如果先执行new Widget、执行computePriority()、执行std::shared_ptr的构造，因此如果computeProirity()中如果产生异常，则Widget会泄漏

  processWidget(std::make_shared<Widget>(),computePriority());

• 不存在内存泄漏问题

智能指针 weak_ptr

目的

• 解决shared_ptr指针循环引用出现内存泄漏问题

方法

• ptr.expired()判断是否被释放
• ptr.use_count()返回原生指针引用次数
• std::shared_ptr<CTxxx>ptr2 = ptr.lock()返回为空的shared_ptr或转化为强指针shared_ptr
• reset()将本身置为空

应用场景

• 观察者功能

  class CTxxx{
  public:
    CTxxx(){printf("CTxxx cst\n");}
    ~CTxxx(){printf("CTxxx dst\n");}

  };
  int main(){
    std::shared_ptr<CTxxx> sp_ct(new CTxxx);
    std::weak_ptr<CTxxx> wk_ct = sp_ct;
    std::weak_ptr<CTxxx> wka1;
    {
      std::cout << "wk_ct.expired()=" << wk_ct.expired() << std::endl;
      std::shared_ptr<CTxxx> tmpP = wk_ct.lock();
      if (tmpP) {
        std::cout << "tmpP usecount=" << tmpP.use_count() << std::endl;
      } else {
        std::cout << "tmpP invalid" << std::endl;
      }
      std::shared_ptr<CTxxx> a1(new CTxxx);
      wka1 = (a1);
    }
    std::cout << "wka1.expired()=" << wka1.expired() << std::endl;
      std::cout << "wka1.lock()=" << wka1.lock() << std::endl;
  
      std::shared_ptr<CTxxx> cpySp = wka1.lock();
      if (cpySp) std::cout << "cpySp is ok" << std::endl;
      else std::cout << "cpySp is destroyed" << std::endl;
      return 1;
  }

• 解决循环引用

• A、B、C三个对象的数据结构中，A和C共享B的所有权，因此各持有一个指向B的std::shared_ptr
• 假设有一个指针从B指回A（即上图中的红色箭头），则该指针的类型应为weak_ptr，而不能是裸指针或shared_ptr
  • 裸指针，当A被析构时，由于C仍指向B，所以B会被保留。但B中保存着指向A的空悬指针（野指针），而B却检测不出来，但解引用该指针时会产生未定义行为
  • shared_ptr时。由于A和B相互保存着指向对方的shared_ptr，此时会形成循环引用，从而阻止了A和B的析构。
  • weak_ptr，这可以避免循环引用。假设A被析构，那么B的回指指针会空悬，但B可以检测到这一点，同时由于该指针是weak_ptr，不会影响A的强引用计数，因此当shared_ptr不再指向A时，不会阻止A的析构

  #include <iostream>
  #include <memory>
  using namespace std;
  class A {
  public:
    std::weak_ptr<B> bptr; // 修改为weak_ptr
    ~A() {
      cout << "A is deleted" << endl;
    }
  };
  class B {
  public:
    std::shared_ptr<A> aptr;
    ~B() {
      cout << "B is deleted" << endl;
    }
  };
  int main()
  {
    {//设定一个作用域
      std::shared_ptr<A> ap(new A);
      std::shared_ptr<B> bp(new B);
      ap->bptr = bp;
      bp->aptr = ap;
    }
    cout<< "main leave" << endl; 
    return 0;
  }

• 缓存对象
  • 对工厂函数loadWidget（基于唯一ID来创建一些指向只读对象的智能指针）
    • 只读对象需要频繁使用
    • 需要从文件或数据库中加载
    • 可以考虑将对象缓存。当不再使用时，则将该对象删除。
  • 由于除了工厂函数还有缓存管理，unique_ptr不合适
  • 当用户用完工厂函数的对象后，对象会析构，缓存条目悬空。
    • 考虑将工厂函数的返回值设定为shared_ptr类型
    • 缓存类型为weak_ptr类型
• 线程安全的对象回调与析构 —— 弱回调
  • 如果对象还在，则调用其成员函数，否则忽略
  • 线程A和线程B访问一个共享的对象，如果线程A正在析构这个对象的时候，线程B又要调用该共享对象的成员方法，此时可能线程A已经把对象析构完了，线程B再去访问该对象，就会发生不可预期的错误。
• 做法：在开启新线程时，传入共享对象的弱指针

  class Test
  {
  public:
    // 构造Test对象，_ptr指向一块int堆内存，初始值是20
    Test() :_ptr(new int(20)) 
    {
      cout << "Test()" << endl;
    }
    // 析构Test对象，释放_ptr指向的堆内存
    ~Test()
    {
      delete _ptr;
      _ptr = nullptr;
      cout << "~Test()" << endl;
    }
    // 该show会在另外一个线程中被执行
    void show()
    {
      cout << *_ptr << endl;
    }
  private:
    int *volatile _ptr;
  };
  void threadProc(weak_ptr<Test> pw) // 通过弱智能指针观察强智能指针
  {
    // 睡眠两秒
    std::this_thread::sleep_for(std::chrono::seconds(2));
    /* 
    如果想访问对象的方法，先通过pw的lock方法进行提升操作，把weak_ptr提升
    为shared_ptr强智能指针，提升过程中，是通过检测它所观察的强智能指针保存
    的Test对象的引用计数，来判定Test对象是否存活，ps如果为nullptr，说明Test对象
    已经析构，不能再访问；如果ps!=nullptr，则可以正常访问Test对象的方法。
    */
    shared_ptr<Test> ps = pw.lock();
    if (ps != nullptr)
    {
      ps->show();
    }
  }
  int main()
  {
    // 在堆上定义共享对象
    shared_ptr<Test> p(new Test);
    // 使用C++11的线程，开启一个新线程，并传入共享对象的弱智能指针
    std::thread t1(threadProc, weak_ptr<Test>(p));
    // 在main线程中析构Test共享对象
    // 等待子线程运行结束
    t1.join();

    return 0;
  }

• 当将t1.join()换为t1.detach()时候，让main主线程结束，p智能指针析构，Test对象析构，此时show()不会被调用
  • threadProc方法中，pw提升到ps时，lock方法判定Test对象已经析构，提升失败

unique_ptr

拥有对持有对象的唯一所有权，两个unique_ptr不能同时指向同一个对象

特点

• 不能复制
• 只能通过转移语义将所有权转移到另外一个

  std::unique_ptr<A> a1(new A());
  std::unique_ptr<A> a2 = a1;//编译报错，不允许复制
  std::unique_ptr<A> a3 = std::move(a1);//可以转移所有权，所有权转义后a1不再拥有任何指针

方法

• get() 获取其保存的原生指针
• bool() 判断是否拥有指针
• release() 释放所管理指针的所有权，返回原生指针。但并不销毁原生指针。
• reset()释放并销毁原生指针。如果参数为一个新指针，将管理这个新指针

  std::unique_ptr<A> a1(new A());
  A *origin_a = a1.get();//尽量不要暴露原生指针
  std::unique_ptr<A> a2(a1.release());//常见用法，转义拥有权
  a2.reset(new A());//释放并销毁原有对象，持有一个新对象
  a2.reset();//释放并销毁原有对象，等同于下面的写法
  a2 = nullptr;//释放并销毁原有对象

内存泄漏问题

原因

• 在局部作用域消失时，data区仍然保存其内存空间
• 执行路径不明
  • 对于局部静态变量，构造和析构都取决于程序的执行顺序。程序的实际执行路径不可预知的
• 关系不明
  • 局部静态变量分布在程序代码各处，彼此直接没有明显的关联，很容易让开发者忽略它们之间的这种关系

建议

• 减少使用局部静态变量

arr & arr[0]、&arr区别

print

• 都是首元素地址

+1 print

• arr[0] + 1和 arr + 1在数组内移动
• &arr + 1按照数组单位移动

char、char a[]、char* a、char* a[]、char** a

一维数组名和二维数组名的区别

相同点

• 存储都是一维的
• 一维数组名与二维数组名都指向数组的指针

不同点

• 二维数组名不能赋给二级指针
  • 二级指针：要求指向的是指针，而二维数组确定一维后指向数组
    • 想要获得 a[i] 中第 x 个元素，可以直接使用 *(a+x)
    • 想要获得 b[i][j] 中第 x 行第 y 个元素，则需用 *(*(b+x)+y)
• 一维数组+1跳过对应值，二维数组跳过行或列

引用与指针

  int i = 5;
  // 引用
  int &a = i;
  a = 8;

引用的本质

• & = T * const a
• 本质是常量指针

引用与常量指针相同点

• 都占用4/8字节
• 都必须初始化

引用与常量指针不同点

是否可寻址

• 指针常量允许寻址 -> &p返回指针常量的地址 *p返回被指向对象
• 引用不允许寻址 -> &r返回指向对象的地址

是否可空

• 指针常量 -> 可NULL
• 引用 -> 不允许NULL

是否支持数组

• 指针常量 -> 支持
• 引用 -> 不支持

参数传递

• 指针常量 -> 值传递。编译的时候：会将指针和变量存放符号表（变量名和对应地址）地址为指针变量的地址值。参数传递时候：会在开辟空间的时候形成实参的副本，因此对此参数的操作最终只是对局部变量的操作，并不会影响实参指针对应的值。如果想要使用，需要使用指向指针的指针或指针引用
• 引用 ->引用传递。编译的时候：存放的地址是引用对象的地址。参数传递时候：是主调函数放进来的实参变量值，被调函数任何操作都会影响主调函数的实参变量

sizeof()的不同

• 指针常量 -> 指针的大小
• 引用 -> 得到指向对象的大小

fork、wait和exec函数

在早期unix系统中，当调⽤ fork 时，内核会把所有的内部数据结构复制⼀份，复制进程的⻚表项，然后把⽗进程的地址空间中的内容逐⻚的复制到⼦进程的地址空间中。但从内核⻆度来说，逐⻚的复制⽅式是⼗分耗时的。现代的 Unix 系统采取了更多的优化，例如 Linux，采⽤了写时复制的⽅法，⽽不是对⽗进程空间进程整体复制。

• ⽗进程产⽣⼦进程使⽤ fork 拷⻉出来⼀个⽗进程的副本，此时只拷⻉了⽗进程的⻚表，两个进程都读同⼀块内存。
• 当有进程写的时候使⽤写实拷⻉机制分配内存，exec 函数可以加载⼀个 elf ⽂件去替换⽗进程，从此⽗进程和⼦进程就可以运⾏不同的程序了。
• fork 从⽗进程返回⼦进程的 pid，从⼦进程返回 0，调⽤了 wait 的⽗进程将会发⽣阻塞，直到有⼦进程状态改变，执⾏成功返回 0，错误返回 -1。
• exec 执⾏成功则⼦进程从新的程序开始运⾏，⽆返回值，执⾏失败返回 -1。

int main(int argc, char *argv[])
{
    printf("hello world (pid:%d)\n", (int) getpid());
    
    // fork以后子进程pid=0，父进程pid=子进程
    int rc = fork();
    if (rc < 0) {
        // fork failed; exit
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if (rc == 0) {
        // child (new process)
        printf("hello, I am child (pid:%d)\n", (int) getpid());

        // 子进程程序执行为execvp的命令
        char *myargs[3];
        myargs[0] = strdup("wc");   // program: "wc" (word count)
        myargs[1] = strdup("exec.c"); // argument: file to count
        myargs[2] = NULL;           // marks end of array
        execvp(myargs[0], myargs);  // runs word count

        // 子进程已经执行了wc程序，因此不会返回此处执行
        printf("this shouldn't print out");
    } else {
        // 父进程等待子进程结束，如果为多个的话等待其中一个结束
        // parent goes down this path (original process)
        int wc = wait(NULL);
        printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
	       rc, wc, (int) getpid());
    }
    return 0;
}

回调函数

当发⽣某种事件时，系统或其他函数将会⾃动调⽤你定义的⼀段函数，相当于中断处理函数，当系统在符合条件的时候自动调用，其通过函数指针调用的函数，如果将某函数的指针作为参数给另外一个函数，当另外的这个函数在满足一定条件后通过函数指针完成函数的调用，那么称这个被调用的函数为回调函数

步骤：声明，定义，设置触发条件

右值引用

Person get(){
  Person p;
  return p;
}
Person p = get();

上述获得并初始化过程涉及3次构造、2次析构，因此为了方便传递，引入右值引用，类似move语义，从右值直接拿数据初始化并修改左值，不需要重新构造再析构

class Person{
public:
 Person(Person&& rhs){...}
 ...
};

初始化列表 std::initializer_list

class A{
public:
  A(std::initializer_list<int> list);
};
A a = {1,2,3};
// 只是初始化的时候长度可以变化，只能静态构造
A b = {1,2};

范围for循环

构造函数委托

可以在构造函数中调用同一个类的其他构造函数

元组

typedef std::tuple< int , double, string > tuple_1 t1;
typedef std::tuple< char, short , const char * > tuple_2 t2 ('X', 2,
"Hola!");
t1 = t2 ; // 隐式类型转换