0

std::map (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)

マップがエントリの挿入/検索に使用するアルゴリズムは何ですか?

4

1 に答える 1

1

これは実装に依存します。唯一の要件は、insertとfind/の両方[]が O(log n) でなければならないことです。* 通常、これは赤黒木での挿入/検索であり、完全にバランスが取れていない可能性があります。

(std::mapテンプレートと同様に、すべての実装の詳細は、熟読できるヘッダー ファイルにあることに注意してください...)

* このユースケースでは、少なくとも。

于 2013-03-12T19:16:54.153 に答える