C++

111111111111111

C++11新特性

智能指针

shared_ptr

共享智能指针。他记录着当前共享资源正被多少个智能指针引用着。当新增一个智能指针指向某对象时,其引用计数+1,当某智能指针不再指向该对象时,引用减1.当引用计数为0时,自动释放其内存资源,从而避免了内存泄漏。

1
2
3
4
5
usercount() //引用计数
unique() //返回是否独占(即use_count == 1)
swap() // 交换两个智能指针指向的对象
reset() // 引用计数-1
get() // 返回裸指针

实现原理

  • 默认构造函数中初始化引用计数为0
  • 用普通指针(不为NULL)为一个shared_ptr赋值时,引用数+1(这里无法防止循环引用,若我们用同一个普通指针去初始化两个shared_ptr,此时两个ptr均指向同一片内存区域,但是引用计数器均为1,使用时需要注意。)
  • 拷贝构造函数需要注意,用一个shared_ptr对象去初始化另一个shared_ptr对象时,引用计数器加一,并指向同一片内存区域.
  • 赋值运算符时,左边引用计数减1,右边引用计数加1.
  • 析构时候,引用计数-1.若结果为0,则释放其引用的对象的内存。</br>
    循环引用问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    using namespace std;
    #include"boost/shared_ptr.hpp"


    struct Node
    {
    Node(int value)
    :_value(value)
    {
    cout << "Node()" << endl;
    }
    ~Node()
    {
    cout << "~Node()" << endl;
    }
    shared_ptr<Node> _prev;
    shared_ptr<Node> _next;
    int _value;
    };

    void Test2()
    {
    shared_ptr<Node> sp1(new Node(1));
    shared_ptr<Node> sp2(new Node(2));
    cout << sp1.use_count() << endl;
    cout << sp2.use_count() << endl;
    sp1->_next = sp2;
    sp2->_prev = sp1;
    cout << sp1.use_count() << endl;
    cout << sp2.use_count() << endl;
    }

    int main()
    {
    Test2();
    return 0;
    }
  • 由于先构造的后释放,后构造的先释放可知,先释放的是sp2,那么因为它的引用计数为2,减去1之后就成为了1,不能释放空间,因为还有其他的对象在管理这块空间。但是sp2这个变量已经被销毁,因为它是栈上的变量,但是sp2管理的堆上的空间并没有释放。

  • 接下来释放sp1,同样,先检查引用计数,由于sp1的引用计数也是2,所以减1后成为1,也不会释放sp1管理的动态空间。由此造成了内存泄漏

weak_ptr

弱引用当引用的对象活的时候不一定存在 。仅仅是当它存在的时候的一个引用。弱引用并不修改该对象的引用技术,这意味这弱引用它并不对对象的内存进行管理,在功能上类似普通的指针,然而一个比较大的区别是:弱引用能检测到所管理的对象是否已经被释放,从而避免访问非法内存。</br>
由此常用于解决shared_ptr的死锁问题,将其中一个替换为weak_ptr即可。
通过lock函数可以获得该对象的shared_ptr指针。

四种类型转换

static_cast

完成编译器默认的类型转换.不能用于不相关类型转换如int <-> int* ,不能将const<->non-const转换。常用于

  • 基本类型数据转换
    1
    2
    int a = 1;
    double b = static_cats<double>(a);

reinterpret_cast

可将指针转换为整数

const_cast

可以将const->non-const

1
2
3
4
5
volatile const int i = 10;   //const修饰的变量会被编译器优化到寄存器中,再次访问该变量时,就会直接从寄存器中区读取... 加上volatile后,则会强制从内存读取变量
int* p = const_cast<int*>(&i);
*p = 20;
cout<<i<<endl; //注意如果不加volatile关键字,这里输出i任然为10,因为是从寄存器读取的值。如果加上volatile后则会是20.
cout<<*p<<endl;

dynmic_cast(动态转换)

将基类指针转换为子类的指针。

  • 若对指针进行dynamic_cast,失败返回null,成功返回正常cast后的对象指针;
  • 若对引用进行dynamic_cast,失败抛出一个异常,成功返回正常cast后的对象引用。

  • dynamic_cast在将父类cast到子类时,父类必须要有虚函数,否则编译器会报错。

  • dynamic_cast主要用于类层次间的上行转换和下行转换,还可以用于类之间的交叉转换。在类层次间进行上行转换时,dynamic_cast和static_cast的效果是一样的;在进行下行转换时,dynamic_cast具有类型检查的功能,比static_cast更安全。

final

  • 使用final修饰的类不能被继承,即不能作为基类
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    不能继承的类 

    方法1:使用final
    class A final {

    };


    方法2:构造函数设为私有。因为如果作为基类,则子类构造时候会先调用基类的构造函数,但由于私有导致不能调用基类的构造函数
    class B {

    private:
    B() {

    }
    };

    方法3:采用protected继承或private继承的派生类不能被继承

lambda

C++11支持的匿名函数,可用于代替函数指针,默认为内联函数,其基本表达式如下

1
2
3
4
5
6
7
8
9
10
[函数对象参数] (操作符重载函数参数) mutable 或 exception声明 -> 返回值类型 {函数体}



int a;

[&a] () -> int {
a++;
return a;
};

函数对象参数

表示所需要的参数,不能省略。只能是到定义lambda为止的可见的局部变量(包含lambda所在类的this指针),有如下形式

  • [] : 无
  • [=] : 可以使用可见的所有局部变量(包括this指针),且为值传递方式。此时lambda默认为const的。
  • [&] : 。。。。。。。。。。。。。。。。。。。。, 且为引用传递方式,可以修改参数值。
  • [this] : 可以使用this
  • [a] : 可以使用变量a,值传递,此时lambda为const,若要修改a的拷贝,需加mutable声明,但只是修改a的拷贝,原a的值不会改变.
  • [&a] : 可以使用a, 引用传递,可以修改原a的值.
  • [=, &a, &b] : 除了a,b为引用传递,其余为值传递
  • [&, a, b] : ……….
操作符重载对象参数

无参数时可以省略。有值传递和引用传递。

mutable声明和exception声明

这部分可以省略。按值传递函数对象参数时,加上 mutable 修饰符后,可以修改传递进来的拷贝(注意是能修改拷贝,而不是
值本身)。exception 声明用于指定函数抛出的异常,如抛出整数类型的异常,可以使用 throw(int)。

返回值类型

void时或函数体中只有一处return语句时(此时编译器可以自动推导返回类型)可省略。

函数体

不可省略,但可以为空

thread_local

线程局部储存变量,有如下特性

  • 变量在线程创建时生成(不同编译器实现略有差异,但在线程内变量第一次使用前必然已构造完毕)。
  • 线程结束时被销毁(析构,利用析构特性,thread_local变量可以感知线程销毁事件)。
  • 每个线程都拥有其自己的变量副本,不同线程不会干扰。
  • thread_local可以和static或extern联合使用,这将会影响变量的链接属性。

C++

程序编译过程

预编译(生成.i文件)

1
g++ -E a.cc

编译(生成.s .asm汇编文件)

1
g++ -S

汇编(生成.o文件)

1
g++ -c

链接

静态链接
  • 将汇编形成的.o文件与引用到的库一起打包到可执行文件中。即在编译过程中就链接。
  • 静态库一般为(.a,windos下为.lib),是许多.o文件的集合。
  • 特点:
  1. 静态库对函数库的链接在编译时期完成
  2. 程序运行时候与函数库无关,方便移植
  3. 浪费空间和资源。
  • 命名规范

    1
    lib[项目名称].a 如libcharon.a
  • 使用静态库:

    1
    g++ -L静态库搜索路径 -l静态库名(不需要lib前缀和.a后缀)
动态链接
  • 在程序运行的时候才链接,因此节约了空间。也称为共享库。
  • 命名规范

    1
    如 libcharon.so
  • 生成静态库

    1
    2
    3
    4
    1.生成目标文件 —fPIC创建与地址无关的编译程序,为了在多个程序实现共享
    g++ -fPIC -c a.cc
    2.生成动态库 -shared指定生成动态库
    g++ -shared -o lib???.so a.o
  • 使用动态库

    1
    2
    与静态库一样,但需要将动态库文件复制到 /usr/lib下以便找到动态库
    g++ -L -l

extern

  • 作用1:extern常用于变量或函数前,表示该变量或函数定义在别的文件中。如在文件 a中定义了一个变量 在文件b中如果需要使用这个变量则需要包含文件a
    1
    2
    3
    // a.cc

    int t = 1;
1
2
3
4
5
// b.cc

extern int t;
cout << t;
// 输出 1
  • 作用2: 当出现以下情况则说明编译器在编译其中内容适合需要按照C语言的规则去翻译函数。因为

    1
    2
    3
    extern "C" {
    ///////
    }
  • 因为C++支持重载,因此编译器对函数名会进去各种变化,修饰。而C不会,当我们需要用到c代码编写的库函数时候,使用extern c 能保证编译器按照C的规则来编译。

    const

  • 定义常量

  • 修饰指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int* const p;  //指针p不可变,即指针不能修改p指向其他内存,但p指向的变量可变。

    const int* p; //指针p指向的变量不可变,但指针p可以指向其他变量。即p指向可以修改

    const int* const p; //指针p指向不可变,且p指向的变量也不可变。

    区分方法:
    沿着*分割:
    若const位于*左侧,const修饰指针指向的变量,即指针指向常量。
    若const位于*有责, const修饰指针,即不能改变指针指向。
  • 函数中修饰参数

1
2
3
4
void f(const int a);    //无意义,因为a本身为值传递
void f(const int* a) //指针a指向的内容为常用,不可变
void f(int* const a) //无意义
void f(const int& a) //引用a不可改变
  • 修饰函数返回值
  • 修饰类的成员变量(此时该成员变量只能在初始化列表中赋值)
  • 修饰类的成员函数(此时该函数不能修改类的成员变量,也不能调用类的非const成员函数)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class A {
    void get() const {
    a = 1; //错误 不能修改成员
    set(); //错误 不能调用非const成员函数

    }
    void set() {
    a = 2;
    }
    int a;
    };
  • 修饰类的对象/对象的指针/对象的引用(此时不能修改对象的成员,也不能调用非const成员函数)

    1
    2
    3
    4
    class A;
    const A a;
    const A& b = a;
    const A* c = new A;
  • 在类中的常量如何初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    方法1 使用静态常量在外部初始化
    class A {
    static const int M; //注意必须是static静态成员
    };

    const A::M = 10;


    方法2 使用初始化列表
    class A {
    A(int i) : M(i) {

    }
    const int M;
    };

mutable

可变的,突破const的限制。在类的const函数中,不能修改变量的值,而如果变量加上mutable,则即使const函数也可以修改这个变量的值。

C++多态

静态多态

指在编译时期完成的,编译器会根据实参调用合适的函数。

  • 函数重载
  • 模板(泛型编程)

动态多态(依靠虚函数实现)

在程序运行时实现的,根据基类的引用或指针指向的子类的对象决定该调用哪一个类的虚函数。

C++内存分布

  • 栈区(stack):由编译器自动分配和释放,用来存放函数的参数、局部变量等。其操作方式类似于数据结构中的栈。
  • 堆区(heap):一般由程序员分配和释放(通过malloc/free、new/delete),若程序员没有释放,则程序结束时由操作系统回收。它与数据结构中的堆是两回事,分配方式类似于链表。
  • 全局/静态区:全局变量和静态变量的存储是放在一块的,初始化的全局变量和初始化的静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域,程序结束后由操作系统回收。
  • 文字常量区:存放常量值,如常量字符串等,不允许修改,程序结束后由操作系统回收。
  • 程序代码区:存放函数体的二进制代码。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <stdlib.h>
    #include <string.h>
    int a = 0; // 全局初始化区
    char* p1; // 全局未初始化区
    int main() {
    int a; // 栈区
    char s[] = "abc"; // 栈区
    char* p2; // 栈区
    char* p3 = "123456"; // 123456\0在常量区,p3在栈区
    static int c = 0; // 全局/静态初始化区
    p1 = (char*) malloc(10);
    p2 = (char*) malloc(20); // 分配得来的10和20字节在堆区
    strcpy(p1, "123456"); // 123456\0放在常量区,编译器可能将它与p3所指向的"123456"优化成一个地方
    return 0;
    }

static

C中static作用

  • 主要作用(隐藏变量或函数,使其仅限本文件使用)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // a.c

    static int a = 1;

    // b.c

    int main() {
    extern int a;
    a++;
    }

    // 同时编译这两个文件 由于static 使得变量a只能在文件a.c中使用,
    // 对于其他文件是隐藏的,因此在b.c中使用extern int a也无法访问a.c中的变量a。因此会报错
    // 若去掉static关键字 则能够运行成功
  • 保持变量内容持久
    :存储在静态数据区的变量会在程序刚开始运行时就完成初始化,也是唯一的一次初始化。共有两种变量存储在静态存储区:全局变量和 static 变量,只不过和全局变量比起来,static 可以控制变量的可见范围。

C++中static

除了C中的语法外,还额外添加了以下两点:

  • 静态数据成员:属于类而不属于类的某一个对象。所有对象共享一份静态数据成员,存储在全局数据区。因为定义静态变量要分配内存,因此不能再类声明中定义。

    1
    2
    3
    4
    5
    class A {
    static int a;
    };
    // 静态成员必须这样初始化
    int A::a = 10;
  • 静态函数成员:可以不通过对象直接调用。他没有this指针,因此不能访问非静态数据成员和非静态函数成员。它可以直接通过类名来访问(推荐),也可以通过对象来访问。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class A {
    static void Get();

    static int b;
    int a;
    };
    void A::Get() {

    cout << "11";


    a = 1; // 错 不能访问非静态数据成员


    b = 2; // 正确 可以访问静态数据成员
    }

    // 可以通过以下代码来直接访问静态成员函数
    A::Get();

explicit

作用是防止隐式转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
class A
{
public:
A(int i = 5)
{
m_a = i;
}
private:
int m_a;
};


A a = 1; //会正确执行 1被隐式转换为一个类型为A的对象 即 A a = A temp(1);

当类的构造函数只有一个参数时(或其他参数都有默认值),类A的对象可以直接被对应的内置类型隐式转换而赋值给其他对象。此时若在构造函数前加上explicit声明,则可以抑制这种转换。

纯虚函数

基类虚函数定义后面加上 “= 0”。可以不用在基类实现该虚函数的定义,直接在子类实现该虚函数即可。拥有纯虚函数的类不能实例化出对象,常常作为接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class A {
virtual ~A() = 0;
virtual void test() = 0; // 在基类中不用实现纯虚函数
};

class B : public A {

void test() override {
....
}
};

// 错误 拥有纯虚函数的类不能实例化出对象
A a;

为什么父类析构函数总是虚函数

首先 正常执行顺序为 : 父类构造函数 -> 子类构造函数 -> 子类析构函数 -> 父类析构函数 </br>
因此 当我们用一个父类的指针p指向子类的对象的时候,若执行delete p。此时由于父类析构函数为虚函数,则p会根据其所指的对象(即子类)来调用相应的析构函数,即会调用子类的析构函数。</br>
当p指向的为父类对象时候,此时就会调用父类的析构函数。</br>

如果父类析构函数不是虚函数,则delete p时候就只会调用父类的析构函数。此时如果p指向的是子类对象的话,则无法调用到子类的析构函数,便造成了内存泄漏。

单例设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <memory> // shared_ptr
#include <mutex> // mutex

// version 2:
// with problems below fixed:
// 1. thread is safe now
// 2. memory doesn't leak

class Singleton{
public:
typedef std::shared_ptr<Singleton> Ptr;
~Singleton(){
std::cout<<"destructor called!"<<std::endl;
}
Singleton(Singleton&)=delete;
Singleton& operator=(const Singleton&)=delete;
static Ptr get_instance(){

// "double checked lock"
if(m_instance_ptr==nullptr){
std::lock_guard<std::mutex> lk(m_mutex);
if(m_instance_ptr == nullptr){
m_instance_ptr = std::shared_ptr<Singleton>(new Singleton);
}
}
return m_instance_ptr;
}


private:
Singleton(){
std::cout<<"constructor called!"<<std::endl;
}
static Ptr m_instance_ptr;
static std::mutex m_mutex;
};

// initialization static variables out of class
Singleton::Ptr Singleton::m_instance_ptr = nullptr;
std::mutex Singleton::m_mutex;

int main(){
Singleton::Ptr instance = Singleton::get_instance();
Singleton::Ptr instance2 = Singleton::get_instance();
return 0;
}
  • 单例模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // C++11规定了local static在多线程条件下的初始化行为,
    // 要求编译器保证了内部静态变量的线程安全性。
    // 在C++11标准下,《Effective C++》提出了一种更优雅的单例模式实现,使用函数内的 local static 对象。
    // C++0x之后该实现是线程安全的,C++0x之前仍需加锁。

    template<class T>
    class Singleton {
    public:
    /**
    * @brief 返回单例裸指针
    */
    static T* GetInstance() {
    static T v; // 注意这里必须是static变量 该语句只会执行一次 即对象v只会被初始化一次,即使多次调用该函数,也只会返回第一次创建的对象指针
    return &v;
    }
    private:
    Singleton() { };
    ~Singleton() { };
    Singleton(const Singleton&);
    Singleton& operator=(const Singleton&);
    };

内联函数

定义: 当函数被声明为内联函数之后, 编译器会将其内联展开, 而不是按通常的函数调用机制进行调用.
</br>优点: 当函数体比较小的时候, 内联该函数可以令目标代码更加高效. 对于存取函数以及其它函数体比较短, 性能关键的函数, 鼓励使用内联.
</br>缺点: 滥用内联将导致程序变慢. 内联可能使目标代码量或增或减, 这取决于内联函数的大小. 内联非常短小的存取函数通常会减少代码大小, 但内联一个相当大的函数将戏剧性的增加代码大小. 现代处理器由于更好的利用了指令缓存, 小巧的代码往往执行更快。
</br>有些函数即使声明为内联的也不一定会被编译器内联, 这点很重要; 比如虚函数和递归函数就不会被正常内联. 通常, 递归函数不应该声明成内联函数

引用和指针

指针指向一块内存,它的内容是所指内存的地址;而引用则是某块内存的别名。

★不同点:

●指针是一个实体,占用内存空间,而引用仅是个别名;

●引用只能在定义时被初始化一次,之后不可变;指针可变;引用“从一而终”,指针可以“见异思迁”;

●引用没有const,指针有const,const的指针不可变;(具体指没有int& const a这种形式,而const int& a是有 的, 前者指引用本身即别名不可以改变,这是当然的,所以不需要这种形式,后者指引用所指的值不可以改变)

●引用不能为空,指针可以为空;

●“sizeof 引用”得到的是所指向的变量(对象)的大小,而“sizeof 指针”得到的是指针本身的大小;

●指针和引用的自增(++)运算意义不一样;

●引用是类型安全的,而指针不是。

无论你传值还是传指针,函数都会生成一个临时变量,
但传引用时,不会生成临时变量,

当你传值时,只可以引用值而不可以改变值,但传值引用时,可以改变值,
当你传指针时,只可以改变指针所指的内容,不可以改变指针本身,但传指针引用时,既可以改变指针所指的内容,又可以改变指针本身,

但传引用主要是它不生成临时变量,不进行返回值copy等,速度快。

虚函数原理

单继承

派生类中仅有一个虚函数表。这个虚函数表和基类的虚函数表不是一个表(无论派生类有没有重写基类的虚函数,两个虚函数表指针vptr也是不同的),但是如果派生类没有重写基类的虚函数的话,基类和派生类的虚函数表指向的函数地址都是相同的,但vptr值也是不同的。若子类重写了虚函数,则在子类虚函数表中会对应替换为重写的函数指针。

判断大小端

大端 : 低地址存放高位。</br>
小端:低地址存放低位。</br>
网络字节序一般为大端。 </br>
对于一个4字节整数 i = 0000 0000 0000 0001;

  • 若为小端。则高地址放数据高位,低地址放数据低位,因此按照地址由低到高,i存储顺序为 0001 0000 0000 0000,则其第一个字节中值即为1.
  • 若为大端。则高地址放低位。则地址由低到高为 0000 0000 0000 0001,则其第一个字节中值为0,
  • 使用联合体,利用char取得int的第一个字节,判断其值便可知道大小端

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    union t {
    int a,
    char c,
    };

    t.a = 1;

    if(t.c == 1) {
    // 小端
    } else {
    大端
    }
  • 大小端转换函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

    int32_t swapInt32(int32_t value)
    {
    return ((value & 0x000000FF) << 24) |
    ((value & 0x0000FF00) << 8) |
    ((value & 0x00FF0000) >> 8) |
    ((value & 0xFF000000) >> 24) ;

    }

    // h为主机 n为网络 网络字节序一般为大端 l为long s为short
    uint16_t htons(uint16_t host16bitvalue);
    uint32_t htonl(uint32_t host16bitvalue); //均返回网络字节序的值

    uint16_t ntohs(uint16_t host16bitvalue);
    uint32_t ntohl(uint32_t host16bitvalue); //均返回主机字节序的值

构造函数和析构函数中可以调用调用虚函数吗

可以调用,但没有多态效果

  • a) 如果有继承,构造函数会先调用父类构造函数,而如果构造函数中有虚函数,此时子类还没有构造,所以此时的对象还是父类的,不会触发多态。更容易记的是基类构造期间,virtual函数不是virtual函数。
  • b) 析构函数也是一样,子类先进行析构,这时,如果有virtual函数的话,子类的内容已经被析构了,C++会视其父类,执行父类的virtual函数。

内存泄漏与内存溢出

内存泄漏

1:内存泄漏是指程序中已动态分配的堆内存由于某种原因未释放或无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统奔溃等严重后果。

2:一次泄漏似乎不会有大的影响,但内存泄漏后堆积的结果就是内存溢出。

3:内存泄漏具有隐蔽性,积累性的特征,比其他内存非法访问错误更难检测。这是因为内存泄漏产生的原因是内存块未被释放,属于遗漏型缺陷而不是过错型缺陷。此外,内存泄漏不会直接产生可观察的错误,而是逐渐积累,降低系统的整体性性能。

4:如何有效的进行内存分配和释放,防止内存泄漏,是软件开发人员的关键问题,比如一个服务器应用软件要长时间服务多个客户端,若存在内存泄漏,则会逐渐堆积,导致一系列严重后果。

内存溢出

指程序在申请内存时,没有足够的内存供申请者使用,或者说,给了你一块存储int类型数据的存储空间,但是你却存储long类型的数据,就会导致内存不够用,报错OOM,即出现内存溢出的错误。

如何定位内存泄漏

使用valgrind工具,其内置的memcheck工具常用来检查内存错误使用情况:</br>

  1. 使用未初始化的内存 (Use of uninitialised memory)

  2. 使用已经释放了的内存 (Reading/writing memory after it has been free’d)

  3. 使用超过 malloc分配的内存空间(Reading/writing off the endof malloc’d blocks)

  4. 对堆栈的非法访问 (Reading/writing inappropriate areas on the stack)

  5. 申请的空间是否有释放 (Memory leaks – where pointers to malloc’d blocks are lost forever)

  6. malloc/free/new/delete申请和释放内存的匹配(Mismatched use of malloc/new/new [] vs free/delete/delete [])

  7. src和dst的重叠(Overlapping src and dst pointers inmemcpy() and related functions)
1
2
g++ -0 test -g main.cc      // 注意要加-g调试信息
valgrind--leak-check=yes ./test

类的默认函数成员

  1. 构造函数
  2. 析构函数
  3. 拷贝构造函授
  4. 赋值操作符重载
  5. 取地址操作符重载
  6. const修饰的取地址操作符重载

linux内部调试宏

1
2
3
4
5
__FILE__:表示在哪个文件

__LINE__:表示在当前多少行

__FUNCTION__:表示在执行在哪个函数

struct 与 class区别

  • struct默认为public,class默认为private
  • struct默认继承方式为public, class默认继承方式为private
  • 只有class能作为模板参数,struct不能。

C++继承方式

  • public继承(默认) :public和protected不变,private子类不可见。
  • protected继承:public->protected ,而protected->private,private依然不可见。
  • private继承:public和protec均变为private,private依旧不可见。

必须在初始化列表赋值的情况

  • const成员
  • 引用成员
  • 没有默认构造函数的其它类B的对象成员b(因为当实例化一个对象A时候,会自动初始化其成员,由于b没有默认构造函数,因此就会出错)
  • 继承关系时,派生类必须在其初始化列表构建基类对象

手写函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
int strlen(const char *str) {
assert(str != NULL);

int len = 0;
while( (*str++) != '\0')
len++;

return len;
}

字符串复制函数,strcpy把含有'\0'结束符的字符串复制到另一个地址空间,返回值的类型为char*。
char *strcpy(char *strDes, const char *strSrc) {
if(strSrc == NULL || strDes == NULL)
return NULL;

char *address = strDes;

while( (*strDest++ = *strSrc++) != '\0');

return address;

}

功能:把src所指向的字符串(包括“\0”)复制到dest所指向的字符串后面(删除*dest原来末尾的“\0”)。要保证*dest足够长,以容纳被复制进来的*src。*src中原有的字符不变。返回指向dest的指针。
char* strcat(char* strDest, const char* strSrc) {
char* address = strDest;
assert( (strDest != NULL) && (strSrc != NULL) );

while(*strDest != '\0') //当strDest='\0'时结束,即为字符串的结尾,将strSrc添加到此处
strDest++;

while(*strSrc != '\0')
*strDest++ = *strSrc++;

*strDest = '\0';

return address;
}


对两个字符串进行比较,若s1、s2字符串相等,则返回零;若s1大于s2,则返回正数;否则,则返回负数。


int strcmp(const char* str1, const char* str2) {
assert( (str1 != NULL) && (str2 != NULL) );
int ret = 0;

while( !(ret = *(unsigned char*)str1 - *(unsigned char*)str2) && *str1 ) {//ret=0,相等,相等时要确定两个字符不为'\0'; ret!=0时,循环结束,判断ret值
str1++;
str2++;
}

if(ret > 0)
return 1;

else if(ret < 0)
return -1;

return 0;
}

将str指向地址为起始地址的连续n个字节的数据复制到以dest指向地址为起始地址的空间内,函数返回一个指向dest的指针.

 

实现:

void* memcpy(void *dest, const void *src, size_t n) {
if(dest == NULL || src == NULL)
return NULL;

char* pdest = (char*)dest;
char* psrc = (char*)src;

while(n--)
*pdest++ = *psrc++;

return dest;
}


int Myatoi( string str){
int i =0;
int n = str.size();
int flag = 0; //标记正负
int ans = 0;
int ans_end = 0;
for(i; i<n; i++)
{
if(flag == 0)
{
if(str[i] == '+') flag = 1;
else if (str[i] == '-') flag = -1;
else if (str[i] >= '0' && str[i] <= '9')
{
ans = str[i] - '0';
flag = 1;
}
else if( str[i] == 0) continue;
else return 0;
}
else
{
if(str[i] >= '0' && str[i] <= '9')
{
ans_end = ans; //这里用ans_end 标记转换前的数, 目的是为了判断转换后是否值溢出(超过Int最大位或最小位)
ans = ans * 10 + (str[i] - '0');
if( ans /10 != ans_end) // 不相等就证明值已经溢出了
{
if(flag == 1) return INT_MAX:
else return INT_MIN;
}
}
else if( ans!= 0) break;
else return 0;
}
}
return ans * flag;
}

POD对象

一个类中,只包含一些基本成员,没有构造,没有析构,没有拷贝构造。

能否用memset实例化一个类

1、memset只适用于POD类型结构。对非POD类型,用构造函数来初始化。
2、memset让非POD崩溃的根本原因,是把里面的数据(例如虚函数表),即指向虚函数表的指针置空之后,导致后续的一些函数调用会访问到非法内存,这才是崩溃的根本原因。

析构函数不要抛出异常

  • 析构函数绝对不能抛出异常;如果一个被析构函数调用的函数可能抛出异常,析构函数应该捕捉任何异常,然后吞下它们(不传播)或结束程序。如果析构函数抛出异常,可能导致两个异常同时存在,程序若不是结束执行就是导致不明确行为。如果客户需要对某个操作函数运行期间抛出的异常做出反应,那么类应该提供一个普通函数(而非在析构函数中)执行该操作。

  • 构造函数中抛出异常,会导致析构函数不能被调用,但对象本身已申请到的内存资源会被系统释放(已申请到资源的内部成员变量会被系统依次逆序调用其析构函数)。

  • 因为析构函数不能被调用,所以可能会造成内存泄露或系统资源未被释放。

  • 构造函数中如要抛出异常,但必须保证在构造函数抛出异常之前,把系统资源释放掉,防止内存泄露。(如何保证???使用auto_ptr???)

  • C++ 里面当构造函数抛出异常时,其会调用构造函数里面已经创建对象的析构函数,但是对以自己的析构函数没有调用,就可能产生内存泄漏,比如自己new 出来的内存没有释放。
    有两个办法。在Catch 块里面释放已经申请的资源 或者 用智能指针把资源当做对象处理

    operator= 返回一个reference to *this

    为了实现“连锁赋值”等

    1
    x=y=z=10;

new/delete 与 malloc/free

new与delete

  • new与delete是运算符,不是函数!
  • new和delete开辟的内存空间为自由存储区。自由存储区是一个抽象的区域,它可以是堆,可以是其他内存区,这取决于operator new的内部实现。若new内部使用 malloc来申请内存,则此时自由存储区就是堆。
  • new返回分配的内存空间首地址,分配失败返回NULL。
  • new必须与delete配套使用。
  • new 和 delete会调用对象的构造和析构函数
  • new过程如下:
    1. 分配内存
    2. 调用构造函数
  • delete过程如下:
    1. 调用析构函数
    2. 释放内存
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      //申请一块内存空间存放一个整形变量并赋值5 使用指针p指向这个变量
      int *p = new int(5);

      //delete只是销毁上述申请的那个整形变量 而指针p依然存在 故需要使p指向NULL防止p变为野指针
      delete p;
      p = NULL;

      //申请一个大小为x+y的数组
      int *a = new int[x+y];
      //注意 对于数组delete语句一定要加上[] 不然只会销毁数组首地址所存的对象 而不会销毁整个数组
      delete []a;
      a = NULL;

placement new

  • 不开辟内存 值调用构造函数
    如 STL源码中的配置器模块中的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <new.h>  //使用 palcement new 需包含此头文件

    template <class T1, class T2>
    inline void construct(T1 *p, const T2 &value) {
    //在p所指向的空间创建一个T1型对象 对象内容从T2类型转换过来 调用构造函数T1::T1(value)
    new (p) T1(value);
    }
    tmeplate <calss T>
    inline void destroy(T *pointer) {
    pointer->~T(); //调用T1::~T1()
    }
  • 释放placement new对象不能使用delete 而是直接调用析构函数即可 如上

malloc和free

  • 不像new/delete针对自由存储区,malloc/free是对堆上的内存开辟或释放。
  • malloc/free是函数,不是运算符。
  • 返回分配内存的地址,void* 类型。失败返回NULL。
  • 并不是申请多少字节就会分配多少字节,malloc()在分配用户传入的大小的时候,还分配的一个用于管理的额外内存空间。
    1
    2
    int *p = (int *)malloc(sizeof(int));
    free(p);

malloc底层原理

字节对齐

  • 数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小(只要该成员有子成员,比如说是数组,结构体等)的整数倍开始(比如int在32位机为4字节,则要从4的整数倍地址开始存储。
  • 结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存储.(struct a里存有struct b,b里有char,int,double等元素,那b应该从8的整数倍开始存储.)
  • 收尾工作:结构体的总大小,也就是sizeof的结果,必须是其内部最大成员的整数倍.不足的要补齐.
  • pragma pack (n)代表以n个字节为标准对齐,n=1时代表不对齐。

C++ Const与define的区别

  • const定义的变量,带有类型而define定义的数据没有类型
  • define是在程序的预编译阶段起的作用,而const是在程序的编译,运行阶段起的作用
  • define只是简单的进行字符串替换,并没有进行类型检查,容易造成各种边界错误,而const提供了类型检查。
    const常量是可以进行调试的,而define是无法进行调试的,在预编译阶段就已经替换了

野指针与空指针

空指针

void*</br>
支持操作:

  1. 与另一个指针比较
  2. 传参
  3. 返回值
  4. 给另一个void*指针赋值</br>

不支持操作:</br>

  1. 解引用
  2. 不能进行移位等指针运算

野指针

指向一个非法的或已销毁的内存的指针,对系统造成不可预知的错误,出现

  • 指针变量未初始化

    1
    int* a;
  • 指针被delete后,未指向NULL。

重载与重写

  • 重载:两个函数名相同,但是参数列表不同(个数,类型),返回值类型没有要求,在同一作用域中。注意 两个同样函数,一个带const,一个不带const也算是重载
  • 重写:子类继承了父类,父类中的函数是虚函数,在子类中重新定义了这个虚函数,这种情况是重写

++i实现

1
2
3
4
5
int&  int::operator++()
{
*this +=1;
return *this;
}

i++实现

1
2
3
4
5
const int  int::operator(int){
int oldValue = *this;
++(*this);
return oldValue;
}

如何在 main() 执行之前先运行其它函数

  • C++的全局对象的构造函数会在main函数之前运行
  • 全局static变量的初始化在程序初始阶段,先于main函数的执行,所以可以利用这一点。在leetcode里经常见到利用一点,在main之前关闭cin与stdin的同步来“加快”速度的黑科技:
1
2
3
4
static int _ = []{
cin.sync_with_stdio(false);
return 0;
}();
  • 使用attribute关键字,attribute((constructor))是gcc扩展,标记这个函数应当在main函数之前执行。同样有一个attribute((destructor)),标记函数应当在程序结束之前(main结束之后,或者调用了exit后)执行
    1
    2
    3
    4
    5
    6
    7
    8
    9
    __attribute((constructor))void before()
    {
    printf("before main\n");
    }

    __attribute((destructor))void end()
    {
    printf("end main\n");
    }

区域

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

char * brr = “123”;

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

const char crr[] = “123”;

//这里123本来是在栈上的,但是编译器可能会做某些优化,将其放到常量区

char drr[] = “123”;

//字符串123保存在栈区,可以通过drr去修改

RTTI

运行时类型检查,在C++层面主要体现在dynamic_cast和typeid,VS中虚函数表的-1位置存放了指向type_info的指针。对于存在虚函数的类型,typeid和dynamic_cast都会去查询type_info

C++中拷贝赋值函数的形参能否进行值传递?

不能。如果是这种情况下,调用拷贝构造函数的时候,首先要将实参传递给形参,这个传递的时候又要调用拷贝构造函数。。如此循环,无法完成拷贝,栈也会满。

set和map

map和set都是C++的关联容器,其底层实现都是红黑树(RB-Tree)。由于 map 和set所开放的各种操作接口,RB-tree 也都提供了,所以几乎所有的 map 和set的操作行为,都只是转调 RB-tree 的操作行为。
map和set区别在于:

(1)map中的元素是key-value(关键字—值)对:关键字起到索引的作用,值则表示与索引相关联的数据;Set与之相对就是关键字的简单集合,set中每个元素只包含一个关键字。

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

(3)map支持下标操作,set不支持下标操作。map可以用key做下标,map的下标运算符[ ]将关键码作为下标去执行查找,如果关键码不存在,则插入一个具有该关键码和mapped_type类型默认值的元素至map中,因此下标运算符[ ]在map应用中需要慎用,const_map不能用,只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用,mapped_type类型没有默认值也不应该使用。如果find能解决需要,尽可能用find。

请你来说一说STL迭代器删除元素

参考回答:
这个主要考察的是迭代器失效的问题。1.对于序列容器vector,deque来说,使用erase(itertor)后,后边的每个元素的迭代器都会失效,但是后边每个元素都会往前移动一个位置,但是erase会返回下一个有效的迭代器;2.对于关联容器map set来说,使用了erase(iterator)后,当前元素的迭代器失效,但是其结构是红黑树,删除当前元素的,不会影响到下一个元素的迭代器,所以在调用erase之前,记录下一个元素的迭代器即可。3.对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此上面两种正确的方法都可以使用。

请你说一说vector和list的区别,应用,越详细越好

参考回答:
1、概念:
(1)Vector

连续存储的容器,动态数组,在堆上分配空间

底层实现:数组

两倍容量增长:

vector 增加(插入)新元素时,如果未超过当时的容量,则还有剩余空间,那么直接添加到最后(插入指定位置),然后调整迭代器。

如果没有剩余空间了,则会重新配置原有元素个数的两倍空间,然后将原空间元素通过复制的方式初始化新空间,再向新空间增加元素,最后析构并释放原空间,之前的迭代器会失效。

性能:

访问:O(1)

插入:在最后插入(空间够):很快

在最后插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。

在中间插入(空间够):内存拷贝

在中间插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。

删除:在最后删除:很快

在中间删除:内存拷贝

适用场景:经常随机访问,且不经常对非尾节点进行插入删除。

2、List

动态链表,在堆上分配空间,每插入一个元数都会分配空间,每删除一个元素都会释放空间。

底层:双向链表

性能:

访问:随机访问性能很差,只能快速访问头尾节点。

插入:很快,一般是常数开销

删除:很快,一般是常数开销

适用场景:经常插入删除大量数据

2、区别:

1)vector底层实现是数组;list是双向 链表。

2)vector支持随机访问,list不支持。

3)vector是顺序内存,list不是。

4)vector在中间节点进行插入删除会导致内存拷贝,list不会。

5)vector一次性分配好内存,不够时才进行2倍扩容;list每次插入新节点都会进行内存申请。

6)vector随机访问性能好,插入删除性能差;list随机访问性能差,插入删除性能好。

3、应用

vector拥有一段连续的内存空间,因此支持随机访问,如果需要高效的随即访问,而不在乎插入和删除的效率,使用vector。

list拥有一段不连续的内存空间,如果需要高效的插入和删除,而不关心随机访问,则应使用list。

请你来说一下STL中迭代器的作用,有指针为何还要迭代器

参考回答:
1、迭代器
Iterator(迭代器)模式又称Cursor(游标)模式,用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解:Iterator模式是运用于聚合对象的一种模式,通过运用该模式,使得我们可以在不知道对象内部表示的情况下,按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。

由于Iterator模式的以上特性:与聚合对象耦合,在一定程度上限制了它的广泛运用,一般仅用于底层聚合支持类,如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

2、迭代器和指针的区别

迭代器不是指针,是类模板,表现的像指针。他只是模拟了指针的一些功能,通过重载了指针的一些操作符,->、*、++、—等。迭代器封装了指针,是一个“可遍历STL( Standard Template Library)容器内全部或部分元素”的对象, 本质是封装了原生指针,是指针概念的一种提升(lift),提供了比指针更高级的行为,相当于一种智能指针,他可以根据不同类型的数据结构来实现不同的++,—等操作。

迭代器返回的是对象引用而不是对象的值,所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。

3、迭代器产生原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来,使得不用暴露集合内部的结构而达到循环遍历集合的效果。

请你回答一下什么是右值引用,跟左值又有什么区别?

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

  1. 消除两个对象交互时不必要的对象拷贝,节省运算存储资源,提高效率。

  2. 能够更简洁明确地定义泛型函数。

左值和右值的概念:

左值:能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。

右值:不能对表达式取地址,或匿名对象。一般指表达式结束就不再存在的临时对象。

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

  1. 左值可以寻址,而右值不可以。

  2. 左值可以被赋值,右值不可以被赋值,可以用来给左值赋值。

  3. 左值可变,右值不可变(仅对基础类型适用,用户自定义类型右值引用可以通过成员函数改变)。

请你回答一下malloc的原理,另外brk系统调用和mmap系统调用的作用分别是什么?

参考回答:
Malloc函数用于动态分配内存。为了减少内存碎片和系统调用的开销,malloc其采用内存池的方式,先申请大块内存作为堆区,然后将堆区分为多个内存块,以块作为内存管理的基本单位。当用户申请内存时,直接从堆区分配一块合适的空闲块。Malloc采用隐式链表结构将堆区分成连续的、大小不一的块,包含已分配块和未分配块;同时malloc采用显示链表结构来管理所有的空闲块,即使用一个双向链表将空闲块连接起来,每一个空闲块记录了一个连续的、未分配的地址。
当进行内存分配时,Malloc会通过隐式链表遍历所有的空闲块,选择满足要求的块进行分配;当进行内存合并时,malloc采用边界标记法,根据每个块的前后块是否已经分配来决定是否进行块合并。

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

请你说一说C++的内存管理是怎样的

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

数据段:存储程序中已初始化的全局变量和静态变量

bss 段:存储未初始化的全局变量和静态变量(局部+全局),以及所有被初始化为0的全局变量和静态变量。

堆区:调用new/malloc函数时在堆区动态分配内存,同时需要调用delete/free来手动释放申请的内存。

映射区:存储动态链接库以及调用mmap函数进行的文件映射

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

静态区域:

text segment(代码段):包括只读存储区和文本区,其中只读存储区存储字符串常量,文本区存储程序的机器代码。

data segment(数据段):存储程序中已初始化的全局变量和静态变量

bss segment:存储未初始化的全局变量和静态变量(局部+全局),以及所有被初始化为0的全局变量和静态变量,对于未初始化的全局变量和静态变量,程序运行main之前时会统一清零。即未初始化的全局变量编译器会初始化为0

动态区域:

heap(堆): 当进程未调用malloc时是没有堆段的,只有调用malloc时采用分配一个堆,并且在程序运行过程中可以动态增加堆大小(移动break指针),从低地址向高地址增长。分配小内存时使用该区域。 堆的起始地址由mm_struct 结构体中的start_brk标识,结束地址由brk标识。

memory mapping segment(映射区):存储动态链接库等文件映射、申请大内存(malloc时调用mmap函数)

stack(栈):使用栈空间存储函数的返回地址、参数、局部变量、返回值,从高地址向低地址增长。在创建进程时会有一个最大栈大小,Linux可以通过ulimit命令指定。

空间配置器

对象构造和析构器

1
2
3
4
5
6
7
8
9
10
11
inline void construct(T1* p,  const T2& value) {
new (p) T1(value);
// 此处为placement new运算符,不分配空间,在指针p所在位置建立对象(调用T1构造函数)
}

inline void destroy(T* p) {
p->~T();
// 对于placement new运算符,需要调用析构函数而不是使用delete
}

destroy对于char、wchar进行特化处理(空操作)

空间配置和释放

底层使用malloc和free

一级配置器(大于128字节时)

  • 直接使用malloc
  • 模拟了new的分配失败处理机制,可以自定义处理函数

二级配置器(小于等于128字节)

  • 维护16个自由链表(从8->16->24—>32….->128)
  • 为节省内存,链表结点使用联合体结构。
  • 会自动将请求内存上调为8的倍数
  • 过程如下
    1
    2
    3
    4
    1. 若链表有可用区块,直接返回
    2. 调用refill(n),n为上调8倍数后的值。
    3. refill调用chunk_alloc(n, &count);配置count个大小为n的区块,默认为20个。注意count为引用传参,可能配置得区块数目不为20个,配置数目会返回到count变量上。若只得到一个区块就返回给客户,若有多余的区块就配置到链表上。
    4. chunk_alloc函数从内存池从获取区块。若内存池足够配置要求的总字节数或者只能供应一个区块则返回,否则将参与零头分配给适当的链表后再次调用malloc扩充内存池大小。新大小为原来的两倍再加上一个随配置次数递增的变量。

迭代器

特性萃取iterator_traits

  • 负责萃取迭代器的特性

    1
    2
    3
    4
    5
    iterator_categpry   
    value_type
    pointer
    reference
    difference_type
  • 对原生指针和指向常量的指针做模板偏特化处理。

  • 五大迭代器(为五个空类,因为要做模板参数)

    1
    2
    3
    4
    5
    Input Iterator  只读
    Output ... 只写
    Forward ... 允许读写
    Bidirectional ...可双向移动(添加--操作)
    Rando Access ...可随机移动(添加+-n操作,以及指针的比较操作) 原生指针和指向常量的指针默认为该型别
  • 任一个迭代器型别应该属于其迭代器型别中最强的那个。但STL算法以岂能接受的最低阶迭代器来为其迭代器型别命名。

STL私房菜__type_traits

  • 负责萃取型别的特性,即某个型别是否具有无关痛痒的析构函数等。
  • 定义两个空类true_type和false_type表示是否。
  • 默认都定义为__false_type,即不具有无关痛痒的析构函数。这样是为了保守起见。对C++标量型别(int、char….)进行特化处理,定义为true_type。

序列式容器

vector

  • vertor提供的是Random Access迭代器,实质内部就用普通指针作为其迭代器。
  • vector当新增元素时超过其容量,若原大小为0则扩为1,否则会扩充至两倍,前半段用于放原数据。由于扩充过程会释放原来的空间,重新配置新的空间,因此指向原来vector的迭代器都会失效。为解决这个问题,在配置过程最后会是迭代器指向新的空间。

list

  • list为一个环状双向链表,其迭代器为Bidirectional,即不能随机访问。
  • list在尾部增加了一个空白节点,并且让一个指针node一直指向这个结点,由此满足前闭后开的要求。

    1
    2
    3
    4
    5
    6
    iterator begin() {
    return (link_type)((*node).next);
    }
    iterator void end() {
    return node;
    }
  • list插入和结合操作不会使迭代器失效,删除也只有被删除的结点的迭代器失效,其余结点不受影响。

关联式容器

关联式容器每个数据都有键和值组成,没有头和尾。

红黑树

特点:

  1. 每个结点非红即黑(null视为黑结点)。
  2. 根结点为黑。
  3. 父子结点不能同时为红。
  4. 从根结点到任一NULL结点的路径黑色结点数目一致。
  • 由于规则4,则新增结点必为红色,由规则3,新增结点其父节点一定为黑。
  • 插入规则,设X为新增结点,P为父节点,S为叔叔结点,G为祖父结点。本身为4状况:
  1. 若S为黑且X为外侧插入,则对P、G做一次单旋并改变颜色即可。
  2. 若S为黑且X为内侧插入,则对P、X做一次单旋并改变G、X颜色,在对G做一次单旋。
  3. 若S为红且为外侧插入,则先对PG单旋,并改变X的颜色,此时如果GG为黑则搞定。但若GG为红。则为第4中状况
  4. 若GG也为红色,则害的持续往上做状况3的1操作指导不再由父子均为红色。
  • 为避免状况4,STL中在插入前会先执行一段由上而下的程序

    1
    假设新增结点为X,从根结点到X待插入位置的路径,只要看到某结点A其两个子节点均为红,就把该节点改为红,两个子节点改为黑。修改后如果A的父节点也为红色(注意此时A的S结点绝不会为红),则就得像状况1一样做一次单旋并改颜色或者像状况2一样做双旋和改色。
  • 在执行了这个程序后,此时结点X的插入就很简单了。

  1. S为黑且为外侧插入,执行状况1操作。
  2. S为黑且为内侧,执行状况2操作。
  3. 否则就直接插入。
  • STL特别为根节点再设计了一个父节点header,header与root互为父节点。初始时候其左节点和右节点也指向root结点,当新增元素时候,会维护header令其:
  1. header父节点始终指向根节点
  2. header的左结点指向最小的元素。
  3. header右节点指向最大的元素。
  • STL红黑树提供两种插入:
  1. insert_unique(),表示插入值不能重复,若树中存在相同的键则不会插入。返回值为一个pair,其第一元素为新增结点迭代器,第二元素为插入成功与否的bool变量。
  2. insert_equal(),可重复插入。返回值为新增结点迭代器。

set

  • set的所有元素会根据键值自动排序(其键值就等于实值)。set不允许两个元素具有相同键值。
  • set元素的迭代器为底层红黑树的const_iterator,即不能通过迭代器修改set元素的值。
  • set新增和删除其迭代器不会失效,当然被删除的那个结点的迭代器肯定失效了。

map

  • map元素为pair,第一元素为键值,第二元素为实值。
  • map也不允许两个元素有相同键值。
  • map迭代器算半个常量迭代器,不可修改map元素的键值,但可以修改元素的实值。
  • map新增和删除其迭代器不会失效,当然被删除的那个结点的迭代器肯定失效了。

哈希表

  • STL哈希表采用开链法。
  • 哈希表的迭代器没有后退操作。
  • STL中哈希表其表格用vector实现,而每一个vector元素为一个桶子,其上可能有很多结点以链表形式相连。以质数来设计表格大小。预先将28个质数(逐渐约为2倍关系)(最小为53)计算好。

hash_set

  • 没有自动排序功能。其余与set机会相同。

hash_map

  • 同样无自动排序,其余与map基本相同。
Donate comment here