I'm working on Splay Tree. I have a lot of command input (add, delete and etc), Hence the output is also huge (32MB of text in a txt file (very long string (more than 1000-10000 characters)))
I have a memory problem, I am currently using two Vector and my program take over 250 MB of virtual memory (128 MB is needed for the project) I run on Linux with the command:
$ g++ -std=c++17 -g -O3 -fno-asm -lm main.cpp
$ /usr/bin/time -v valgrind ./a.out
result: Maximum resident set size (kbytes): 277832 (With each launch different sizes but about 250)
how can i reduce the size? The vector changes when I output a new line of one vertex of the tree
using namespace std;
class SplayTree {
public:
class Node;
Node *ROOT = nullptr;
class Node {
public:
long long key;
string value;
Node *_parent;
Node *_RightChild;
Node *_LeftChild;
Node(long long _key = 0, string _value = NULL) {
this->key = _key;
this->value = _value;
this->_parent = nullptr;
this->_RightChild = nullptr;
this->_LeftChild = nullptr;
}
..........
void PrintNode() {
if (_parent == nullptr) {
cout << "[" << key << " " << value << "]";
} else {
cout << "[" << key << " " << value << " " << _parent->key << "]";
}
}
};
..........
//here problems
void Print() { //string
if (ROOT == nullptr) {
//return "_\n";
cout << "_\n";
} else {
ROOT->PrintNode();
cout << "\n";
long long n = 1;
vector<Node *> NOWqueueVec; //to store the current descendants
NOWqueueVec.push_back(ROOT);
vector<Node *> BABYqueue; //for storing future descendants
long long h = height(ROOT);
for (size_t v = 0; v < h-1; v++) {
for (size_t i = 0; i < NOWqueueVec.size(); i++) {
if (NOWqueueVec[i] != nullptr) {
// left
if (NOWqueueVec[i]->haveLeftBaby()) {
BABYqueue.push_back(NOWqueueVec[i]->_LeftChild);
NOWqueueVec[i]->_LeftChild->PrintNode();
} else {
BABYqueue.push_back(nullptr);
cout << "_"; // << endl;
}
cout << " ";
// right
if (NOWqueueVec[i]->haveRightBaby()) {
BABYqueue.push_back(NOWqueueVec[i]->_RightChild);
NOWqueueVec[i]->_RightChild->PrintNode();
} else {
//BABYqueue[pos] = null
BABYqueue.push_back(nullptr);
cout << "_";
}
} else { // if empty then + 2 "_"
BABYqueue.push_back(nullptr);
BABYqueue.push_back(nullptr);
cout << "- -";
}
}
NOWqueueVec.clear();
// Is there a problem here? ////////////
for (Node* b : BABYqueue) { // for NOWqueueVec=BABYqueue
NOWqueueVec.push_back(b);
}
cout << endl;
BABYqueue.clear();
}
NOWqueueVec.clear();
BABYqueue.clear();
}
}
};
int main() {
SplayTree SPLAY;
..........
..........
return 0;
}
I think the problem is in this block
for (Node* b : BABYqueue) { // for NOWqueueVec=BABYqueue
NOWqueueVec.push_back(b);
}
Are there any ways to optimize memory ?