的std ::映射更比需要對比

Question

我試圖在std ::地圖（MinGW和MSVC2008），我用下面的代碼：

#include <map> 
#include <string.h> 
#include <iostream> 
using namespace std; 

class MapManager 
{public: 
    void insert(char* n){ 
     cout << "Inserting " << n << endl; 
     m_map[n] = 0;} 
    void get(char* n){ 
     cout << "Finding (" << n << ")" << endl; 
     int x = m_map[n];} 
    struct cmp_str{ 
     bool operator()(char const *a, char const *b){ 
      cout << "operator(" << a << " " << b << ")\n"; 
      return strcmp(a, b) < 0;} 
    }; 
    std::map<char*,int,cmp_str> m_map; 
}; 
int main(){ 
    MapManager m; 
    m.insert("Abc"); m.insert("Xyz"); m.insert("123"); m.insert("987"); 
    m.get("Abc"); m.get("Xyz"); 
} 

結果如下：

Inserting Abc 
Inserting Xyz 
operator(Abc Xyz) 
operator(Xyz Abc) 
operator(Abc Xyz) 
operator(Xyz Abc) 
Inserting 123 
operator(Abc 123) 
operator(123 Abc) 
operator(123 Abc) 
operator(Abc 123) 
Inserting 987 
operator(Abc 987) 
operator(123 987) 
operator(987 123) 
operator(987 Abc) 
operator(987 Abc) 
operator(Abc 987) 
operator(123 987) 
operator(987 123) 
Finding (Abc) 
operator(Abc Abc) 
operator(123 Abc) 
operator(Abc 123) 
operator(987 Abc) 
operator(Abc 987) 
operator(Abc Abc) 
Finding (Xyz) 
operator(Abc Xyz) 
operator(Xyz Abc) 
operator(Xyz Xyz) 
operator(Xyz Xyz) 

奇怪的是，Inserting Xyz需要4個來電比較！

operator(Abc Xyz) 
operator(Xyz Abc) 
operator(Abc Xyz) 
operator(Xyz Abc) 

map用來插入/查找條目的算法是什麼？

Answer 1

它取決於實現，唯一的要求是insert和find/[]必須是O（log n）。 ^*通常它是一個插入/搜索red-black tree，可能不是完美平衡。

（注意，std::map是一個模板，所有的實施細節將在頭文件，你可以仔細閱讀...）

---

_{*對於該用例，至少。}