23.常用代码

0.C++万能库

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    std::getline(std::cin, input); //可以输入带空格的字符串
    while (cin >> a >> b) {
        if (a == 0 && b == 0) break;
        cout << a + b << endl;
    }
}

1.排序类

快排

void QuichSort(vector<int> &arr,int start,int end) //快排需要传入 开始 结束
{
    if(end <= start) return; //结束条件为开始大于等于结束
    int left = start,right = end,cur = arr[start]; //定义left，right以及cur（左边第一个值）
    while(left < right) //循环遍历
    {
        while(left < right && arr[right] >= cur) right--; //找到右边比cur小的数
        arr[left] = arr[right]; //将其交换到左边
        while(left < right && arr[left] <= cur) left++;//找到左边比cur大的数
        arr[right] = arr[left];//将其交换到右边
    }
    arr[left] = cur;//将cur 放到中间，保证cur左边小于，右边大于
    QuichSort(arr,0,left - 1); //递归遍历左边
    QuichSort(arr,left + 1,end); //递归遍历右边
}

归并

这里注意，对比的是temp：if(temp[start] > temp[end]) arr[cnt++] = temp[end++];

void Sort(vector<int> &arr) //快排需要传入 开始 结束
{
    vector<int> temp = arr;
    function<void(int,int)> MySort = [&](int left, int right){
        if(left >= right) return;
        //先拆分
        int mid = (left + right) / 2;
        MySort(left,mid);
        MySort(mid + 1,right);
        //后排序，此时arr在（left,mid）,(mid,right)是有序的，需要合并至temp
        int start = left, end = mid + 1,cnt = start; //注意这里，开始的合并的初始化
        for(int i = left; i <= right;i++) temp[i] = arr[i]; //先进行拷贝
        //进行合并
        while(start <= mid && end <= right)
        {
            if(temp[start] > temp[end]) arr[cnt++] = temp[end++]; //这里注意，对比的是temp
            else arr[cnt++] = temp[start++];
        }
        while(start <= mid) arr[cnt++] = temp[start++];
        while(end <= right) arr[cnt++] = temp[end++];

    };
    MySort(0,arr.size() - 1);
}

快速幂运算求-Pow

double myPow2(double x, long long n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n < 0) return 1 / myPow2(x, abs(n));
        //现在是正数了
        double temp = myPow2(x, n / 2);
        return n % 2 == 0 ? temp * temp : temp * temp * x;
    }

2.其余类

二叉数的迭代遍历

//前序遍历 -> 中 左 右
vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode* > st; //使用栈
        st.push(root);
        while(!st.empty())
        {
            TreeNode* top = st.top();
            st.pop();
            res.push_back(top->val); //中
            if(top->right) st.push(top->right); //右 -> 右边节点先入栈，后出
            if(top->left) st.push(top->left); //左-> 右边节点后入栈，先出
        }
        return res;
}

//中序遍历
vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        while(!st.empty() || root)
        {
            if(root)
            {
                st.push(root);
                root = root->left;
            }
            else
            {
                TreeNode* top = st.top();
                st.pop();
                res.push_back(top->val);
                root = top->right;
            }   
        }
        return res;
    }


//后序遍历 -> 左 右 中（可以由前序遍历改 中右左）反序得到
vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode* > st; //使用栈
        st.push(root);
        while(!st.empty())
        {
            TreeNode* top = st.top();
            st.pop();
            res.push_back(top->val); //中
            if(top->left) st.push(top->left); //左-> 右边节点后入栈，先出
            if(top->right) st.push(top->right); //右 -> 右边节点先入栈，后出
        }
        reverse(res.begin(),res.end());
        return res;
    }

智能指针sheard_ptr

#include <iostream>
#include <mutex>

template <typename T>
class SharedPtr {
private:
    T* data;
    size_t* count;
    std::mutex mtx;  // 添加互斥锁

public:
    // 构造函数
    SharedPtr(T* ptr = nullptr) : data(ptr), count(new size_t(1)) {}

    // 拷贝构造函数
    SharedPtr(const SharedPtr& other) : data(other.data), count(other.count) {
        std::lock_guard<std::mutex> lock(mtx);  // 加锁
        (*count)++;
    }

    // 赋值运算符重载
    SharedPtr& operator=(const SharedPtr& other) {
        if (this != &other) {
            // 减少旧对象的引用计数
            release();

            // 复制新对象的数据
            std::lock_guard<std::mutex> lock(mtx);  // 加锁
            data = other.data;
            count = other.count;

            // 增加新对象的引用计数
            (*count)++;
        }
        return *this;
    }

    // 析构函数
    ~SharedPtr() {
        release();
    }

    // 解引用运算符重载
    T& operator*() const {
        return *data;
    }

    // 成员访问运算符重载
    T* operator->() const {
        return data;
    }

private:
    // 释放资源的辅助函数
    void release() {
        if (count != nullptr) {
            std::lock_guard<std::mutex> lock(mtx);  // 加锁
            (*count)--;
            if (*count == 0) {
                delete data;
                delete count;
            }
        }
    }
};

int main() {
    SharedPtr<int> ptr1(new int(42));
    SharedPtr<int> ptr2 = ptr1;

    std::cout << "ptr1: " << *ptr1 << std::endl;
    std::cout << "ptr2: " << *ptr2 << std::endl;

    return 0;
}

线程池

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>

class ThreadPool {
public:
    // 构造函数，初始化线程池
    ThreadPool(size_t numThreads) : stop(false) {
        // 创建指定数量的工作线程，并将它们添加到线程池中
        for (size_t i = 0; i < numThreads; ++i) {
            workers.emplace_back([this] {
                // 线程主循环
                while (true) {
                    std::function<void()> task;

                    {
                        // 使用互斥锁保护任务队列
                        std::unique_lock<std::mutex> lock(queueMutex);

                        // 使用条件变量等待任务队列不为空或停止信号
                        condition.wait(lock, [this] { return stop || !tasks.empty(); });

                        // 如果收到停止信号且任务队列为空，线程退出
                        if (stop && tasks.empty()) {
                            return;
                        }

                        // 取出队列头部的任务
                        task = std::move(tasks.front());
                        tasks.pop();
                    }

                    // 执行取出的任务
                    task();
                }
            });
        }
    }

    // 将任务加入到任务队列
    template<class F>
    void enqueue(F&& func) {
        {
            // 使用互斥锁保护任务队列
            std::unique_lock<std::mutex> lock(queueMutex);
            
            // 将任务移动到队列中
            tasks.emplace(std::forward<F>(func));
        }

        // 通知一个等待中的线程有新任务可以执行
        condition.notify_one();
    }

    // 析构函数，停止线程池，并等待所有线程结束
    ~ThreadPool() {
        {
            // 使用互斥锁保护停止信号
            std::unique_lock<std::mutex> lock(queueMutex);
            stop = true;
        }

        // 唤醒所有等待中的线程
        condition.notify_all();

        // 等待所有线程结束
        for (std::thread &worker : workers) {
            worker.join();
        }
    }

private:
    // 工作线程
    std::vector<std::thread> workers;
    
    // 任务队列
    std::queue<std::function<void()>> tasks;
    
    // 互斥锁用于保护对任务队列的访问
    std::mutex queueMutex;
    
    // 条件变量用于通知工作线程有新任务
    std::condition_variable condition;
    
    // 停止信号，用于通知工作线程停止
    bool stop;
};

int main() {
    // 创建包含4个工作线程的线程池
    ThreadPool threadPool(4);

    // 向线程池中提交8个任务
    for (int i = 0; i < 8; ++i) {
        threadPool.enqueue([i] {
            // 打印任务信息和执行线程的ID
            std::cout << "Task " << i << " processed by thread " << std::this_thread::get_id() << std::endl;
        });
    }

    // 给予一些时间让任务被处理
    std::this_thread::sleep_for(std::chrono::seconds(2));

    return 0;
}

哈希表

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>

// HashNode表示哈希表中的一个节点
template <typename K, typename V>
struct HashNode {
    K key;
    V value;
};

// HashMap表示哈希表
template <typename K, typename V, typename Hash = std::hash<K>>
class HashMap {
private:
    std::vector<std::list<HashNode<K, V>>> buckets;
    Hash hashFunction;

public:
    HashMap(size_t size = 10) : buckets(size) {}

    // 插入键值对
    void insert(const K& key, const V& value) {
        size_t index = hashFunction(key) % buckets.size();
        auto& bucket = buckets[index];

        // 检查是否已经存在相同的键，如果是，更新值
        auto it = std::find_if(bucket.begin(), bucket.end(), [&key](const HashNode<K, V>& node) {
            return node.key == key;
        });

        if (it != bucket.end()) {
            it->value = value;
        } else {
            // 否则，在链表头部插入新节点
            bucket.push_front({key, value});
        }
    }

    // 查找键对应的值
    bool find(const K& key, V& value) const {
        size_t index = hashFunction(key) % buckets.size();
        const auto& bucket = buckets[index];

        // 在链表中查找键
        auto it = std::find_if(bucket.begin(), bucket.end(), [&key](const HashNode<K, V>& node) {
            return node.key == key;
        });

        // 如果找到了，返回对应的值
        if (it != bucket.end()) {
            value = it->value;
            return true;
        }

        return false; // 没找到
    }

    // 移除键值对
    void remove(const K& key) {
        size_t index = hashFunction(key) % buckets.size();
        auto& bucket = buckets[index];

        // 移除链表中的节点
        bucket.remove_if([&key](const HashNode<K, V>& node) {
            return node.key == key;
        });
    }
};

int main() {
    HashMap<std::string, int> myMap;

    myMap.insert("one", 1);
    myMap.insert("two", 2);
    myMap.insert("three", 3);

    int value;

    if (myMap.find("two", value)) {
        std::cout << "Value for key 'two': " << value << std::endl;
    } else {
        std::cout << "Key 'two' not found." << std::endl;
    }

    myMap.remove("two");

    if (myMap.find("two", value)) {
        std::cout << "Value for key 'two': " << value << std::endl;
    } else {
        std::cout << "Key 'two' not found." << std::endl;
    }

    return 0;
}

线程同步问题-3线程交替打印 1 - 100

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <atomic>

const int target = 100;

std::mutex mtx,numMutx;
std::condition_variable cv;
std::atomic<int> atomicInt(1);

void printNumber(int threadId, int mod) {
    while (atomicInt <= target) {
        std::unique_lock<std::mutex> lock(mtx);

        // 等待轮到当前线程打印
        cv.wait(lock, [threadId] { return (atomicInt % 3) == threadId; });
        if(atomicInt <= target) std::cout << "Thread " << threadId + 1 << ": " << atomicInt << std::endl;
        atomicInt++;
        
        cv.notify_all();
    }
}

int main() {
    std::thread t1(printNumber, 0, 3);
    std::thread t2(printNumber, 1, 3);
    std::thread t3(printNumber, 2, 3);

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

实现可能含交集的memcpy（memmove）

#include <iostream>

//考虑内存᯿叠的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;
}
 

int main() {
    char buffer[20] = "Hello, World!ABCD";
    
    // 将 "World!" 移动到 buffer 的开头
    memmove(buffer, buffer + 7, 10);

    std::cout << "Buffer: " << buffer << std::endl;

    return 0;
}

单例模式

饿汉

class Chairman
{
public:
    void print()
    {
        cout << "对象调用" << endl;
    }
private:
    Chairman()  //私有构造函数
    {
        cout << "创建chairman类" << endl;
    }
 
public:
    static Chairman* singleman;  //类内声明chairman对象指针
};
 
Chairman* Chairman::singleman = new Chairman;  //类外进行初始化
 
int main()
{
    cout << "main函数开始执行" << endl;
    Chairman::singleman->print();
 
    system("pause");
    return 0;
}

懒汉

#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;

///  内部静态变量的懒汉实现  //
class Singleton
{
public:
    ~Singleton(){
        std::cout<<"destructor called!"<<std::endl;
    }
    //或者放到private中
    Singleton(const Singleton&)=delete;
    Singleton& operator=(const Singleton&)=delete;
    static Singleton& get_instance(){
        //关键点！
        static Singleton instance;
        return instance;
    }
    //不推荐，返回指针的方式
    /*static Singleton* get_instance(){
        static Singleton instance;
        return &instance;
    }*/
private:
    Singleton(){
        std::cout<<"constructor called!"<<std::endl;
    }
};

无锁队列

#include <atomic>

template <typename T>
class LockFreeQueue {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data) : data(data), next(nullptr) {} // 节点构造函数
    };

    std::atomic<Node*> head; // 原子指针，指向队列头节点
    std::atomic<Node*> tail; // 原子指针，指向队列尾节点

public:
    LockFreeQueue() : head(nullptr), tail(nullptr) {} // 构造函数

    void enqueue(const T& value) {
        Node* newNode = new Node(value); // 创建新节点
        Node* oldTail = tail.exchange(newNode); // 原子替换尾指针，并返回之前的尾指针
        if (oldTail != nullptr) {
            oldTail->next = newNode; // 如果之前的尾指针不为空，更新之前尾节点的下一个节点为新节点
        } else {
            head.store(newNode); // 如果之前的尾指针为空，则表示队列为空，更新头指针为新节点
        }
    }

    bool dequeue(T& value) {
        Node* oldHead = head.load(); // 加载头指针的值
        if (oldHead == nullptr) {
            return false; // 如果头指针为空，表示队列为空，返回失败
        }

        if (oldHead->next == nullptr) { // 如果头节点的下一个节点为空，表示队列只有一个节点
            tail.compare_exchange_strong(oldHead, nullptr); // 原子比较并交换，将尾指针置为空
        }

        value = oldHead->data; // 获取头节点的数据
        head.store(oldHead->next); // 更新头指针为头节点的下一个节点
        delete oldHead; // 释放头节点的内存
        return true; // 返回成功
    }

    ~LockFreeQueue() { // 析构函数，释放队列中的所有节点
        T temp;
        while (dequeue(temp)); // 循环调用 dequeue 方法，直到队列为空
    }
};