一、基本语法

1.static关键字的作用

  • 全局静态变量、局部静态变量
    • 在全局/局部变量前加上关键字static，全局变量就定义成一个全局/局部静态变量。
    • 内存中的位置：静态存储区，在整个程序运行期间一直存在。
    • 初始化：未经初始化的全局/局部静态变量会被自动初始化为0(自动对象的值是任意的，除非它被显式初始化)
    • 作用域：
      • 全局静态变量：在声明他的文件之外是不可见的(从定义之处开始，到文件结尾)
    • 局部静态变量：仍然是局部作用域，当定义它的函数或者语句块结束的时候，作用域结束。但是当局部静态变量离开作用域后，并没有销毁，而是仍然驻留在内存当中，只不过我们不能再对它进行访问，直到该函数再次被调用，并且值不变。
  • 静态函数
    • 在函数返回类型前加static，函数就定义为静态函数。函数的定义和声明在默认情况下都是extern的，但静态函数只是在声明他的文件当中可见，不能被其他文件所用。
    • 函数的实现使用static修饰，那么这个函数只可在本cpp内使用，不会同其他cpp中的同名函数引起冲突warning：不要再头文件中声明static的全局函数，不要在cpp内声明非static的全局函数，如果你要在多个cpp中复用该函数，就把它的声明提 到头文件里去，否则cpp内部声明需加上static修饰；
  • 类的静态成员变量
    • 在类中，静态成员可以实现多个对象之间的数据共享，并且使用静态数据成员还不会破坏隐藏的原则，即保证了安全性。因此，静态成员是类的所有对象中共享的成员，而不是某个对象的成员。对多个对象来说，静态数据成员只存储一处，供所有对象共用。
    • 类的静态成员变量的初始化不能在声明时进行初始化，只能在类外实现中进行初始化。

  • 类的静态函数

    • 静态成员函数和静态成员变量一样，它们都属于类的静态成员，它们都不是对象成员。因此，对静态成员的引用不需要用对象名。
    • 在静态成员函数的实现中不能直接引用类中说明的非静态成员，可以引用类中说明的静态成员（这点非常重要）。如果静态成员函数中要引用非静态成员时，可通过对象来引用。从中可看出，调用静态成员函数使用如下格式：<类名>::<静态成员函数名>(<参数表>)
    • 类的静态成员变量的初始化不能在声明时进行初始化，只能在类外实现中进行初始化。

      2.C++和C的区别

  • 设计思想上

    • C++是面向对象的语言，而C是面向过程的结构化编程语言

  • 语法上

    • C++具有继承、封装、多态三种特性
    • C++相比C，增加许多安全带功能，比如强制类型转换
    • C++支持范式编程，比如模板编程、函数模板等

      3.C++中四种cast转换

  • static_cast, dynamic_cast, const_cast, reinterpret_cast | static_cast | 用于将const变量转为非const | | —- | —- | | dynamic_cast | 用于各种隐式转换，比如非const转const，void*转指针等, static_cast能用于多态向上转化，但不进行安全检查。 | | const_cast | 用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。 只能转指针或引用。向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。 要深入了解内部转换的原理。向上转换：指的是子类向基类的转换向下转换：指的是基类向子类的转换它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否 相同来判断是否能够进行向下转换。 | | reinterpret_cast | 几乎什么都可以转，比如将int转指针。没有任何类型检查和格式转换，仅仅是二进制的拷贝，可能会出问题，尽量少用。 |

  • 为什么不使用 C 的强制转换？

    • C 的强制转换表面上看起来功能强大什么都能转，但是转化不够明确，不能进行错误检查，容易出错。

      4.C/C++ 中指针和引用的区别？

  • 定义：

    • 引用：引用就是某一变量的一个别名，对引用的操作与对变量直接操作完全一样。引用的声明方法：类型标识符 &引用名=目标变量名。引用引入了对象的一个同义词。定义引用的表示方法与定义指针相似，只是用&代替了*。
    • 指针：指针利用地址，它的值直接指向存在电脑存储器中另一个地方的值。由于通过地址能找到所需的变量单元，可以说，地址指向该变量单元。因此，将地址形象化的称为“指针”。意思是通过它能找到以它为地址的内存单元。

  • 区别：

    • 1.指针有自己的一块空间，而引用只是一个别名；
    • 2.使用sizeof看一个指针的大小是4，而引用则是被引用对象的大小；
    • 3.指针可以被初始化为NULL也可指向其它对象；引用在定义时必须进行初始化，初始化后不可以再进行更改。
    • 4.作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引用的修改都会改变引用所指向的对象；
    • 5.可以有const指针，但是没有const引用；
    • 6.指针可以有多级指针(**p)，而引用没有(没有引用的引用，指向引用的指针，引用数组)
    • 7.指针和引用使用++运算符的意义不一样；
    • 8.如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄露。

      6.野指针是什么？

  • 野指针就是指向一个已删除的对象或者未申请访问受限内存区域的指针

    7.C++中的智能指针

  • 智能指针主要用于管理在堆上分配的内存，它将普通的指针封装为一个栈对象。当栈对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。

  • C++11中最常用的智能指针类型为shared_ptr,它采用引用计数的方法，记录当前内存资源被多少个智能指针引用。该引用计数的内存在堆上分配。当新增一个时引用计数加1，当过期时引用计数减1。只有引用计数为0时，智能指针才会自动释放引用的内存资源。

  • 对shared_ptr进行初始化时不能将一个普通指针直接赋值给智能指针，因为一个是指针，一个是类。可以通过make_shared函数或者通过构造函数传入普通指针。并可以通过get函数获得普通指针。

    8.为什么析构函数必须是虚函数？为什么C++默认的析构函数不是虚函数

  • 将可能会被继承的父类的析构函数设置为虚函数，可以保证当我们new一个子类，然后使用基类指针指向该子类对象，释放基类指针时可以释放掉子类的空间，防止内存泄漏。

  • C++默认的析构函数不是虚函数是因为虚函数需要额外的虚函数表和虚表指针，占用额外的内存。而对于不会被继承的类来说，其析构函数如果是虚函数，就会浪费内存。因此C++默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。

    9.函数指针

  • 定义

    • 函数指针是指向函数的指针变量。
    • 函数指针本身首先是一个指针变量，该指针变量指向一个具体的函数。这正如用指针变量可指向整型变量、字符型、数组一样，这里是指向函数。
    • C在编译时，每一个函数都有一个入口地址，该入口地址就是函数指针所指向的地址。有了指向函数的指针变量后，可用该指针变量调用函数，就如同用指针变量可引用其他类型变量一样，在这些概念上是大体一致的。
  • 用途：
    • 调用函数和做函数的参数，比如回调函数。
  • 示例：
    1. char * fun(char* p) {…};  // 函数fun
    2. char * (*pf)(char* p);    // 函数指针pf
    3. pf = fun;                 // 函数指针pf指向函数fun
    4. pf(p);                    // 通过函数指针pf调用函数fun

    10.数组和指针的区别

    指针和数组的主要区别如下：
指针 数组
保存数据的地址 保存数据
间接访问数据，首先获得指针的内容，然后将其作为地址，从该地址中提取数据 直接访问数据
通常用于动态的数据结构 通常用于固定数目且数据类型相同的元素
通过Malloc分配内存，free释放内存 隐式的分配和删除
通常指向匿名数据，操作匿名函数 自身即为数据名

11.C++中析构函数的作用

  • 析构函数与构造函数对应，当对象结束其生命周期，如对象所在的函数已调用完毕时，系统会自动执行析构函数。
  • 析构函数名也应与类名相同，只是在函数名前面加一个位取反符~，例如~student( )，以区别于构造函数。它不能带任何参数，也没有返回值（包括void类型）。只能有一个析构函数，不能重载。
  • 如果用户没有编写析构函数，编译系统会自动生成一个缺省的析构函数（即使自定义了析构函数，编译器也总是会为我们合成一个析构函数，并且如果自定义了析构函数，编译器在执行时会先调用自定义的析构函数再调用合成的析构函数），它也不进行任何操作。所以许多简单的类中没有用显式的析构函数。
  • 如果一个类中有指针，且在使用的过程中动态的申请了内存，那么最好显示构造析构函数在销毁类之前，释放掉申请的内存空间，避免内存泄漏。

  • 类析构顺序：1）派生类本身的析构函数；2）对象成员析构函数；3）基类析构函数。

    12.静态函数和虚函数的区别

  • 静态函数在编译的时候就已经确定运行时机，虚函数在运行的时候动态绑定。虚函数因为用了虚函数表机制，调用的时候会增加一次内存开销

    13.重载和覆盖

  • 重载：两个函数名相同，但是参数列表不同（个数，类型），返回值类型没有要求，在同一作用域中

  • 重写：子类继承了父类，父类中的函数是虚函数，在子类中重新定义了这个虚函数，这种情况是重写

    14.strcpy和strlen

  • strcpy是字符串拷贝函数，原型：char strcpy(char dest, const char *src);

  • 从src逐字节拷贝到dest，直到遇到’\0’结束，因为没有指定长度，可能会导致拷贝越界，造成缓冲区溢出漏洞,安全版本是strncpy函数。

  • strlen函数是计算字符串长度的函数，返回从开始到’\0’之间的字符个数

    15.你理解的虚函数和多态

  • 多态的实现主要分为静态多态和动态多态，静态多态主要是重载，在编译的时候就已经确定；动态多态是用虚函数机制实现的，在运行期间动态绑定。举个例子：一个父类类型的指针指向一个子类对象时候，使用父类的指针去调用子类中重写了的父类中的虚函数的时候，会调用子类重写过后的函数，在父类中声明为加了virtual关键字的函数，在子类中重写时候不需要加virtual也是虚函数。

  • 虚函数的实现：在有虚函数的类中，类的最开始部分是一个虚函数表的指针，这个指针指向一个虚函数表，表中放了虚函数的地址，实际的虚函数在代码段(.text)中。当子类继承了父类的时候也会继承其虚函数表，当子类重写父类中虚函数时候，会将其继承到的虚函数表中的地址替换为重新写的函数地址。使用了虚函数，会增加访问内存开销，降低效率。

    16.C++里是怎么定义常量的？常量存放在内存的哪个位置？

  • 常量在C++里的定义就是一个top-level const加上对象类型，常量定义必须初始化。对于局部对象，常量存放在栈区，对于全局对象，常量存放在全局/静态存储区。对于字面值常量，常量存放在常量存储区。

    17.const修饰成员函数的目的是什么？

  • const修饰的成员函数表明函数调用不会对对象做出任何更改，事实上，如果确认不会对对象做更改，就应该为函数加上const限定，这样无论const对象还是普通对象都可以调用该函数。

    18.++i和i++的区别和实现

    1. // ++i 实现：
    2. int& int::operator++(){
    3.   *this +=1;
    4.   return *this;
    5. }
    6. // i++ 实现：
    7. const int int::operator(int) {
    8.   int oldValue = *this;
    9.   ++(*this);
    10.   return oldValue;
    11. }

    19.以下四行代码的区别是什么？

    ```cpp //字符串123保存在常量区，const本来是修饰arr指向的值不能通过arr去修改，但是字符串“123”在常量区，本来就不能改变，所以加不加const效果都一样 const char * arr = “123”;

//字符串123保存在常量区，这个arr指针指向的是同一个位置，同样不能通过brr去修改”123”的值 char * brr = “123”;

//这里123本来是在栈上的，但是编译器可能会做某些优化，将其放到常量区 const char crr[] = “123”;

//字符串123保存在栈区，可以通过drr去修改 char drr[] = “123”;

  1. <a name="oM8nN"></a>
  2. ## 20.函数在main函数执行前先运行的例子
  3. ```cpp
  4. __attribute((constructor))void before(){
  5.     printf("before main\n");
  6. }

21.有段代码写成了下边这样，如果在只修改一个字符的前提下，使代码输出20个hello?

// for(int i = 0; i < 20; i--) cout << "hello" << endl;

for(int i = 0; i + 20; i--){
    cout << "hello" << endl;
}

22.static关键字

  • 加了static关键字的全局变量只能在本文件中使用。例如在a.c中定义了static int a=10;那么在b.c中用extern int a是拿不到a的值得，a的作用域只在a.c中。
  • static定义的静态局部变量分配在数据段上，普通的局部变量分配在栈上，会因为函数栈帧的释放而被释放掉。
  • 对一个类中成员变量和成员函数来说，加了static关键字，则此变量/函数就没有了this指针了，必须通过类名才能访问。

二、容器和算法

三、类和数据抽象

C++中类成员的访问权限

public：

  • 公有的，类内、类外、继承的类都可以访问

private:

  • 私有的，类内可以访问，类外、继承的类不能访问

protected:

  • 受保护的，类内可以访问，类外不可访问，继承的类可以访问

    C++中struct和class的区别

    相同点：

  • 都可以定义类，都可以继承。

不同点：

  • struct的默认继承权限和默认访问权限是public，而class的默认继承权限和默认访问权限是private

  • class可以定义模板类形参，比如template <class T, int i>

    C++类内可以定义引用数据成员

    可以，必须通过成员函数初始化列表初始化。

    四、面向对象与泛型编程

    什么是右值引用，跟左值又有什么区别？

    右值引用是C++11中引入的新特性 , 它实现了转移语义和精确传递。它的主要目的有两个方面：

    1. 消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
    1. 能够更简洁明确地定义泛型函数。

左值和右值的概念：

  • 左值：能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。
  • 右值：不能对表达式取地址，或匿名对象。一般指表达式结束就不再存在的临时对象。

右值引用和左值引用的区别：

    1. 左值可以寻址，而右值不可以。
    1. 左值可以被赋值，右值不可以被赋值，可以用来给左值赋值。
    1. 左值可变,右值不可变（仅对基础类型适用，用户自定义类型右值引用可以通过成员函数改变）。

      五、编译和底层

      1.一个C++源文件从文本到可执行文件经历的过程

  • 对于C++源文件，从文本到可执行文件一般需要四个过程：

    • 预处理阶段：对源代码文件中文件包含关系（头文件）、预编译语句（宏定义）进行分析和替换，生成预编译文件。
    • 编译阶段：将经过预处理后的预编译文件转换成特定汇编代码，生成汇编文件
    • 汇编阶段：将编译阶段生成的汇编文件转化成机器码，生成可重定位目标文件
    • 链接阶段：将多个目标文件及所需要的库连接成最终的可执行目标文件

      2.include头文件的顺序以及双引号””和尖括号<>的区别？

  • Include头文件的顺序：对于include的头文件来说，如果在文件a.h中声明一个在文件b.h中定义的变量，而不引用b.h。那么要在a.c文件中引用b.h文件，并且要先引用b.h，后引用a.h,否则汇报变量类型未声明错误。

  • 双引号和尖括号的区别：编译器预处理阶段查找头文件的路径不一样。
  • 对于使用双引号包含的头文件，查找头文件路径的顺序为：
    • 当前头文件目录
    • 编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）
    • 系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径

  • 对于使用尖括号包含的头文件，查找头文件的路径顺序为：

    • 编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）
    • 系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径

      3.malloc的原理，另外brk系统调用和mmap系统调用的作用分别是什么？

  • Malloc函数用于动态分配内存。为了减少内存碎片和系统调用的开销，malloc其采用内存池的方式，先申请大块内存作为堆区，然后将堆区分为多个内存块，以块作为内存管理的基本单位。当用户申请内存时，直接从堆区分配一块合适的空闲块。Malloc采用隐式链表结构将堆区分成连续的、大小不一的块，包含已分配块和未分配块；同时malloc采用显示链表结构来管理所有的空闲块，即使用一个双向链表将空闲块连接起来，每一个空闲块记录了一个连续的、未分配的地址。

  • 当进行内存分配时，Malloc会通过隐式链表遍历所有的空闲块，选择满足要求的块进行分配；当进行内存合并时，malloc采用边界标记法，根据每个块的前后块是否已经分配来决定是否进行块合并。

  • Malloc在申请内存时，一般会通过brk或者mmap系统调用进行申请。其中当申请内存小于128K时，会使用系统函数brk在堆区中分配；而当申请内存大于128K时，会使用系统函数mmap在映射区分配。

    4.C++的内存管理是怎样的

    在C++中，虚拟内存分为代码段、数据段、BSS段、堆区、文件映射区以及栈区六部分。

  • 代码段:包括只读存储区和文本区，其中只读存储区存储字符串常量，文本区存储程序的机器代码。

  • 数据段：存储程序中已初始化的全局变量和静态变量
  • bss 段：存储未初始化的全局变量和静态变量（局部+全局），以及所有被初始化为0的全局变量和静态变量。
  • 堆区：调用new/malloc函数时在堆区动态分配内存，同时需要调用delete/free来手动释放申请的内存。
  • 映射区:存储动态链接库以及调用mmap函数进行的文件映射

  • 栈：使用栈空间存储函数的返回地址、参数、局部变量、返回值

    5.如何判断内存泄漏？

  • 内存泄漏通常是由于调用了malloc/new等内存申请的操作，但是缺少了对应的free/delete。为了判断内存是否泄露，我们一方面可以使用linux环境下的内存泄漏检查工具Valgrind,另一方面我们在写代码时可以添加内存申请和释放的统计功能，统计当前申请和释放的内存是否一致，以此来判断内存是否泄露。

    6.什么时候会发生段错误

  • 段错误通常发生在访问非法内存地址的时候，具体来说分为以下几种情况：

    • 使用野指针
    • 试图修改字符串常量的内容

      7.什么是memory leak 内存泄漏

  • 内存泄漏(memory leak)是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，失去了对该段内存的控制，因而造成了内存的浪费。

  • 内存泄漏的分类：

    • 堆内存泄漏。对内存指的是程序运行中根据需要分配通过malloc,realloc new等从堆中分配的一块内存，再是完成后必须通过调用对应的 free或者delete 删掉。如果程序的设计的错误导致这部分内存没有被释放，那么此后这块内存将不会被使用，就会产生Heap Leak.
    • 系统资源泄露。主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉，导致系统资源的浪费，严重可导致系统效能降低，系统运行不稳定。
    • 没有将基类的析构函数定义为虚函数。当基类指针指向子类对象时，如果基类的析构函数不是virtual，那么子类的析构函数将不会被调用，子类的资源没有正确是释放，因此造成内存泄露。

      8.new和malloc的区别

  • new分配内存按照数据类型进行分配，malloc分配内存按照指定的大小分配；

  • new返回的是指定对象的指针，而malloc返回的是void*，因此malloc的返回值一般都需要进行类型转化。
  • new不仅分配一段内存，而且会调用构造函数，malloc不会。
  • new分配的内存要用delete销毁，malloc要用free来销毁；delete销毁的时候会调用对象的析构函数，而free则不会。
  • new是一个操作符可以重载，malloc是一个库函数。
  • malloc分配的内存不够的时候，可以用realloc扩容。扩容的原理？new没用这样操作。
  • new如果分配失败了会抛出bad_malloc的异常，而malloc失败了会返回NULL。

  • 申请数组时： new[]一次分配所有内存，多次调用构造函数，搭配使用delete[]，delete[]多次调用析构函数，销毁数组中的每个对象。而malloc则只能sizeof(int) * n。

    六、C++11

    1.auto与decltype
    2.初始化列表
    3.range-based for循环
    4.lambad表达式
    4.nullptr

    5.与类有关的
    5.1 final override virtual
    5.2 default delete explicit
    5.3 委托构造函数、集成构造函数
    5.4
    6.智能指针
    share_ptr
    weak_ptr
    unique_ptr
    7.const constexpr

七、STL相关

A01:map和set有什么区别

相同点：

  • map和set都是C++的关联容器，其底层实现都是红黑树。
  • 由于map和set所开放的各种操作接口，红黑树也都提供了，所以几乎所有的map和set的操作行为，都只是转调红黑树的操作行为。

不同点：

  • map中的元素是key-value对：关键字起到索引的作用，值则表示与索引相关联的数据；而set只保存关键字
  • set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。
  • map支持下标操作，set不支持下标操作。

    第二点： 其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

    第三点： map可以用key做下标去执行查找，如果关键码不存在，会返回与value类型的默认值(map被const修饰时，不能直接使用下标操作，因为如果key不存在会抛异常，可使用count(key)判断该key的个数，然后再进行具体逻辑)。

STL中map与multimap的区别

相同点

  • 都拥有键值对
  • 底层实现都是红黑树
  • 都是有序的关联容器

不同点

  • map：有序键值对不重复映射
  • multimap：有序键值对可重复映射

STL中vector和list的区别

概念

  • vector：可变大小数组
  • list：双向链表

区别：

  • vector底层实现是数组；list是双向链表。
  • vector内存空间连续，支持随机访问，插入删除性能差；list内存空间不连续，不能随机访问，插入删除性能好。
  • vector一次性分配好内存，不够时进行扩容；list在每次插入新节点都会进行内存申请。
  • vector在中间节点进行插入删除会导致内存拷贝，list不会。

适用场景

  • vector：经常随机访问，且不经常对非尾节点进行插入删除。

  • list：经常插入删除大量数据

    A02:STL迭代器删除元素

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

  • 对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。
  • 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。 ```cpp vector v = { 1, 2, 3, 4, 5, 6, 7, 8 }; vector::iterator v_iter; for (v_iter = v.begin(); v_iter != v.end(); v_iter++) { if (*v_iter == 5) {
      v_iter = v.erase(v_iter); // 注意v_iter需要更新一下
    } cout << *v_iter << “, “; } cout << endl; // 1, 2, 3, 4, 6, 7, 8,

// ————————————————————————————————————————— map m = { { “a”, 1 }, { “b”, 2 }, { “c”, 3 }, { “d”, 4 } }; map::iterator m_iter; for (m_iter = m.begin(); m_iter != m.end(); m_iter++) { if (m_iter->first == “b”) { m_iter = m.erase(m_iter); // 注意m_iter需要更新一下 } cout << m_iter->first << “: “ << m_iter->second << “, “; } cout << endl; // a: 1, c: 3, d: 4,

// ————————————————————————————————————————— list l = { 1, 2, 3, 4, 5, 6, 7, 8 }; list::iterator l_iter; for (l_iter = l.begin(); l_iter != l.end(); l_iter++) { if (l_iter == 7) { l_iter = l.erase(l_iter); // 注意iter需要更新一下 } cout << l_iter << “, “; } cout << endl; // 1, 2, 3, 4, 5, 6, 8, ```

STL中map数据存放形式

  • map底层结构是红黑树
  • unordered map底层结构是哈希表

STL由什么基本组成

STL主要由：以下几部分组成：

  • 容器
  • 迭代器
  • 仿函数
  • 算法
  • 分配器
  • 配接器

他们之间的关系：分配器给容器分配存储空间，算法通过迭代器获取容器中的内容，仿函数可以协助算法完成各种操作，配接器用来套接适配仿函数

STL中迭代器的作用，有指针为何还要迭代器

1、迭代器
Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。
由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。
2、迭代器和指针的区别
迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、、++、—等。迭代器封装了指针，是一个“可遍历STL（Standard Template Library）容器内全部或部分元素”的对象， 本质是封装了原生指针，是指针概念的一种提升（lift），提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，—等操作。
迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。
3、迭代器产生原因
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

A0: STL 的 allocaotr
STL 的分配器用于封装 STL 容器在内存管理上的底层细节。
STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下：
new运算分两个阶段：(1)调用::operator new配置内存;(2)调用对象构造函数构造对象内容

delete运算分两个阶段：(1)调用对象析构函数；(2)掉用::operator delete释放内存

为了精密分工，STL allocator将两个阶段操作区分开来：内存配置有alloc::allocate()负责，
内存释放由alloc::deallocate()负责；对象构造由::construct()负责，对象析构由::destroy()负责。

同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，SGI STL采用了两级配置器，
当分配的空间大小超过128B时，会使用第一级空间配置器；当分配的空间大小小于128B时，将使用第
二级空间配置器。第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的
分配和释放，而第二级空间配置器采用了内存池技术，通过空闲链表来管理内存。

B01.vector的底层（存储）机制

Vector将元素复制到内部dynamic array。元素之间总是存在一定的顺序，所以 vector是一种有序集合，且支持随机访问。
而当空间不够装下数据时，会自动申请另一片更大的空间，然后把原来的数据拷贝过去，接着释放原来的那片空间；当释放或者删除里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

02.vector的自增长机制

标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些控件作为备用，可用来保存更多的新元素。这样，就不需要每次添加新元素都重新分配容器的内存空间了。
即：

  • 完全弃用现有的内存空间，重新申请更大的内存空间
  • 将旧内存空间中的数据，按原有顺序移动到新的内存空间中
  • 最后将旧的内存空间释放

但，vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效；内存重新分配很耗时。

03.list的底层（存储）机制

04.什么情况下用vector，什么情况下用list

05.list自带排序函数的排序原理
06.deque的底层机制
07.deque与vector的区别
08.map底层机制，查找复杂度，能不能边遍历边插入
09.vector插入删除和list有什么区别
10.hashtable如何避免地址冲突
11.hashtable、hash_set、hash_map的区别
12.hash_map与map的区别、什么时候用它们两个？
13.红黑树有什么性质？
14.map和set的3个问题
15.为什么vector插入操作可能导致迭代器失效
16.hashtable和hashmap的区别
17.STL底层数据结构实现
18.STL提供哪六大组件？
19.auto_ptr可以做vector的元素吗？为什么？
20.简单说一下next_permutation和partition的实现？
21.不允许有遍历行为的容器有哪些？（不提供迭代器）

设计模式
6个设计原则
单例模式
简单工厂模式 工厂模式 抽象工厂模式
原型模式

原文链接：https://blog.csdn.net/xiongluo0628/article/details/81546197

STL容器
容器：
分类：序列式容器 关联式容器 无序容器 关联式数组
Array
Vector
Deque
List
Forward List
Set和Multiset
无序容器 Unordered Container
特殊容器：
堆栈
队列
带优先级的队列
迭代器
种类：六种 433

STL容器

C 基础整理 - 图1> 参考资料：《C++ 11 STL中常用容器分类和对比》

顺序容器

  • vector
    • 可变大小数组
    • 支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢
  • deque
    • 双端队列
    • 支持快速随机访问，在头尾位置插入/删除速度很快
  • list
    • 双向链表
    • 只支持双向顺序访问。在链表任何位置进行插入/删除操作速度都很快
  • forward_list
    • 单向链表
    • 只支持单项顺序访问，在链表任何位置进行插入/删除操作速度都很快
  • array
    • 固定大小数组。支持快速随机访问，不能添加或删除元素
  • string
    • 与vector相似的容器，但专门用于保存字符。随机访问快，在尾部插入/删除速度快

顺序容器选择的基本原则

  • 除非你有更好的理由选择其它容器，否则应使用vector
  • 如果你的程序有很多小的元素，且控件的额外开销很重要，则不要使用list或forward_list
  • 如果程序要求随机访问元素，应使用 vector或deque
  • 如果程序要求在容器中间插入或删除元素，应使用list或forward_list
  • 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除元素，则使用deque

  • 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则

    • 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。
    • 如果比如在中间位置插入元素，考虑在输入截断使用list，一旦输入完成，将list中的内容拷贝到一个vector中

      关联容器

  • 有序关联容器

    • map 关联数组：保存 关键字-值 对
    • set 关键字即值，即只保存关键字的容器
    • multimap 关键字可重复出现的map
    • multiset 关键字可重复出现的set
  • 无序关联容器
    • unordered_map 用哈希函数组织的map
    • unordered_set 用哈希函数组织的set
    • unordered_multimap 哈希函数组织的map，关键字可重复出现
    • unordered_multiset 哈希函数组织的set,关键字可重复出现

https://www.nowcoder.com/ta/review-c