0%

map和set的模拟实现

改造红黑树

关联式容器存储的是K, V键值对,故在改造红黑树时,K为key类型,对于V来说,如果是set,则其为K类型,如果是map则为

pair<K, V>,类型,除此之外,还需要一个仿函数类KeyOfValue来兼容map与set的大小比较,其迭代器也需要封装指针为一个类,迭代器的自加自减相当于红黑树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
template <class V>
struct RBTIterator
{
typedef RBNode<V> Node;
typedef RBTIterator<V> Self;
RBTIterator(Node* node);

V& operator*();

V* operator->();

bool operator!=(const Self& it);

bool operator==(const Self& it);

Self& operator++();

Self operator++(int);

Self& operator--();

Self operator--(int);

private:
void add();

void sub();

Node* _node;
};

template <class K, class V, class KeyOfValue>
class RBTree
{
public:
typedef RBNode<V> Node;
typedef RBTIterator<V> iterator;

iterator begin();

iterator end();

RBTree();

bool empty();

pair<iterator, bool> insert(const V& val);

iterator Find(const K& data);

size_t size();

Node* leftMost();

Node* rightMost();

void RotateL(Node* parent);

void RotateR(Node* parent);
private:
Node* _header;
};

map和set的实现

通过封装红黑树类,传入仿函数类和具体类型,修改等操作调用红黑树的接口,遍历操作通过迭代器完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
template <class K, class V>
class Map
{
public:
struct MapKeyOfValue
{
const K& operator()(const pair<K, V>& value)
{
return value.first;
}
};

typedef typename RBTree<K, pair<K, V>, MapKeyOfValue>::iterator iterator;

iterator begin()
{
return _rbt.begin();
}

iterator end()
{
return _rbt.end();
}

bool empty()
{
return _rbt->empty();
}

size_t size()
{
return _rbt.size();
}

pair<iterator, bool> insert(const pair<K, V>& value)
{
return _rbt.insert(value);
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = _rbt.insert(make_pair(key, V()));
return ret.first->second;
}

iterator find(const K& key)
{
return _rbt.Find(pair<K, V>(key, V()));
}

private:
RBTree<K, pair<K, V>, MapKeyOfValue> _rbt;
};

template <class K>
class Set
{
struct SetKeyOfValue
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;
iterator begin()
{
return _rbt.begin();
}

iterator end()
{
return _rbt.end();
}

bool empty()
{
return _rbt.empty();
}

iterator find(const K& key)
{
return _rbt.Find(key);
}

size_t size()
{
return _rbt.size();
}

pair<iterator, bool> insert(const K& key)
{
return _rbt.insert(key);
}
private:

RBTree<K, K, SetKeyOfValue> _rbt;
};

GitHub链接

map和set的实现-GitHub

-------------本文结束感谢您的阅读-------------