map 的 subscript 運算子跟你想的不一樣

map 是一個 key-value pairs 群集, key 可以被當作索引,用以取回 value 。

這篇文章想講的重要的觀念就是,map 的下標操作(subscripting, [] 運算子)的行為與 vector 和 array 下標操作非常不同,即便索引尚未存在,我們可以直接使用尚未存在的索引,用來幫 map 添加一個帶索引的元素。

下標 (subscript) 真好用

map 的 subscript 特性使得程式可以寫的更為簡潔!即便該 key 不存在,也會有一個新元素針對這個 key 被創建出來,並被插入 map 。新元素除了被創建出來,還會以該 value 型別的 default constructor 進行初始化。

下面舉例來說,想要透過一個 map 來計算所有單字出現的次數,顯然的一開始 map 是空的,任何的 input ,將透過下標動作取出該 key 所對應的 value 出來,如果該 key 不存在,則會呼叫 value 型別的 default constructor ,就是 integer 的預設建構式,因此該 value 將被初始化為 0 ,緊接著再執行 ++ 的動作。

// This is an empty map
map<string, int> word_count;
string word;
while (cin >> word)
{
    word_count[word]++;
}

map 的下標動作看似相當方便,但實際上存在很多潛在問題值得留意。

太過昂貴的 constructor

前面例子中 value 的型別為 integer ,其 default constructor 還算 cheap ,如果 value 的型別是一個巨大的 class ,那一切就非常不理想了。

class BigClass{

};
map <string, BigClass> m;
m[1] = BigClass(constructor argument1, constructor argument2, 
            ..., construct argument3);

上面的例子中,使用下標運算時, class BigClass 的 default constructor 就已經被呼叫了,接著又使用了另外一個 constructor ,再把後來創建的賦值過去,等於創建了兩個 constructor ,顯然的,這個動作相當不必要。

與 const 格格不入

下方程式碼實現 run_query function ,到 word_map 這個 map 找尋找是否已經有這個 key ,如果存在的話,直接回傳 value 。這個 function 僅用來搜尋,因此將 function 宣告為 const 是很安全的作法。

set<TextQuery::lineno> TextQuery::run_query (const string& target) const {
        if (word_map.find (target) != word_map.end())
                return word_map[target];    
    else
        return set<lineno>();

}

實際編譯後,卻會得到以下錯誤:

TextQuery.c: In member function ‘std::set<long unsigned int> TextQuery::run_query(const string&) const’:
TextQuery.c:11:31: error: passing ‘const std::map<std::__cxx11::basic_string<char>, std::set<long unsigned int> >’ as ‘this’ argument discards qualifiers [-fpermissive]
   11 |         return word_map[target];
      |                               ^

在[3] 中,該 facebook 工程師即是以此為例子,指出這是新手工程師常犯的錯誤,看到這樣的錯誤訊息,一般人就會直接將 const 移除(沒錯,我就是這樣做...),而程式就可以順利編譯過了。但這明顯就是治標不治本的方法。

出現這個錯誤的根本原因,就是因為 operator [] 並不是 const-qualified ,如果 key 並不存在,下標運算子可是會建立新元素並初始化,並不是一個 const-qualified 的操作,理解這個來由之後,就能了解為什麼會有這樣的編譯錯誤。

該如何安全的使用呢?

前面太過昂貴的 constructor 章節中,要避免創建兩個物件,可以改用 insert() 來取代下標。

想要搜尋或取回某個 map 元素,透過 count() 或 find () 來取代直接下標,而 find() 函數回返回一個 iterator ,如果該 key 確實存在,可以透過 it→second 來得到元素。以下提供簡單例子:

map<string, int>:: iterator it = word_count.find ("Apple");
if (it != word_count.end())
    int val = it->second;

另外, map 也支援 at() 運算子,當 key 不存在時,exception std::out_of_range 會被丟出, 也可以用 at() 取代下標運算子。

Reference

  1. C++ Primer ch10.3
  2. The std::map subscript operator is a convenience, but a potentially dangerous one
  3. CppCon 2017: Louis Brandy “Curiously Recurring C++ Bugs at Facebook”
  4. https://stackoverflow.com/a/262872