У меня есть класс персистентного массива. Помоги, пожалуйста, написать метод, который бы…
- User
У меня есть класс персистентного массива. Помоги, пожалуйста, написать метод, который бы возвращал в виде int* одну из версий class PersistentArray { private: int* base; int size; std::vector<Node*> versions;
void buildTree(Node* node, int* arr, int l, int r) { if (l == r) { node->val = base[l - 1]; } else { int m = (l + r) / 2; //std::cout << "m = " << m << "\n"; node->lchild = new Node();//std::cout << "\nmaking left child"; buildTree(node->lchild, arr, l, m); node->rchild = new Node();//std::cout << "\nmaking right child"; buildTree(node->rchild, arr, m + 1, r); } } void add(Node* to, Node* from, int l, int r, int npos, int nv) { if (l == r) { to->val = nv; } else { int m = (l + r) / 2; //std::cout << "m = " << m << "\n"; if (npos <= m) { to->rchild = from->rchild; Node* left = new Node(); add(left, from->lchild, l, m, npos, nv); to->lchild = left; } else { to->lchild = from->lchild; Node* right = new Node(); add(right, from->rchild, m + 1, r, npos, nv); to->rchild = right; } } } int get(Node* node, int l, int r, int pos) { if (l == r) { return node->val; } else { int m = (l + r) / 2; if (pos <= m) { return get(node->lchild, l, m, pos); } else { return get(node->rchild, m + 1, r, pos); } } }public: PersistentArray(int _size) { this->base = new int[_size]; this->size = _size;
versions.push_back(new Node()); int l = 1; int r = _size; buildTree(versions.at(0), base, l, r); } PersistentArray(int* _arr, int _size) { this->base = new int[_size]; this->size = _size; for (int i = 0; i < _size; i++) { this->base[i] = _arr[i]; } int l = 1; int r = _size; versions.push_back(new Node()); buildTree(versions.at(0), base, l, r); } ~PersistentArray() { delete[] base; } void changeVersion(int number_of_version, int newPos, int newVal) { int l = 1; int r = size; add(versions[number_of_version - 1], versions.at(number_of_version - 1), l, r, newPos, newVal); } void addVersion(int rootPos, int newPos, int newVal) { int l = 1; int r = size; versions.push_back(new Node()); add(versions.back(), versions.at(rootPos - 1), l, r, newPos, newVal); } int* getStart() { return this->base; } int* getArray(int number_of_version) { // }};
- Assistant
Для того чтобы написать метод, который бы возвращал в виде int* одну из версий массива, можно воспользоваться методом
getиз классаPersistentArray. В этом методе, мы будем искать элемент массива на заданной позиции в соответствующей версии массива и возвращать его значение.Ниже приведен код реализации метода
getArray:int* getArray(int number_of_version) { Node* root = versions[number_of_version - 1]; int* result = new int[size]; for (int i = 1; i <= size; i++) { result[i - 1] = get(root, 1, size, i); } return result; }В этом методе мы создаем новый массив
resultразмеромsizeи заполняем его значениями из версии массива с номеромnumber_of_version. Для этого мы последовательно вызываем методgetдля каждой позиции массива и сохраняем полученные значения вresult.Обратите внимание, что возвращаемый массив
resultвыделяется динамически с помощью оператораnew, поэтому не забудьте освободить память, вызвавdelete[]для этого массива, когда он будет больше не нужен.