手撕code(1~5)

手撕code

01 交叉打印ABC

#include 
#include 
#include 
#include 

using namespace std;

int flag = 0;

mutex mtx;
condition_variable cv;

void printA() {
  unique_lock<mutex> lk(mtx);
  int count = 0;
  while (count < 10) {
    while (flag != 0) cv.wait(lk);
    cout << "thread 1: a" << endl;
    flag = 1;
    cv.notify_all();
    count++;
  }
  cout << "thread 1 has finsihed" << endl;
}

void printB() {
  unique_lock<mutex> lk(mtx);
  int count = 0;
  while (count < 10) {
    while (flag != 1) cv.wait(lk);
    cout << "thread 2: b" << endl;
    flag = 2;
    cv.notify_all();
    count++;
  }
  cout << "thread 2 has finsihed" << endl;
}

void printC() {
  unique_lock<mutex> lk(mtx);
  int count = 0;
  while (count < 10) {
    while (flag != 2) cv.wait(lk);
    cout << "thread 3: c" << endl;
    flag = 0;
    cv.notify_all();
    count++;
  }
  cout << "thread 3 has finsihed" << endl;
}

int main() {
  thread t1(printA);
  thread t2(printB);
  thread t3(printC);
  t1.join();
  t2.join();
  t3.join();

  system("pause");
  return 0;
}

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

运行结果：

02 智能指针

原理：利用栈上的对象出作用域自动析构的特征，采用了栈上面的指针去管理堆上面的内容

//不带引用计数智能指针
#include 

using namespace std;

template<typename T>
class SmartPtr {
public:
    SmartPtr(T* ptr = nullptr)
        :_mptr(ptr) {}
    ~SmartPtr() { delete _mptr; }
    T& operator*() { return *_mptr; }//传引用 传值 传*_mptr
    T* operator->() { return _mptr; }//传指针 传_mptr;
private:
    T* _mptr;
};

class Test {
public:
    void test() { cout << "call Test::test" << endl; }
};

int main() {
  SmartPtr<int> ptr1(new int);
  *ptr1 = 20;
  cout << *ptr1 << endl;

  SmartPtr<Test> ptr2(new Test());
  ptr2->test();

  system("pause");
  return 0;
}
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

运行结果：

//带引用计数智能指针
#include 
#include 

using namespace std;

template<typename T> 
class RefCnt
{
public:
	RefCnt(T *ptr = nullptr):mptr (ptr)
	{
		if (mptr != nullptr)
			mcount = 1;
	}
	void addRef(){ mcount++; }//增加引用计数
	int delRef(){ return --mcount;}//减少引用计数
private :
	T *mptr;
	int mcount;
};

template<typename T>
class Csmartptr
{
public:
	Csmartptr(T* ptr = nullptr) :mptr(ptr) 				
	{
		mpRefCnt = new RefCnt<T>(mptr);
	}
	/*Csmartptr(const Csmartptr &src)
	{
		mptr = new T(*src .mptr) ;
	}*/
	~Csmartptr() 
	{ 
		if (0 == mpRefCnt->delRef () )
		{
			delete mptr; 
			mptr = nullptr;
		}
	}
	T& operator*() { return *mptr; }
	T* operator->() {return mptr; }

	Csmartptr(const Csmartptr<T> &src):mptr(src.mptr), mpRefCnt(src.mpRefCnt)
	{
		if (mptr != nullptr)
		mpRefCnt->addRef() ;
	}

	Csmartptr<T>& operator= (const Csmartptr<T> &src)
	{
		if (this == &src)
			return *this;
		//删除原有对象指向的资源
		if (0 == mpRefCnt->delRef () )
		{
			delete mptr;
		}
		mptr = src.mptr;
		mpRefCnt = src.mpRefCnt ;
		mpRefCnt->addRef () ;
		return *this;
	}

private:
	T* mptr;//指向资源的指针
	RefCnt<T> *mpRefCnt;//指向该资源引用计数对象的指针
};


int main() {
    Csmartptr<int> ptr1 (new int) ;
    Csmartptr<int> ptr2(ptr1) ;
    Csmartptr<int> ptr3;
    ptr3 = ptr2;
    *ptr1 = 20;
    cout << *ptr2 << " " << *ptr3 << endl ;

    system("pause");
    return 0;
}
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

（1）auto_ptr c++98引入

拷贝构造时，将原先的auto_ptr对象置为空，而通常我们说赋值或者拷贝的时候应该两个对象具有相同的值

缺点：

不能使用auto_ptr指向动态分配的数组的指针，因为当释放对象的时候它使用的只是一个普通的delete操作符。不是delete[]
尽量不要对他进程赋值和拷贝
不能使用两个auto_ptr对象指向同一对象，这会导致对空间析构两次

（2）scoped_ptr

方便管理单个堆内存对象，但是scoped_ptr独享所有权，避免了auto_ptr的烦恼，主要的设计思想就是防拷贝，底层源码直接delete掉了

（3）unique_ptr C++11

unique_ptr 独享所有权语义，转移一个unique_ptr将会把所有权全部从源指针转移给目标指针，源指针被置空；所以unique_ptr不支持普通的拷贝和赋值操作，配合move移动语义（类型强转强制把左值转为右值）。

（4）shared_ptr C++11 带引用计数

采用引用计数的方法，允许多个智能指针指向同一个对象，指向该对象的所有智能指针内部的引用计数会加1，每减少一个智能指针指向对象时引用计数减一，当引用计数为0时自动析构

（5）weak_ptr C++11 不带引用计数

主要为了解决引用计数形成的问题也就是循环引用，即互相交叉引用，这样两个指针指向的内存都无法被释放，需要weak_ptr打破环形引用。weak_ptr是为了配合强指针而引入的弱指针，它指向由shared_ptr指向的对象同时不会影响对象的生命周期，它的构造和析构不改变引用计数。

当使用shared_ptr指向对方的对象的时候，使用weak_ptr就不会出现资源无法释放

循环引用问题：

总结来说无法释放内存的原因是，由于对象是动态分配的，而对象本身又含有shared_ptr指针，释放对象需要shared_ptr的释放使引用计数减为零，而shared_ptr的释放又需要对象的释放，两者互相等待对方先释放，往往是两者都无法释放。

03 设计模式

单例模式

//懒汉式单例模式
#include

using namespace std;


//懒汉式单例模式
class SingleTon {
public:
    static SingleTon* getInstance() {
        cout << "SingleTon::getInstance()" << endl;
        return &instance;
    }
private:
    SingleTon() {
        cout << "Singleton()" << endl;
    }
    static SingleTon instance;
    SingleTon(const SingleTon&) = delete;
    SingleTon& operator=(const SingleTon&) = delete;
};
SingleTon SingleTon::instance;

int main() {
    SingleTon* p1 = SingleTon::getInstance();
    SingleTon* p2 = SingleTon::getInstance();
    SingleTon* p3 = SingleTon::getInstance();

    system("pause");
    return 0;
}
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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y2L5hk51-1662965236503)(…/…/…/…/…/…/AppData/Roaming/Typora/typora-user-images/image-20220906095240291.png)]

//饿汉式单例模式
#include

using namespace std;

class SingleTon {
public:
    static SingleTon* getInstance() {
        static SingleTon instance;
        cout << "SingleTon::getInstance()" << endl;
        return &instance;
    }
private:
    SingleTon() {
        cout << "SingleTon()" << endl;
    }

    SingleTon(const SingleTon&) = delete;
    SingleTon& operator=(const SingleTon&) = delete;

};
int main() {
    SingleTon* p1 = SingleTon::getInstance();
    SingleTon* p2 = SingleTon::getInstance();
    SingleTon* p3 = SingleTon::getInstance();

    system("pause");
    return 0;
}
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

工厂模式

简单工厂模式

#include
using namespace std;

enum Type {
    type1,
    type2
};

class product {
public:
    virtual void show() = 0;
};

class productA : public product{
public:
    void show() {
        cout << "productA" << endl;
    }
};

class productB : public product{
public:
    void show() {
        cout << "productB" << endl;
    }
};

class Factory {
public:
    product *Create(enum Type type) {
        switch(type) {
            case type1:
                return new productA();
            case type2:
                return new productB();
            default:
                break;
        }
    }
};

int main() {
    Factory factory;
    factory.Create(type1)->show();
    factory.Create(type2)->show();
    system("pause");
    return 0;
}
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

04 move与forward

左值：能在内存中取得地址，即是左值左值持久左值通常是变量

右值：在内存中无法取得地址的是右值右值短暂右值通常是表达式求值过程中创建的临时对象

左值引用：绑定到确定存储空间以及变量名的对象上，表达式结束后对象依然存在

右值引用：绑定到要求转换的表达式、字面常量、返回右值的临时对象上，表达式结束后对象就会销毁

move移动语义的基本实现原理：

引用折叠

左值引用 + 左值引用 = 左值引用

左值引用 + 右值引用 = 左值引用

右值引用 + 左值引用 = 左值引用

右值引用 + 右值引用 = 右值引用

move：使用移动语义，强制把一个左值转为右值，减少了一次临时对象的创建，提升效率

forward：完美转发在函数模板中，完全按照模板参数的类型传递给调用的另一个函数，侦测是左值还是右值，然后进行对应类型的转发

#include

using namespace std;

void other_func(int& a) {
    cout << "int&" << endl;
}

void other_func(int&& a) {
    cout << "int&&" << endl;
}

void other_func(const int& a) {
    cout << "const int&" << endl;
}

void other_func(const int&& a) {
    cout << "const int&&" << endl;
}

template<typename T>
void func(T&& t) {
    other_func(forward<T>(t));
}
int main() {
    int a = 0;
    int b = 0;
    const int c = 0;
    const int d = 0;

    other_func(a);
    other_func(move(b));
    other_func(c);
    other_func(move(c));

    system("pause");
    return 0;
}
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

05 排序算法

冒泡排序

#include
#include

using namespace std;

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    bool flag = false;
    for (int i = 0; i < n - 1; i++) {
        flag = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

int main() {
    int val;
    vector<int> nums;
    while (cin >> val) {
        nums.push_back(val);
        if (cin.get() == '\n') break;
    }
    bubbleSort(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    system("pause");
    return 0;
}
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

选择排序

#include
#include

using namespace std;

void choiceSort(vector<int>& nums) {
    int n = nums.size();
    int minIndex = 0;
    for (int i = 0; i < n; i++) {
        minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) minIndex = j;
        }
        swap(nums[i], nums[minIndex]);
    }
}

int main() {
    int val;
    vector<int> nums;
    while (cin >> val) {
        nums.push_back(val);
        if (cin.get() == '\n') break;
    }
    choiceSort(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    system("pause");
    return 0;
}
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

插入排序

#include
#include

using namespace std;

void insertSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        int val = nums[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (nums[j] <= val) break;
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = val;
    }
}

int main() {
    int val;
    vector<int> nums;
    while (cin >> val) {
        nums.push_back(val);
        if (cin.get() == '\n') break;
    }
    insertSort(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    system("pause");
    return 0;
}
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

希尔排序

#include
#include

using namespace std;

void shellSort(vector<int>& nums) {
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int val = nums[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (nums[j] <= val) break;
                nums[j + gap] = nums[j];
            }
            nums[j + gap] = val;
        }
    }
}

int main() {
    int val;
    vector<int> nums;
    while (cin >> val) {
        nums.push_back(val);
        if (cin.get() == '\n') break;
    }
    shellSort(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    system("pause");
    return 0;
}
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

快速排序

#include
using namespace std;
#include 

void quickSort(vector<int>& nums, int begin, int end) {  //数组可以直接传递 vector对象必须要引用传递 值传递无法改变实参
    if (begin >= end) return;

    //选择基准数
    int l = begin, r = end;
    int val = nums[l];

    // 一次快排处理
    while (l < r) {
        while (l < r && nums[r] > val) {
            r--;
        } 
        if (l < r) {
            nums[l] = nums[r];
            l++;
        }

        while (l < r && nums[l] < val) {
            l++;
        }
        if (l < r) {
            nums[r] = nums[l];
            r--;
        }
    }
   
    //直至 l == r
    nums[l] = val;

    //递归两端
    quickSort(nums, begin, l - 1);
    quickSort(nums, l + 1, end);
}

int main() {
    int data;
    vector<int> nums;
    while (cin >> data) {
        nums.push_back(data);
        if (cin.get() == '\n') break;
    }
    int n = nums.size(); 
    
    quickSort(nums, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}
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

归并排序

#include
using namespace std;
#include 

void mergeSort(vector<int>& nums, int begin, int end, int* p) {  //数组可以直接传递 vector对象必须要引用传递 值传递无法改变实参
    if (begin >= end) return;

    int mid = (begin + end) / 2;
    // 先递
    mergeSort(nums, begin, mid, p);
    mergeSort(nums, mid + 1, end, p);

    //再归并
    int index = 0;
    int i = begin;
    int j = mid + 1;

    while (i <= mid && j <= end) {
        if (nums[i] <= nums[j]) {
            p[index++] = nums[i++];
        } else {
            p[index++] = nums[j++];
        }
    }

    while (i <= mid) {
        p[index++] = nums[i++];
    }

    while (j <= end) {
        p[index++] = nums[j++];
    }

    for (i = begin, j = 0; i <= end; i++, j++) {
        nums[i] = p[j];
    }
}

int main() {
    int data;
    vector<int> nums;
    while (cin >> data) {
        nums.push_back(data);
        if (cin.get() == '\n') break;
    }
    int n = nums.size(); 
    
    int* p = new int[n];
    mergeSort(nums, 0, n - 1, p);
    delete[] p;

    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}
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

堆排序

#include
#include

using namespace std;

//堆的下沉调整  大根堆
void siftDown(vector<int>& arr, int i, int size) {
    int val = arr[i];
    while (i < size / 2) {   // i <= (size - 2) / 2 = size / 2 - 1  等价于 i < size / 2 
        int child = 2 * i + 1;   //左孩子
        if (child + 1 < size && arr[child + 1] > arr[child]) {
            child = child + 1; // 记录值比较大的孩子
        }

        if (arr[child] > val) {
            arr[i] = arr[child];
            i = child; // i继续指向它的孩子，继续调整，一直调整到最后有孩子的节点处
        } else {
            break;
        }
        arr[i] = val;
    }
}

void heap_Sort(vector<int>& arr, int size) {
    int n = size - 1;

    // 从第一个非叶子节点  成为大根堆
    for (int i = (n - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, size);
    }
    //把堆顶元素和末尾元素进行交换，从堆顶进行下沉操作  只是大根堆 并非升序
    for (int i = n; i >= 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        siftDown(arr, 0, i); //第三个参数表示参与调整元素的个数
    }

}

int main() {
    int data;
    vector<int> nums;
    while (cin >> data) {
        nums.push_back(data);
        if (cin.get() == '\n') break;
    }
    int size = nums.size();
    heap_Sort(nums, size);

    for (int val : nums) {
        cout << val << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}
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

基数排序

#include
#include
#include

using namespace std;


//基数排序
void radixSort(vector<int>& nums) {
    int n = nums.size();
    int maxData = nums[0];

    //获取最大值 以及桶排序的趟数（位数）
    for (int i = 1; i < n; i++) {
        if (maxData < nums[i]) {
            maxData = nums[i];
        }
    }
    cout << maxData << endl;

    int len = to_string(maxData).size();

    // 存储桶
    vector<vector<int>> vecs;
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < len; mod *= 10, dev *= 10, i++) {   // o(d) d:数据长度
        vecs.resize(10);  // 0-9号桶  改为20个桶 为了能处理负数 -9 到 9

        for (int j = 0; j < n; j++) {   //o(n)
            //得到当前元素第i个位置的数字
            int index = nums[j] % mod / dev; // 0-9 放负数 10-19 放正数
            vecs[index].push_back(nums[j]);
        }

        //依次遍历所有的桶，把元素拷贝回原始数组中
        int idx = 0;
        for (auto vec : vecs) {    //o(20)
            for (int v : vec) {    //o(n) * o(20) = o(20n) = o(n) 与上面的o(n) 并列
                nums[idx++] = v;
            }
        }
        //清空所有元素
        vecs.clear();
    }
}
//整体复杂度为  时间 o(nd) 空间o(n) 稳定性：稳定排序 不改变相同的元素的顺序

int main() {
    int val;
    vector<int> nums;
    while (cin >> val) {
        nums.push_back(val);
        if (cin.get() == '\n') break;
    }
    radixSort(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    system("pause");
    return 0;
}
//浮点数 、 负数无法处理
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

相关阅读:
设计模式案例
 Megatron-LM GPT 源码分析（三） Pipeline Parallel分析
 Nacos——注册中心源码详解
 python经典百题之特殊图形打印
 【UI自动化】通过剪切板发送文本
 Python应用：画出任意二维函数的轨迹
 4、Ribbon负载均衡
 【电路笔记】-欧姆定律
 【译】宣布在 Visual Studio 17.10 预览2中为 ARM64 架构提供 SSDT
通用游戏服务器架构设计
原文地址：https://blog.csdn.net/qq_41945053/article/details/126817265