一、单例模式优化实现

原代码问题分析

1. ​内存序重排序风险​：双重检查锁在C++中可能因指令重排导致半初始化对象被访问
2. ​锁粒度过大​：每次获取实例都需要加锁，影响性能
3. ​线程安全性不足​：未考虑C++11前的内存模型问题

改进方案（C++11标准实现）

class Singleton {
public:static Singleton& getInstance() {static Singleton instance;  // C++11保证线程安全初始化return instance;}
private:Singleton() = default;~Singleton() = default;Singleton(const Singleton&) = delete;Singleton& operator=(const Singleton&) = delete;
};

技术要点​：

• 利用局部静态变量实现线程安全初始化（Meyers Singleton）
• 禁用拷贝构造和赋值操作
• 自动内存管理，无需手动释放

---

二、排序算法深度解析

1. 快速排序优化版

void quick_sort(int arr[], int l, int r) {if (l >= r) return;int pivot = arr[(l + r) / 2];  // 三数取中优化int i = l - 1, j = r + 1;while (i < j) {do i++; while (arr[i] < pivot);do j--; while (arr[j] > pivot);if (i < j) swap(arr[i], arr[j]);}quick_sort(arr, l, j);quick_sort(arr, j + 1, r);
}

优化点​：

• 三数取中法选择基准值
• 循环展开减少分支预测失败

2. 归并排序改进

void merge_sort(int arr[], int l, int r) {if (l >= r) return;int mid = l + (r - l) / 2;merge_sort(arr, l, mid);merge_sort(arr, mid + 1, r);vector<int> tmp(r - l + 1);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) tmp[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];while (i <= mid) tmp[k++] = arr[i++];while (j <= r) tmp[k++] = arr[j++];copy(tmp.begin(), tmp.end(), arr + l);
}

改进点​：

• 使用vector临时存储避免全局数组
• 尾递归优化减少栈空间消耗

---

三、KMP算法原理与实现

算法核心

1. ​前缀函数构建​：

vector<int> computeLPS(const string& p) {int n = p.size();vector<int> lps(n, 0);for (int i = 1, len = 0; i < n; ) {if (p[i] == p[len]) lps[i++] = ++len;else if (len) len = lps[len-1];else lps[i++] = 0;}return lps;
}

 2.​匹配过程​： 

void kmp(const string& text, const string& pattern) {auto lps = computeLPS(pattern);int i = 0, j = 0;while (i < text.size()) {if (text[i] == pattern[j]) {i++; j++;if (j == pattern.size()) {cout << "Found at " << i - j << endl;j = lps[j-1];}} else if (j) j = lps[j-1];else i++;}
}

技术优势​：

• 线性时间复杂度O(n+m)
• 避免主串回溯

---

四、LRU缓存机制实现

数据结构设计

class LRUCache {struct Node {int key, val;Node* prev, *next;Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}};
public:LRUCache(int capacity) : cap(capacity) {head = new Node(-1, -1);tail = new Node(-1, -1);head->next = tail;tail->prev = head;}int get(int key) {if (cache.count(key)) {auto node = cache[key];moveToHead(node);return node->val;}return -1;}void put(int key, int val) {if (cache.count(key)) {auto node = cache[key];node->val = val;moveToHead(node);} else {if (cache.size() == cap) {auto last = tail->prev;removeNode(last);cache.erase(last->key);delete last;}auto newNode = new Node(key, val);addToHead(newNode);cache[key] = newNode;}}
private:unordered_map<int, Node*> cache;Node* head, *tail;int cap;void addToHead(Node* node) { /*...*/ }void removeNode(Node* node) { /*...*/ }void moveToHead(Node* node) { /*...*/ }
};

实现要点​：

• 双向链表维护访问顺序
• 哈希表实现O(1)查找
• 虚拟头尾节点简化边界处理

---

五、字符串类安全实现

class SafeString {
public:SafeString(const char* str = "") {size_ = strlen(str);data_ = new char[size_ + 1];strncpy(data_, str, size_);data_[size_] = '\0';}SafeString(const SafeString& other) {size_ = other.size_;data_ = new char[size_ + 1];strcpy(data_, other.data_);}SafeString& operator=(const SafeString& other) {if (this != &other) {delete[] data_;size_ = other.size_;data_ = new char[size_ + 1];strcpy(data_, other.data_);}return *this;}~SafeString() { delete[] data_; }char& operator[](size_t index) {if (index >= size_) throw out_of_range("");return data_[index];}
private:char* data_;size_t size_;
};

安全改进​：

• 深拷贝避免浅拷贝问题
• 边界检查防止越界访问
• RAII内存管理

---

六、智能指针实现优化

template<typename T>
class SharedPtr {struct ControlBlock {size_t count;T* ptr;ControlBlock(T* p) : ptr(p), count(1) {}};
public:explicit SharedPtr(T* ptr = nullptr) : control_(ptr ? new ControlBlock(ptr) : nullptr) {}SharedPtr(const SharedPtr& other) : control_(other.control_) {if (control_) ++control_->count;}SharedPtr& operator=(const SharedPtr& other) {if (this != &other) {release();control_ = other.control_;if (control_) ++control_->count;}return *this;}~SharedPtr() { release(); }T* get() const { return control_ ? control_->ptr : nullptr; }size_t use_count() const { return control_ ? control_->count : 0; }
private:void release() {if (control_ && --control_->count == 0) {delete control_->ptr;delete control_;}}ControlBlock* control_;
};

关键改进​：

• 控制块独立管理引用计数
• 线程安全需增加原子操作
• 支持自定义删除器

---

>>>C/C++入门及练手项目<<<

七、其他重要知识点补充

1. ​main前执行函数​：

class Initializer {
public:Initializer() { /* main前执行代码 */ }
};
static Initializer init;

利用静态对象构造顺序特性[用户代码正确]

​2.管道通信优化​：

int pipefd[2];
if (pipe(pipefd) == -1) handle_error();
pid_t pid = fork();
if (pid == 0) { close(pipefd[1]);  // 子进程关闭写端//... 
} else {close(pipefd[0]);  // 父进程关闭读端//...
}

增加错误处理和资源管理[用户代码正确]

3.​rand7生成rand10优化​：

int rand10() {int a = rand7(), b = rand7();int num = (a-1)*7 + b;  // 1-49均匀分布return (num <= 40) ? (num % 10 + 1) : rand10();  // 拒绝采样
}

八、技术对比与选型建议

数据结构/算法	时间复杂度	空间复杂度	适用场景	优化方向
快速排序	O(n log n)	O(log n)	随机数据	三数取中+尾递归优化
归并排序	O(n log n)	O(n)	链表/大文件	自底向上迭代实现
LRU缓存	O(1)	O(capacity)	热点数据	多级缓存+预加载
KMP算法	O(n+m)	O(m)	字符串匹配	BM算法替代

 完整C++后端八股文：>> C++八股文（完整版）<<