C++/map

<map>頭文件聲明了關聯性容器map與multimap。這兩個容器對應的是映射抽象容器。

map為單映射有序關聯容器。存儲的信息為「鍵->值」的形式。按照鍵排序。排序函數為構造函數的參數Compare。各種訪問操作基本是對數時間複雜度。典型的map以二叉搜索樹實現，SGI版本的stl使用紅黑樹實現。

multimap為一對多映射容器，即一個Key可能映射到多個值。

運算符

operator [] 對特殊情況的處理非常罕見。 函數傳入一個鍵k：

• 如果鍵k在map中，函數返回k映射的內容值；
• 如果鍵k不在map中，那麼函數會插入一個新的鍵值對，對插入的值進行默認構造，並且返回這個值得引用。

Observers

• key_comp() const;
• value_comp() const;

返回comparison object，可以分別對鍵、值進行比較。

lower_bound與upper_bound

• lower_bound返回傳入鍵的下界，包括該鍵（如果存在的話）：
• upper_bound返回傳入鍵的上界，不包括該鍵（如果存在的話）:

特殊函數

• find：如果有多個值，返回任意一個
• count：key所對應的value數量。因為map是單映射，所以它的返回至只可能是1或0。
• equal_range：返回給定鍵的元素範圍，因為map是單映射，返回的範圍為空或包含一個元素。 返回值為迭代器pair，分別等於調用lower_bound和upper_bound的結果。