C++シミュレーションMap

JDKのMapタイプはキー値ペアでデータを保存し、キー(key)を繰り返すことはできません.HashMapの実装では実際にHash分類に配列ソートを加える方式が採用されている.C++ではこのようなアルゴリズムを採用していません.まずKey値をツリー順に並べ替えて、対応するValueを検索します.ツリー全体のソートには、最も基本的な中順ループが使用されます.これらはすべてデータ構造の知識で、よく知らないのは私の前のブログ(ツリーADTを検索)を見ることができます.次は本題に戻る.
シーンは、一連の人名+年齢を入力し、人名辞書のソートに従ってすべてのデータを表示する必要があるとします.テスト方法は次のとおりです.

 1 int main() {
 2     using namespace std;
 3     Item<string, int>* it1 = new Item<string, int>("Done", 18);
 4     it1->put("Tom", 17);
 5     it1->put("Kate", 15);
 6     it1->put("Lory", 22);
 7     it1->put("Xiaom", 14);
 8     it1->put("Kate", 23); //     
 9 
10     cout << it1->size() << endl; //   ：5
11 
12     Item<string, int>* it2 = it1; //       
13     Item<string, int>::Entry* ep = it2->sort(); //       
14 
15     for (int i = 0; i < it2->size(); i++) { //     
16         cout << ep[i].str_k << "=" << ep[i].str_v << endl;
17     }
18     return 0;
19 }

(1)8行目に重複データを追加し,5行目のデータを上書きすべきである.
(2)12行目にコピー関数を呼び出し,ポインタ割り当てが正しいかどうかをテストする.
(3)15行目は配列を遍歴し,データを照会する.
テンプレートクラスの設計は次のとおりです.

#ifndef ITEM_H_
#define ITEM_H_
#include 
template
class Item {
public:
    struct Entry { //                 
        K str_k;
        V str_v;
    };
private:
    static int len; //         +1，  size()    
    static int index; //       
    K _key; //  
    V _value; //  
    Item* _left; //    
    Item* _right; //    
    void _sort(Item& item, Entry entry[]); //       
public:
    Item(const K& key, const V& value) :
            _key(key), _value(value), _left(0), _right(0) {
        len++;
    }
    virtual ~Item() { //              
        if (_left != 0)
            delete _left;
        if (_right != 0)
            delete _right;
    }
    Item(const Item& o) : //     
            _key(o._key), _value(o._value), _left(o._left), _right(o._right) {
    }
    Item& operator=(const Item& it) { //       
        _key = it._key;
        _value = it._value;
        if (_left != 0)
            delete _left;
        if (_right != 0)
            delete _right;
        _left = it._left;
        _right = it._right;
        return *this;
    }
    void put(const K& key, const V& value);

    V get(const K& key) const;

    int size() const;

    Entry* sort() { //           
        Entry* entry = new Entry[len];
        _sort(*this, entry);
        return entry;
    }
};

template
int Item::len = 0;

template
int Item::index = 0;

template
void Item::put(const K& key, const V& value) {
    if (key == _key) {
        _key = key;
        _value = value;
    } else if (key > _key) {
        if (_right == 0) {
            Item* r = new Item(key, value);
            _right = r;
        } else {
            _right->put(key, value);
        }
    } else if (key < _key) {
        if (_left == 0) {
            Item* l = new Item(key, value);
            _left = l;
        } else {
            _left->put(key, value);
        }
    }
}

template
V Item::get(const K& key) const {
    if (key == _key) {
        return _value;
    } else if (key < _key) {
        if (_left == 0) {
            return 0;
        } else {
            _left->get(key);
        }
    } else if (key > _key) {
        if (_right == 0) {
            return 0;
        } else {
            _right->get(key);
        }
    }
}
template
int Item::size() const {
    return len;
}

template
void Item::_sort(Item& item, Entry entry[]) {
    if (item._left == 0) {
        entry[index].str_k = item._key;
        entry[index].str_v = item._value;
        index++;
    } else {
        _sort(*item._left, entry);
        entry[index].str_k = item._key;
        entry[index].str_v = item._value;
        index++;
    }
    if (item._right == 0) {
        return;
    } else {
        _sort(*item._right, entry);
    }
}

#endif /* ITEM_H_ */

一部の注釈私がダウンロードしたコードの中で、ここでいくつかの説明をします.
(1)二叉木並べ替えの原則は,まず木の根を形成し,次に新しく入ったデータを木の根と比較することである.木の根元より小さい場合は、新しい二叉木構造を形成し、左側に置いて左のサブツリーを形成します.逆に右の木ができます.左サブツリー(右サブツリー)が既に存在する場合は、再帰的に挿入します.
(2)二叉木遍歴の原則は,まず左子木を処理し,次に樹根を処理し,最後に右子木を処理することである.再帰クエリも必要です.
(3)C++はJavaとは異なり,コピー構造とリロード付与関数を自ら実現することが望ましい.通常、コピー構造とリロード付与関数の効果は同じですが、この例ではわかります.再負荷付与関数は,まず自分の左右のサブツリーのポインタを解析して再付与する必要がある.
(4)C++コンパイル方式の違いにより,クラス内の静的定数は直接付与できない.宣言後にデータを定義する必要があり、定義の順序も重要です.