C++

Forum

 
Constructor Destructor

thanhquan1704 (38)
My code is:

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
 
#include <iostream>
#include <random>
#include <functional>
template <typename Key>
struct treap_node {
	Key key{}; // {} invokes default constructor
	int priority{ (std::uniform_int_distribution<>{})(engine) };
	treap_node* left = nullptr, * right = nullptr;
private:
	static std::mt19937 engine;
};
template <typename K>
class treap {
public:
	treap();
	treap(const std::initializer_list<K>&);
	~treap();
	void insert(const K&);
	void remove(const K&);
	bool find(const K&) const;
	size_t height() const;
	size_t size() const; // number of nodes in the tree
	void inorder_traversal(std::function<void(const treap_node<K>*)>);
private:
	treap_node<K>* root = nullptr;
};


Now I want to do 2 things:
1. Define two constructors: a default constructor, and another which takes an
initializer list as input so you can define a treap as follows
treap<int> my_tree = {1,2,3,4,5,6,7,8,9};
A std::initializer list is just a container with the usual begin() and end() methods returning iterators.
std::initializer_list<int> nums = {1,2,3,4,5};
for (auto i=nums.begin(); i != nums.end(); ++i)
2. Define a destructor which (correctly) frees all the data allocated by the treap. Do the usual postorder traversal.

How can I do it? Can anybody help me please
Last edited on
highwayman (582)
What exactly are you having trouble with?
thanhquan1704 (38)
I don't know how to define constructors and destructors following the question.
highwayman (582)
Lines 15 and 16 are your constructors and line 17 is or destructor. Just add braces and code. Also they provided you with some starting code for the initializer_list right in the question:
A std::initializer list is just a container with the usual begin() and end() methods returning iterators.
std::initializer_list<int> nums = {1,2,3,4,5};
for (auto i=nums.begin(); i != nums.end(); ++i)


So you can stick that in immediately and go from there. 

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
 
#include <iostream>
#include <random>
#include <functional>
template <typename Key>
struct treap_node {
	Key key{}; // {} invokes default constructor
	int priority{ (std::uniform_int_distribution<>{})(engine) };
	treap_node* left = nullptr, * right = nullptr;
private:
	static std::mt19937 engine;
};
template <typename K>
class treap {
public:
	treap() {
            // your code for default constructor 
        }
	treap(const std::initializer_list<K>& nums) {
            for (auto i=nums.begin(); i != nums.end(); ++i) {
                // your code
            }
        }
	~treap() {
            // your code for destructor
        }
	void insert(const K&);
	void remove(const K&);
	bool find(const K&) const;
	size_t height() const;
	size_t size() const; // number of nodes in the tree
	void inorder_traversal(std::function<void(const treap_node<K>*)>);
private:
	treap_node<K>* root = nullptr;
};
Last edited on
thanhquan1704 (38)
yeah!! I got it so far by myself. I stuck at what do I have to write inside
highwayman (582)
Do you know what a treap is? If so, describe it, write down what you said. And then examine that very closely.....

(This is gonna be weird cause ican’t give you code :/ 😬 sry.)
Last edited on
thanhquan1704 (38)
I got this so far
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
 
#include <iostream>
#include <functional>
#include <initializer_list>
#include <random>
// #include <stack? whatever else?>
using namespace std;
template <typename Key>
struct treap_node {
	Key key{}; // {} invokes default constructor
	int priority{ (std::uniform_int_distribution<> {})(engine) };
	treap_node* left = nullptr, * right = nullptr;
private:
	static std::mt19937 engine;
};

// Initialize (non-int) static member ouside the class definition
template <typename Key>
std::mt19937 treap_node<Key>::engine{};

template <typename K>
class treap {
public:
	treap()
	{
		treap<int> my_tree = {1,2,3,4,5,6,7,8,9};
	}
	treap(const std::initializer_list<K>& nums) 
	{
		std::initializer_list<int> nums = { 1,2,3,4,5 };
		for (auto i = nums.begin(); i != nums.end(); ++i) {
			// your code
		}
	}
	~treap() {
		// your code for destructor
	}
	void insert(const K&);
	void remove(const K&);
	bool find(const K&) const;
	int height() const;
	size_t size() const; // number of nodes in the tree
	void inorder_traversal(std::function<void(const treap_node<K>*)>);
private:
	treap_node<K>* root = nullptr;
	treap_node<K>* nullNode;
	void insert(const K& my_tree, treap_node<K>*& key);
	void remove(const K& my_tree, treap_node<K>*& key);
	bool find(const K& my_tree, treap_node<K>*& key) const;
	void rotate_left(treap_node<K>*& my_tree);
	void rotate_right(treap_node<K>*& my_tree);
};
template<typename K>
void rotate_left(treap_node<K>*& my_tree)
{
	treap_node<K>* r = my_tree->right;
	treap_node<K>* tmpr = my_tree->right->left;

	r->left = my_tree;
	my_tree->right = tmpr;
	my_tree = r;
}
template <typename K>
void rotate_right(treap_node<K>*& my_tree)
{
	treap_node<K>* l = my_tree->left;
	treap_node<K>* tmpl = my_tree->left->right;

	l->right = my_tree;
	my_tree->left = tmpl;
	my_tree = l;
}
template <typename K>
void treap<K>::insert(const K& my_tree, treap_node<K>*& key)
{
	if (my_tree == nullptr)
	{
		my_tree = new treap_node(key);
		return;
	}
	if (key < my_tree->key)
	{
		insert(my_tree->left, key);
		if (my_tree->left != nullptr && my_tree->left->priority > my_tree->priority)
		{
			rotate_right(my_tree);
		}
	}
	else
	{
		insert(my_tree->right, key);
		if (my_tree->right != nullptr && my_tree->right->priority > my_tree->priority)
		{
			rotate_left(my_tree);
		}
	}
}
template <typename K>
void treap<K>::remove(const K& my_tree, treap_node<K>*& k)
{
	if (k != nullNode)
	{
		if (my_tree < k->key)
			remove(my_tree, k->left);
		else if (k->key < my_tree)
			remove(my_tree, k->right);
		else
		{
			// Match found
			if (k->left->priority < k->right->priority)
				rotate_left(k);
			else
				rotate_right(k);

			if (k != nullNode)      // Continue on down
				remove(my_tree, k);
			else
			{
				delete k->left;
				k->left = nullNode;  // At a leaf
			}
		}
	}
}
template <typename K>
bool treap<K>::find(const K& my_tree, treap_node<K>*& key) const
{
	treap_node<K>* current = root;
	nullNode->key = my_tree;
	for (;;)
	{
		if (my_tree < current->key)
		{
			current = current->left;
		}
		else if (current->key < my_tree)
			current = current->right;
		else if (current != nullNode)
			return current->key;
		else
			return false;
	}
}
template <typename K>
int height(const treap_node<K>*& my_tree)
{
	if (my_tree == nullptr) return -1;
	else return 1 + std::max(height(my_tree->left), height(my_tree->right));
}
template <typename K>
void inorder_traversal(std::function<void(const treap_node<K>*root)>)
{
	
}

How can I write the function inorder_traversal? Can you help me please
highwayman (582)
Emmm maybe? What is inorder_traversal supposed do?

Edit: a bit of warning here: I’m beginning to feel like the ignorant leading the blind here or something however the saying goes so take everything I say with a grain of salt..
Last edited on
MikeyBoy (5631)
23
24
25
26
 
        treap()
	{
		treap<int> my_tree = {1,2,3,4,5,6,7,8,9};
	}


This is not initialising the object whose constructor is being invoked. This is creating a whole new treap object with local scope, which then gets destroyed the moment your constructor exits (since it has local scope).

What your constructor needs to do is set up the objects own initial state, by setting the data member variables to appropriate values.

Ask yourself this: what should happen when you first create a treap object? What should the state of that treap object be? What shopuld the values of its data members be?

You can't write a constructor until you've thought about what it is that you want that constructor to actually do, can you?

27
28
29
30
31
32
33
 
        treap(const std::initializer_list<K>& nums) 
	{
		std::initializer_list<int> nums = { 1,2,3,4,5 };
		for (auto i = nums.begin(); i != nums.end(); ++i) {
			// your code
		}
	}


What's the purpose of your line 29? Why are you creating a local variable here? Why are you making it the same name as the argument passed into the method, so that it shadows that argument and makes it inaccessible? What are you trying to achieve with that line?
Last edited on
Topic archived. No new replies allowed.