C++ 頭文件系列(map)

簡介

該頭文件包含兩個概念相似的容器----map、multimap。 而這兩個容器反映的概念就是 映射。

這兩個容器 相同 的屬性有：

• 關聯性
• 映射
• 動態增長
• 鍵（Key）唯一性

這兩個不相同的屬性是：

• 映射關系

容器類別

既然說到關聯性容器，自然得說說標准庫的容器類別。 C++庫容器主要能分成以下幾類：

1. 序列性容器： 將存儲對象組織成線性模型，使用戶能夠像線性數組那樣存取。
2. 關聯性容器： 將存儲內容以鍵（Key）相關聯 ，通過鍵來存取內容。
3. 亂序容器： 存儲對象以亂序存儲，不具有順序。
4. 容器適配器： 通過適配的方式實現，內部使用的是其它已有的容器。

map

map為單映射容器，所謂單映射，就是一對一映射的意思。 每種信息都以 鍵 -> 值 的形式被存儲，由鍵 映射到 值，這是該類容器與vector等容器最大的不同。

實現

典型的map是以Binary Search Tree實現的，但也有可能使用其他合適的數據結構。 例如sgi stl使用的就是紅黑樹。

operator [ ]

除了迭代器，存取map元素時使用的較多的就是這個運算符了。 但實際上這個函數的語義不像看上去那麼簡單，這主要是因為這個函數對特殊情況的處理非常罕見（相比而言，C++11新增的at成員函數就比較符合正常邏輯）。 函數傳入一個鍵k：

如果鍵k在map中，函數返回k映射的內容值；

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

Observers

這裡有兩個特別的函數，它們在C++標准文檔裡被成為Observers（可能是因為通過這兩個函數能夠一定程度上的觀察鍵值對，一定程度是因為它們只能對鍵值對進行比較）。

key_compare     key_comp() const;
value_compare   value_comp() const;

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

lower_bound、upper_bound

這兩個函數比較晦澀難懂，這裡提出來說明一下。

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

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

兩個函數這樣設計的話：

1. 傳入同一個鍵，能正確地將一個range分成上下兩部分。
2. 用迭代器表示的range，開始和結尾分別以閉區間和開區間表示，這兩個函數的返回至可以非常直觀的代表range。

特殊函數

因為映射容器的特殊性，map和multimap具有其他容器所沒有的一些特殊函數：

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

multimap

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

因為是一對多映射的關系，該庫沒有提供像map::operator []、map::at那樣的元素存取函數， 而是想讓用戶依賴於lower_bound、upper_bound這些函數。

語義完整的函數

同時，因為允許一個鍵有對應多個值，某些函數也得到了它真正的意義：

• count（不止是返回0、1）
• equal_range（不止是返回空范圍或包含一個元素的范圍）

語義有異的函數

• find（如果有多個值，返回任意一個）