面試題總結(jié)(四) – STL與算法篇

<1> 請(qǐng)列舉 C++ STL 中常用的容器（如 vector、list、map 等）及其特點(diǎn)。

vector (向量):

• 特點(diǎn): 動(dòng)態(tài)數(shù)組，內(nèi)存連續(xù)存儲(chǔ)，支持隨機(jī)訪問(wèn)，在尾部添加和刪除元素效率高，在中間插入和刪除元素效率低。
• 理由: 連續(xù)存儲(chǔ)使得隨機(jī)訪問(wèn)速度快，但中間插入刪除需要移動(dòng)大量元素。

list (鏈表):

• 特點(diǎn): 雙向鏈表，非連續(xù)存儲(chǔ)，在任意位置插入和刪除元素效率高，不支持隨機(jī)訪問(wèn)。
• 理由: 鏈表結(jié)構(gòu)決定了插入刪除操作只需修改指針，無(wú)需移動(dòng)元素，但隨機(jī)訪問(wèn)需要遍歷。

map (映射):

• 特點(diǎn): 基于紅黑樹(shù)實(shí)現(xiàn)的鍵值對(duì)數(shù)據(jù)結(jié)構(gòu)，按鍵有序存儲(chǔ)，查找、插入和刪除的平均時(shí)間復(fù)雜度為 O(log n)。
• 理由: 紅黑樹(shù)的特性保證了元素的有序性和較好的查找效率。

unordered_map (無(wú)序映射):

• 特點(diǎn): 基于哈希表實(shí)現(xiàn)，查找、插入和刪除的平均時(shí)間復(fù)雜度為 O(1)，元素?zé)o序。
• 理由: 哈希表的特性使得查找速度快，但不保證元素順序。

<2> 如何在 C++ 中使用 STL 算法（如排序、查找等）？

排序:

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> numbers = {5, 2, 8, 1, 3};std::sort(numbers.begin(), numbers.end());for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

理由: std::sort 函數(shù)接受兩個(gè)迭代器指定排序范圍，對(duì)范圍內(nèi)的元素進(jìn)行排序。

查找:

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> numbers = {5, 2, 8, 1, 3};auto it = std::find(numbers.begin(), numbers.end(), 8);if (it != numbers.end()) {std::cout << "找到了 8" << std::endl;} else {std::cout << "未找到 8" << std::endl;}return 0;
}

理由: std::find 函數(shù)返回指向找到元素的迭代器，如果未找到則返回結(jié)束迭代器。

<3> 解釋 STL 迭代器的概念和作用。

概念: 迭代器是一種用于遍歷容器中元素的工具。

作用: 1.提供統(tǒng)一的訪問(wèn)方式，使得不同容器的遍歷操作具有相似性；2.解耦算法和容器的具體實(shí)現(xiàn)，算法只需通過(guò)迭代器操作元素，無(wú)需關(guān)心容器的內(nèi)部結(jié)構(gòu)。

<4> C++ 中 map 和 unordered_map 的區(qū)別是什么？

存儲(chǔ)結(jié)構(gòu):

• map 基于紅黑樹(shù)，元素按鍵有序存儲(chǔ)。
• unordered_map 基于哈希表，元素?zé)o序存儲(chǔ)。

查找效率:

• 平均情況下，unordered_map 的查找、插入和刪除操作通常更快，時(shí)間復(fù)雜度接近 O(1)。
• map 的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為 O(log n)。

空間占用: unordered_map 通常需要更多的空間來(lái)存儲(chǔ)哈希表的相關(guān)信息。

迭代順序:

• map 按照鍵的升序迭代。
• unordered_map 的迭代順序是不確定的。

<5> 談?wù)?STL 中容器適配器（stack、queue、priority_queue）的使用。

stack (棧):

#include <iostream>
#include <stack>int main() {std::stack<int> myStack;myStack.push(1);myStack.push(2);myStack.push(3);std::cout << "棧頂元素: " << myStack.top() << std::endl;myStack.pop();std::cout << "棧頂元素: " << myStack.top() << std::endl;return 0;
}

理由: push 用于入棧，top 獲取棧頂元素，pop 彈出棧頂元素。

queue (隊(duì)列):

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;myQueue.push(1);myQueue.push(2);myQueue.push(3);std::cout << "隊(duì)頭元素: " << myQueue.front() << std::endl;myQueue.pop();std::cout << "隊(duì)頭元素: " << myQueue.front() << std::endl;return 0;
}

理由: push 用于入隊(duì)，front 獲取隊(duì)頭元素，pop 彈出隊(duì)頭元素。

priority_queue (優(yōu)先隊(duì)列):

#include <iostream>
#include <queue>int main() {std::priority_queue<int> myPriorityQueue;myPriorityQueue.push(1);myPriorityQueue.push(3);myPriorityQueue.push(2);std::cout << "隊(duì)頭元素: " << myPriorityQueue.top() << std::endl;myPriorityQueue.pop();std::cout << "隊(duì)頭元素: " << myPriorityQueue.top() << std::endl;return 0;
}

理由: push 用于入隊(duì)，top 獲取隊(duì)頭元素，pop 彈出隊(duì)頭元素。

<6> 如何自定義 C++ STL 容器的比較函數(shù)？

對(duì)于 map 或 set 等有序容器:

struct CustomComparator {bool operator()(const int& a, const int& b) {return a % 2 < b % 2;  // 按照奇數(shù)偶數(shù)比較}
};std::map<int, int, CustomComparator> myMap;

對(duì)于排序算法:

bool customSort(int a, int b) {return a > b;  // 降序排序
}std::vector<int> numbers = {5, 2, 8, 1, 3};
std::sort(numbers.begin(), numbers.end(), customSort);

<7> 描述 C++ 中算法的復(fù)雜度分析（時(shí)間復(fù)雜度和空間復(fù)雜度）。

時(shí)間復(fù)雜度: 表示算法執(zhí)行所需的時(shí)間與輸入規(guī)模之間的關(guān)系。

常見(jiàn)的時(shí)間復(fù)雜度有：O(1)（常數(shù)時(shí)間）、O(log n)（對(duì)數(shù)時(shí)間）、O(n)（線性時(shí)間）、O(n log n)、O(n^2) 等。

空間復(fù)雜度: 表示算法執(zhí)行所需的額外空間與輸入規(guī)模之間的關(guān)系。

例如，對(duì)于 std::sort 函數(shù)，其平均時(shí)間復(fù)雜度為 O(n log n)，空間復(fù)雜度為 O(log n)。

<8> 舉例說(shuō)明在 C++ 中如何使用 STL 進(jìn)行數(shù)據(jù)的批量處理。

假設(shè)要對(duì)一個(gè)整數(shù) vector 中的所有元素進(jìn)行平方操作:

#include <iostream>
#include <vector>
#include <algorithm>void square(int& num) {num *= num;
}int main() {std::vector<int> numbers = {1, 2, 3, 4, 5};std::for_each(numbers.begin(), numbers.end(), square);for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

<9> 解釋 C++ 中函數(shù)對(duì)象（functor）在 STL 中的應(yīng)用。

函數(shù)對(duì)象可以用于傳遞給 STL 算法作為操作函數(shù)。

例如，在 std::sort 中使用自定義的函數(shù)對(duì)象來(lái)定義排序規(guī)則:

#include <iostream>
#include <vector>
#include <algorithm>struct DescendingComparator {bool operator()(int a, int b) {return a > b;}
};int main() {std::vector<int> numbers = {5, 2, 8, 1, 3};std::sort(numbers.begin(), numbers.end(), DescendingComparator());for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

<10> 如何解決 C++ 中 STL 容器的迭代器失效問(wèn)題？

1. 對(duì)于 vector 和 deque:

• 在插入或刪除元素時(shí)，如果導(dǎo)致容器重新分配內(nèi)存，可能會(huì)使迭代器失效。
• 解決方法：在插入或刪除操作后，重新獲取迭代器。

2. 對(duì)于 list：

插入和刪除操作不會(huì)使迭代器失效，只會(huì)使指向被刪除元素的迭代器失效。

3. 對(duì)于 map 和 set 等關(guān)聯(lián)容器：

• 插入操作不會(huì)使迭代器失效，但刪除操作會(huì)使指向被刪除元素的迭代器失效。

• 解決方法：在刪除操作前，先保存需要的迭代器，或者使用返回的新迭代器。

例如，對(duì)于 vector：

#include <iostream>
#include <vector>int main() {std::vector<int> numbers = {1, 2, 3, 4, 5};auto it = numbers.begin() + 2;numbers.insert(numbers.begin() + 2, 6);  // 插入可能導(dǎo)致迭代器失效it = numbers.begin() + 3;  // 重新獲取迭代器std::cout << *it << std::endl;return 0;
}