C++ 容器與迭代器

應依據所需的查找、走訪、插入、刪除、記憶體局部性與參照穩定性特性選擇容器。複雜度描述操作在滿足前置條件時的行為；失效規則與所有權則決定設計在修改後是否仍然正確。

選擇容器 #

• std::vector 是需要連續儲存、隨機存取、快取局部性，以及透過 data() 與 C 互通時的預設序列容器。附加元素的攤銷時間為常數。任何容量增長都會使所有迭代器、指標與參照失效；若容量未增長，插入操作會使插入點及其後方的迭代器與參照失效。
• std::deque 支援索引存取。在兩端插入會使迭代器失效，但不會使參照失效；其儲存空間不連續，而在中間插入會使迭代器與參照失效。
• std::list 與 std::forward_list 在插入及刪除後，仍會保留指向未受影響節點的迭代器與參照。因為節點配置與指標追蹤會帶來成本，應在測量後選用，而非作為預設選擇。
• std::map 與 std::set 提供有序走訪及對數時間查找。除被刪除的元素外，插入不會使迭代器或參照失效。
• std::unordered_map 與 std::unordered_set 提供平均常數時間查找。重新雜湊會使迭代器失效，但指向元素的參照與指標仍然有效；刪除只會使被刪除的元素失效。

reserve() 可避免預期中的 vector 重新配置，也能減少 unordered_* 重新雜湊。但若某項操作依文件規則會使迭代器失效，呼叫它並不能讓該迭代器繼續有效。

插入與轉移值 #

insert 接受元素或範圍，emplace 則根據引數直接在容器的儲存空間中建構元素：

#include <string>
#include <utility>
#include <vector>

std::vector<std::string> names;
std::string name = "Ada";

names.push_back(name);            // copies; name remains owned by the caller
names.push_back(std::move(name)); // moves; name stays valid but has unspecified value
names.emplace_back(3, 'x');       // constructs "xxx" in the vector

物件已存在時，使用 insert 或 push_back(std::move(value)) 可明確呈現所有權轉移。只有在能直接提供建構函式引數時，emplace 才能避免建立暫存物件；它既非一律更快，也無法取代對元素建構函式的驗證。關聯式容器的 emplace 可能在鍵已存在時建構並捨棄元素。try_emplace 可在鍵重複時避免建構對應值，而 insert_or_assign 則明確表達替換原則。

對於節點式容器，extract 會產生節點控制代碼；在該節點插入其他容器或遭到銷毀之前，控制代碼擁有已移除的節點。它能在不移動內含值的情況下轉移相容節點，但仍須符合配置器相容性及容器文件所述的前置條件。

迭代器與前置條件 #

演算法會宣告所需的迭代器類別。輸入迭代器只能單次走訪；前向迭代器可多次走訪；雙向迭代器另支援遞減；隨機存取迭代器另支援算術與排序操作；連續迭代器還表示相鄰的儲存空間。應傳入演算法所要求類別的迭代器，而非假設某個容器的迭代器會具有另一個容器的行為。

呼叫演算法或容器成員之前，應先驗證範圍的前置條件：

auto first = values.begin();
auto last = values.end();
if (first != last) {
    values.erase(first); // `first` is valid and dereferenceable
}

end() 是哨兵而非元素。切勿對其解除參照；除非 API 明確允許，否則也不要比較來自不同容器的迭代器。若要在修改容器後保留迭代器，應先查閱該容器的具體失效規則表；範圍 for 迴圈與標準演算法可減少手動處理迭代器，但不會暫停套用這些規則。