一、單例模式優化實現

原代碼問題分析

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++八股文（完整版）<<