消化C++

做题的发现

1. unordered_map比map要快一点
2. map比vector费空间很多
3. 函数调用时候，地址传递，比值传递，快。
4. 先开辟指定长度数组vector res(k+1)，再对res[i]赋值，这种方式，比把值给push-back进来，速度要快些。

知识点

1. 如果使用循环，程序的性能可能更高；如果使用递归，可读性更好。如何选择要看什么更重要。
   • 所有递归都能改写成循环吗？可以。有些递归只需要一个循环就可以替代，而有些递归的改写需要循环+栈。（比如二叉树dfs）
   • 所有循环都能改写成递归吗？可以但没必要。 来自。（递归：空间复杂度就是O(n)。）
2. 对于尾递归，通常地，编译器已经优化成循环。
   • 尾递归：递归调用只有一次，是递归函数中的最后一条指令。
3. 浅复制与深复制
   • 浅复制会将对象所有成员的值复制到另一个对象里。
   • 深复制在此基础上，还会进一步复制所有指针对象。
   • 多数情况下，使用浅复制是为了传递一块复杂结构的信息，但又不想真的复制一份数据。
   • 实际开发中，很少用浅复制。
   • 大部分情况下，都会使用深复制。
4. Java处理输入、输出，时间比C++长很多。
5. 随机数有关 -srand((unsigned)time(NULL))要放在main里，不是循环/局部函数里
6. 既然有了malloc/free，为何还要new/delete？
   • malloc/free基于过程，是C库函数；new/delete基于对象，是C++运算符
   • 对于内部数据类型对象，没有构造/析构过程，此时，malloc/free和new/delete是等价的。
   • 对于外部对象（自己定义的class/struct）👇
     • 申请内存(还有初始化)涉及构造函数，释放内存涉及析构函数，
     • 对于动态对象的内存管理，
       • 此时，如果用malloc/free来完成，需要额外写构造/析构。(由于malloc/free是库函数，不是运算符，不在编译器控制权限之内，不能把执行构造函数和析构函数任务编译进来)
       • new/delete则很方便。(new和delete内部实现的核心还是malloc和free，在调用malloc/free同时，还调用了构造和析构函数)

C++知识点

1. vector没有push_front，只有push_back。
2. 排序

   condition1 = is_sorted(nums.begin(),nums.end()); //是否是升序 sort(A.begin()+index, A.end()); //递增 sort(vec.rbegin(), vec.rend()); //递减 reverse(A.begin(),A.end());

3. 插入 nums.insert(nums.begin()+i,value); // A.begin()是在前面插入，A.end()是在后面插入
4. 删除： string.erase()三种用法： （1）erase(index, n); 删除从index开始的多个(n)字符（i从0开始） （2）erase(iterator);删除iterator处的1个字符 （3）erase(iterator1, iterator2);删除从iterator1到iterator2之间的字符 如：

   str.erase(i, 1); A.erase( A.begin()+i ); //A是vector或string str.erase (str.begin()+5, str.end()-7);

5. 删除尾部元素

   even.pop_back();

6. 访问头尾元素 访问第一个元素： vector.front(); 访问最后一个元素： vector.back();

7. remove remove的作用是将值为val的元素都移动到末尾，返回新的迭代器end()（非val部分的end） 但原vector的end并没有发生改变，size也就没有变化.

   两者结合应用：删除vector中所有值为x的元素 vec.erase(remove(vec.begin(),vec.end(),x),vec.end()); 具体可参见leetcode 26

8. map、hash_map

   STL的map底层是用红黑树实现的，查找时间复杂度是log(n)；

• hash_map底层是用hash表存储的
  • 查询时间复杂度是O(1)，空间复杂度是O(n)。
  • 数据量太大的时候，空间消耗大。

C++中的map、unordered_map，相当于java中的TreeMap、HashMap。

map判断一个key是否出现： count统计的是key出现的次数，只能为0/1；而find基于迭代器实现，以mp.end()判断是否找到要求的key。 if(m.count(key)!=0)
if(m.find(key)!=m.end())

1. substr: string a = s.substr(0,5); //获得字符串s中从第0位开始的长度为5的字串
2. auto关键字

   #include<iostream>
   using namespace std;
   int main()
   {
    string s("hello world");
    for(auto c:s)
      c='t';
    cout<<s<<endl;//结果为hello world
    for(auto &c:s)
      c='t';
    cout<<s<<endl; //结果为ttttttttttt
   

3. pair用法
   • pair <string,double> A (“tomatoes”,3.25);
   • pair <int, int>A = make_pair(1, 2); pair <string,double> C = make_pair (“shoes”,20.0);
   • pair <string,int> B; B.first =”aa”; B.second = 99;
4. 局部、全局变量，没有初始化的区别
   • 局部变量，都是存在栈中的。而栈往往是会快速重复的大量使用，如果每次使用都初始化，开销会比较大。不如，直接让程序员来手动初始化。
   • 相反，全局变量，存储的空间不会快速大量重复的使用，存活时间很长，所以初始化一下，开销并不会很大。
5. virtual关键字
   • 多态是什么：虚函数/重写（运行时）、重载（编译时，同一作用域）
   • 虚函数
   • 为什么有虚函数
   • 作用
     • 有利于类多态
     • 基类指针（引用）可以访问基类或派生类中的同名函数。 - 虚基类：避免”菱形继承”造成的二义性。
   • 在构造派生类时，最终派生类中含有多个同一个基类的情况，就会产生二义性的问题（不知道该调用哪个基类的成员变量和函数），为解决此问题，需要使用虚基类，即只对此基类生成一块内存区域，这样最终派生类中就只含有一个基类。

     "菱形继承"（多继承的两个或以上父级 继承同一个祖级）
       A 
      /     \ 
     B       C 
      \     / 
       D
     

         - `纯虚函数`
     

   • 在基类中声明（没有实现），在派生类中实现。（只能被继承）
   • 纯虚函数需要在类声明的后面加上关键词“=0”。
   • 若一个类的成员函数被声明为纯虚函数，则意味着该类是抽象基类。

1. 堆/优先队列
   • 堆不是STL基本组件，本质上是用vector实现的完全二叉树。分为最小/大堆。 优先队列，即最大堆。在实现上，调用的就是堆有关的函数。也是有最小/大堆。 堆/优先队列，默认都是less最大堆。
   • C++ reference make_heap,pop_heap(),push_heap(),sort_heap() priority_queue
   • blog [priority_queue还是方便些。因为pop_heap(),push_heap()必须与make_heap()的compare保持一致，走哪带到哪] (https://blog.csdn.net/qq_29630271/article/details/66478256)
   • 做题遇见的 优先队列：用greater表示最小堆。其实就是compare 优先队列：还可以自己写bool类型的compare，适合多关键字
2. 堆操作： 建立堆：make_heap 堆插入、删除 push_heap,pop_heap 访问头尾元素：vec.front(),vec.back() 堆排序(原地排序)：sort_heap()。如果不用这个，时间复杂度也是NlogN，但是空间上多了N。
3. 优先队列 操作： 定义最小堆 priority_queue<int, vector, greater > minheap; 定义最大堆(默认less) priority_queue max_heap(nums.begin(),nums.end()); // O(N) 插入 minheap.push(k); // k是一个int //O(logN) 删除 minheap.pop(); // 删除最值(堆顶元素) //O(logN) 访问头元素：minheap.top(); //queue里面访问是front，但是这里不行。

• 代替greater/less的方法：

  struct compare {
  bool operator()(const pair<int,int>&a, const pair<int,int>&b) {
      return a.second < b.second;
    }
  };
  priority_queue<pair<int,int>, vector<pair<int,int>>, compare> Q(p.begin(),p.end());
  

1. set集合：去重、插入元素时还可以自动排序

2. 整数 转 字符串
   • to_string() 整数（不论正负，几位数）👉字符串
3. 字符串 转 整数
   • int n = atoi(p.c_str());
4. multiset
   • 默认：less：排序是 小👉大
5. vector和数组

• Previous
  Leetcode-Relative Sort Array
• Next
  python常用操作