1. STL常見容器及其內部實現的數據結構

序號 名稱 描述 存儲結構 常用方法和操作

1	vector	動態分配的數組	順序數組（array）	v.push_back(),?v.pop_back(),?v.insert(),?v.erase(),?v.capacity(),?v.size(),?v.at(idx),?v.front(),?v.back()
2	list	雙向鏈表	離散	lt.push_back(),?lt.push_front(),?lt.insert(),?lt.erase(),?lt.sort(),?lt.merge(),?lt.splice()
3	stack	棧	用?list?或?deque?實現	push(),?pop(),?top()
4	queue	隊列	用?list?或?deque?實現	push(),?pop(),?front(),?back()
5	deque	雙端隊列	分段連續（多個?vector?連續）	d.push_back(),?d.push_front(),?d.pop_back(),?d.pop_front(),?d.insert(),?d.erase()
6	priority_queue	優先級隊列	vector	push(),?pop(),?top()
7	set	集合（有序不重復）	紅黑樹（弱平衡二叉搜索樹）	insert(),?erase(),?find(),?count(),?clear()
8	multiset	集合（有序可重復）	紅黑樹	insert(),?erase(),?find(),?count(),?clear()
9	unordered_set	集合（無序不重復）	哈希表	insert(),?erase(),?find(),?count(),?clear()
10	map	鍵值對（有序不重復）	紅黑樹	insert(),?erase(),?find(),?count(),?clear()
11	multimap	鍵值對（有序可重復）	紅黑樹	insert(),?erase(),?find(),?count(),?clear()
12	unordered_map	鍵值對（無序不重復）	哈希表	insert(),?erase(),?find(),?count(),?clear()
13	hash_map	哈希表（類似?map）	哈希表	insert(),?erase(),?find(),?count(),?clear()

2. deque底層數據結構

deque?底層實現通常是分段連續的內存結構，即由多個?vector?組成，允許高效的從兩端進行元素的插入和刪除。

3. 紅黑樹

紅黑樹是一種非嚴格平衡的二叉查找樹，具有自動排序的功能。每個節點存儲一個顏色（紅或黑），并且通過調整樹的結構保持特定的平衡條件，從而保證最壞情況下的查找效率。

4. 常見排序算法

4.1?sort()

• 適用容器：僅支持隨機訪問的容器，如?vector、deque、array。
• 功能：快速排序。

bool func(int a, int b) {return a > b;  // 降序排列
}
sort(vec.begin(), vec.end(), func);  // 對vector進行排序

4.2?partial_sort()

• 功能：對部分元素進行排序，使用堆排序實現。
• 參數：排序范圍，默認排序前?n?個元素。

int n = 4;  // 需要排序的元素個數
partial_sort(vec.begin(), vec.begin() + n, vec.end(), func);  // 排序前4個元素

4.3?is_sorted()

• 功能：檢查容器是否已排序。
• 返回值：布爾值，true?表示已排序。

bool result = is_sorted(vec.begin(), vec.end(), func);

4.4?is_sorted_until()

• 功能：返回第一個破壞排序規則的元素位置。

auto it = is_sorted_until(vec.begin(), vec.end(), func);

5. 查找操作

5.1?find()

• 功能：查找指定元素。

vector<int> vec{10, 20, 30, 40, 50};
auto it = find(vec.begin(), vec.end(), 30);  // 查找30
if (it != vec.end()) {cout << "查找成功：" << *it;
} else {cout << "查找失敗";
}

5.2?find_if()

• 功能：根據自定義謂詞查找元素。

bool mycomp(int i) {return (i % 2) == 1;  // 查找奇數
}
vector<int> myvector{4, 2, 3, 1, 5};
auto it = find_if(myvector.begin(), myvector.end(), mycomp);

6. 使用?vector?避免頻繁的內存重新分配

vector?在擴容時通常會以 2 倍容量增長，這會導致頻繁的內存分配和元素拷貝。為了優化性能，可以采取以下策略：

6.1 預分配內存

在創建?vector?時，可以使用?reserve()?方法預先分配內存，以減少多次擴容。

6.2 合理選擇初始容量

根據數據的預計大小選擇合適的初始容量，避免不必要的擴容操作。

6.3 優化算法

使用時間復雜度較低的算法，避免在數據量增大時造成性能瓶頸。

7.?vector?的?resize()?與?reserve()

7.1?resize()

• 功能：調整容器的大小。
• 效果：如果?n?小于當前大小，則刪除尾部元素；如果?n?大于當前大小，新的元素會被默認構造并添加到尾部。

7.2?reserve()

• 功能：調整容器的容量，不會改變當前大小。
• 效果：用于減少擴容次數，確保容器有足夠的內存空間。

8.?vector?擴容原理

• 擴容過程：每次擴容時，vector?會分配新的內存塊并將現有元素復制到新內存中，舊內存被釋放。
• 擴容系數：通常情況下，vector?容量每次會翻倍或增加 1.5 倍，這可以減少頻繁的擴容。

8.1 Linux中的內存管理

在Linux系統中，內存區域以2的倍數擴容，以便進行高效的內存分配。

8.2 Windows中的內存管理

在Windows系統中，內存分配通常會增加1.5倍，以便更好地利用已經釋放的內存。

9. 迭代器

迭代器是STL中用于訪問容器元素的一種抽象工具。通過迭代器，容器元素的訪問具有一致的接口，并且可以實現多態。

注意：迭代器只能前進，不能回退。

10. 迭代器失效的情況

迭代器可能會因為容器結構的修改而失效。不同類型的容器失效的情況略有不同：

• 數組型數據結構（如?vector）：insert?和?erase?操作會使插入或刪除點之后的所有迭代器失效。
• 鏈表型數據結構（如?list）：erase?操作只會使指向刪除元素的迭代器失效，其他迭代器不受影響。
• 樹型數據結構（如?map）：erase?操作會使指向刪除元素的迭代器失效，其他迭代器不受影響。?insert?操作不會使任何迭代器失效。