17.05.2013, 15:13. Просмотров 401. Ответов 2
Доброго времени суток.
Получил задачу написать set, не просто set, а быстрый основанный на бинарном дереве поиска set.
Вот что получилось.
| C++ |
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| #ifndef SET_H
#define SET_H
template <class T> struct SetElement
{
T value;
SetElement *left;
SetElement *right;
};
template <class T> class Set
{
public:
Set();
Set(T value);
int getCount() const;
bool insert(T value);
bool isInside(T value);
bool remove(T value);
private:
int count;
SetElement<T> *top;
bool add( SetElement<T> *&ptr, T value);
bool del( SetElement<T> *&ptr, T value);
};
template <class T> Set<T>::Set(): count(0), top(NULL) {}
template <class T> Set<T>::Set(T value): count(1)
{
top = new SetElement<T>();
top -> left = NULL;
top -> right = NULL;
top -> value = value;
}
template <class T> int Set<T>::getCount() const
{
return this -> count;
}
template <class T> bool Set<T>::insert(T value)
{
return add(top, value);
}
template <class T> bool Set<T>::remove(T value)
{
return del(top, value);
}
template <class T> bool Set<T>::add(SetElement<T> *&ptr, T value)
{
if (ptr == NULL) {
ptr = new SetElement<T>();
ptr -> left = NULL;
ptr -> right = NULL;
ptr -> value = value;
count++;
return true;
}
if (value == ptr->value) {
return false;
}
if (value < ptr->value) {
return add(ptr->left, value);
} else {
return add(ptr->right, value);
}
}
template <class T> bool Set<T>::isInside(T value)
{
SetElement<T> *copy = top;
while (copy != NULL) {
if (copy -> value == value) {
return true;
} else
if (value < copy -> value) {
copy = copy -> left;
} else {
copy = copy -> right;
}
}
return false;
}
template <class T> bool Set<T>::del(SetElement<T> *&ptr, T value)
{
// no element
if (ptr == NULL)
return false;
// if element with value exists in tree
if (ptr -> value == value) {
//if elements doesnt have a children
if (ptr -> left == NULL && ptr -> right == NULL) {
SetElement<T> *fake = ptr;
ptr = NULL;
delete fake;
count--;
return true;
}
//if exists left children
if (ptr -> right == NULL) {
SetElement<T> *fake = ptr;
ptr = ptr -> left;
delete fake;
count--;
return true;
}
//if exists right children
if (ptr -> left == NULL) {
SetElement<T> *fake = ptr;
ptr = ptr -> left;
delete fake;
count--;
return true;
}
// if exists both
SetElement<T> *maxLeft = ptr -> left;
while (maxLeft -> right != NULL) {
maxLeft = maxLeft -> right;
}
ptr -> value = maxLeft ->value;
del(ptr -> left, ptr -> value);
return true;
} else
if (value < ptr -> value) {
return del(ptr -> left, value);
} else {
return del(ptr -> right, value);
}
}
#endif // SET_H |
|
И тут сел я проводить тестирование скорости работы, относитель STL.
Тест:
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include "set.h"
using namespace std;
int main()
{
Set<int> myset;
for (int i = 0; i < 10000; i++) {
myset.insert(i);
}
return 0;
}
// result time = 0.831 |
|
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> myset;
for (int i = 0; i < 10000; i++) {
myset.insert(i);
}
return 0;
}
// result time = 0.031 |
|
Как вы уже, я думаю поняли, STL SET работает куда быстрее.
Внимание вопрос: почему My Set работает так медленно ?
